You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by tn...@apache.org on 2013/06/13 23:01:01 UTC
svn commit: r1492866 [2/3] - in /commons/proper/collections/trunk/src:
main/java/org/apache/commons/collections4/trie/
main/java/org/apache/commons/collections4/trie/analyzer/
test/java/org/apache/commons/collections4/trie/
test/java/org/apache/commons...
Modified: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/PatriciaTrie.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/PatriciaTrie.java?rev=1492866&r1=1492865&r2=1492866&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/PatriciaTrie.java (original)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/PatriciaTrie.java Thu Jun 13 21:01:00 2013
@@ -16,17 +16,10 @@
*/
package org.apache.commons.collections4.trie;
-import java.util.AbstractMap;
-import java.util.AbstractSet;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.Iterator;
import java.util.Map;
-import java.util.NoSuchElementException;
-import java.util.Set;
-import java.util.SortedMap;
import org.apache.commons.collections4.Trie;
+import org.apache.commons.collections4.trie.analyzer.StringKeyAnalyzer;
/**
* Implementation of a PATRICIA Trie (Practical Algorithm to Retrieve Information
@@ -47,20 +40,14 @@ import org.apache.commons.collections4.T
* the given key, instead of comparing the entire key to another key.
* <p>
* The {@link Trie} can return operations in lexicographical order using the
- * {@link #traverse(Cursor)}, 'prefix', 'submap', or 'iterator' methods. The
- * {@link Trie} can also scan for items that are 'bitwise' (using an XOR
- * metric) by the 'select' method. Bitwise closeness is determined by the
- * {@link KeyAnalyzer} returning true or false for a bit being set or not in
- * a given key.
+ * 'prefixMap', 'submap', or 'iterator' methods. The {@link Trie} can also
+ * scan for items that are 'bitwise' (using an XOR metric) by the 'select' method.
+ * Bitwise closeness is determined by the {@link KeyAnalyzer} returning true or
+ * false for a bit being set or not in a given key.
* <p>
* This PATRICIA {@link Trie} supports both variable length & fixed length
- * keys. Some methods, such as {@link #getPrefixedBy(Object)} are suited only
- * to variable length keys, whereas {@link #getPrefixedByBits(Object, int)} is
- * suited to fixed-size keys.
- * <p>
- * Any methods here that take an {@link Object} argument may throw a
- * {@link ClassCastException} if the method is expecting an instance of K
- * and it isn't K.
+ * keys. Some methods, such as {@link #prefixMap(Object)} are suited only
+ * to variable length keys.
*
* @see <a href="http://en.wikipedia.org/wiki/Radix_tree">Radix Tree</a>
* @see <a href="http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA">PATRICIA</a>
@@ -68,1187 +55,16 @@ import org.apache.commons.collections4.T
* @since 4.0
* @version $Id$
*/
-public class PatriciaTrie<K, V> extends PatriciaTrieBase<K, V> implements Trie<K, V> {
+public class PatriciaTrie<E> extends AbstractPatriciaTrie<String, E> implements Trie<String, E> {
private static final long serialVersionUID = 4446367780901817838L;
- public PatriciaTrie(final KeyAnalyzer<? super K> keyAnalyzer) {
- super(keyAnalyzer);
- }
-
- public PatriciaTrie(final KeyAnalyzer<? super K> keyAnalyzer, final Map<? extends K, ? extends V> m) {
- super(keyAnalyzer, m);
- }
-
- public Comparator<? super K> comparator() {
- return keyAnalyzer;
- }
-
- public SortedMap<K, V> getPrefixedBy(final K key) {
- return getPrefixedByBits(key, 0, lengthInBits(key));
- }
-
- public SortedMap<K, V> getPrefixedBy(final K key, final int length) {
- return getPrefixedByBits(key, 0, length * bitsPerElement());
- }
-
- public SortedMap<K, V> getPrefixedBy(final K key, final int offset, final int length) {
- final int bitsPerElement = bitsPerElement();
- return getPrefixedByBits(key, offset*bitsPerElement, length*bitsPerElement);
- }
-
- public SortedMap<K, V> getPrefixedByBits(final K key, final int lengthInBits) {
- return getPrefixedByBits(key, 0, lengthInBits);
- }
-
- public K firstKey() {
- return firstEntry().getKey();
- }
-
- public K lastKey() {
- final TrieEntry<K, V> entry = lastEntry();
- if (entry != null) {
- return entry.getKey();
- }
- return null;
- }
-
- /**
- * {@inheritDoc}
- *
- * The view that this returns is optimized to have a very efficient
- * {@link Iterator}. The {@link SortedMap#firstKey()},
- * {@link SortedMap#lastKey()} & {@link Map#size()} methods must
- * iterate over all possible values in order to determine the results.
- * This information is cached until the PATRICIA {@link Trie} changes.
- * All other methods (except {@link Iterator}) must compare the given
- * key to the prefix to ensure that it is within the range of the view.
- * The {@link Iterator}'s remove method must also relocate the subtree
- * that contains the prefixes if the entry holding the subtree is
- * removed or changes. Changing the subtree takes O(K) time.
- */
- public SortedMap<K, V> getPrefixedByBits(final K key, final int offsetInBits, final int lengthInBits) {
-
- final int offsetLength = offsetInBits + lengthInBits;
- if (offsetLength > lengthInBits(key)) {
- throw new IllegalArgumentException(offsetInBits + " + "
- + lengthInBits + " > " + lengthInBits(key));
- }
-
- if (offsetLength == 0) {
- return this;
- }
-
- return new PrefixRangeMap(key, offsetInBits, lengthInBits);
- }
-
- public SortedMap<K, V> headMap(final K toKey) {
- return new RangeEntryMap(null, toKey);
- }
-
- public SortedMap<K, V> subMap(final K fromKey, final K toKey) {
- return new RangeEntryMap(fromKey, toKey);
- }
-
- public SortedMap<K, V> tailMap(final K fromKey) {
- return new RangeEntryMap(fromKey, null);
- }
-
- /**
- * Returns an entry strictly higher than the given key,
- * or null if no such entry exists.
- */
- TrieEntry<K,V> higherEntry(final K key) {
- // TODO: Cleanup so that we don't actually have to add/remove from the
- // tree. (We do it here because there are other well-defined
- // functions to perform the search.)
- final int lengthInBits = lengthInBits(key);
-
- if (lengthInBits == 0) {
- if (!root.isEmpty()) {
- // If data in root, and more after -- return it.
- if (size() > 1) {
- return nextEntry(root);
- } else { // If no more after, no higher entry.
- return null;
- }
- } else {
- // Root is empty & we want something after empty, return first.
- return firstEntry();
- }
- }
-
- final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
- if (compareKeys(key, found.key)) {
- return nextEntry(found);
- }
-
- final int bitIndex = bitIndex(key, found.key);
- if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
- final TrieEntry<K, V> added = new TrieEntry<K, V>(key, null, bitIndex);
- addEntry(added, lengthInBits);
- incrementSize(); // must increment because remove will decrement
- final TrieEntry<K, V> ceil = nextEntry(added);
- removeEntry(added);
- modCount -= 2; // we didn't really modify it.
- return ceil;
- } else if (KeyAnalyzer.isNullBitKey(bitIndex)) {
- if (!root.isEmpty()) {
- return firstEntry();
- } else if (size() > 1) {
- return nextEntry(firstEntry());
- } else {
- return null;
- }
- } else if (KeyAnalyzer.isEqualBitKey(bitIndex)) {
- return nextEntry(found);
- }
-
- // we should have exited above.
- throw new IllegalStateException("invalid lookup: " + key);
- }
-
- /**
- * Returns a key-value mapping associated with the least key greater
- * than or equal to the given key, or null if there is no such key.
- */
- TrieEntry<K,V> ceilingEntry(final K key) {
- // Basically:
- // Follow the steps of adding an entry, but instead...
- //
- // - If we ever encounter a situation where we found an equal
- // key, we return it immediately.
- //
- // - If we hit an empty root, return the first iterable item.
- //
- // - If we have to add a new item, we temporarily add it,
- // find the successor to it, then remove the added item.
- //
- // These steps ensure that the returned value is either the
- // entry for the key itself, or the first entry directly after
- // the key.
-
- // TODO: Cleanup so that we don't actually have to add/remove from the
- // tree. (We do it here because there are other well-defined
- // functions to perform the search.)
- final int lengthInBits = lengthInBits(key);
-
- if (lengthInBits == 0) {
- if (!root.isEmpty()) {
- return root;
- } else {
- return firstEntry();
- }
- }
-
- final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
- if (compareKeys(key, found.key)) {
- return found;
- }
-
- final int bitIndex = bitIndex(key, found.key);
- if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
- final TrieEntry<K, V> added = new TrieEntry<K, V>(key, null, bitIndex);
- addEntry(added, lengthInBits);
- incrementSize(); // must increment because remove will decrement
- final TrieEntry<K, V> ceil = nextEntry(added);
- removeEntry(added);
- modCount -= 2; // we didn't really modify it.
- return ceil;
- } else if (KeyAnalyzer.isNullBitKey(bitIndex)) {
- if (!root.isEmpty()) {
- return root;
- } else {
- return firstEntry();
- }
- } else if (KeyAnalyzer.isEqualBitKey(bitIndex)) {
- return found;
- }
-
- // we should have exited above.
- throw new IllegalStateException("invalid lookup: " + key);
- }
-
- /**
- * Returns a key-value mapping associated with the greatest key
- * strictly less than the given key, or null if there is no such key.
- */
- TrieEntry<K,V> lowerEntry(final K key) {
- // Basically:
- // Follow the steps of adding an entry, but instead...
- //
- // - If we ever encounter a situation where we found an equal
- // key, we return it's previousEntry immediately.
- //
- // - If we hit root (empty or not), return null.
- //
- // - If we have to add a new item, we temporarily add it,
- // find the previousEntry to it, then remove the added item.
- //
- // These steps ensure that the returned value is always just before
- // the key or null (if there was nothing before it).
-
- // TODO: Cleanup so that we don't actually have to add/remove from the
- // tree. (We do it here because there are other well-defined
- // functions to perform the search.)
- final int lengthInBits = lengthInBits(key);
-
- if (lengthInBits == 0) {
- return null; // there can never be anything before root.
- }
-
- final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
- if (compareKeys(key, found.key)) {
- return previousEntry(found);
- }
-
- final int bitIndex = bitIndex(key, found.key);
- if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
- final TrieEntry<K, V> added = new TrieEntry<K, V>(key, null, bitIndex);
- addEntry(added, lengthInBits);
- incrementSize(); // must increment because remove will decrement
- final TrieEntry<K, V> prior = previousEntry(added);
- removeEntry(added);
- modCount -= 2; // we didn't really modify it.
- return prior;
- } else if (KeyAnalyzer.isNullBitKey(bitIndex)) {
- return null;
- } else if (KeyAnalyzer.isEqualBitKey(bitIndex)) {
- return previousEntry(found);
- }
-
- // we should have exited above.
- throw new IllegalStateException("invalid lookup: " + key);
- }
-
- /**
- * Returns a key-value mapping associated with the greatest key
- * less than or equal to the given key, or null if there is no such key.
- */
- TrieEntry<K,V> floorEntry(final K key) {
- // TODO: Cleanup so that we don't actually have to add/remove from the
- // tree. (We do it here because there are other well-defined
- // functions to perform the search.)
- final int lengthInBits = lengthInBits(key);
-
- if (lengthInBits == 0) {
- if (!root.isEmpty()) {
- return root;
- } else {
- return null;
- }
- }
-
- final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
- if (compareKeys(key, found.key)) {
- return found;
- }
-
- final int bitIndex = bitIndex(key, found.key);
- if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
- final TrieEntry<K, V> added = new TrieEntry<K, V>(key, null, bitIndex);
- addEntry(added, lengthInBits);
- incrementSize(); // must increment because remove will decrement
- final TrieEntry<K, V> floor = previousEntry(added);
- removeEntry(added);
- modCount -= 2; // we didn't really modify it.
- return floor;
- } else if (KeyAnalyzer.isNullBitKey(bitIndex)) {
- if (!root.isEmpty()) {
- return root;
- } else {
- return null;
- }
- } else if (KeyAnalyzer.isEqualBitKey(bitIndex)) {
- return found;
- }
-
- // we should have exited above.
- throw new IllegalStateException("invalid lookup: " + key);
- }
-
- /**
- * Finds the subtree that contains the prefix.
- *
- * This is very similar to getR but with the difference that
- * we stop the lookup if h.bitIndex > lengthInBits.
- */
- TrieEntry<K, V> subtree(final K prefix, final int offsetInBits, final int lengthInBits) {
- TrieEntry<K, V> current = root.left;
- TrieEntry<K, V> path = root;
- while(true) {
- if (current.bitIndex <= path.bitIndex || lengthInBits < current.bitIndex) {
- break;
- }
-
- path = current;
- if (!isBitSet(prefix, offsetInBits + current.bitIndex, offsetInBits + lengthInBits)) {
- current = current.left;
- } else {
- current = current.right;
- }
- }
-
- // Make sure the entry is valid for a subtree.
- final TrieEntry<K, V> entry = current.isEmpty() ? path : current;
-
- // If entry is root, it can't be empty.
- if (entry.isEmpty()) {
- return null;
- }
-
- final int endIndexInBits = offsetInBits + lengthInBits;
-
- // if root && length of root is less than length of lookup,
- // there's nothing.
- // (this prevents returning the whole subtree if root has an empty
- // string and we want to lookup things with "\0")
- if (entry == root && lengthInBits(entry.getKey()) < endIndexInBits) {
- return null;
- }
-
- // Found key's length-th bit differs from our key
- // which means it cannot be the prefix...
- if (isBitSet(prefix, endIndexInBits, endIndexInBits)
- != isBitSet(entry.key, lengthInBits, lengthInBits(entry.key))) {
- return null;
- }
-
- // ... or there are less than 'length' equal bits
- final int bitIndex = keyAnalyzer.bitIndex(prefix, offsetInBits,
- lengthInBits, entry.key, 0, lengthInBits(entry.getKey()));
-
- if (bitIndex >= 0 && bitIndex < lengthInBits) {
- return null;
- }
-
- return entry;
- }
-
- /**
- * Returns the last entry the {@link Trie} is storing.
- *
- * <p>This is implemented by going always to the right until
- * we encounter a valid uplink. That uplink is the last key.
- */
- TrieEntry<K, V> lastEntry() {
- return followRight(root.left);
- }
-
- /**
- * Traverses down the right path until it finds an uplink.
- */
- TrieEntry<K, V> followRight(TrieEntry<K, V> node) {
- // if Trie is empty, no last entry.
- if (node.right == null) {
- return null;
- }
-
- // Go as far right as possible, until we encounter an uplink.
- while (node.right.bitIndex > node.bitIndex) {
- node = node.right;
- }
-
- return node.right;
- }
-
- /**
- * Returns the node lexicographically before the given node (or null if none).
- *
- * This follows four simple branches:
- * - If the uplink that returned us was a right uplink:
- * - If predecessor's left is a valid uplink from predecessor, return it.
- * - Else, follow the right path from the predecessor's left.
- * - If the uplink that returned us was a left uplink:
- * - Loop back through parents until we encounter a node where
- * node != node.parent.left.
- * - If node.parent.left is uplink from node.parent:
- * - If node.parent.left is not root, return it.
- * - If it is root & root isEmpty, return null.
- * - If it is root & root !isEmpty, return root.
- * - If node.parent.left is not uplink from node.parent:
- * - Follow right path for first right child from node.parent.left
- *
- * @param start the start entry
- */
- TrieEntry<K, V> previousEntry(final TrieEntry<K, V> start) {
- if (start.predecessor == null) {
- throw new IllegalArgumentException("must have come from somewhere!");
- }
-
- if (start.predecessor.right == start) {
- if (isValidUplink(start.predecessor.left, start.predecessor)) {
- return start.predecessor.left;
- } else {
- return followRight(start.predecessor.left);
- }
- } else {
- TrieEntry<K, V> node = start.predecessor;
- while (node.parent != null && node == node.parent.left) {
- node = node.parent;
- }
-
- if (node.parent == null) { // can be null if we're looking up root.
- return null;
- }
-
- if (isValidUplink(node.parent.left, node.parent)) {
- if (node.parent.left == root) {
- if (root.isEmpty()) {
- return null;
- } else {
- return root;
- }
-
- } else {
- return node.parent.left;
- }
- } else {
- return followRight(node.parent.left);
- }
- }
- }
-
- /**
- * Returns the entry lexicographically after the given entry.
- * If the given entry is null, returns the first node.
- *
- * This will traverse only within the subtree. If the given node
- * is not within the subtree, this will have undefined results.
- */
- TrieEntry<K, V> nextEntryInSubtree(final TrieEntry<K, V> node,
- final TrieEntry<K, V> parentOfSubtree) {
- if (node == null) {
- return firstEntry();
- } else {
- return nextEntryImpl(node.predecessor, node, parentOfSubtree);
- }
- }
-
- /**
- * A range view of the {@link Trie}.
- */
- private abstract class RangeMap extends AbstractMap<K, V>
- implements SortedMap<K, V> {
-
- /** The {@link #entrySet()} view. */
- private transient volatile Set<Map.Entry<K, V>> entrySet;
-
- /**
- * Creates and returns an {@link #entrySet()} view of the {@link RangeMap}.
- */
- protected abstract Set<Map.Entry<K, V>> createEntrySet();
-
- /**
- * Returns the FROM Key.
- */
- protected abstract K getFromKey();
-
- /**
- * Whether or not the {@link #getFromKey()} is in the range.
- */
- protected abstract boolean isFromInclusive();
-
- /**
- * Returns the TO Key.
- */
- protected abstract K getToKey();
-
- /**
- * Whether or not the {@link #getToKey()} is in the range.
- */
- protected abstract boolean isToInclusive();
-
- public Comparator<? super K> comparator() {
- return PatriciaTrie.this.comparator();
- }
-
- @Override
- public boolean containsKey(final Object key) {
- if (!inRange(castKey(key))) {
- return false;
- }
-
- return PatriciaTrie.this.containsKey(key);
- }
-
- @Override
- public V remove(final Object key) {
- if (!inRange(castKey(key))) {
- return null;
- }
-
- return PatriciaTrie.this.remove(key);
- }
-
- @Override
- public V get(final Object key) {
- if (!inRange(castKey(key))) {
- return null;
- }
-
- return PatriciaTrie.this.get(key);
- }
-
- @Override
- public V put(final K key, final V value) {
- if (!inRange(key)) {
- throw new IllegalArgumentException("Key is out of range: " + key);
- }
- return PatriciaTrie.this.put(key, value);
- }
-
- @Override
- public Set<Map.Entry<K, V>> entrySet() {
- if (entrySet == null) {
- entrySet = createEntrySet();
- }
- return entrySet;
- }
-
- public SortedMap<K, V> subMap(final K fromKey, final K toKey) {
- if (!inRange2(fromKey)) {
- throw new IllegalArgumentException("FromKey is out of range: " + fromKey);
- }
-
- if (!inRange2(toKey)) {
- throw new IllegalArgumentException("ToKey is out of range: " + toKey);
- }
-
- return createRangeMap(fromKey, isFromInclusive(), toKey, isToInclusive());
- }
-
- public SortedMap<K, V> headMap(final K toKey) {
- if (!inRange2(toKey)) {
- throw new IllegalArgumentException("ToKey is out of range: " + toKey);
- }
- return createRangeMap(getFromKey(), isFromInclusive(), toKey, isToInclusive());
- }
-
- public SortedMap<K, V> tailMap(final K fromKey) {
- if (!inRange2(fromKey)) {
- throw new IllegalArgumentException("FromKey is out of range: " + fromKey);
- }
- return createRangeMap(fromKey, isFromInclusive(), getToKey(), isToInclusive());
- }
-
- /**
- * Returns true if the provided key is greater than TO and less than FROM.
- */
- protected boolean inRange(final K key) {
- final K fromKey = getFromKey();
- final K toKey = getToKey();
-
- return (fromKey == null || inFromRange(key, false)) && (toKey == null || inToRange(key, false));
- }
-
- /**
- * This form allows the high endpoint (as well as all legit keys).
- */
- protected boolean inRange2(final K key) {
- final K fromKey = getFromKey();
- final K toKey = getToKey();
-
- return (fromKey == null || inFromRange(key, false)) && (toKey == null || inToRange(key, true));
- }
-
- /**
- * Returns true if the provided key is in the FROM range of the {@link RangeMap}.
- */
- protected boolean inFromRange(final K key, final boolean forceInclusive) {
- final K fromKey = getFromKey();
- final boolean fromInclusive = isFromInclusive();
-
- final int ret = keyAnalyzer.compare(key, fromKey);
- if (fromInclusive || forceInclusive) {
- return ret >= 0;
- } else {
- return ret > 0;
- }
- }
-
- /**
- * Returns true if the provided key is in the TO range of the {@link RangeMap}.
- */
- protected boolean inToRange(final K key, final boolean forceInclusive) {
- final K toKey = getToKey();
- final boolean toInclusive = isToInclusive();
-
- final int ret = keyAnalyzer.compare(key, toKey);
- if (toInclusive || forceInclusive) {
- return ret <= 0;
- } else {
- return ret < 0;
- }
- }
-
- /**
- * Creates and returns a sub-range view of the current {@link RangeMap}.
- */
- protected abstract SortedMap<K, V> createRangeMap(K fromKey, boolean fromInclusive,
- K toKey, boolean toInclusive);
+ public PatriciaTrie() {
+ super(new StringKeyAnalyzer());
}
- /**
- * A {@link RangeMap} that deals with {@link Entry}s.
- */
- private class RangeEntryMap extends RangeMap {
-
- /** The key to start from, null if the beginning. */
- private final K fromKey;
-
- /** The key to end at, null if till the end. */
- private final K toKey;
-
- /** Whether or not the 'from' is inclusive. */
- private final boolean fromInclusive;
-
- /** Whether or not the 'to' is inclusive. */
- private final boolean toInclusive;
-
- /**
- * Creates a {@link RangeEntryMap} with the fromKey included and
- * the toKey excluded from the range.
- */
- protected RangeEntryMap(final K fromKey, final K toKey) {
- this(fromKey, true, toKey, false);
- }
-
- /**
- * Creates a {@link RangeEntryMap}.
- */
- protected RangeEntryMap(final K fromKey, final boolean fromInclusive,
- final K toKey, final boolean toInclusive) {
-
- if (fromKey == null && toKey == null) {
- throw new IllegalArgumentException("must have a from or to!");
- }
-
- if (fromKey != null && toKey != null
- && keyAnalyzer.compare(fromKey, toKey) > 0) {
- throw new IllegalArgumentException("fromKey > toKey");
- }
-
- this.fromKey = fromKey;
- this.fromInclusive = fromInclusive;
- this.toKey = toKey;
- this.toInclusive = toInclusive;
- }
-
- public K firstKey() {
- Map.Entry<K,V> e = null;
- if (fromKey == null) {
- e = firstEntry();
- } else {
- if (fromInclusive) {
- e = ceilingEntry(fromKey);
- } else {
- e = higherEntry(fromKey);
- }
- }
-
- final K first = e != null ? e.getKey() : null;
- if (e == null || toKey != null && !inToRange(first, false)) {
- throw new NoSuchElementException();
- }
- return first;
- }
-
- public K lastKey() {
- Map.Entry<K,V> e;
- if (toKey == null) {
- e = lastEntry();
- } else {
- if (toInclusive) {
- e = floorEntry(toKey);
- } else {
- e = lowerEntry(toKey);
- }
- }
-
- final K last = e != null ? e.getKey() : null;
- if (e == null || fromKey != null && !inFromRange(last, false)) {
- throw new NoSuchElementException();
- }
- return last;
- }
-
- @Override
- protected Set<Entry<K, V>> createEntrySet() {
- return new RangeEntrySet(this);
- }
-
- @Override
- public K getFromKey() {
- return fromKey;
- }
-
- @Override
- public K getToKey() {
- return toKey;
- }
-
- @Override
- public boolean isFromInclusive() {
- return fromInclusive;
- }
-
- @Override
- public boolean isToInclusive() {
- return toInclusive;
- }
-
- @Override
- protected SortedMap<K, V> createRangeMap(final K fromKey, final boolean fromInclusive,
- final K toKey, final boolean toInclusive) {
- return new RangeEntryMap(fromKey, fromInclusive, toKey, toInclusive);
- }
- }
-
- /**
- * A {@link Set} view of a {@link RangeMap}.
- */
- private class RangeEntrySet extends AbstractSet<Map.Entry<K, V>> {
-
- private final RangeMap delegate;
-
- private transient int size = -1;
-
- private transient int expectedModCount;
-
- /**
- * Creates a {@link RangeEntrySet}.
- */
- public RangeEntrySet(final RangeMap delegate) {
- if (delegate == null) {
- throw new NullPointerException("delegate");
- }
-
- this.delegate = delegate;
- }
-
- @Override
- public Iterator<Map.Entry<K, V>> iterator() {
- final K fromKey = delegate.getFromKey();
- final K toKey = delegate.getToKey();
-
- TrieEntry<K, V> first = null;
- if (fromKey == null) {
- first = firstEntry();
- } else {
- first = ceilingEntry(fromKey);
- }
-
- TrieEntry<K, V> last = null;
- if (toKey != null) {
- last = ceilingEntry(toKey);
- }
-
- return new EntryIterator(first, last);
- }
-
- @Override
- public int size() {
- if (size == -1 || expectedModCount != PatriciaTrie.this.modCount) {
- size = 0;
-
- for (final Iterator<?> it = iterator(); it.hasNext(); it.next()) {
- ++size;
- }
-
- expectedModCount = PatriciaTrie.this.modCount;
- }
- return size;
- }
-
- @Override
- public boolean isEmpty() {
- return !iterator().hasNext();
- }
-
- @SuppressWarnings("unchecked")
- @Override
- public boolean contains(final Object o) {
- if (!(o instanceof Map.Entry)) {
- return false;
- }
-
- final Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
- final K key = entry.getKey();
- if (!delegate.inRange(key)) {
- return false;
- }
-
- final TrieEntry<K, V> node = getEntry(key);
- return node != null && compare(node.getValue(), entry.getValue());
- }
-
- @SuppressWarnings("unchecked")
- @Override
- public boolean remove(final Object o) {
- if (!(o instanceof Map.Entry)) {
- return false;
- }
-
- final Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
- final K key = entry.getKey();
- if (!delegate.inRange(key)) {
- return false;
- }
-
- final TrieEntry<K, V> node = getEntry(key);
- if (node != null && compare(node.getValue(), entry.getValue())) {
- removeEntry(node);
- return true;
- }
- return false;
- }
-
- /**
- * An {@link Iterator} for {@link RangeEntrySet}s.
- */
- private final class EntryIterator extends TrieIterator<Map.Entry<K,V>> {
-
- private final K excludedKey;
-
- /**
- * Creates a {@link EntryIterator}.
- */
- private EntryIterator(final TrieEntry<K,V> first, final TrieEntry<K,V> last) {
- super(first);
- this.excludedKey = last != null ? last.getKey() : null;
- }
-
- @Override
- public boolean hasNext() {
- return next != null && !compare(next.key, excludedKey);
- }
-
- public Map.Entry<K,V> next() {
- if (next == null || compare(next.key, excludedKey)) {
- throw new NoSuchElementException();
- }
- return nextEntry();
- }
- }
+ public PatriciaTrie(final Map<? extends String, ? extends E> m) {
+ super(new StringKeyAnalyzer(), m);
}
- /**
- * A submap used for prefix views over the {@link Trie}.
- */
- private class PrefixRangeMap extends RangeMap {
-
- private final K prefix;
-
- private final int offsetInBits;
-
- private final int lengthInBits;
-
- private K fromKey = null;
-
- private K toKey = null;
-
- private transient int expectedModCount = 0;
-
- private int size = -1;
-
- /**
- * Creates a {@link PrefixRangeMap}.
- */
- private PrefixRangeMap(final K prefix, final int offsetInBits, final int lengthInBits) {
- this.prefix = prefix;
- this.offsetInBits = offsetInBits;
- this.lengthInBits = lengthInBits;
- }
-
- /**
- * This method does two things. It determinates the FROM
- * and TO range of the {@link PrefixRangeMap} and the number
- * of elements in the range. This method must be called every
- * time the {@link Trie} has changed.
- */
- private int fixup() {
- // The trie has changed since we last
- // found our toKey / fromKey
- if (size == - 1 || PatriciaTrie.this.modCount != expectedModCount) {
- final Iterator<Map.Entry<K, V>> it = entrySet().iterator();
- size = 0;
-
- Map.Entry<K, V> entry = null;
- if (it.hasNext()) {
- entry = it.next();
- size = 1;
- }
-
- fromKey = entry == null ? null : entry.getKey();
- if (fromKey != null) {
- final TrieEntry<K, V> prior = previousEntry((TrieEntry<K, V>)entry);
- fromKey = prior == null ? null : prior.getKey();
- }
-
- toKey = fromKey;
-
- while (it.hasNext()) {
- ++size;
- entry = it.next();
- }
-
- toKey = entry == null ? null : entry.getKey();
-
- if (toKey != null) {
- entry = nextEntry((TrieEntry<K, V>)entry);
- toKey = entry == null ? null : entry.getKey();
- }
-
- expectedModCount = PatriciaTrie.this.modCount;
- }
-
- return size;
- }
-
- public K firstKey() {
- fixup();
-
- Map.Entry<K,V> e = null;
- if (fromKey == null) {
- e = firstEntry();
- } else {
- e = higherEntry(fromKey);
- }
-
- final K first = e != null ? e.getKey() : null;
- if (e == null || !keyAnalyzer.isPrefix(prefix,
- offsetInBits, lengthInBits, first)) {
- throw new NoSuchElementException();
- }
-
- return first;
- }
-
- public K lastKey() {
- fixup();
-
- Map.Entry<K,V> e = null;
- if (toKey == null) {
- e = lastEntry();
- } else {
- e = lowerEntry(toKey);
- }
-
- final K last = e != null ? e.getKey() : null;
- if (e == null || !keyAnalyzer.isPrefix(prefix,
- offsetInBits, lengthInBits, last)) {
- throw new NoSuchElementException();
- }
-
- return last;
- }
-
- /**
- * Returns true if this {@link PrefixRangeMap}'s key is a prefix of the provided key.
- */
- @Override
- protected boolean inRange(final K key) {
- return keyAnalyzer.isPrefix(prefix, offsetInBits, lengthInBits, key);
- }
-
- /**
- * Same as {@link #inRange(Object)}.
- */
- @Override
- protected boolean inRange2(final K key) {
- return inRange(key);
- }
-
- /**
- * Returns true if the provided Key is in the FROM range of the {@link PrefixRangeMap}.
- */
- @Override
- protected boolean inFromRange(final K key, final boolean forceInclusive) {
- return keyAnalyzer.isPrefix(prefix, offsetInBits, lengthInBits, key);
- }
-
- /**
- * Returns true if the provided Key is in the TO range of the {@link PrefixRangeMap}.
- */
- @Override
- protected boolean inToRange(final K key, final boolean forceInclusive) {
- return keyAnalyzer.isPrefix(prefix, offsetInBits, lengthInBits, key);
- }
-
- @Override
- protected Set<Map.Entry<K, V>> createEntrySet() {
- return new PrefixRangeEntrySet(this);
- }
-
- @Override
- public K getFromKey() {
- return fromKey;
- }
-
- @Override
- public K getToKey() {
- return toKey;
- }
-
- @Override
- public boolean isFromInclusive() {
- return false;
- }
-
- @Override
- public boolean isToInclusive() {
- return false;
- }
-
- @Override
- protected SortedMap<K, V> createRangeMap(final K fromKey, final boolean fromInclusive,
- final K toKey, final boolean toInclusive) {
- return new RangeEntryMap(fromKey, fromInclusive, toKey, toInclusive);
- }
- }
-
- /**
- * A prefix {@link RangeEntrySet} view of the {@link Trie}.
- */
- private final class PrefixRangeEntrySet extends RangeEntrySet {
-
- private final PrefixRangeMap delegate;
-
- private TrieEntry<K, V> prefixStart;
-
- private int expectedModCount = 0;
-
- /**
- * Creates a {@link PrefixRangeEntrySet}.
- */
- public PrefixRangeEntrySet(final PrefixRangeMap delegate) {
- super(delegate);
- this.delegate = delegate;
- }
-
- @Override
- public int size() {
- return delegate.fixup();
- }
-
- @Override
- public Iterator<Map.Entry<K,V>> iterator() {
- if (PatriciaTrie.this.modCount != expectedModCount) {
- prefixStart = subtree(delegate.prefix, delegate.offsetInBits, delegate.lengthInBits);
- expectedModCount = PatriciaTrie.this.modCount;
- }
-
- if (prefixStart == null) {
- final Set<Map.Entry<K,V>> empty = Collections.emptySet();
- return empty.iterator();
- } else if (delegate.lengthInBits >= prefixStart.bitIndex) {
- return new SingletonIterator(prefixStart);
- } else {
- return new EntryIterator(prefixStart, delegate.prefix, delegate.offsetInBits, delegate.lengthInBits);
- }
- }
-
- /**
- * An {@link Iterator} that holds a single {@link TrieEntry}.
- */
- private final class SingletonIterator implements Iterator<Map.Entry<K, V>> {
-
- private final TrieEntry<K, V> entry;
-
- private int hit = 0;
-
- public SingletonIterator(final TrieEntry<K, V> entry) {
- this.entry = entry;
- }
-
- public boolean hasNext() {
- return hit == 0;
- }
-
- public Map.Entry<K, V> next() {
- if (hit != 0) {
- throw new NoSuchElementException();
- }
-
- ++hit;
- return entry;
- }
-
- public void remove() {
- if (hit != 1) {
- throw new IllegalStateException();
- }
-
- ++hit;
- PatriciaTrie.this.removeEntry(entry);
- }
- }
-
- /**
- * An {@link Iterator} for iterating over a prefix search.
- */
- private final class EntryIterator extends TrieIterator<Map.Entry<K, V>> {
-
- // values to reset the subtree if we remove it.
- private final K prefix;
- private final int offset;
- private final int lengthInBits;
- private boolean lastOne;
-
- private TrieEntry<K, V> subtree; // the subtree to search within
-
- /**
- * Starts iteration at the given entry & search only
- * within the given subtree.
- */
- EntryIterator(final TrieEntry<K, V> startScan, final K prefix,
- final int offset, final int lengthInBits) {
- subtree = startScan;
- next = PatriciaTrie.this.followLeft(startScan);
- this.prefix = prefix;
- this.offset = offset;
- this.lengthInBits = lengthInBits;
- }
-
- public Map.Entry<K,V> next() {
- final Map.Entry<K, V> entry = nextEntry();
- if (lastOne) {
- next = null;
- }
- return entry;
- }
-
- @Override
- protected TrieEntry<K, V> findNext(final TrieEntry<K, V> prior) {
- return PatriciaTrie.this.nextEntryInSubtree(prior, subtree);
- }
-
- @Override
- public void remove() {
- // If the current entry we're removing is the subtree
- // then we need to find a new subtree parent.
- boolean needsFixing = false;
- final int bitIdx = subtree.bitIndex;
- if (current == subtree) {
- needsFixing = true;
- }
-
- super.remove();
-
- // If the subtree changed its bitIndex or we
- // removed the old subtree, get a new one.
- if (bitIdx != subtree.bitIndex || needsFixing) {
- subtree = subtree(prefix, offset, lengthInBits);
- }
-
- // If the subtree's bitIndex is less than the
- // length of our prefix, it's the last item
- // in the prefix tree.
- if (lengthInBits >= subtree.bitIndex) {
- lastOne = true;
- }
- }
- }
- }
}
Modified: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/SynchronizedTrie.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/SynchronizedTrie.java?rev=1492866&r1=1492865&r2=1492866&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/SynchronizedTrie.java (original)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/SynchronizedTrie.java Thu Jun 13 21:01:00 2013
@@ -24,6 +24,7 @@ import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
+import org.apache.commons.collections4.OrderedMapIterator;
import org.apache.commons.collections4.Trie;
import org.apache.commons.collections4.collection.SynchronizedCollection;
@@ -66,10 +67,6 @@ public class SynchronizedTrie<K, V> impl
this.delegate = trie;
}
- public synchronized Entry<K, V> traverse(final Cursor<? super K, ? super V> cursor) {
- return delegate.traverse(cursor);
- }
-
public synchronized Set<Entry<K, V>> entrySet() {
return Collections.synchronizedSet(delegate.entrySet());
}
@@ -114,6 +111,10 @@ public class SynchronizedTrie<K, V> impl
return delegate.remove(key);
}
+ public synchronized int size() {
+ return delegate.size();
+ }
+
public synchronized K lastKey() {
return delegate.lastKey();
}
@@ -138,31 +139,26 @@ public class SynchronizedTrie<K, V> impl
return Collections.synchronizedSortedMap(delegate.headMap(toKey));
}
- public synchronized SortedMap<K, V> getPrefixedBy(final K key, final int offset, final int length) {
- return Collections.synchronizedSortedMap(delegate.getPrefixedBy(key, offset, length));
- }
-
- public synchronized SortedMap<K, V> getPrefixedBy(final K key, final int length) {
- return Collections.synchronizedSortedMap(delegate.getPrefixedBy(key, length));
+ public synchronized SortedMap<K, V> prefixMap(final K key) {
+ return Collections.synchronizedSortedMap(delegate.prefixMap(key));
}
- public synchronized SortedMap<K, V> getPrefixedBy(final K key) {
- return Collections.synchronizedSortedMap(delegate.getPrefixedBy(key));
+ //-----------------------------------------------------------------------
+ public synchronized OrderedMapIterator<K, V> mapIterator() {
+ // TODO: make ordered map iterator synchronized too
+ final OrderedMapIterator<K, V> it = delegate.mapIterator();
+ return it;
}
- public synchronized SortedMap<K, V> getPrefixedByBits(final K key, final int lengthInBits) {
- return Collections.synchronizedSortedMap(delegate.getPrefixedByBits(key, lengthInBits));
+ public synchronized K nextKey(K key) {
+ return delegate.nextKey(key);
}
- public synchronized SortedMap<K, V> getPrefixedByBits(final K key,
- final int offsetInBits, final int lengthInBits) {
- return Collections.synchronizedSortedMap(delegate.getPrefixedByBits(key, offsetInBits, lengthInBits));
- }
-
- public synchronized int size() {
- return delegate.size();
+ public synchronized K previousKey(K key) {
+ return delegate.previousKey(key);
}
+ //-----------------------------------------------------------------------
@Override
public synchronized int hashCode() {
return delegate.hashCode();
@@ -177,4 +173,5 @@ public class SynchronizedTrie<K, V> impl
public synchronized String toString() {
return delegate.toString();
}
+
}
Modified: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/UnmodifiableTrie.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/UnmodifiableTrie.java?rev=1492866&r1=1492865&r2=1492866&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/UnmodifiableTrie.java (original)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/UnmodifiableTrie.java Thu Jun 13 21:01:00 2013
@@ -24,8 +24,10 @@ import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
+import org.apache.commons.collections4.OrderedMapIterator;
import org.apache.commons.collections4.Trie;
import org.apache.commons.collections4.Unmodifiable;
+import org.apache.commons.collections4.iterators.UnmodifiableOrderedMapIterator;
/**
* An unmodifiable {@link Trie}.
@@ -35,6 +37,7 @@ import org.apache.commons.collections4.U
*/
public class UnmodifiableTrie<K, V> implements Trie<K, V>, Serializable, Unmodifiable {
+ /** Serialization version */
private static final long serialVersionUID = -7156426030315945159L;
private final Trie<K, V> delegate;
@@ -66,25 +69,7 @@ public class UnmodifiableTrie<K, V> impl
this.delegate = trie;
}
- public Entry<K, V> traverse(final Cursor<? super K, ? super V> cursor) {
- final Cursor<K, V> c = new Cursor<K, V>() {
- public Decision select(final Map.Entry<? extends K, ? extends V> entry) {
- final Decision decision = cursor.select(entry);
- switch (decision) {
- case REMOVE:
- case REMOVE_AND_EXIT:
- throw new UnsupportedOperationException();
- default:
- // other decisions are fine
- break;
- }
-
- return decision;
- }
- };
-
- return delegate.traverse(c);
- }
+ //-----------------------------------------------------------------------
public Set<Entry<K, V>> entrySet() {
return Collections.unmodifiableSet(delegate.entrySet());
@@ -130,6 +115,10 @@ public class UnmodifiableTrie<K, V> impl
throw new UnsupportedOperationException();
}
+ public int size() {
+ return delegate.size();
+ }
+
public K firstKey() {
return delegate.firstKey();
}
@@ -150,34 +139,29 @@ public class UnmodifiableTrie<K, V> impl
return Collections.unmodifiableSortedMap(delegate.tailMap(fromKey));
}
- public SortedMap<K, V> getPrefixedBy(final K key, final int offset, final int length) {
- return Collections.unmodifiableSortedMap(delegate.getPrefixedBy(key, offset, length));
- }
-
- public SortedMap<K, V> getPrefixedBy(final K key, final int length) {
- return Collections.unmodifiableSortedMap(delegate.getPrefixedBy(key, length));
- }
-
- public SortedMap<K, V> getPrefixedBy(final K key) {
- return Collections.unmodifiableSortedMap(delegate.getPrefixedBy(key));
+ public SortedMap<K, V> prefixMap(final K key) {
+ return Collections.unmodifiableSortedMap(delegate.prefixMap(key));
}
- public SortedMap<K, V> getPrefixedByBits(final K key, final int lengthInBits) {
- return Collections.unmodifiableSortedMap(delegate.getPrefixedByBits(key, lengthInBits));
+ public Comparator<? super K> comparator() {
+ return delegate.comparator();
}
- public SortedMap<K, V> getPrefixedByBits(final K key, final int offsetInBits, final int lengthInBits) {
- return Collections.unmodifiableSortedMap(delegate.getPrefixedByBits(key, offsetInBits, lengthInBits));
+ //-----------------------------------------------------------------------
+ public OrderedMapIterator<K, V> mapIterator() {
+ final OrderedMapIterator<K, V> it = delegate.mapIterator();
+ return UnmodifiableOrderedMapIterator.unmodifiableOrderedMapIterator(it);
}
- public Comparator<? super K> comparator() {
- return delegate.comparator();
+ public K nextKey(K key) {
+ return delegate.nextKey(key);
}
- public int size() {
- return delegate.size();
+ public K previousKey(K key) {
+ return delegate.previousKey(key);
}
+ //-----------------------------------------------------------------------
@Override
public int hashCode() {
return delegate.hashCode();
@@ -192,4 +176,5 @@ public class UnmodifiableTrie<K, V> impl
public String toString() {
return delegate.toString();
}
+
}
Added: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/trie/PatriciaTrie2Test.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/trie/PatriciaTrie2Test.java?rev=1492866&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/trie/PatriciaTrie2Test.java (added)
+++ commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/trie/PatriciaTrie2Test.java Thu Jun 13 21:01:00 2013
@@ -0,0 +1,58 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.collections4.trie;
+
+import junit.framework.Test;
+
+import org.apache.commons.collections4.BulkTest;
+import org.apache.commons.collections4.OrderedMap;
+import org.apache.commons.collections4.map.AbstractOrderedMapTest;
+
+/**
+ * JUnit test of the OrderedMap interface of a PatriciaTrie.
+ *
+ * @since 4.0
+ * @version $Id$
+ */
+public class PatriciaTrie2Test<V> extends AbstractOrderedMapTest<String, V> {
+
+ public PatriciaTrie2Test(final String testName) {
+ super(testName);
+ }
+
+ public static Test suite() {
+ return BulkTest.makeSuite(PatriciaTrie2Test.class);
+ }
+
+ @Override
+ public OrderedMap<String, V> makeObject() {
+ return new PatriciaTrie<V>();
+ }
+
+ @Override
+ public boolean isAllowNullKey() {
+ return false;
+ }
+
+ //-----------------------------------------------------------------------
+
+ @Override
+ public String getCompatibilityVersion() {
+ return "4";
+ }
+
+}
Propchange: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/trie/PatriciaTrie2Test.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/trie/PatriciaTrie2Test.java
------------------------------------------------------------------------------
svn:keywords = Id Revision HeadURL
Propchange: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections4/trie/PatriciaTrie2Test.java
------------------------------------------------------------------------------
svn:mime-type = text/plain