Mailing-List: contact commits-help@commons.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@commons.apache.org
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: svn commit: r1365732 [1/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 -0000
To: commits@commons.apache.org
From: tn@apache.org
Message-Id: <20120725204250.6075C238890D@eris.apache.org>

Author: tn
Date: Wed Jul 25 20:42:48 2012
New Revision: 1365732

URL: http://svn.apache.org/viewvc?rev=1365732&view=rev
Log:
[COLLECTION-225] Added first version patricia trie contribution.

Added:
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/Trie.java   (with props)
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/TrieUtils.java   (with props)
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/AbstractKeyAnalyzer.java   (with props)
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/AbstractTrie.java   (with props)
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ByteArrayKeyAnalyzer.java   (with props)
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ByteKeyAnalyzer.java   (with props)
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/CharArrayKeyAnalyzer.java   (with props)
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/CharacterKeyAnalyzer.java   (with props)
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/IntegerKeyAnalyzer.java   (with props)
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/KeyAnalyzer.java   (with props)
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/LongKeyAnalyzer.java   (with props)
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/PatriciaTrie.java   (with props)
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/PatriciaTrieBase.java   (with props)
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ShortKeyAnalyzer.java   (with props)
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/StringKeyAnalyzer.java   (with props)
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/SynchronizedTrie.java   (with props)
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/UnmodifiableTrie.java   (with props)
    commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/package-info.java   (with props)
    commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/
    commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/ByteArrayKeyAnalyzerTest.java   (with props)
    commons/proper/collections/trunk/src/test/java/org/apache/commons/collections/trie/PatriciaTrieTest.java   (with props)
    commons/proper/collections/trunk/src/test/resources/org/
    commons/proper/collections/trunk/src/test/resources/org/apache/
    commons/proper/collections/trunk/src/test/resources/org/apache/commons/
    commons/proper/collections/trunk/src/test/resources/org/apache/commons/collections/
    commons/proper/collections/trunk/src/test/resources/org/apache/commons/collections/trie/
    commons/proper/collections/trunk/src/test/resources/org/apache/commons/collections/trie/hamlet.txt   (with props)
Modified:
    commons/proper/collections/trunk/pom.xml

Modified: commons/proper/collections/trunk/pom.xml
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/pom.xml?rev=1365732&r1=1365731&r2=1365732&view=diff
==============================================================================
--- commons/proper/collections/trunk/pom.xml (original)
+++ commons/proper/collections/trunk/pom.xml Wed Jul 25 20:42:48 2012
@@ -131,6 +131,9 @@
       <name>Ola Berg</name>
     </contributor>
     <contributor>
+      <name>Sam Berlin</name>
+    </contributor>
+    <contributor>
       <name>Christopher Berry</name>
     </contributor>
     <contributor>
@@ -206,6 +209,9 @@
       <name>Marc Johnson</name>
     </contributor>
     <contributor>
+      <name>Roger Kapsi</name>
+    </contributor>
+    <contributor>
       <name>Nissim Karpenstein</name>
     </contributor>
     <contributor>

Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/Trie.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/Trie.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/Trie.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/Trie.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,238 @@
+/*
+ * 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;
+
+import java.util.Map;
+import java.util.SortedMap;
+import java.util.Map.Entry;
+
+/**
+ * Defines the interface for a prefix tree, an ordered tree data structure. For 
+ * more information, see <a href="http://en.wikipedia.org/wiki/Trie">Tries</a>.
+ * 
+ * @since 4.0
+ * @version $Id$
+ */
+public interface Trie<K, V> extends SortedMap<K, V> {
+
+    /**
+     * Returns the {@link Entry} whose key is closest in a bitwise XOR 
+     * metric to the given key. This is NOT lexicographic closeness.
+     * For example, given the keys:
+     *
+     * <ol>
+     * <li>D = 1000100
+     * <li>H = 1001000
+     * <li>L = 1001100
+     * </ol>
+     * 
+     * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would 
+     * return 'L', because the XOR distance between D &amp; L is smaller 
+     * than the XOR distance between D &amp; H. 
+     * 
+     * @return The {@link Entry} whose key is closest in a bitwise XOR metric
+     * to the provided key.
+     */
+    public Map.Entry<K, V> select(K key);
+    
+    /**
+     * Returns the key that is closest in a bitwise XOR metric to the 
+     * provided key. This is NOT lexicographic closeness!
+     * 
+     * For example, given the keys:
+     * 
+     * <ol>
+     * <li>D = 1000100
+     * <li>H = 1001000
+     * <li>L = 1001100
+     * </ol>
+     * 
+     * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would 
+     * return 'L', because the XOR distance between D &amp; L is smaller 
+     * than the XOR distance between D &amp; H. 
+     * 
+     * @return The key that is closest in a bitwise XOR metric to the provided key.
+     */
+    public K selectKey(K key);
+    
+    /**
+     * Returns the value whose key is closest in a bitwise XOR metric to 
+     * the provided key. This is NOT lexicographic closeness!
+     * 
+     * For example, given the keys:
+     * 
+     * <ol>
+     * <li>D = 1000100
+     * <li>H = 1001000
+     * <li>L = 1001100
+     * </ol>
+     * 
+     * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would 
+     * return 'L', because the XOR distance between D &amp; L is smaller 
+     * than the XOR distance between D &amp; H. 
+     * 
+     * @return The value whose key is closest in a bitwise XOR metric
+     * to the provided key.
+     */
+    public V selectValue(K key);
+    
+    /**
+     * Iterates through the {@link Trie}, starting with the entry whose bitwise
+     * value is closest in an XOR metric to the given key. After the closest
+     * entry is found, the {@link Trie} will call select on that entry and continue
+     * calling select for each entry (traversing in order of XOR closeness,
+     * NOT lexicographically) until the cursor returns {@link Decision#EXIT}.
+     * 
+     * <p>The cursor can return {@link Decision#CONTINUE} to continue traversing.
+     * 
+     * <p>{@link Decision#REMOVE_AND_EXIT} is used to remove the current element
+     * and stop traversing.
+     * 
+     * <p>Note: The {@link Decision#REMOVE} operation is not supported.
+     * 
+     * @return The entry the cursor returned {@link Decision#EXIT} on, or null 
+     * if it continued till the end.
+     */
+    public Map.Entry<K,V> select(K key, Cursor<? super K, ? super V> cursor);
+    
+    /**
+     * Traverses the {@link Trie} in lexicographical order. 
+     * {@link Cursor#select(java.util.Map.Entry)} will be called on each entry.
+     * 
+     * <p>The traversal will stop when the cursor returns {@link Decision#EXIT}, 
+     * {@link Decision#CONTINUE} is used to continue traversing and 
+     * {@link Decision#REMOVE} is used to remove the element that was selected 
+     * and continue traversing.
+     * 
+     * <p>{@link Decision#REMOVE_AND_EXIT} is used to remove the current element
+     * and stop traversing.
+     *   
+     * @return The entry the cursor returned {@link Decision#EXIT} on, or null 
+     * if it continued till the end.
+     */
+    public Map.Entry<K,V> traverse(Cursor<? super K, ? super V> cursor);
+    
+    /**
+     * Returns a view of this {@link SortedTrie} of all elements that are prefixed 
+     * by the given key.
+     * 
+     * <p>In a {@link SortedTrie} with fixed size keys, this is essentially a 
+     * {@link #get(Object)} operation.
+     * 
+     * <p>For example, if the {@link SortedTrie} contains 'Anna', 'Anael', 
+     * 'Analu', 'Andreas', 'Andrea', 'Andres', and 'Anatole', then
+     * a lookup of 'And' would return 'Andreas', 'Andrea', and 'Andres'.
+     */
+    public SortedMap<K, V> getPrefixedBy(K key);
+    
+    /**
+     * Returns a view of this {@link SortedTrie} of all elements that are prefixed 
+     * by the length of the key.
+     * 
+     * <p>{@link SortedTrie}s with fixed size keys will not support this operation 
+     * (because all keys are the same length).
+     * 
+     * <p>For example, if the {@link SortedTrie} contains 'Anna', 'Anael', 'Analu', 
+     * 'Andreas', 'Andrea', 'Andres', and 'Anatole', then a lookup for 'Andrey' 
+     * and a length of 4 would return 'Andreas', 'Andrea', and 'Andres'.
+     */
+    public SortedMap<K, V> getPrefixedBy(K key, int length);
+    
+    /**
+     * Returns a view of this {@link SortedTrie} of all elements that are prefixed
+     * by the key, starting at the given offset and for the given length.
+     * 
+     * <p>{@link SortedTrie}s with fixed size keys will not support this operation 
+     * (because all keys are the same length).
+     * 
+     * <p>For example, if the {@link SortedTrie} contains 'Anna', 'Anael', 'Analu', 
+     * 'Andreas', 'Andrea', 'Andres', and 'Anatole', then a lookup for 
+     * 'Hello Andrey Smith', an offset of 6 and a length of 4 would return 
+     * 'Andreas', 'Andrea', and 'Andres'.
+     */
+    public SortedMap<K, V> getPrefixedBy(K key, int offset, int length);
+    
+    /**
+     * Returns a view of this {@link SortedTrie} of all elements that are prefixed
+     * by the number of bits in the given Key.
+     * 
+     * <p>In {@link SortedTrie}s with fixed size keys like IP addresses this method
+     * can be used to lookup partial keys. That is you can lookup all addresses
+     * that begin with '192.168' by providing the key '192.168.X.X' and a 
+     * length of 16.
+     */
+    public SortedMap<K, V> getPrefixedByBits(K key, int lengthInBits);
+    
+    /**
+     * Returns a view of this {@link SortedTrie} of all elements that are prefixed
+     * by the number of bits in the given Key.
+     */
+    public SortedMap<K, V> getPrefixedByBits(K key, int offsetInBits, int lengthInBits);
+    
+    /**
+     * A {@link Cursor} can be used to traverse a {@link Trie}, visit each node 
+     * step by step and make {@link Decision}s on each step how to continue with 
+     * traversing the {@link Trie}.
+     */
+    public interface Cursor<K, V> {
+        
+        /**
+         * The {@link Decision} tells the {@link Cursor} what to do on each step 
+         * while traversing the {@link Trie}.
+         * 
+         * NOTE: Not all operations that work with a {@link Cursor} support all 
+         * {@link Decision} types
+         */
+        public static enum Decision {
+            
+            /**
+             * Exit the traverse operation
+             */
+            EXIT, 
+            
+            /**
+             * Continue with the traverse operation
+             */
+            CONTINUE, 
+            
+            /**
+             * Remove the previously returned element
+             * from the {@link Trie} and continue
+             */
+            REMOVE, 
+            
+            /**
+             * Remove the previously returned element
+             * from the {@link Trie} and exit from the
+             * traverse operation
+             */
+            REMOVE_AND_EXIT;
+        }
+        
+        /**
+         * Called for each {@link Entry} in the {@link Trie}. Return 
+         * {@link Decision#EXIT} to finish the {@link Trie} operation,
+         * {@link Decision#CONTINUE} to go to the next {@link Entry},
+         * {@link Decision#REMOVE} to remove the {@link Entry} and
+         * continue iterating or {@link Decision#REMOVE_AND_EXIT} to
+         * remove the {@link Entry} and stop iterating.
+         * 
+         * Note: Not all operations support {@link Decision#REMOVE}.
+         */
+        public Decision select(Map.Entry<? extends K, ? extends V> entry);
+    }
+}

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

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

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

Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/TrieUtils.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/TrieUtils.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/TrieUtils.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/TrieUtils.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,53 @@
+/*
+ * 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;
+
+import org.apache.commons.collections.trie.SynchronizedTrie;
+import org.apache.commons.collections.trie.UnmodifiableTrie;
+
+/**
+ * A collection of {@link Trie} utilities.
+ * 
+ * @since 4.0
+ * @version $Id$
+ */
+public class TrieUtils {
+
+    /**
+     * {@link TrieUtils} should not normally be instantiated.
+     */
+    private TrieUtils() {}
+    
+    /**
+     * Returns a synchronized instance of a {@link Trie}
+     * 
+     * @see Collections#synchronizedMap(Map)
+     */
+    public static <K, V> Trie<K, V> synchronizedTrie(Trie<K, V> trie) {
+        return SynchronizedTrie.synchronizedTrie(trie);
+    }
+    
+    /**
+     * Returns an unmodifiable instance of a {@link Trie}
+     * 
+     * @see Collections#unmodifiableMap(Map)
+     */
+    public static <K, V> Trie<K, V> unmodifiableTrie(Trie<K, V> trie) {
+        return UnmodifiableTrie.unmodifiableTrie(trie);
+    }
+
+}

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

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

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

Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/AbstractKeyAnalyzer.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/AbstractKeyAnalyzer.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/AbstractKeyAnalyzer.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/AbstractKeyAnalyzer.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,72 @@
+/*
+ * 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;
+
+/**
+ * TODO: add javadoc
+ * 
+ * @since 4.0
+ * @version $Id$
+ */
+public abstract class AbstractKeyAnalyzer<K> implements KeyAnalyzer<K> {
+    
+    private static final long serialVersionUID = -20497563720380683L;
+
+    /**
+     * {@inheritDoc}
+     */
+    @SuppressWarnings("unchecked")
+    public int compare(K o1, K o2) {
+        if (o1 == null) {
+            return (o2 == null) ? 0 : -1;
+        } else if (o2 == null) {
+            return (o1 == null) ? 0 : 1;
+        }
+        
+        return ((Comparable<K>)o1).compareTo(o2);
+    }
+    
+    /** 
+     * Returns true if bitIndex is a {@link KeyAnalyzer#OUT_OF_BOUNDS_BIT_KEY}
+     */
+    static boolean isOutOfBoundsIndex(int bitIndex) {
+        return bitIndex == OUT_OF_BOUNDS_BIT_KEY;
+    }
+
+    /** 
+     * Returns true if bitIndex is a {@link KeyAnalyzer#EQUAL_BIT_KEY}
+     */
+    static boolean isEqualBitKey(int bitIndex) {
+        return bitIndex == EQUAL_BIT_KEY;
+    }
+
+    /** 
+     * Returns true if bitIndex is a {@link KeyAnalyzer#NULL_BIT_KEY} 
+     */
+    static boolean isNullBitKey(int bitIndex) {
+        return bitIndex == NULL_BIT_KEY;
+    }
+
+    /** 
+     * Returns true if the given bitIndex is valid. Indices 
+     * are considered valid if they're between 0 and 
+     * {@link Integer#MAX_VALUE}
+     */
+    static boolean isValidBitIndex(int bitIndex) {
+        return 0 <= bitIndex && bitIndex <= Integer.MAX_VALUE;
+    }
+}

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

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

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

Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/AbstractTrie.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/AbstractTrie.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/AbstractTrie.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/AbstractTrie.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,250 @@
+/*
+ * 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.AbstractMap;
+import java.util.Map;
+
+import org.apache.commons.collections.Trie;
+
+/**
+ * This class provides some basic {@link Trie} functionality and 
+ * utility methods for actual {@link Trie} implementations.
+ * 
+ * @since 4.0
+ * @version $Id$
+ */
+abstract class AbstractTrie<K, V> extends AbstractMap<K, V> 
+        implements Trie<K, V>, Serializable {
+    
+    private static final long serialVersionUID = 5826987063535505652L;
+    
+    /**
+     * The {@link KeyAnalyzer} that's being used to build the 
+     * PATRICIA {@link Trie}.
+     */
+    protected final KeyAnalyzer<? super K> keyAnalyzer;
+    
+    /** 
+     * Constructs a new {@link Trie} using the given {@link KeyAnalyzer}.
+     */
+    public AbstractTrie(KeyAnalyzer<? super K> keyAnalyzer) {
+        if (keyAnalyzer == null) {
+            throw new NullPointerException("keyAnalyzer");
+        }
+        
+        this.keyAnalyzer = keyAnalyzer;
+    }
+    
+    /**
+     * Returns the {@link KeyAnalyzer} that constructed the {@link Trie}.
+     */
+    public KeyAnalyzer<? super K> getKeyAnalyzer() {
+        return keyAnalyzer;
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public K selectKey(K key) {
+        Map.Entry<K, V> entry = select(key);
+        if (entry == null) {
+            return null;
+        }
+        return entry.getKey();
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public V selectValue(K key) {
+        Map.Entry<K, V> entry = select(key);
+        if (entry == null) {
+            return null;
+        }
+        return entry.getValue();
+    }
+    
+    @Override
+    public String toString() {
+        StringBuilder buffer = new StringBuilder();
+        buffer.append("Trie[").append(size()).append("]={\n");
+        for (Map.Entry<K, V> entry : entrySet()) {
+            buffer.append("  ").append(entry).append("\n");
+        }
+        buffer.append("}\n");
+        return buffer.toString();
+    }
+    
+    /**
+     * A utility method to cast keys. It actually doesn't
+     * cast anything. It's just fooling the compiler!
+     */
+    @SuppressWarnings("unchecked")
+    final K castKey(Object key) {
+        return (K)key;
+    }
+    
+    /**
+     * Returns the length of the given key in bits
+     * 
+     * @see KeyAnalyzer#lengthInBits(Object)
+     */
+    final int lengthInBits(K key) {
+        if (key == null) {
+            return 0;
+        }
+        
+        return keyAnalyzer.lengthInBits(key);
+    }
+    
+    /**
+     * Returns the number of bits per element in the key
+     * 
+     * @see KeyAnalyzer#bitsPerElement()
+     */
+    final int bitsPerElement() {
+        return keyAnalyzer.bitsPerElement();
+    }
+    
+    /**
+     * Returns whether or not the given bit on the 
+     * key is set or false if the key is null.
+     * 
+     * @see KeyAnalyzer#isBitSet(Object, int, int)
+     */
+    final boolean isBitSet(K key, int bitIndex, int lengthInBits) {
+        if (key == null) { // root's might be null!
+            return false;
+        }
+        return keyAnalyzer.isBitSet(key, bitIndex, lengthInBits);
+    }
+    
+    /**
+     * Utility method for calling {@link KeyAnalyzer#bitIndex(Object, int, int, Object, int, int)}
+     */
+    final int bitIndex(K key, K foundKey) {
+        return keyAnalyzer.bitIndex(key, 0, lengthInBits(key), 
+                foundKey, 0, lengthInBits(foundKey));
+    }
+    
+    /**
+     * An utility method for calling {@link KeyAnalyzer#compare(Object, Object)}
+     */
+    final boolean compareKeys(K key, K other) {
+        if (key == null) {
+            return (other == null);
+        } else if (other == null) {
+            return (key == null);
+        }
+        
+        return keyAnalyzer.compare(key, other) == 0;
+    }
+    
+    /**
+     * Returns true if both values are either null or equal
+     */
+    static boolean compare(Object a, Object b) {
+        return (a == null ? b == null : a.equals(b));
+    }
+    
+    /**
+     * A basic implementation of {@link Entry}
+     */
+    abstract static class BasicEntry<K, V> implements Map.Entry<K, V>, Serializable {
+        
+        private static final long serialVersionUID = -944364551314110330L;
+
+        protected K key;
+        
+        protected V value;
+        
+        private final int hashCode;
+        
+        public BasicEntry(K key) {
+            this.key = key;
+            this.hashCode = (key != null ? key.hashCode() : 0);
+        }
+        
+        public BasicEntry(K key, V value) {
+            this.key = key;
+            this.value = value;
+            
+            this.hashCode = (key != null ? key.hashCode() : 0)
+                    ^ (value != null ? value.hashCode() : 0);
+        }
+        
+        /**
+         * Replaces the current key and value with the provided
+         * key &amp; value
+         */
+        public V setKeyValue(K key, V value) {
+            this.key = key;
+            return setValue(value);
+        }
+        
+        /**
+         * {@inheritDoc}
+         */
+        public K getKey() {
+            return key;
+        }
+        
+        /**
+         * {@inheritDoc}
+         */
+        public V getValue() {
+            return value;
+        }
+
+        /**
+         * {@inheritDoc}
+         */
+        public V setValue(V value) {
+            V previous = this.value;
+            this.value = value;
+            return previous;
+        }
+        
+        @Override
+        public int hashCode() {
+            return hashCode;
+        }
+        
+        @Override
+        public boolean equals(Object o) {
+            if (o == this) {
+                return true;
+            } else if (!(o instanceof Map.Entry)) {
+                return false;
+            }
+            
+            Map.Entry<?, ?> other = (Map.Entry<?, ?>)o;
+            if (compare(key, other.getKey()) 
+                    && compare(value, other.getValue())) {
+                return true;
+            }
+            return false;
+        }
+        
+        @Override
+        public String toString() {
+            return key + "=" + value;
+        }
+    }
+}

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

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

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

Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ByteArrayKeyAnalyzer.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ByteArrayKeyAnalyzer.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ByteArrayKeyAnalyzer.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ByteArrayKeyAnalyzer.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,200 @@
+/*
+ * 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 byte[]s.
+ * 
+ * @since 4.0
+ * @version $Id$
+ */
+public class ByteArrayKeyAnalyzer extends AbstractKeyAnalyzer<byte[]> {
+    
+    private static final long serialVersionUID = 7382825097492285877L;
+
+    /**
+     * A singleton instance of {@link ByteArrayKeyAnalyzer}
+     */
+    public static final ByteArrayKeyAnalyzer INSTANCE 
+        = new ByteArrayKeyAnalyzer(Integer.MAX_VALUE);
+    
+    /**
+     * The length of an {@link Byte} in bits
+     */
+    public static final int LENGTH = Byte.SIZE;
+    
+    /**
+     * A bit mask where the first bit is 1 and the others are zero
+     */
+    private static final int MSB = 0x80;
+    
+    /**
+     * A place holder for null
+     */
+    private static final byte[] NULL = new byte[0];
+    
+    /**
+     * The maximum length of a key in bits
+     */
+    private final int maxLengthInBits;
+    
+    public ByteArrayKeyAnalyzer(int maxLengthInBits) {
+        if (maxLengthInBits < 0) {
+            throw new IllegalArgumentException(
+                    "maxLengthInBits=" + maxLengthInBits);
+        }
+        
+        this.maxLengthInBits = maxLengthInBits;
+    }
+    
+    /**
+     * Returns a bit mask where the given bit is set
+     */
+    private static int mask(int bit) {
+        return MSB >>> bit;
+    }
+
+    /**
+     * Returns the maximum length of a key in bits
+     * @return the maximum key length in bits
+     */
+    public int getMaxLengthInBits() {
+        return maxLengthInBits;
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public int bitsPerElement() {
+        return LENGTH;
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public int lengthInBits(byte[] key) {
+        return (key != null ? key.length * bitsPerElement() : 0);
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public boolean isBitSet(byte[] key, int bitIndex, int lengthInBits) {
+        if (key == null) {     
+            return false;
+        }
+        
+        int prefix = maxLengthInBits - lengthInBits;
+        int keyBitIndex = bitIndex - prefix;
+        
+        if (keyBitIndex >= lengthInBits || keyBitIndex < 0) {
+            return false;
+        }
+        
+        int index = (int)(keyBitIndex / LENGTH);
+        int bit = (int)(keyBitIndex % LENGTH);
+        return (key[index] & mask(bit)) != 0;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public int bitIndex(byte[] key, int offsetInBits, int lengthInBits, 
+            byte[] other, int otherOffsetInBits, int otherLengthInBits) {
+        
+        if (other == null) {
+            other = NULL;
+        }
+        
+        boolean allNull = true;
+        int length = Math.max(lengthInBits, otherLengthInBits);
+        int prefix = maxLengthInBits - length;
+        
+        if (prefix < 0) {
+            return KeyAnalyzer.OUT_OF_BOUNDS_BIT_KEY;
+        }
+        
+        for (int i = 0; i < length; i++) {
+            int index = prefix + (offsetInBits + i);
+            boolean value = isBitSet(key, index, lengthInBits);
+                
+            if (value) {
+                allNull = false;
+            }
+            
+            int otherIndex = prefix + (otherOffsetInBits + i);
+            boolean otherValue = isBitSet(other, otherIndex, otherLengthInBits);
+            
+            if (value != otherValue) {
+                return index;
+            }
+        }
+        
+        if (allNull) {
+            return KeyAnalyzer.NULL_BIT_KEY;
+        }
+        
+        return KeyAnalyzer.EQUAL_BIT_KEY;
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public boolean isPrefix(byte[] prefix, int offsetInBits, 
+            int lengthInBits, byte[] key) {
+        
+        int keyLength = lengthInBits(key);
+        if (lengthInBits > keyLength) {
+            return false;
+        }
+        
+        int elements = lengthInBits - offsetInBits;
+        for (int i = 0; i < elements; i++) {
+            if (isBitSet(prefix, i+offsetInBits, lengthInBits) 
+                    != isBitSet(key, i, keyLength)) {
+                return false;
+            }
+        }
+        
+        return true;
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public int compare(byte[] o1, byte[] o2) {
+        if (o1 == null) {
+            return (o2 == null) ? 0 : -1;
+        } else if (o2 == null) {
+            return (o1 == null) ? 0 : 1;
+        }
+        
+        if (o1.length != o2.length) {
+            return o1.length - o2.length;
+        }
+        
+        for (int i = 0; i < o1.length; i++) {
+            int diff = (o1[i] & 0xFF) - (o2[i] & 0xFF);
+            if (diff != 0) {
+                return diff;
+            }
+        }
+
+        return 0;
+    }
+}

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

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

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

Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ByteKeyAnalyzer.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ByteKeyAnalyzer.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ByteKeyAnalyzer.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/ByteKeyAnalyzer.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,118 @@
+/*
+ * 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 Byte}s.
+ * 
+ * @since 4.0
+ * @version $Id$
+ */
+public class ByteKeyAnalyzer extends AbstractKeyAnalyzer<Byte> {
+    
+    private static final long serialVersionUID = 3395803342983289829L;
+
+    /**
+     * A singleton instance of {@link ByteKeyAnalyzer}
+     */
+    public static final ByteKeyAnalyzer INSTANCE = new ByteKeyAnalyzer();
+    
+    /**
+     * The length of an {@link Byte} in bits
+     */
+    public static final int LENGTH = Byte.SIZE;
+    
+    /**
+     * A bit mask where the first bit is 1 and the others are zero
+     */
+    private static final int MSB = 0x80;
+    
+    /**
+     * 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(Byte key) {
+        return LENGTH;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean isBitSet(Byte key, int bitIndex, int lengthInBits) {
+        return (key & mask(bitIndex)) != 0;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public int bitIndex(Byte key, int offsetInBits, int lengthInBits, 
+            Byte other, int otherOffsetInBits, int otherLengthInBits) {
+        
+        if (offsetInBits != 0 || otherOffsetInBits != 0) {
+            throw new IllegalArgumentException("offsetInBits=" + offsetInBits 
+                    + ", otherOffsetInBits=" + otherOffsetInBits);
+        }
+        
+        byte keyValue = key.byteValue();
+        if (keyValue == 0) {
+            return NULL_BIT_KEY;
+        }
+
+        byte otherValue = (other != null ? other.byteValue() : 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 boolean isPrefix(Byte prefix, int offsetInBits, 
+            int lengthInBits, Byte key) {
+        
+        int value1 = (prefix.byteValue() << offsetInBits);
+        int value2 = key.byteValue();
+        
+        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/ByteKeyAnalyzer.java
------------------------------------------------------------------------------
    svn:eol-style = native

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

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

Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/CharArrayKeyAnalyzer.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/CharArrayKeyAnalyzer.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/CharArrayKeyAnalyzer.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/CharArrayKeyAnalyzer.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,159 @@
+/*
+ * 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 {@code char[]}s.
+ * 
+ * @since 4.0
+ * @version $Id$
+ */
+public class CharArrayKeyAnalyzer extends AbstractKeyAnalyzer<char[]> {
+    
+    private static final long serialVersionUID = -8167897361549463457L;
+
+    /**
+     * A singleton instance of {@link CharArrayKeyAnalyzer}
+     */
+    public static final CharArrayKeyAnalyzer INSTANCE = new CharArrayKeyAnalyzer();
+
+    /**
+     * 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(char[] key) {
+        return (key != null ? key.length * LENGTH : 0);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public int bitIndex(char[] key, int offsetInBits, int lengthInBits,
+            char[] 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[index1];
+            }
+
+            if (other == null || index2 >= endIndex2) {
+                f = 0;
+            } else {
+                f = other[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(char[] key, int bitIndex, int lengthInBits) {
+        if (key == null || bitIndex >= lengthInBits) {
+            return false;
+        }
+
+        int index = (int)(bitIndex / LENGTH);
+        int bit = (int)(bitIndex % LENGTH);
+
+        return (key[index] & mask(bit)) != 0;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean isPrefix(char[] prefix, int offsetInBits,
+            int lengthInBits, char[] key) {
+        if (offsetInBits % LENGTH != 0 || lengthInBits % LENGTH != 0) {
+            throw new IllegalArgumentException(
+                    "Cannot determine prefix outside of Character boundaries");
+        }
+
+        int off = offsetInBits / LENGTH;
+        int len = lengthInBits / LENGTH;
+        for (int i = 0; i < len; i ++) {
+            if (prefix[i + off] != key[i]) {
+                return false;
+            }
+        }
+        return true;
+    }
+}

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

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

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

Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/CharacterKeyAnalyzer.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/CharacterKeyAnalyzer.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/CharacterKeyAnalyzer.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/CharacterKeyAnalyzer.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,123 @@
+/*
+ * 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 Character}s.
+ * 
+ * @since 4.0
+ * @version $Id$
+ */
+public class CharacterKeyAnalyzer extends AbstractKeyAnalyzer<Character> {
+    
+    private static final long serialVersionUID = 3928565962744720753L;
+    
+    /**
+     * A singleton instance of the {@link CharacterKeyAnalyzer}.
+     */
+    public static final CharacterKeyAnalyzer INSTANCE 
+        = new CharacterKeyAnalyzer();
+    
+    /**
+     * The length of a {@link Character} in bits
+     */
+    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 1;
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public int lengthInBits(Character key) {
+        return LENGTH;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean isBitSet(Character key, int bitIndex, int lengthInBits) {
+        return (key & mask(bitIndex)) != 0;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public int bitIndex(Character key, int offsetInBits, int lengthInBits, 
+            Character other, int otherOffsetInBits, int otherLengthInBits) {
+        
+        if (offsetInBits != 0 || otherOffsetInBits != 0) {
+            throw new IllegalArgumentException("offsetInBits=" + offsetInBits 
+                    + ", otherOffsetInBits=" + otherOffsetInBits);
+        }
+        
+        char keyValue = key.charValue();
+        if (keyValue == Character.MIN_VALUE) {
+            return NULL_BIT_KEY;
+        }
+        
+        if (other == null) {
+            other = Character.MIN_VALUE;
+        }
+        
+        char otherValue = (other != null ? other.charValue() : Character.MIN_VALUE);
+        
+        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 boolean isPrefix(Character prefix, int offsetInBits, 
+            int lengthInBits, Character key) {
+        
+        int value1 = (prefix.charValue() << offsetInBits);
+        int value2 = key.charValue();
+        
+        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/CharacterKeyAnalyzer.java
------------------------------------------------------------------------------
    svn:eol-style = native

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

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

Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/IntegerKeyAnalyzer.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/IntegerKeyAnalyzer.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/IntegerKeyAnalyzer.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/IntegerKeyAnalyzer.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,118 @@
+/*
+ * 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 Integer}s.
+ * 
+ * @since 4.0
+ * @version $Id$
+ */
+public class IntegerKeyAnalyzer extends AbstractKeyAnalyzer<Integer> {
+    
+    private static final long serialVersionUID = 4928508653722068982L;
+    
+    /**
+     * A singleton instance of {@link IntegerKeyAnalyzer}
+     */
+    public static final IntegerKeyAnalyzer INSTANCE = new IntegerKeyAnalyzer();
+    
+    /**
+     * The length of an {@link Integer} in bits
+     */
+    public static final int LENGTH = Integer.SIZE;
+    
+    /**
+     * A bit mask where the first bit is 1 and the others are zero
+     */
+    private static final int MSB = 0x80000000;
+    
+    /**
+     * 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(Integer key) {
+        return LENGTH;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean isBitSet(Integer key, int bitIndex, int lengthInBits) {
+        return (key & mask(bitIndex)) != 0;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public int bitIndex(Integer key, int offsetInBits, int lengthInBits, 
+            Integer other, int otherOffsetInBits, int otherLengthInBits) {
+        
+        if (offsetInBits != 0 || otherOffsetInBits != 0) {
+            throw new IllegalArgumentException("offsetInBits=" + offsetInBits 
+                    + ", otherOffsetInBits=" + otherOffsetInBits);
+        }
+        
+        int keyValue = key.intValue();
+        if (keyValue == 0) {
+            return NULL_BIT_KEY;
+        }
+
+        int otherValue = (other != null ? other.intValue() : 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 boolean isPrefix(Integer prefix, int offsetInBits, 
+            int lengthInBits, Integer key) {
+        
+        int value1 = (prefix.intValue() << offsetInBits);
+        int value2 = key.intValue();
+        
+        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/IntegerKeyAnalyzer.java
------------------------------------------------------------------------------
    svn:eol-style = native

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

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

Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/KeyAnalyzer.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/KeyAnalyzer.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/KeyAnalyzer.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/KeyAnalyzer.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,82 @@
+/*
+ * 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.Comparator;
+
+/** 
+ * Defines the interface to analyze {@link Trie} keys on a bit level. 
+ * {@link KeyAnalyzer}'s methods return the length of the key in bits, 
+ * whether or not a bit is set, and bits per element in the key. 
+ * 
+ * <p>Additionally, a method determines if a key is a prefix of another 
+ * key and returns the bit index where one key is different from another 
+ * key (if the key and found key are equal than the return value is 
+ * {@link #EQUAL_BIT_KEY}).
+ * 
+ * @since 4.0
+ * @version $Id$
+ */
+public interface KeyAnalyzer<K> extends Comparator<K>, Serializable {
+    
+    /** 
+     * Returned by {@link #bitIndex(Object, int, int, Object, int, int)} 
+     * if key's bits are all 0 
+     */
+    public static final int NULL_BIT_KEY = -1;
+    
+    /** 
+     * Returned by {@link #bitIndex(Object, int, int, Object, int, int)} 
+     * if key and found key are equal. This is a very very specific case 
+     * and shouldn't happen on a regular basis
+     */
+    public static final int EQUAL_BIT_KEY = -2;
+    
+    public static final int OUT_OF_BOUNDS_BIT_KEY = -3;
+    
+    /**
+     * Returns the number of bits per element in the key.
+     * This is only useful for variable-length keys, such as Strings.
+     */
+    public int bitsPerElement();
+    
+    /** 
+     * Returns the length of the Key in bits. 
+     */
+    public int lengthInBits(K key);
+    
+    /** 
+     * Returns whether or not a bit is set 
+     */
+    public boolean isBitSet(K key, int bitIndex, int lengthInBits);
+    
+    /**
+     * Returns the n-th different bit between key and found.
+     * This starts the comparison in key at 'keyStart' and goes
+     * for 'keyLength' bits, and compares to the found key
+     * starting at 'foundStart' and going for 'foundLength' bits.
+     */
+    public int bitIndex(K key, int offsetInBits, int lengthInBits, 
+            K other, int otherOffsetInBits, int otherLengthInBits);
+    
+    /**
+     * Determines whether or not the given prefix (from offset to length)
+     * is a prefix of the given key.
+     */
+    public boolean isPrefix(K prefix, int offsetInBits, int lengthInBits, K key);
+}

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

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

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

Added: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/LongKeyAnalyzer.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/LongKeyAnalyzer.java?rev=1365732&view=auto
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/LongKeyAnalyzer.java (added)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections/trie/LongKeyAnalyzer.java Wed Jul 25 20:42:48 2012
@@ -0,0 +1,118 @@
+/*
+ * 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 Long}s.
+ * 
+ * @since 4.0
+ * @version $Id$
+ */
+public class LongKeyAnalyzer extends AbstractKeyAnalyzer<Long> {
+    
+    private static final long serialVersionUID = -4119639247588227409L;
+
+    /**
+     * A singleton instance of {@link LongKeyAnalyzer}
+     */
+    public static final LongKeyAnalyzer INSTANCE = new LongKeyAnalyzer();
+    
+    /**
+     * The length of an {@link Long} in bits
+     */
+    public static final int LENGTH = Long.SIZE;
+    
+    /**
+     * A bit mask where the first bit is 1 and the others are zero
+     */
+    private static final long MSB = 0x8000000000000000L;
+    
+    /**
+     * Returns a bit mask where the given bit is set
+     */
+    private static long mask(int bit) {
+        return MSB >>> bit;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public int bitsPerElement() {
+        return 1;
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public int lengthInBits(Long key) {
+        return LENGTH;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean isBitSet(Long key, int bitIndex, int lengthInBits) {
+        return (key & mask(bitIndex)) != 0;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public int bitIndex(Long key, int offsetInBits, int lengthInBits, 
+            Long other, int otherOffsetInBits, int otherLengthInBits) {
+        
+        if (offsetInBits != 0 || otherOffsetInBits != 0) {
+            throw new IllegalArgumentException("offsetInBits=" + offsetInBits 
+                    + ", otherOffsetInBits=" + otherOffsetInBits);
+        }
+        
+        long keyValue = key.longValue();
+        if (keyValue == 0L) {
+            return NULL_BIT_KEY;
+        }
+
+        long otherValue = (other != null ? other.longValue() : 0L);
+        
+        if (keyValue != otherValue) {
+            long xorValue = keyValue ^ otherValue;
+            for (int i = 0; i < LENGTH; i++) {
+                if ((xorValue & mask(i)) != 0L) {
+                    return i;
+                }
+            }
+        }
+        
+        return KeyAnalyzer.EQUAL_BIT_KEY;
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public boolean isPrefix(Long prefix, int offsetInBits, 
+            int lengthInBits, Long key) {
+        
+        long value1 = (prefix.longValue() << offsetInBits);
+        long value2 = key.longValue();
+        
+        long mask = 0L;
+        for (int i = 0; i < lengthInBits; i++) {
+            mask |= (0x1L << i);
+        }
+        
+        return (value1 & mask) == (value2 & mask);
+    }
+}

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

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

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