Author: tn
Date: Mon Jun 10 22:05:38 2013
New Revision: 1491621
URL: http://svn.apache.org/r1491621
Log:
Further cleanup of trie package & interface, renamed AbstractTrie to
AbstractBitwiseTrie, added TODOs.
Added:
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractBitwiseTrie.java
- copied, changed from r1491615,
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractTrie.java
Removed:
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractTrie.java
Modified:
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/Trie.java
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/KeyAnalyzer.java
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/PatriciaTrie.java
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/PatriciaTrieBase.java
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/SynchronizedTrie.java
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/UnmodifiableTrie.java
Modified:
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/Trie.java
URL:
http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/Trie.java?rev=1491621&r1=1491620&r2=1491621&view=diff
==============================================================================
---
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/Trie.java
(original)
+++
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/Trie.java
Mon Jun 10 22:05:38 2013
@@ -27,94 +27,13 @@ import java.util.Map.Entry;
* @since 4.0
* @version $Id$
*/
+// TODO: should extend IterableSortedMap
+// TODO: move bitwise getPrefixedBy methods to AbstractBitwiseTrie
+// TODO: consider a BitwiseTrie interface which extends Trie and supports the
bitwise selection methods
+// TODO: consider a better name for getPrefixedBy: maybe prefixMap(...)
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.
- *
- * @param key the key to use in the search
- * @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.
- *
- * @param key the key to use in the search
- * @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.
- *
- * @param key the key to use in the search
- * @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
Cursor.Decision#EXIT}.
- * <p>
- * The cursor can return {@link Cursor.Decision#CONTINUE} to continue
traversing.
- * <p>
- * {@link Cursor.Decision#REMOVE_AND_EXIT} is used to remove the current
element
- * and stop traversing.
- * <p>
- * Note: The {@link Cursor.Decision#REMOVE} operation is not supported.
- *
- * @param key the key to use in the search
- * @param cursor the cursor used throughout the search
- * @return the entry the cursor returned {@link Cursor.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>
Copied:
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractBitwiseTrie.java
(from r1491615,
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractTrie.java)
URL:
http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractBitwiseTrie.java?p2=commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractBitwiseTrie.java&p1=commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractTrie.java&r1=1491615&r2=1491621&rev=1491621&view=diff
==============================================================================
---
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractTrie.java
(original)
+++
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractBitwiseTrie.java
Mon Jun 10 22:05:38 2013
@@ -19,17 +19,18 @@ package org.apache.commons.collections4.
import java.io.Serializable;
import java.util.AbstractMap;
import java.util.Map;
+import java.util.Map.Entry;
import org.apache.commons.collections4.Trie;
/**
* This class provides some basic {@link Trie} functionality and
- * utility methods for actual {@link Trie} implementations.
+ * utility methods for actual bitwise {@link Trie} implementations.
*
* @since 4.0
* @version $Id$
*/
-abstract class AbstractTrie<K, V> extends AbstractMap<K, V>
+abstract class AbstractBitwiseTrie<K, V> extends AbstractMap<K, V>
implements Trie<K, V>, Serializable {
private static final long serialVersionUID = 5826987063535505652L;
@@ -37,15 +38,14 @@ abstract class AbstractTrie<K, V> extend
// TODO Privatise fields?
/**
- * The {@link KeyAnalyzer} that's being used to build the
- * PATRICIA {@link Trie}.
+ * 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(final KeyAnalyzer<? super K> keyAnalyzer) {
+ public AbstractBitwiseTrie(final KeyAnalyzer<? super K> keyAnalyzer) {
if (keyAnalyzer == null) {
throw new NullPointerException("keyAnalyzer");
}
@@ -60,6 +60,46 @@ abstract class AbstractTrie<K, V> extend
return keyAnalyzer;
}
+ /**
+ * 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.
+ *
+ * @param key the key to use in the search
+ * @return the {@link Entry} whose key is closest in a bitwise XOR metric
+ * to the provided key
+ */
+ public abstract 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.
+ *
+ * @param key the key to use in the search
+ * @return the key that is closest in a bitwise XOR metric to the provided
key
+ */
public K selectKey(final K key) {
final Map.Entry<K, V> entry = select(key);
if (entry == null) {
@@ -68,6 +108,26 @@ abstract class AbstractTrie<K, V> extend
return entry.getKey();
}
+ /**
+ * 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.
+ *
+ * @param key the key to use in the search
+ * @return the value whose key is closest in a bitwise XOR metric
+ * to the provided key
+ */
public V selectValue(final K key) {
final Map.Entry<K, V> entry = select(key);
if (entry == null) {
@@ -76,6 +136,27 @@ abstract class AbstractTrie<K, V> extend
return entry.getValue();
}
+ /**
+ * 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
Cursor.Decision#EXIT}.
+ * <p>
+ * The cursor can return {@link Cursor.Decision#CONTINUE} to continue
traversing.
+ * <p>
+ * {@link Cursor.Decision#REMOVE_AND_EXIT} is used to remove the current
element
+ * and stop traversing.
+ * <p>
+ * Note: The {@link Cursor.Decision#REMOVE} operation is not supported.
+ *
+ * @param key the key to use in the search
+ * @param cursor the cursor used throughout the search
+ * @return the entry the cursor returned {@link Cursor.Decision#EXIT} on,
or null
+ * if it continued till the end
+ */
+ public abstract Map.Entry<K,V> select(K key, Cursor<? super K, ? super V>
cursor);
+
@Override
public String toString() {
final StringBuilder buffer = new StringBuilder();
Modified:
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/KeyAnalyzer.java
URL:
http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/KeyAnalyzer.java?rev=1491621&r1=1491620&r2=1491621&view=diff
==============================================================================
---
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/KeyAnalyzer.java
(original)
+++
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/KeyAnalyzer.java
Mon Jun 10 22:05:38 2013
@@ -21,8 +21,8 @@ import java.util.Comparator;
/**
* Defines the interface to analyze {@link
org.apache.commons.collections4.Trie 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.
+ * {@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
@@ -39,44 +39,42 @@ public abstract class KeyAnalyzer<K> imp
/**
* Returned by {@link #bitIndex(Object, int, int, Object, int, int)}
- * if key's bits are all 0
+ * 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
+ * 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 true if bitIndex is a {@link KeyAnalyzer#OUT_OF_BOUNDS_BIT_KEY}
+ * Returns true if bitIndex is a {@link KeyAnalyzer#OUT_OF_BOUNDS_BIT_KEY}.
*/
static boolean isOutOfBoundsIndex(final int bitIndex) {
return bitIndex == OUT_OF_BOUNDS_BIT_KEY;
}
/**
- * Returns true if bitIndex is a {@link KeyAnalyzer#EQUAL_BIT_KEY}
+ * Returns true if bitIndex is a {@link KeyAnalyzer#EQUAL_BIT_KEY}.
*/
static boolean isEqualBitKey(final int bitIndex) {
return bitIndex == EQUAL_BIT_KEY;
}
/**
- * Returns true if bitIndex is a {@link KeyAnalyzer#NULL_BIT_KEY}
+ * Returns true if bitIndex is a {@link KeyAnalyzer#NULL_BIT_KEY}.
*/
static boolean isNullBitKey(final 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}
+ * 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(final int bitIndex) {
return bitIndex >= 0;
Modified:
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/PatriciaTrie.java
URL:
http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/PatriciaTrie.java?rev=1491621&r1=1491620&r2=1491621&view=diff
==============================================================================
---
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/PatriciaTrie.java
(original)
+++
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/PatriciaTrie.java
Mon Jun 10 22:05:38 2013
@@ -29,11 +29,10 @@ import java.util.SortedMap;
import org.apache.commons.collections4.Trie;
/**
- * <h3>PATRICIA {@link Trie}</h3>
- *
- * <i>Practical Algorithm to Retrieve Information Coded in Alphanumeric</i>
- *
- * <p>A PATRICIA {@link Trie} is a compressed {@link Trie}. Instead of storing
+ * Implementation of a PATRICIA Trie (Practical Algorithm to Retrieve
Information
+ * Coded in Alphanumeric).
+ * <p>
+ * A PATRICIA {@link Trie} is a compressed {@link Trie}. Instead of storing
* all data at the edges of the {@link Trie} (and having empty internal nodes),
* PATRICIA stores data in every node. This allows for very efficient
traversal,
* insert, delete, predecessor, successor, prefix, range, and {@link
#select(Object)}
@@ -41,25 +40,25 @@ import org.apache.commons.collections4.T
* is the number of bits in the largest item in the tree. In practice,
* operations actually take O(A(K)) time, where A(K) is the average number of
* bits of all items in the tree.
- *
- * <p>Most importantly, PATRICIA requires very few comparisons to keys while
+ * <p>
+ * Most importantly, PATRICIA requires very few comparisons to keys while
* doing any operation. While performing a lookup, each comparison (at most
* K of them, described above) will perform a single bit comparison against
* the given key, instead of comparing the entire key to another key.
- *
- * <p>The {@link Trie} can return operations in lexicographical order using the
+ * <p>
+ * The {@link Trie} can return operations in lexicographical order using the
* {@link #traverse(Cursor)}, 'prefix', 'submap', or 'iterator' methods. The
* {@link Trie} can also scan for items that are 'bitwise' (using an XOR
* metric) by the 'select' method. Bitwise closeness is determined by the
* {@link KeyAnalyzer} returning true or false for a bit being set or not in
* a given key.
- *
- * <p>This PATRICIA {@link Trie} supports both variable length & fixed length
+ * <p>
+ * This PATRICIA {@link Trie} supports both variable length & fixed length
* keys. Some methods, such as {@link #getPrefixedBy(Object)} are suited only
* to variable length keys, whereas {@link #getPrefixedByBits(Object, int)} is
* suited to fixed-size keys.
- *
- * <p>Any methods here that take an {@link Object} argument may throw a
+ * <p>
+ * Any methods here that take an {@link Object} argument may throw a
* {@link ClassCastException} if the method is expecting an instance of K
* and it isn't K.
*
Modified:
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/PatriciaTrieBase.java
URL:
http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/PatriciaTrieBase.java?rev=1491621&r1=1491620&r2=1491621&view=diff
==============================================================================
---
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/PatriciaTrieBase.java
(original)
+++
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/PatriciaTrieBase.java
Mon Jun 10 22:05:38 2013
@@ -34,7 +34,7 @@ import org.apache.commons.collections4.T
* @since 4.0
* @version $Id$
*/
-abstract class PatriciaTrieBase<K, V> extends AbstractTrie<K, V> {
+abstract class PatriciaTrieBase<K, V> extends AbstractBitwiseTrie<K, V> {
private static final long serialVersionUID = 5155253417231339498L;
Modified:
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/SynchronizedTrie.java
URL:
http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/SynchronizedTrie.java?rev=1491621&r1=1491620&r2=1491621&view=diff
==============================================================================
---
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/SynchronizedTrie.java
(original)
+++
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/SynchronizedTrie.java
Mon Jun 10 22:05:38 2013
@@ -66,22 +66,6 @@ public class SynchronizedTrie<K, V> impl
this.delegate = trie;
}
- public synchronized Entry<K, V> select(final K key, final Cursor<? super
K, ? super V> cursor) {
- return delegate.select(key, cursor);
- }
-
- public synchronized Entry<K, V> select(final K key) {
- return delegate.select(key);
- }
-
- public synchronized K selectKey(final K key) {
- return delegate.selectKey(key);
- }
-
- public synchronized V selectValue(final K key) {
- return delegate.selectValue(key);
- }
-
public synchronized Entry<K, V> traverse(final Cursor<? super K, ? super
V> cursor) {
return delegate.traverse(cursor);
}
Modified:
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/UnmodifiableTrie.java
URL:
http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/UnmodifiableTrie.java?rev=1491621&r1=1491620&r2=1491621&view=diff
==============================================================================
---
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/UnmodifiableTrie.java
(original)
+++
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/UnmodifiableTrie.java
Mon Jun 10 22:05:38 2013
@@ -66,38 +66,6 @@ public class UnmodifiableTrie<K, V> impl
this.delegate = trie;
}
- public Entry<K, V> select(final K key, final Cursor<? super K, ? super V>
cursor) {
- final Cursor<K, V> c = new Cursor<K, V>() {
- public Decision select(final Map.Entry<? extends K, ? extends V>
entry) {
- final Decision decision = cursor.select(entry);
- switch (decision) {
- case REMOVE:
- case REMOVE_AND_EXIT:
- throw new UnsupportedOperationException();
- default:
- // other decisions are fine
- break;
- }
-
- return decision;
- }
- };
-
- return delegate.select(key, c);
- }
-
- public Entry<K, V> select(final K key) {
- return delegate.select(key);
- }
-
- public K selectKey(final K key) {
- return delegate.selectKey(key);
- }
-
- public V selectValue(final K key) {
- return delegate.selectValue(key);
- }
-
public Entry<K, V> traverse(final Cursor<? super K, ? super V> cursor) {
final Cursor<K, V> c = new Cursor<K, V>() {
public Decision select(final Map.Entry<? extends K, ? extends V>
entry) {
@@ -175,8 +143,7 @@ public class UnmodifiableTrie<K, V> impl
}
public SortedMap<K, V> subMap(final K fromKey, final K toKey) {
- return Collections.unmodifiableSortedMap(
- delegate.subMap(fromKey, toKey));
+ return Collections.unmodifiableSortedMap(delegate.subMap(fromKey,
toKey));
}
public SortedMap<K, V> tailMap(final K fromKey) {
@@ -184,23 +151,19 @@ public class UnmodifiableTrie<K, V> impl
}
public SortedMap<K, V> getPrefixedBy(final K key, final int offset, final
int length) {
- return Collections.unmodifiableSortedMap(
- delegate.getPrefixedBy(key, offset, length));
+ return Collections.unmodifiableSortedMap(delegate.getPrefixedBy(key,
offset, length));
}
public SortedMap<K, V> getPrefixedBy(final K key, final int length) {
- return Collections.unmodifiableSortedMap(
- delegate.getPrefixedBy(key, length));
+ return Collections.unmodifiableSortedMap(delegate.getPrefixedBy(key,
length));
}
public SortedMap<K, V> getPrefixedBy(final K key) {
- return Collections.unmodifiableSortedMap(
- delegate.getPrefixedBy(key));
+ return Collections.unmodifiableSortedMap(delegate.getPrefixedBy(key));
}
public SortedMap<K, V> getPrefixedByBits(final K key, final int
lengthInBits) {
- return Collections.unmodifiableSortedMap(
- delegate.getPrefixedByBits(key, lengthInBits));
+ return
Collections.unmodifiableSortedMap(delegate.getPrefixedByBits(key,
lengthInBits));
}
public SortedMap<K, V> getPrefixedByBits(final K key, final int
offsetInBits, final int lengthInBits) {
