You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by tn...@apache.org on 2012/07/25 22:42:49 UTC
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...
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 & L is smaller
+ * than the XOR distance between D & 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 & L is smaller
+ * than the XOR distance between D & 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 & L is smaller
+ * than the XOR distance between D & 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 & 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