commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t.@apache.org
Subject 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...
Date Thu, 13 Jun 2013 21:01:01 GMT
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()} &amp; {@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



Mime
View raw message