commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t.@apache.org
Subject svn commit: r1365732 [3/5] - in /commons/proper/collections/trunk: ./ src/main/java/org/apache/commons/collections/ src/main/java/org/apache/commons/collections/trie/ src/test/java/org/apache/commons/collections/trie/ src/test/resources/org/ src/test/r...
Date Wed, 25 Jul 2012 20:42:49 GMT
Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ShortKeyAnalyzer.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ShortKeyAnalyzer.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ShortKeyAnalyzer.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ShortKeyAnalyzer.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,125 @@
+/*
+ * 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.collections.trie;
+
+/**
+ * A {@link KeyAnalyzer} for {@link Short}s.
+ * 
+ * @since 4.0
+ * @version $Id$
+ */
+public class ShortKeyAnalyzer implements KeyAnalyzer<Short> {
+    
+    private static final long serialVersionUID = -8631376733513512017L;
+
+    /**
+     * A singleton instance of {@link ShortKeyAnalyzer}
+     */
+    public static final ShortKeyAnalyzer INSTANCE = new ShortKeyAnalyzer();
+    
+    /**
+     * The length of an {@link Short} in bits
+     */
+    public static final int LENGTH = Short.SIZE;
+    
+    /**
+     * A bit mask where the first bit is 1 and the others are zero
+     */
+    private static final int MSB = 0x8000;
+    
+    /**
+     * Returns a bit mask where the given bit is set
+     */
+    private static int mask(int bit) {
+        return MSB >>> bit;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public int bitsPerElement() {
+        return 1;
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public int lengthInBits(Short key) {
+        return LENGTH;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean isBitSet(Short key, int bitIndex, int lengthInBits) {
+        return (key & mask(bitIndex)) != 0;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public int bitIndex(Short key, int offsetInBits, int lengthInBits, 
+            Short other, int otherOffsetInBits, int otherLengthInBits) {
+        
+        if (offsetInBits != 0 || otherOffsetInBits != 0) {
+            throw new IllegalArgumentException("offsetInBits=" + offsetInBits 
+                    + ", otherOffsetInBits=" + otherOffsetInBits);
+        }
+        
+        int keyValue = key.shortValue();
+        if (keyValue == 0) {
+            return NULL_BIT_KEY;
+        }
+
+        int otherValue = (other != null ? other.shortValue() : 0);
+        
+        if (keyValue != otherValue) {
+            int xorValue = keyValue ^ otherValue;
+            for (int i = 0; i < LENGTH; i++) {
+                if ((xorValue & mask(i)) != 0) {
+                    return i;
+                }
+            }
+        }
+        
+        return KeyAnalyzer.EQUAL_BIT_KEY;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public int compare(Short o1, Short o2) {
+        return o1.compareTo(o2);
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public boolean isPrefix(Short prefix, int offsetInBits, 
+            int lengthInBits, Short key) {
+        
+        int value1 = (prefix.shortValue() << offsetInBits);
+        int value2 = key.shortValue();
+        
+        int mask = 0;
+        for (int i = 0; i < lengthInBits; i++) {
+            mask |= (0x1 << i);
+        }
+        
+        return (value1 & mask) == (value2 & mask);
+    }
+}

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ShortKeyAnalyzer.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ShortKeyAnalyzer.java
------------------------------------------------------------------------------
    svn:keywords = Id Revision HeadURL

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ShortKeyAnalyzer.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/StringKeyAnalyzer.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/StringKeyAnalyzer.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/StringKeyAnalyzer.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/StringKeyAnalyzer.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,153 @@
+/*
+ * 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.collections.trie;
+
+/**
+ * An {@link KeyAnalyzer} for {@link String}s.
+ * 
+ * @since 4.0
+ * @version $Id$
+ */
+public class StringKeyAnalyzer extends AbstractKeyAnalyzer<String> {
+    
+    private static final long serialVersionUID = -7032449491269434877L;
+    
+    /**
+     * A singleton instance of {@link StringKeyAnalyzer}
+     */
+    public static final StringKeyAnalyzer INSTANCE = new StringKeyAnalyzer();
+    
+    /**
+     * The number of bits per {@link Character}
+     */
+    public static final int LENGTH = Character.SIZE;
+    
+    /**
+     * A bit mask where the first bit is 1 and the others are zero
+     */
+    private static final int MSB = 0x8000;
+    
+    /**
+     * Returns a bit mask where the given bit is set
+     */
+    private static int mask(int bit) {
+        return MSB >>> bit;
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public int bitsPerElement() {
+        return LENGTH;
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public int lengthInBits(String key) {
+        return (key != null ? key.length() * LENGTH : 0);
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public int bitIndex(String key, int offsetInBits, int lengthInBits,
+            String other, int otherOffsetInBits, int otherLengthInBits) {
+        boolean allNull = true;
+        
+        if (offsetInBits % LENGTH != 0 || otherOffsetInBits % LENGTH != 0 
+                || lengthInBits % LENGTH != 0 || otherLengthInBits % LENGTH != 0) {
+            throw new IllegalArgumentException(
+                    "The offsets and lengths must be at Character boundaries");
+        }
+        
+        
+        int beginIndex1 = offsetInBits / LENGTH;
+        int beginIndex2 = otherOffsetInBits / LENGTH;
+        
+        int endIndex1 = beginIndex1 + lengthInBits / LENGTH;
+        int endIndex2 = beginIndex2 + otherLengthInBits / LENGTH;
+        
+        int length = Math.max(endIndex1, endIndex2);
+        
+        // Look at each character, and if they're different
+        // then figure out which bit makes the difference
+        // and return it.
+        char k = 0, f = 0;
+        for(int i = 0; i < length; i++) {
+            int index1 = beginIndex1 + i;
+            int index2 = beginIndex2 + i;
+            
+            if (index1 >= endIndex1) {
+                k = 0;
+            } else {
+                k = key.charAt(index1);
+            }
+            
+            if (other == null || index2 >= endIndex2) {
+                f = 0;
+            } else {
+                f = other.charAt(index2);
+            }
+            
+            if (k != f) {
+               int x = k ^ f;
+               return i * LENGTH + (Integer.numberOfLeadingZeros(x) - LENGTH);
+            }
+            
+            if (k != 0) {
+                allNull = false;
+            }
+        }
+        
+        // All bits are 0
+        if (allNull) {
+            return KeyAnalyzer.NULL_BIT_KEY;
+        }
+        
+        // Both keys are equal
+        return KeyAnalyzer.EQUAL_BIT_KEY;
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public boolean isBitSet(String key, int bitIndex, int lengthInBits) {
+        if (key == null || bitIndex >= lengthInBits) {
+            return false;
+        }
+        
+        int index = (int)(bitIndex / LENGTH);
+        int bit = (int)(bitIndex % LENGTH);
+        
+        return (key.charAt(index) & mask(bit)) != 0;
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public boolean isPrefix(String prefix, int offsetInBits, 
+            int lengthInBits, String key) {
+        if (offsetInBits % LENGTH != 0 || lengthInBits % LENGTH != 0) {
+            throw new IllegalArgumentException(
+                    "Cannot determine prefix outside of Character boundaries");
+        }
+    
+        String s1 = prefix.substring(offsetInBits / LENGTH, lengthInBits / LENGTH);
+        return key.startsWith(s1);
+    }
+}

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/StringKeyAnalyzer.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/StringKeyAnalyzer.java
------------------------------------------------------------------------------
    svn:keywords = Id Revision HeadURL

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/StringKeyAnalyzer.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/SynchronizedTrie.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/SynchronizedTrie.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/SynchronizedTrie.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/SynchronizedTrie.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,280 @@
+/*
+ * 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.collections.trie;
+
+import java.io.Serializable;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Map;
+import java.util.Set;
+import java.util.SortedMap;
+
+import org.apache.commons.collections.Trie;
+import org.apache.commons.collections.collection.SynchronizedCollection;
+import org.apache.commons.collections.set.SynchronizedSet;
+
+/**
+ * A synchronized {@link Trie}.
+ * 
+ * @since 4.0
+ * @version $Id$
+ */
+public class SynchronizedTrie<K, V> implements Trie<K, V>, Serializable {
+    
+    private static final long serialVersionUID = 3121878833178676939L;
+    
+    private final Trie<K, V> delegate;
+    
+    /**
+     * Factory method to create a synchronized trie.
+     * 
+     * @param trie  the trie to decorate, must not be null
+     * @return a new synchronized trie
+     * @throws IllegalArgumentException if trie is null
+     */
+    public static <K, V> SynchronizedTrie<K, V> synchronizedTrie(Trie<K, V> trie) {
+        return new SynchronizedTrie<K, V>(trie);
+    }
+
+    //-----------------------------------------------------------------------
+    /**
+     * Constructor that wraps (not copies).
+     * 
+     * @param trie  the trie to decorate, must not be null
+     * @throws IllegalArgumentException if set is null
+     */
+    public SynchronizedTrie(Trie<K, V> trie) {
+        if (trie == null) {
+            throw new IllegalArgumentException("Collection must not be null");
+        }
+        this.delegate = trie;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized Entry<K, V> select(K key, 
+            Cursor<? super K, ? super V> cursor) {
+        return delegate.select(key, cursor);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized Entry<K, V> select(K key) {
+        return delegate.select(key);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized K selectKey(K key) {
+        return delegate.selectKey(key);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized V selectValue(K key) {
+        return delegate.selectValue(key);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized Entry<K, V> traverse(Cursor<? super K, ? super V> cursor) {
+        return delegate.traverse(cursor);
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized Set<Entry<K, V>> entrySet() {
+        return SynchronizedSet.synchronizedSet(delegate.entrySet());
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized Set<K> keySet() {
+        return SynchronizedSet.synchronizedSet(delegate.keySet());
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized Collection<V> values() {
+        return SynchronizedCollection.synchronizedCollection(delegate.values());
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized void clear() {
+        delegate.clear();
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized boolean containsKey(Object key) {
+        return delegate.containsKey(key);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized boolean containsValue(Object value) {
+        return delegate.containsValue(value);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized V get(Object key) {
+        return delegate.get(key);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized boolean isEmpty() {
+        return delegate.isEmpty();
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized V put(K key, V value) {
+        return delegate.put(key, value);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized void putAll(Map<? extends K, ? extends V> m) {
+        delegate.putAll(m);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized V remove(Object key) {
+        return delegate.remove(key);
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized K lastKey() {
+        return delegate.lastKey();
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized SortedMap<K, V> subMap(K fromKey, K toKey) {
+        return Collections.synchronizedSortedMap(delegate.subMap(fromKey, toKey));
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized SortedMap<K, V> tailMap(K fromKey) {
+        return Collections.synchronizedSortedMap(delegate.tailMap(fromKey));
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized Comparator<? super K> comparator() {
+        return delegate.comparator();
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized K firstKey() {
+        return delegate.firstKey();
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized SortedMap<K, V> headMap(K toKey) {
+        return Collections.synchronizedSortedMap(delegate.headMap(toKey));
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized SortedMap<K, V> getPrefixedBy(K key, int offset, int length) {
+        return Collections.synchronizedSortedMap(delegate.getPrefixedBy(key, offset, length));
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized SortedMap<K, V> getPrefixedBy(K key, int length) {
+        return Collections.synchronizedSortedMap(delegate.getPrefixedBy(key, length));
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized SortedMap<K, V> getPrefixedBy(K key) {
+        return Collections.synchronizedSortedMap(delegate.getPrefixedBy(key));
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized SortedMap<K, V> getPrefixedByBits(K key, int lengthInBits) {
+        return Collections.synchronizedSortedMap(delegate.getPrefixedByBits(key, lengthInBits));
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized SortedMap<K, V> getPrefixedByBits(K key, 
+            int offsetInBits, int lengthInBits) {
+        return Collections.synchronizedSortedMap(delegate.getPrefixedByBits(key, offsetInBits, lengthInBits));
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public synchronized int size() {
+        return delegate.size();
+    }
+
+    @Override
+    public synchronized int hashCode() {
+        return delegate.hashCode();
+    }
+    
+    @Override
+    public synchronized boolean equals(Object obj) {
+        return delegate.equals(obj);
+    }
+    
+    @Override
+    public synchronized String toString() {
+        return delegate.toString();
+    }
+}

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/SynchronizedTrie.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/SynchronizedTrie.java
------------------------------------------------------------------------------
    svn:keywords = Id Revision HeadURL

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/SynchronizedTrie.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/UnmodifiableTrie.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/UnmodifiableTrie.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/UnmodifiableTrie.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/UnmodifiableTrie.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,301 @@
+package org.apache.commons.collections.trie;
+
+import java.io.Serializable;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Map;
+import java.util.Set;
+import java.util.SortedMap;
+
+import org.apache.commons.collections.Trie;
+
+/**
+ * An unmodifiable {@link Trie}.
+ * 
+ * @since 4.0
+ * @version $Id$
+ */
+public class UnmodifiableTrie<K, V> implements Trie<K, V>, Serializable {
+    
+    private static final long serialVersionUID = -7156426030315945159L;
+    
+    private final Trie<K, V> delegate;
+    
+    /**
+     * Factory method to create a unmodifiable trie.
+     * 
+     * @param trie  the trie to decorate, must not be null
+     * @return a new unmodifiable trie
+     * @throws IllegalArgumentException if trie is null
+     */
+    public static <K, V> UnmodifiableTrie<K, V> unmodifiableTrie(Trie<K, V> trie) {
+        return new UnmodifiableTrie<K, V>(trie);
+    }
+
+    //-----------------------------------------------------------------------
+    /**
+     * Constructor that wraps (not copies).
+     * 
+     * @param trie  the trie to decorate, must not be null
+     * @throws IllegalArgumentException if set is null
+     */
+    public UnmodifiableTrie(Trie<K, V> trie) {
+        if (trie == null) {
+            throw new IllegalArgumentException("Collection must not be null");
+        }
+        this.delegate = trie;
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public Entry<K, V> select(K key, final Cursor<? super K, ? super V> cursor) {
+        Cursor<K, V> c = new Cursor<K, V>() {
+            public Decision select(Map.Entry<? extends K, ? extends V> entry) {
+                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.select(key, c);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public Entry<K, V> select(K key) {
+        return delegate.select(key);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public K selectKey(K key) {
+        return delegate.selectKey(key);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public V selectValue(K key) {
+        return delegate.selectValue(key);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public Entry<K, V> traverse(final Cursor<? super K, ? super V> cursor) {
+        Cursor<K, V> c = new Cursor<K, V>() {
+            public Decision select(Map.Entry<? extends K, ? extends V> entry) {
+                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);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public Set<Entry<K, V>> entrySet() {
+        return Collections.unmodifiableSet(delegate.entrySet());
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public Set<K> keySet() {
+        return Collections.unmodifiableSet(delegate.keySet());
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public Collection<V> values() {
+        return Collections.unmodifiableCollection(delegate.values());
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public void clear() {
+        throw new UnsupportedOperationException();
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean containsKey(Object key) {
+        return delegate.containsKey(key);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean containsValue(Object value) {
+        return delegate.containsValue(value);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public V get(Object key) {
+        return delegate.get(key);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean isEmpty() {
+        return delegate.isEmpty();
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public V put(K key, V value) {
+        throw new UnsupportedOperationException();
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public void putAll(Map<? extends K, ? extends V> m) {
+        throw new UnsupportedOperationException();
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public V remove(Object key) {
+        throw new UnsupportedOperationException();
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public K firstKey() {
+        return delegate.firstKey();
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public SortedMap<K, V> headMap(K toKey) {
+        return Collections.unmodifiableSortedMap(delegate.headMap(toKey));
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public K lastKey() {
+        return delegate.lastKey();
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public SortedMap<K, V> subMap(K fromKey, K toKey) {
+        return Collections.unmodifiableSortedMap(
+                delegate.subMap(fromKey, toKey));
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public SortedMap<K, V> tailMap(K fromKey) {
+        return Collections.unmodifiableSortedMap(delegate.tailMap(fromKey));
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public SortedMap<K, V> getPrefixedBy(K key, int offset, int length) {
+        return Collections.unmodifiableSortedMap(
+                delegate.getPrefixedBy(key, offset, length));
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public SortedMap<K, V> getPrefixedBy(K key, int length) {
+        return Collections.unmodifiableSortedMap(
+                delegate.getPrefixedBy(key, length));
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public SortedMap<K, V> getPrefixedBy(K key) {
+        return Collections.unmodifiableSortedMap(
+                delegate.getPrefixedBy(key));
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public SortedMap<K, V> getPrefixedByBits(K key, int lengthInBits) {
+        return Collections.unmodifiableSortedMap(
+                delegate.getPrefixedByBits(key, lengthInBits));
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public SortedMap<K, V> getPrefixedByBits(K key, int offsetInBits,
+            int lengthInBits) {
+        return Collections.unmodifiableSortedMap(
+                delegate.getPrefixedByBits(key, offsetInBits, lengthInBits));
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public Comparator<? super K> comparator() {
+        return delegate.comparator();
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public int size() {
+        return delegate.size();
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public int hashCode() {
+        return delegate.hashCode();
+    }
+    
+    @Override
+    public boolean equals(Object obj) {
+        return delegate.equals(obj);
+    }
+    
+    @Override
+    public String toString() {
+        return delegate.toString();
+    }
+}

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/UnmodifiableTrie.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/UnmodifiableTrie.java
------------------------------------------------------------------------------
    svn:keywords = Id Revision HeadURL

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/UnmodifiableTrie.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/package-info.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/package-info.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/package-info.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/package-info.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,38 @@
+/*
+ * 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.
+ */
+/**
+ * This package contains implementations of the
+ * {@link org.apache.commons.collections.Trie Trie} interface.
+ * <p>
+ * The implementations are in the form of direct implementations and decorators.
+ * A decorator wraps another implementation of the interface to add some
+ * specific additional functionality.
+ * <p>
+ * The following implementations are provided in the package:
+ * <ul>
+ *   <li>PatriciaTrie - an implementation of a PATRICIA trie
+ * </ul>
+ * <p>
+ * The following decorators are provided:
+ * <ul>
+ *   <li>Synchronized - synchronizes method access for multi-threaded environments
+ *   <li>Unmodifiable - ensures the collection cannot be altered
+ * </ul>
+ *
+ * @version $Id$
+ */
+package org.apache.commons.collections.trie;

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/package-info.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/package-info.java
------------------------------------------------------------------------------
    svn:keywords = Id Revision HeadURL

Propchange: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/package-info.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Added: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/ByteArrayKeyAnalyzerTest.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/ByteArrayKeyAnalyzerTest.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/ByteArrayKeyAnalyzerTest.java (added)
+++ commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/ByteArrayKeyAnalyzerTest.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,110 @@
+/*
+ * 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.collections.trie;
+
+import java.math.BigInteger;
+import java.util.Map;
+import java.util.TreeMap;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+public class ByteArrayKeyAnalyzerTest {
+
+    private static final int SIZE = 20000;
+    
+    @Test
+    public void bitSet() {
+        byte[] key = toByteArray("10100110", 2);
+        ByteArrayKeyAnalyzer ka = new ByteArrayKeyAnalyzer(key.length * 8);
+        int length = ka.lengthInBits(key);
+        
+        Assert.assertTrue(ka.isBitSet(key, 0, length));
+        Assert.assertFalse(ka.isBitSet(key, 1, length));
+        Assert.assertTrue(ka.isBitSet(key, 2, length));
+        Assert.assertFalse(ka.isBitSet(key, 3, length));
+        Assert.assertFalse(ka.isBitSet(key, 4, length));
+        Assert.assertTrue(ka.isBitSet(key, 5, length));
+        Assert.assertTrue(ka.isBitSet(key, 6, length));
+        Assert.assertFalse(ka.isBitSet(key, 7, length));
+    }
+    
+    @Test
+    public void keys() {
+        PatriciaTrie<byte[], BigInteger> trie
+            = new PatriciaTrie<byte[], BigInteger>(ByteArrayKeyAnalyzer.INSTANCE);
+        
+        Map<byte[], BigInteger> map 
+            = new TreeMap<byte[], BigInteger>(ByteArrayKeyAnalyzer.INSTANCE);
+        
+        for (int i = 0; i < SIZE; i++) {
+            BigInteger value = BigInteger.valueOf(i);
+            byte[] key = toByteArray(value);
+            
+            BigInteger existing = trie.put(key, value);
+            Assert.assertNull(existing);
+            
+            map.put(key, value);
+        }
+        
+        Assert.assertEquals(map.size(), trie.size());
+        
+        for (byte[] key : map.keySet()) {
+            BigInteger expected = new BigInteger(1, key);
+            BigInteger value = trie.get(key);
+            
+            Assert.assertEquals(expected, value);
+        }
+    }
+    
+    @Test
+    public void prefix() {
+        byte[] prefix   = toByteArray("00001010", 2);
+        byte[] key1     = toByteArray("11001010", 2);
+        byte[] key2     = toByteArray("10101100", 2);
+        
+        ByteArrayKeyAnalyzer keyAnalyzer = new ByteArrayKeyAnalyzer(key1.length * 8);
+        
+        int prefixLength = keyAnalyzer.lengthInBits(prefix);
+            
+        Assert.assertFalse(keyAnalyzer.isPrefix(prefix, 4, prefixLength, key1));
+        Assert.assertTrue(keyAnalyzer.isPrefix(prefix, 4, prefixLength, key2));
+    }
+    
+    private static byte[] toByteArray(String value, int radix) {
+        return toByteArray(Long.parseLong(value, radix));
+    }
+    
+    private static byte[] toByteArray(long value) {
+        return toByteArray(BigInteger.valueOf(value));
+    }
+    
+    private static byte[] toByteArray(BigInteger value) {
+        byte[] src = value.toByteArray();
+        if (src.length <= 1) {
+            return src;
+        }
+        
+        if (src[0] != 0) {
+            return src;
+        }
+        
+        byte[] dst = new byte[src.length-1];
+        System.arraycopy(src, 1, dst, 0, dst.length);
+        return dst;
+    }
+}

Propchange: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/ByteArrayKeyAnalyzerTest.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/ByteArrayKeyAnalyzerTest.java
------------------------------------------------------------------------------
    svn:keywords = Id Revision HeadURL

Propchange: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/ByteArrayKeyAnalyzerTest.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Added: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/PatriciaTrieTest.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/PatriciaTrieTest.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/PatriciaTrieTest.java (added)
+++ commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/PatriciaTrieTest.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,1125 @@
+/*
+ * 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.collections.trie;
+
+import java.io.BufferedReader;
+import java.io.InputStream;
+import java.io.InputStreamReader;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.ConcurrentModificationException;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import java.util.Random;
+import java.util.SortedMap;
+import java.util.StringTokenizer;
+import java.util.TreeMap;
+import java.util.Map.Entry;
+
+import org.apache.commons.collections.Trie.Cursor;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+public class PatriciaTrieTest {
+    
+    @Test
+    public void testSimple() {
+        PatriciaTrie<Integer, String> intTrie = new PatriciaTrie<Integer, String>(new IntegerKeyAnalyzer());
+        Assert.assertTrue(intTrie.isEmpty());
+        Assert.assertEquals(0, intTrie.size());
+        
+        intTrie.put(1, "One");
+        Assert.assertFalse(intTrie.isEmpty());
+        Assert.assertEquals(1, intTrie.size());
+        
+        Assert.assertEquals("One", intTrie.remove(1));
+        Assert.assertNull(intTrie.remove(1));
+        Assert.assertTrue(intTrie.isEmpty());
+        Assert.assertEquals(0, intTrie.size());
+        
+        intTrie.put(1, "One");
+        Assert.assertEquals("One", intTrie.get(1));
+        Assert.assertEquals("One", intTrie.put(1, "NotOne"));
+        Assert.assertEquals(1, intTrie.size());
+        Assert.assertEquals("NotOne", intTrie.get(1));
+        Assert.assertEquals("NotOne", intTrie.remove(1));
+        Assert.assertNull(intTrie.put(1, "One"));
+    }
+    
+    @Test
+    public void testCeilingEntry() {
+        PatriciaTrie<Character, String> charTrie 
+            = new PatriciaTrie<Character, String>(new CharacterKeyAnalyzer());
+        charTrie.put('c', "c");
+        charTrie.put('p', "p");
+        charTrie.put('l', "l");
+        charTrie.put('t', "t");
+        charTrie.put('k', "k");
+        charTrie.put('a', "a");
+        charTrie.put('y', "y");
+        charTrie.put('r', "r");
+        charTrie.put('u', "u");
+        charTrie.put('o', "o");
+        charTrie.put('w', "w");
+        charTrie.put('i', "i");
+        charTrie.put('e', "e");
+        charTrie.put('x', "x");
+        charTrie.put('q', "q");
+        charTrie.put('b', "b");
+        charTrie.put('j', "j");
+        charTrie.put('s', "s");
+        charTrie.put('n', "n");
+        charTrie.put('v', "v");
+        charTrie.put('g', "g");
+        charTrie.put('h', "h");
+        charTrie.put('m', "m");
+        charTrie.put('z', "z");
+        charTrie.put('f', "f");
+        charTrie.put('d', "d");
+        
+        Object[] results = new Object[] {
+            'a', "a", 'b', "b", 'c', "c", 'd', "d", 'e', "e",
+            'f', "f", 'g', "g", 'h', "h", 'i', "i", 'j', "j",
+            'k', "k", 'l', "l", 'm', "m", 'n', "n", 'o', "o",
+            'p', "p", 'q', "q", 'r', "r", 's', "s", 't', "t",
+            'u', "u", 'v', "v", 'w', "w", 'x', "x", 'y', "y", 
+            'z', "z"
+        };
+        
+        for(int i = 0; i < results.length; i++) {
+            Map.Entry<Character, String> found = charTrie.ceilingEntry((Character)results[i]);
+            Assert.assertNotNull(found);
+            Assert.assertEquals(results[i], found.getKey());
+            Assert.assertEquals(results[++i], found.getValue());
+        }
+        
+        // Remove some & try again...
+        charTrie.remove('a');
+        charTrie.remove('z');
+        charTrie.remove('q');
+        charTrie.remove('l');
+        charTrie.remove('p');
+        charTrie.remove('m');
+        charTrie.remove('u');
+        
+        Map.Entry<Character, String> found = charTrie.ceilingEntry('u');
+        Assert.assertNotNull(found);
+        Assert.assertEquals((Character)'v', found.getKey());
+        
+        found = charTrie.ceilingEntry('a');
+        Assert.assertNotNull(found);
+        Assert.assertEquals((Character)'b', found.getKey());
+        
+        found = charTrie.ceilingEntry('z');
+        Assert.assertNull(found);
+        
+        found = charTrie.ceilingEntry('q');
+        Assert.assertNotNull(found);
+        Assert.assertEquals((Character)'r', found.getKey());
+        
+        found = charTrie.ceilingEntry('l');
+        Assert.assertNotNull(found);
+        Assert.assertEquals((Character)'n', found.getKey());
+        
+        found = charTrie.ceilingEntry('p');
+        Assert.assertNotNull(found);
+        Assert.assertEquals((Character)'r', found.getKey());
+        
+        found = charTrie.ceilingEntry('m');
+        Assert.assertNotNull(found);
+        Assert.assertEquals((Character)'n', found.getKey());
+        
+        found = charTrie.ceilingEntry('\0');
+        Assert.assertNotNull(found);
+        Assert.assertEquals((Character)'b', found.getKey());
+        
+        charTrie.put('\0', "");
+        found = charTrie.ceilingEntry('\0');
+        Assert.assertNotNull(found);
+        Assert.assertEquals((Character)'\0', found.getKey());      
+    }
+    
+    @Test
+    public void testLowerEntry() {
+        PatriciaTrie<Character, String> charTrie = new PatriciaTrie<Character, String>(new CharacterKeyAnalyzer());
+        charTrie.put('c', "c");
+        charTrie.put('p', "p");
+        charTrie.put('l', "l");
+        charTrie.put('t', "t");
+        charTrie.put('k', "k");
+        charTrie.put('a', "a");
+        charTrie.put('y', "y");
+        charTrie.put('r', "r");
+        charTrie.put('u', "u");
+        charTrie.put('o', "o");
+        charTrie.put('w', "w");
+        charTrie.put('i', "i");
+        charTrie.put('e', "e");
+        charTrie.put('x', "x");
+        charTrie.put('q', "q");
+        charTrie.put('b', "b");
+        charTrie.put('j', "j");
+        charTrie.put('s', "s");
+        charTrie.put('n', "n");
+        charTrie.put('v', "v");
+        charTrie.put('g', "g");
+        charTrie.put('h', "h");
+        charTrie.put('m', "m");
+        charTrie.put('z', "z");
+        charTrie.put('f', "f");
+        charTrie.put('d', "d");
+        
+        Object[] results = new Object[] {
+            'a', "a", 'b', "b", 'c', "c", 'd', "d", 'e', "e",
+            'f', "f", 'g', "g", 'h', "h", 'i', "i", 'j', "j",
+            'k', "k", 'l', "l", 'm', "m", 'n', "n", 'o', "o",
+            'p', "p", 'q', "q", 'r', "r", 's', "s", 't', "t",
+            'u', "u", 'v', "v", 'w', "w", 'x', "x", 'y', "y", 
+            'z', "z"
+        };
+        
+        for(int i = 0; i < results.length; i+=2) {
+            //System.out.println("Looking for: " + results[i]);
+            Map.Entry<Character, String> found = charTrie.lowerEntry((Character)results[i]);
+            if(i == 0) {
+                Assert.assertNull(found);
+            } else {
+                Assert.assertNotNull(found);
+                Assert.assertEquals(results[i-2], found.getKey());
+                Assert.assertEquals(results[i-1], found.getValue());
+            }
+        }
+
+        Map.Entry<Character, String> found = charTrie.lowerEntry((char)('z' + 1));
+        Assert.assertNotNull(found);
+        Assert.assertEquals((Character)'z', found.getKey());
+        
+        // Remove some & try again...
+        charTrie.remove('a');
+        charTrie.remove('z');
+        charTrie.remove('q');
+        charTrie.remove('l');
+        charTrie.remove('p');
+        charTrie.remove('m');
+        charTrie.remove('u');
+        
+        found = charTrie.lowerEntry('u');
+        Assert.assertNotNull(found);
+        Assert.assertEquals((Character)'t', found.getKey());
+        
+        found = charTrie.lowerEntry('v');
+        Assert.assertNotNull(found);
+        Assert.assertEquals((Character)'t', found.getKey());
+        
+        found = charTrie.lowerEntry('a');
+        Assert.assertNull(found);
+        
+        found = charTrie.lowerEntry('z');
+        Assert.assertNotNull(found);
+        Assert.assertEquals((Character)'y', found.getKey());
+        
+        found = charTrie.lowerEntry((char)('z'+1));
+        Assert.assertNotNull(found);
+        Assert.assertEquals((Character)'y', found.getKey());
+        
+        found = charTrie.lowerEntry('q');
+        Assert.assertNotNull(found);
+        Assert.assertEquals((Character)'o', found.getKey());
+        
+        found = charTrie.lowerEntry('r');
+        Assert.assertNotNull(found);
+        Assert.assertEquals((Character)'o', found.getKey());
+        
+        found = charTrie.lowerEntry('p');
+        Assert.assertNotNull(found);
+        Assert.assertEquals((Character)'o', found.getKey());
+        
+        found = charTrie.lowerEntry('l');
+        Assert.assertNotNull(found);
+        Assert.assertEquals((Character)'k', found.getKey());
+        
+        found = charTrie.lowerEntry('m');
+        Assert.assertNotNull(found);
+        Assert.assertEquals((Character)'k', found.getKey());
+        
+        found = charTrie.lowerEntry('\0');
+        Assert.assertNull(found);
+        
+        charTrie.put('\0', "");
+        found = charTrie.lowerEntry('\0');
+        Assert.assertNull(found);      
+    }
+    
+    @Test
+    public void testIteration() {
+        PatriciaTrie<Integer, String> intTrie = new PatriciaTrie<Integer, String>(new IntegerKeyAnalyzer());
+        intTrie.put(1, "One");
+        intTrie.put(5, "Five");
+        intTrie.put(4, "Four");
+        intTrie.put(2, "Two");
+        intTrie.put(3, "Three");
+        intTrie.put(15, "Fifteen");
+        intTrie.put(13, "Thirteen");
+        intTrie.put(14, "Fourteen");
+        intTrie.put(16, "Sixteen");
+        
+        TestCursor cursor = new TestCursor(
+                1, "One", 2, "Two", 3, "Three", 4, "Four", 5, "Five", 13, "Thirteen",
+                14, "Fourteen", 15, "Fifteen", 16, "Sixteen");
+
+        cursor.starting();
+        intTrie.traverse(cursor);
+        cursor.finished();
+        
+        cursor.starting();
+        for (Map.Entry<Integer, String> entry : intTrie.entrySet()) {
+            cursor.select(entry);
+        }
+        cursor.finished();
+        
+        cursor.starting();
+        for (Integer integer : intTrie.keySet()) {
+            cursor.checkKey(integer);
+        }
+        cursor.finished();
+        
+        cursor.starting();
+        for (String string : intTrie.values()) {
+            cursor.checkValue(string);
+        }
+        cursor.finished();
+
+        PatriciaTrie<Character, String> charTrie = new PatriciaTrie<Character, String>(new CharacterKeyAnalyzer());
+        charTrie.put('c', "c");
+        charTrie.put('p', "p");
+        charTrie.put('l', "l");
+        charTrie.put('t', "t");
+        charTrie.put('k', "k");
+        charTrie.put('a', "a");
+        charTrie.put('y', "y");
+        charTrie.put('r', "r");
+        charTrie.put('u', "u");
+        charTrie.put('o', "o");
+        charTrie.put('w', "w");
+        charTrie.put('i', "i");
+        charTrie.put('e', "e");
+        charTrie.put('x', "x");
+        charTrie.put('q', "q");
+        charTrie.put('b', "b");
+        charTrie.put('j', "j");
+        charTrie.put('s', "s");
+        charTrie.put('n', "n");
+        charTrie.put('v', "v");
+        charTrie.put('g', "g");
+        charTrie.put('h', "h");
+        charTrie.put('m', "m");
+        charTrie.put('z', "z");
+        charTrie.put('f', "f");
+        charTrie.put('d', "d");
+        cursor = new TestCursor('a', "a", 'b', "b", 'c', "c", 'd', "d", 'e', "e",
+                'f', "f", 'g', "g", 'h', "h", 'i', "i", 'j', "j",
+                'k', "k", 'l', "l", 'm', "m", 'n', "n", 'o', "o",
+                'p', "p", 'q', "q", 'r', "r", 's', "s", 't', "t",
+                'u', "u", 'v', "v", 'w', "w", 'x', "x", 'y', "y", 
+                'z', "z");
+        
+        cursor.starting();
+        charTrie.traverse(cursor);
+        cursor.finished();
+
+        cursor.starting();
+        for (Map.Entry<Character, String> entry : charTrie.entrySet()) {
+            cursor.select(entry);
+        }
+        cursor.finished();
+        
+        cursor.starting();
+        for (Character character : charTrie.keySet()) {
+            cursor.checkKey(character);
+        }
+        cursor.finished();
+        
+        cursor.starting();
+        for (String string : charTrie.values()) {
+            cursor.checkValue(string);
+        }
+        cursor.finished();
+    }
+    
+    @Test
+    public void testSelect() {
+        PatriciaTrie<Character, String> charTrie = new PatriciaTrie<Character, String>(new CharacterKeyAnalyzer());
+        charTrie.put('c', "c");
+        charTrie.put('p', "p");
+        charTrie.put('l', "l");
+        charTrie.put('t', "t");
+        charTrie.put('k', "k");
+        charTrie.put('a', "a");
+        charTrie.put('y', "y");
+        charTrie.put('r', "r");
+        charTrie.put('u', "u");
+        charTrie.put('o', "o");
+        charTrie.put('w', "w");
+        charTrie.put('i', "i");
+        charTrie.put('e', "e");
+        charTrie.put('x', "x");
+        charTrie.put('q', "q");
+        charTrie.put('b', "b");
+        charTrie.put('j', "j");
+        charTrie.put('s', "s");
+        charTrie.put('n', "n");
+        charTrie.put('v', "v");
+        charTrie.put('g', "g");
+        charTrie.put('h', "h");
+        charTrie.put('m', "m");
+        charTrie.put('z', "z");
+        charTrie.put('f', "f");
+        charTrie.put('d', "d");
+        TestCursor cursor = new TestCursor(
+                'd', "d", 'e', "e", 'f', "f", 'g', "g",
+                'a', "a", 'b', "b", 'c', "c",  
+                'l', "l", 'm', "m", 'n', "n", 'o', "o",
+                'h', "h", 'i', "i", 'j', "j", 'k', "k", 
+                't', "t", 'u', "u", 'v', "v", 'w', "w",
+                'p', "p", 'q', "q", 'r', "r", 's', "s", 
+                'x', "x", 'y', "y", 'z', "z");
+                
+        Assert.assertEquals(26, charTrie.size());
+        
+        cursor.starting();
+        charTrie.select('d', cursor);
+        cursor.finished();
+    }
+    
+    @Test
+    public void testTraverseCursorRemove() {
+        PatriciaTrie<Character, String> charTrie = new PatriciaTrie<Character, String>(new CharacterKeyAnalyzer());
+        charTrie.put('c', "c");
+        charTrie.put('p', "p");
+        charTrie.put('l', "l");
+        charTrie.put('t', "t");
+        charTrie.put('k', "k");
+        charTrie.put('a', "a");
+        charTrie.put('y', "y");
+        charTrie.put('r', "r");
+        charTrie.put('u', "u");
+        charTrie.put('o', "o");
+        charTrie.put('w', "w");
+        charTrie.put('i', "i");
+        charTrie.put('e', "e");
+        charTrie.put('x', "x");
+        charTrie.put('q', "q");
+        charTrie.put('b', "b");
+        charTrie.put('j', "j");
+        charTrie.put('s', "s");
+        charTrie.put('n', "n");
+        charTrie.put('v', "v");
+        charTrie.put('g', "g");
+        charTrie.put('h', "h");
+        charTrie.put('m', "m");
+        charTrie.put('z', "z");
+        charTrie.put('f', "f");
+        charTrie.put('d', "d");
+        TestCursor cursor = new TestCursor('a', "a", 'b', "b", 'c', "c", 'd', "d", 'e', "e",
+                'f', "f", 'g', "g", 'h', "h", 'i', "i", 'j', "j",
+                'k', "k", 'l', "l", 'm', "m", 'n', "n", 'o', "o",
+                'p', "p", 'q', "q", 'r', "r", 's', "s", 't', "t",
+                'u', "u", 'v', "v", 'w', "w", 'x', "x", 'y', "y", 
+                'z', "z");
+        
+        cursor.starting();
+        charTrie.traverse(cursor);
+        cursor.finished();
+        
+        // Test removing both an internal & external node.
+        // 'm' is an example External node in this Trie, and 'p' is an internal.
+        
+        Assert.assertEquals(26, charTrie.size());
+        
+        Object[] toRemove = new Object[] { 'g', 'd', 'e', 'm', 'p', 'q', 'r', 's' };
+        cursor.addToRemove(toRemove);
+        
+        cursor.starting();
+        charTrie.traverse(cursor);
+        cursor.finished();
+            
+        Assert.assertEquals(26 - toRemove.length, charTrie.size());
+
+        cursor.starting();
+        charTrie.traverse(cursor);
+        cursor.finished();
+        
+        cursor.starting();
+        for (Entry<Character, String> entry : charTrie.entrySet()) {
+            cursor.select(entry);
+            if (Arrays.asList(toRemove).contains(entry.getKey())) {
+                Assert.fail("got an: " + entry);
+            }
+        }
+        cursor.finished();
+    }
+    
+    @Test
+    public void testIteratorRemove() {
+        PatriciaTrie<Character, String> charTrie = new PatriciaTrie<Character, String>(new CharacterKeyAnalyzer());
+        charTrie.put('c', "c");
+        charTrie.put('p', "p");
+        charTrie.put('l', "l");
+        charTrie.put('t', "t");
+        charTrie.put('k', "k");
+        charTrie.put('a', "a");
+        charTrie.put('y', "y");
+        charTrie.put('r', "r");
+        charTrie.put('u', "u");
+        charTrie.put('o', "o");
+        charTrie.put('w', "w");
+        charTrie.put('i', "i");
+        charTrie.put('e', "e");
+        charTrie.put('x', "x");
+        charTrie.put('q', "q");
+        charTrie.put('b', "b");
+        charTrie.put('j', "j");
+        charTrie.put('s', "s");
+        charTrie.put('n', "n");
+        charTrie.put('v', "v");
+        charTrie.put('g', "g");
+        charTrie.put('h', "h");
+        charTrie.put('m', "m");
+        charTrie.put('z', "z");
+        charTrie.put('f', "f");
+        charTrie.put('d', "d");
+        TestCursor cursor = new TestCursor('a', "a", 'b', "b", 'c', "c", 'd', "d", 'e', "e",
+                'f', "f", 'g', "g", 'h', "h", 'i', "i", 'j', "j",
+                'k', "k", 'l', "l", 'm', "m", 'n', "n", 'o', "o",
+                'p', "p", 'q', "q", 'r', "r", 's', "s", 't', "t",
+                'u', "u", 'v', "v", 'w', "w", 'x', "x", 'y', "y", 
+                'z', "z");
+        
+        // Test removing both an internal & external node.
+        // 'm' is an example External node in this Trie, and 'p' is an internal.
+        
+        Assert.assertEquals(26, charTrie.size());
+        
+        Object[] toRemove = new Object[] { 'e', 'm', 'p', 'q', 'r', 's' };
+        
+        cursor.starting();
+        for(Iterator<Map.Entry<Character, String>> i = charTrie.entrySet().iterator(); i.hasNext(); ) {
+            Map.Entry<Character,String> entry = i.next();
+            cursor.select(entry);
+            if(Arrays.asList(toRemove).contains(entry.getKey())) {
+                i.remove();            
+            }
+        }
+        cursor.finished();
+            
+        Assert.assertEquals(26 - toRemove.length, charTrie.size());
+        
+        cursor.remove(toRemove);
+
+        cursor.starting();
+        for (Entry<Character, String> entry : charTrie.entrySet()) {
+            cursor.select(entry);
+            if (Arrays.asList(toRemove).contains(entry.getKey())) {
+                Assert.fail("got an: " + entry);
+            }
+        }
+        cursor.finished();
+    }
+    
+    @Test
+    public void testHamlet() throws Exception {
+        // Make sure that Hamlet is read & stored in the same order as a SortedSet.
+        List<String> original = new ArrayList<String>();
+        List<String> control = new ArrayList<String>();
+        SortedMap<String, String> sortedControl = new TreeMap<String, String>();
+        PatriciaTrie<String, String> trie = new PatriciaTrie<String, String>(new StringKeyAnalyzer());
+        
+        InputStream in = getClass().getResourceAsStream("hamlet.txt");
+        BufferedReader reader = new BufferedReader(new InputStreamReader(in));
+        
+        String read = null;
+        while( (read = reader.readLine()) != null) {
+            StringTokenizer st = new StringTokenizer(read);
+            while(st.hasMoreTokens()) {
+                String token = st.nextToken();
+                original.add(token);
+                sortedControl.put(token, token);
+                trie.put(token, token);
+            }
+        }
+        control.addAll(sortedControl.values());
+
+        Assert.assertEquals(control.size(), sortedControl.size());
+        Assert.assertEquals(sortedControl.size(), trie.size());
+        Iterator<String> iter = trie.values().iterator();
+        for (String aControl : control) {
+            Assert.assertEquals(aControl, iter.next());
+        }
+        
+        Random rnd = new Random();
+        int item = 0;
+        iter = trie.values().iterator();
+        int removed = 0;
+        for(; item < control.size(); item++) {
+            Assert.assertEquals(control.get(item), iter.next());
+            if(rnd.nextBoolean()) {
+                iter.remove();
+                removed++;
+            }
+        }
+        
+        Assert.assertEquals(control.size(), item);
+        Assert.assertTrue(removed > 0);
+        Assert.assertEquals(control.size(), trie.size() + removed);
+        
+        // reset hamlet
+        trie.clear();
+        for (String anOriginal : original) {
+            trie.put(anOriginal, anOriginal);
+        }
+        
+        assertEqualArrays(sortedControl.values().toArray(), trie.values().toArray());
+        assertEqualArrays(sortedControl.keySet().toArray(), trie.keySet().toArray());
+        assertEqualArrays(sortedControl.entrySet().toArray(), trie.entrySet().toArray());
+        
+        Assert.assertEquals(sortedControl.firstKey(), trie.firstKey());
+        Assert.assertEquals(sortedControl.lastKey(), trie.lastKey());
+        
+        SortedMap<String, String> sub = trie.headMap(control.get(523));
+        Assert.assertEquals(523, sub.size());
+        for(int i = 0; i < control.size(); i++) {
+            if(i < 523) {
+                Assert.assertTrue(sub.containsKey(control.get(i)));
+            } else {
+                Assert.assertFalse(sub.containsKey(control.get(i)));
+            }
+        }
+        // Too slow to check values on all, so just do a few.
+        Assert.assertTrue(sub.containsValue(control.get(522)));
+        Assert.assertFalse(sub.containsValue(control.get(523)));
+        Assert.assertFalse(sub.containsValue(control.get(524)));
+        
+        try {
+            sub.headMap(control.get(524));
+            Assert.fail("should have thrown IAE");
+        } catch(IllegalArgumentException expected) {}
+        
+        Assert.assertEquals(sub.lastKey(), control.get(522));
+        Assert.assertEquals(sub.firstKey(), control.get(0));
+        
+        sub = sub.tailMap(control.get(234));
+        Assert.assertEquals(289, sub.size());
+        Assert.assertEquals(control.get(234), sub.firstKey());
+        Assert.assertEquals(control.get(522), sub.lastKey());
+        for(int i = 0; i < control.size(); i++) {
+            if(i < 523 && i > 233) {
+                Assert.assertTrue(sub.containsKey(control.get(i)));
+            } else {
+                Assert.assertFalse(sub.containsKey(control.get(i)));
+            }
+        }
+
+        try {
+            sub.tailMap(control.get(232));
+            Assert.fail("should have thrown IAE");
+        } catch(IllegalArgumentException expected) {}
+        
+        sub = sub.subMap(control.get(300), control.get(400));
+        Assert.assertEquals(100, sub.size());
+        Assert.assertEquals(control.get(300), sub.firstKey());
+        Assert.assertEquals(control.get(399), sub.lastKey());
+        
+        for(int i = 0; i < control.size(); i++) {
+            if(i < 400 && i > 299) {
+                Assert.assertTrue(sub.containsKey(control.get(i)));
+            } else {
+                Assert.assertFalse(sub.containsKey(control.get(i)));
+            }
+        }
+    }
+    
+    @Test
+    public void testPrefixedBy() {
+        PatriciaTrie<String, String> trie 
+            = new PatriciaTrie<String, String>(new StringKeyAnalyzer());
+        
+        final String[] keys = new String[]{
+                "", 
+                "Albert", "Xavier", "XyZ", "Anna", "Alien", "Alberto",
+                "Alberts", "Allie", "Alliese", "Alabama", "Banane",
+                "Blabla", "Amber", "Ammun", "Akka", "Akko", "Albertoo",
+                "Amma"
+        };
+
+        for (String key : keys) {
+            trie.put(key, key);
+        }
+        
+        SortedMap<String, String> map;
+        Iterator<String> iterator;
+        Iterator<Map.Entry<String, String>> entryIterator;
+        Map.Entry<String, String> entry;
+        
+        map = trie.getPrefixedBy("Al");
+        Assert.assertEquals(8, map.size());
+        Assert.assertEquals("Alabama", map.firstKey());
+        Assert.assertEquals("Alliese", map.lastKey());
+        Assert.assertEquals("Albertoo", map.get("Albertoo"));
+        Assert.assertNotNull(trie.get("Xavier"));
+        Assert.assertNull(map.get("Xavier"));
+        Assert.assertNull(trie.get("Alice"));
+        Assert.assertNull(map.get("Alice"));
+        iterator = map.values().iterator();
+        Assert.assertEquals("Alabama", iterator.next());
+        Assert.assertEquals("Albert", iterator.next());
+        Assert.assertEquals("Alberto", iterator.next());
+        Assert.assertEquals("Albertoo", iterator.next());
+        Assert.assertEquals("Alberts", iterator.next());
+        Assert.assertEquals("Alien", iterator.next());
+        Assert.assertEquals("Allie", iterator.next());
+        Assert.assertEquals("Alliese", iterator.next());
+        Assert.assertFalse(iterator.hasNext());
+        
+        map = trie.getPrefixedBy("Albert");
+        iterator = map.keySet().iterator();
+        Assert.assertEquals("Albert", iterator.next());
+        Assert.assertEquals("Alberto", iterator.next());
+        Assert.assertEquals("Albertoo", iterator.next());
+        Assert.assertEquals("Alberts", iterator.next());
+        Assert.assertFalse(iterator.hasNext());
+        Assert.assertEquals(4, map.size());
+        Assert.assertEquals("Albert", map.firstKey());
+        Assert.assertEquals("Alberts", map.lastKey());
+        Assert.assertNull(trie.get("Albertz"));
+        map.put("Albertz", "Albertz");
+        Assert.assertEquals("Albertz", trie.get("Albertz"));
+        Assert.assertEquals(5, map.size());
+        Assert.assertEquals("Albertz", map.lastKey());
+        iterator = map.keySet().iterator();
+        Assert.assertEquals("Albert", iterator.next());
+        Assert.assertEquals("Alberto", iterator.next());
+        Assert.assertEquals("Albertoo", iterator.next());
+        Assert.assertEquals("Alberts", iterator.next());
+        Assert.assertEquals("Albertz", iterator.next());
+        Assert.assertFalse(iterator.hasNext());
+        Assert.assertEquals("Albertz", map.remove("Albertz"));
+        
+        map = trie.getPrefixedBy("Alberto");
+        Assert.assertEquals(2, map.size());
+        Assert.assertEquals("Alberto", map.firstKey());
+        Assert.assertEquals("Albertoo", map.lastKey());
+        entryIterator = map.entrySet().iterator();
+        entry = entryIterator.next();
+        Assert.assertEquals("Alberto", entry.getKey());
+        Assert.assertEquals("Alberto", entry.getValue());
+        entry = entryIterator.next();
+        Assert.assertEquals("Albertoo", entry.getKey());
+        Assert.assertEquals("Albertoo", entry.getValue());
+        Assert.assertFalse(entryIterator.hasNext());
+        trie.put("Albertoad", "Albertoad");
+        Assert.assertEquals(3, map.size());
+        Assert.assertEquals("Alberto", map.firstKey());
+        Assert.assertEquals("Albertoo", map.lastKey());
+        entryIterator = map.entrySet().iterator();
+        entry = entryIterator.next();
+        Assert.assertEquals("Alberto", entry.getKey());
+        Assert.assertEquals("Alberto", entry.getValue());
+        entry = entryIterator.next();
+        Assert.assertEquals("Albertoad", entry.getKey());
+        Assert.assertEquals("Albertoad", entry.getValue());
+        entry = entryIterator.next();
+        Assert.assertEquals("Albertoo", entry.getKey());
+        Assert.assertEquals("Albertoo", entry.getValue());
+        Assert.assertFalse(entryIterator.hasNext());
+        Assert.assertEquals("Albertoo", trie.remove("Albertoo"));
+        Assert.assertEquals("Alberto", map.firstKey());
+        Assert.assertEquals("Albertoad", map.lastKey());
+        Assert.assertEquals(2, map.size());
+        entryIterator = map.entrySet().iterator();
+        entry = entryIterator.next();
+        Assert.assertEquals("Alberto", entry.getKey());
+        Assert.assertEquals("Alberto", entry.getValue());
+        entry = entryIterator.next();
+        Assert.assertEquals("Albertoad", entry.getKey());
+        Assert.assertEquals("Albertoad", entry.getValue());
+        Assert.assertFalse(entryIterator.hasNext());
+        Assert.assertEquals("Albertoad", trie.remove("Albertoad"));
+        trie.put("Albertoo", "Albertoo");
+        
+        map = trie.getPrefixedBy("X");
+        Assert.assertEquals(2, map.size());
+        Assert.assertFalse(map.containsKey("Albert"));
+        Assert.assertTrue(map.containsKey("Xavier"));
+        Assert.assertFalse(map.containsKey("Xalan"));
+        iterator = map.values().iterator();
+        Assert.assertEquals("Xavier", iterator.next());
+        Assert.assertEquals("XyZ", iterator.next());
+        Assert.assertFalse(iterator.hasNext());
+        
+        map = trie.getPrefixedBy("An");
+        Assert.assertEquals(1, map.size());
+        Assert.assertEquals("Anna", map.firstKey());
+        Assert.assertEquals("Anna", map.lastKey());
+        iterator = map.keySet().iterator();
+        Assert.assertEquals("Anna", iterator.next());
+        Assert.assertFalse(iterator.hasNext());
+        
+        map = trie.getPrefixedBy("Ban");
+        Assert.assertEquals(1, map.size());
+        Assert.assertEquals("Banane", map.firstKey());
+        Assert.assertEquals("Banane", map.lastKey());
+        iterator = map.keySet().iterator();
+        Assert.assertEquals("Banane", iterator.next());
+        Assert.assertFalse(iterator.hasNext());
+        
+        map = trie.getPrefixedBy("Am");
+        Assert.assertFalse(map.isEmpty());
+        Assert.assertEquals(3, map.size());
+        Assert.assertEquals("Amber", trie.remove("Amber"));
+        iterator = map.keySet().iterator();
+        Assert.assertEquals("Amma", iterator.next());
+        Assert.assertEquals("Ammun", iterator.next());
+        Assert.assertFalse(iterator.hasNext());
+        iterator = map.keySet().iterator();
+        map.put("Amber", "Amber");
+        Assert.assertEquals(3, map.size());
+        try {
+            iterator.next();
+            Assert.fail("CME expected");
+        } catch(ConcurrentModificationException expected) {}
+        Assert.assertEquals("Amber", map.firstKey());
+        Assert.assertEquals("Ammun", map.lastKey());
+        
+        map = trie.getPrefixedBy("Ak\0");
+        Assert.assertTrue(map.isEmpty());
+        
+        map = trie.getPrefixedBy("Ak");
+        Assert.assertEquals(2, map.size());
+        Assert.assertEquals("Akka", map.firstKey());
+        Assert.assertEquals("Akko", map.lastKey());
+        map.put("Ak", "Ak");
+        Assert.assertEquals("Ak", map.firstKey());
+        Assert.assertEquals("Akko", map.lastKey());
+        Assert.assertEquals(3, map.size());
+        trie.put("Al", "Al");
+        Assert.assertEquals(3, map.size());
+        Assert.assertEquals("Ak", map.remove("Ak"));
+        Assert.assertEquals("Akka", map.firstKey());
+        Assert.assertEquals("Akko", map.lastKey());
+        Assert.assertEquals(2, map.size());
+        iterator = map.keySet().iterator();
+        Assert.assertEquals("Akka", iterator.next());
+        Assert.assertEquals("Akko", iterator.next());
+        Assert.assertFalse(iterator.hasNext());
+        Assert.assertEquals("Al", trie.remove("Al"));
+        
+        map = trie.getPrefixedBy("Akka");
+        Assert.assertEquals(1, map.size());
+        Assert.assertEquals("Akka", map.firstKey());
+        Assert.assertEquals("Akka", map.lastKey());
+        iterator = map.keySet().iterator();
+        Assert.assertEquals("Akka", iterator.next());
+        Assert.assertFalse(iterator.hasNext());
+        
+        map = trie.getPrefixedBy("Ab");
+        Assert.assertTrue(map.isEmpty());
+        Assert.assertEquals(0, map.size());
+        try {
+            Object o = map.firstKey();
+            Assert.fail("got a first key: " + o);
+        } catch(NoSuchElementException nsee) {}
+        try {
+            Object o = map.lastKey();
+            Assert.fail("got a last key: " + o);
+        } catch(NoSuchElementException nsee) {}
+        iterator = map.values().iterator();
+        Assert.assertFalse(iterator.hasNext());
+        
+        map = trie.getPrefixedBy("Albertooo");
+        Assert.assertTrue(map.isEmpty());
+        Assert.assertEquals(0, map.size());
+        try {
+            Object o = map.firstKey();
+            Assert.fail("got a first key: " + o);
+        } catch(NoSuchElementException nsee) {}
+        try {
+            Object o = map.lastKey();
+            Assert.fail("got a last key: " + o);
+        } catch(NoSuchElementException nsee) {}
+        iterator = map.values().iterator();
+        Assert.assertFalse(iterator.hasNext());
+        
+        map = trie.getPrefixedBy("");
+        Assert.assertSame(trie, map); // stricter than necessary, but a good check
+        
+        map = trie.getPrefixedBy("\0");
+        Assert.assertTrue(map.isEmpty());
+        Assert.assertEquals(0, map.size());
+        try {
+            Object o = map.firstKey();
+            Assert.fail("got a first key: " + o);
+        } catch(NoSuchElementException nsee) {}
+        try {
+            Object o = map.lastKey();
+            Assert.fail("got a last key: " + o);
+        } catch(NoSuchElementException nsee) {}
+        iterator = map.values().iterator();
+        Assert.assertFalse(iterator.hasNext());
+    }
+    
+    @Test
+    public void testPrefixByOffsetAndLength() {
+        PatriciaTrie<String, String> trie 
+            = new PatriciaTrie<String, String>(new StringKeyAnalyzer());
+        
+        final String[] keys = new String[]{
+                "Albert", "Xavier", "XyZ", "Anna", "Alien", "Alberto",
+                "Alberts", "Allie", "Alliese", "Alabama", "Banane",
+                "Blabla", "Amber", "Ammun", "Akka", "Akko", "Albertoo",
+                "Amma"
+        };
+    
+        for (String key : keys) {
+            trie.put(key, key);
+        }
+        
+        SortedMap<String, String> map;
+        Iterator<String> iterator;
+        
+        map = trie.getPrefixedBy("Alice", 2);
+        Assert.assertEquals(8, map.size());
+        Assert.assertEquals("Alabama", map.firstKey());
+        Assert.assertEquals("Alliese", map.lastKey());
+        Assert.assertEquals("Albertoo", map.get("Albertoo"));
+        Assert.assertNotNull(trie.get("Xavier"));
+        Assert.assertNull(map.get("Xavier"));
+        Assert.assertNull(trie.get("Alice"));
+        Assert.assertNull(map.get("Alice"));
+        iterator = map.values().iterator();
+        Assert.assertEquals("Alabama", iterator.next());
+        Assert.assertEquals("Albert", iterator.next());
+        Assert.assertEquals("Alberto", iterator.next());
+        Assert.assertEquals("Albertoo", iterator.next());
+        Assert.assertEquals("Alberts", iterator.next());
+        Assert.assertEquals("Alien", iterator.next());
+        Assert.assertEquals("Allie", iterator.next());
+        Assert.assertEquals("Alliese", iterator.next());
+        Assert.assertFalse(iterator.hasNext());
+        
+        map = trie.getPrefixedBy("BAlice", 1, 2);
+        Assert.assertEquals(8, map.size());
+        Assert.assertEquals("Alabama", map.firstKey());
+        Assert.assertEquals("Alliese", map.lastKey());
+        Assert.assertEquals("Albertoo", map.get("Albertoo"));
+        Assert.assertNotNull(trie.get("Xavier"));
+        Assert.assertNull(map.get("Xavier"));
+        Assert.assertNull(trie.get("Alice"));
+        Assert.assertNull(map.get("Alice"));
+        iterator = map.values().iterator();
+        Assert.assertEquals("Alabama", iterator.next());
+        Assert.assertEquals("Albert", iterator.next());
+        Assert.assertEquals("Alberto", iterator.next());
+        Assert.assertEquals("Albertoo", iterator.next());
+        Assert.assertEquals("Alberts", iterator.next());
+        Assert.assertEquals("Alien", iterator.next());
+        Assert.assertEquals("Allie", iterator.next());
+        Assert.assertEquals("Alliese", iterator.next());
+        Assert.assertFalse(iterator.hasNext());
+    }
+    
+    @Test
+    public void testPrefixedByRemoval() {
+        PatriciaTrie<String, String> trie 
+            = new PatriciaTrie<String, String>(new StringKeyAnalyzer());
+        
+        final String[] keys = new String[]{
+                "Albert", "Xavier", "XyZ", "Anna", "Alien", "Alberto",
+                "Alberts", "Allie", "Alliese", "Alabama", "Banane",
+                "Blabla", "Amber", "Ammun", "Akka", "Akko", "Albertoo",
+                "Amma"
+        };
+
+        for (String key : keys) {
+            trie.put(key, key);
+        }
+        
+        SortedMap<String, String> map = trie.getPrefixedBy("Al");
+        Assert.assertEquals(8, map.size());
+        Iterator<String> iter = map.keySet().iterator();
+        Assert.assertEquals("Alabama", iter.next());
+        Assert.assertEquals("Albert", iter.next());
+        Assert.assertEquals("Alberto", iter.next());
+        Assert.assertEquals("Albertoo", iter.next());
+        Assert.assertEquals("Alberts", iter.next());
+        Assert.assertEquals("Alien", iter.next());
+        iter.remove();
+        Assert.assertEquals(7, map.size());
+        Assert.assertEquals("Allie", iter.next());
+        Assert.assertEquals("Alliese", iter.next());
+        Assert.assertFalse(iter.hasNext());
+        
+        map = trie.getPrefixedBy("Ak");
+        Assert.assertEquals(2, map.size());
+        iter = map.keySet().iterator();
+        Assert.assertEquals("Akka", iter.next());
+        iter.remove();
+        Assert.assertEquals(1, map.size());
+        Assert.assertEquals("Akko", iter.next());
+        if(iter.hasNext()) {
+            Assert.fail("shouldn't have next (but was: " + iter.next() + ")");
+        }
+        Assert.assertFalse(iter.hasNext());
+    }
+
+    @Test
+    public void testTraverseWithAllNullBitKey() {
+        PatriciaTrie<String, String> trie 
+            = new PatriciaTrie<String, String>(new StringKeyAnalyzer());
+        
+        //
+        // One entry in the Trie
+        // Entry is stored at the root
+        //
+        
+        // trie.put("", "All Bits Are Zero");
+        trie.put("\0", "All Bits Are Zero");
+        
+        //
+        //  / ("")   <-- root
+        //  \_/  \
+        //       null
+        //
+        
+        final List<String> strings = new ArrayList<String>();
+        trie.traverse(new Cursor<String, String>() {
+            public Decision select(Entry<? extends String, ? extends String> entry) {
+                strings.add(entry.getValue());
+                return Decision.CONTINUE;
+            }
+        });
+        
+        Assert.assertEquals(1, strings.size());
+        
+        strings.clear();
+        for (String s : trie.values()) {
+            strings.add(s);
+        }
+        Assert.assertEquals(1, strings.size());
+    }
+    
+    @Test
+    public void testSelectWithAllNullBitKey() {
+        PatriciaTrie<String, String> trie 
+            = new PatriciaTrie<String, String>(new StringKeyAnalyzer());
+        
+        // trie.put("", "All Bits Are Zero");
+        trie.put("\0", "All Bits Are Zero");
+        
+        final List<String> strings = new ArrayList<String>();
+        trie.select("Hello", new Cursor<String, String>() {
+            public Decision select(Entry<? extends String, ? extends String> entry) {
+                strings.add(entry.getValue());
+                return Decision.CONTINUE;
+            }
+        });
+        Assert.assertEquals(1, strings.size());
+    }
+    
+    private static class TestCursor implements Cursor<Object, Object> {
+        private List<Object> keys;
+        private List<Object> values;
+        private Object selectFor;
+        private List<Object> toRemove;
+        private int index = 0;
+        
+        TestCursor(Object... objects) {
+            if(objects.length % 2 != 0) {
+                throw new IllegalArgumentException("must be * 2");
+            }
+            
+            keys = new ArrayList<Object>(objects.length / 2);
+            values = new ArrayList<Object>(keys.size());
+            toRemove = Collections.emptyList();
+            for(int i = 0; i < objects.length; i++) {
+                keys.add(objects[i]);
+                values.add(objects[++i]);
+            }
+        }
+        
+        void selectFor(Object object) {
+            selectFor = object;
+        }
+        
+        void addToRemove(Object... objects) {
+            toRemove = new ArrayList<Object>(Arrays.asList(objects));
+        }
+        
+        void remove(Object... objects) {
+            for (Object object : objects) {
+                int idx = keys.indexOf(object);
+                keys.remove(idx);
+                values.remove(idx);
+            }
+        }
+        
+        void starting() {
+            index = 0;
+        }
+        
+        public void checkKey(Object k) {
+            Assert.assertEquals(keys.get(index++), k);
+        }
+        
+        public void checkValue(Object o) {
+            Assert.assertEquals(values.get(index++), o);
+        }
+
+        public Decision select(Entry<?, ?> entry) {
+          //  System.out.println("Scanning: " + entry.getKey());
+            Assert.assertEquals(keys.get(index), entry.getKey());
+            Assert.assertEquals(values.get(index), entry.getValue());
+            index++;
+            
+            if(toRemove.contains(entry.getKey())) {
+              // System.out.println("Removing: " + entry.getKey());
+                index--;
+                keys.remove(index);
+                values.remove(index);
+                toRemove.remove(entry.getKey());
+                return Decision.REMOVE;
+            } 
+            
+            if(selectFor != null && selectFor.equals(entry.getKey())) {
+                return Decision.EXIT;
+            } else {
+                return Decision.CONTINUE;
+            }
+        }
+        
+        void finished() {
+            Assert.assertEquals(keys.size(), index);
+        }
+    }
+    
+    private static void assertEqualArrays(Object[] a, Object[] b) {
+        Assert.assertTrue(Arrays.equals(a, b));
+    }
+}

Propchange: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/PatriciaTrieTest.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/PatriciaTrieTest.java
------------------------------------------------------------------------------
    svn:executable = *

Propchange: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/PatriciaTrieTest.java
------------------------------------------------------------------------------
    svn:keywords = Id Revision HeadURL

Propchange: commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/PatriciaTrieTest.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain



Mime
View raw message