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 2013/04/30 21:42:04 UTC
svn commit: r1477794 [2/2] -
/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/
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=1477794&r1=1477793&r2=1477794&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 Tue Apr 30 19:42:03 2013
@@ -30,19 +30,19 @@ import org.apache.commons.collections4.T
/**
* This class implements the base PATRICIA algorithm and everything that
* is related to the {@link Map} interface.
- *
+ *
* @since 4.0
* @version $Id$
*/
abstract class PatriciaTrieBase<K, V> extends AbstractTrie<K, V> {
-
+
private static final long serialVersionUID = 5155253417231339498L;
/**
- * The root node of the {@link Trie}.
+ * The root node of the {@link Trie}.
*/
final TrieEntry<K, V> root = new TrieEntry<K, V>(null, null, -1);
-
+
/**
* Each of these fields are initialized to contain an instance of the
* appropriate view the first time this view is requested. The views are
@@ -51,39 +51,39 @@ abstract class PatriciaTrieBase<K, V> ex
private transient volatile Set<K> keySet;
private transient volatile Collection<V> values;
private transient volatile Set<Map.Entry<K,V>> entrySet;
-
+
/**
* The current size of the {@link Trie}
*/
private int size = 0;
-
+
/**
* The number of times this {@link Trie} has been modified.
* It's used to detect concurrent modifications and fail-fast
* the {@link Iterator}s.
*/
transient int modCount = 0;
-
+
public PatriciaTrieBase(final KeyAnalyzer<? super K> keyAnalyzer) {
super(keyAnalyzer);
}
-
+
/**
- * Constructs a new {@link org.apache.commons.collections4.Trie Trie} using the given {@link KeyAnalyzer}
- * and initializes the {@link org.apache.commons.collections4.Trie Trie} with the values from the
+ * Constructs a new {@link org.apache.commons.collections4.Trie Trie} using the given {@link KeyAnalyzer}
+ * and initializes the {@link org.apache.commons.collections4.Trie Trie} with the values from the
* provided {@link Map}.
*/
- public PatriciaTrieBase(final KeyAnalyzer<? super K> keyAnalyzer,
+ public PatriciaTrieBase(final KeyAnalyzer<? super K> keyAnalyzer,
final Map<? extends K, ? extends V> m) {
super(keyAnalyzer);
-
+
if (m == null) {
throw new NullPointerException("m");
}
-
+
putAll(m);
}
-
+
/**
* {@inheritDoc}
*/
@@ -92,16 +92,16 @@ abstract class PatriciaTrieBase<K, V> ex
root.key = null;
root.bitIndex = -1;
root.value = null;
-
+
root.parent = null;
root.left = root;
root.right = null;
root.predecessor = root;
-
+
size = 0;
incrementModCount();
}
-
+
/**
* {@inheritDoc}
*/
@@ -109,7 +109,7 @@ abstract class PatriciaTrieBase<K, V> ex
public int size() {
return size;
}
-
+
/**
* A helper method to increment the {@link Trie} size
* and the modification counter.
@@ -118,7 +118,7 @@ abstract class PatriciaTrieBase<K, V> ex
size++;
incrementModCount();
}
-
+
/**
* A helper method to decrement the {@link Trie} size
* and increment the modification counter.
@@ -127,14 +127,14 @@ abstract class PatriciaTrieBase<K, V> ex
size--;
incrementModCount();
}
-
+
/**
* A helper method to increment the modification counter.
*/
private void incrementModCount() {
++modCount;
}
-
+
/**
* {@inheritDoc}
*/
@@ -143,9 +143,9 @@ abstract class PatriciaTrieBase<K, V> ex
if (key == null) {
throw new NullPointerException("Key cannot be null");
}
-
+
final int lengthInBits = lengthInBits(key);
-
+
// The only place to store a key with a length
// of zero bits is the root node
if (lengthInBits == 0) {
@@ -156,7 +156,7 @@ abstract class PatriciaTrieBase<K, V> ex
}
return root.setKeyValue(key, value);
}
-
+
final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
if (compareKeys(key, found.key)) {
if (found.isEmpty()) { // <- must be the root
@@ -166,7 +166,7 @@ abstract class PatriciaTrieBase<K, V> ex
}
return found.setKeyValue(key, value);
}
-
+
final int bitIndex = bitIndex(key, found.key);
if (!AbstractKeyAnalyzer.isOutOfBoundsIndex(bitIndex)) {
if (AbstractKeyAnalyzer.isValidBitIndex(bitIndex)) { // in 99.999...9% the case
@@ -178,7 +178,7 @@ abstract class PatriciaTrieBase<K, V> ex
} else if (AbstractKeyAnalyzer.isNullBitKey(bitIndex)) {
// A bits of the Key are zero. The only place to
// store such a Key is the root Node!
-
+
/* NULL BIT KEY */
if (root.isEmpty()) {
incrementSize();
@@ -186,10 +186,10 @@ abstract class PatriciaTrieBase<K, V> ex
incrementModCount();
}
return root.setKeyValue(key, value);
-
+
} else if (AbstractKeyAnalyzer.isEqualBitKey(bitIndex)) {
// This is a very special and rare case.
-
+
/* REPLACE OLD KEY+VALUE */
if (found != root) {
incrementModCount();
@@ -197,10 +197,10 @@ abstract class PatriciaTrieBase<K, V> ex
}
}
}
-
+
throw new IndexOutOfBoundsException("Failed to put: " + key + " -> " + value + ", " + bitIndex);
}
-
+
/**
* Adds the given {@link TrieEntry} to the {@link Trie}
*/
@@ -208,10 +208,10 @@ abstract class PatriciaTrieBase<K, V> ex
TrieEntry<K, V> current = root.left;
TrieEntry<K, V> path = root;
while(true) {
- if (current.bitIndex >= entry.bitIndex
+ if (current.bitIndex >= entry.bitIndex
|| current.bitIndex <= path.bitIndex) {
entry.predecessor = entry;
-
+
if (!isBitSet(entry.key, entry.bitIndex, lengthInBits)) {
entry.left = entry;
entry.right = current;
@@ -219,28 +219,28 @@ abstract class PatriciaTrieBase<K, V> ex
entry.left = current;
entry.right = entry;
}
-
+
entry.parent = path;
if (current.bitIndex >= entry.bitIndex) {
current.parent = entry;
}
-
+
// if we inserted an uplink, set the predecessor on it
if (current.bitIndex <= path.bitIndex) {
current.predecessor = entry;
}
-
+
if (path == root || !isBitSet(entry.key, path.bitIndex, lengthInBits)) {
path.left = entry;
} else {
path.right = entry;
}
-
+
return entry;
}
-
+
path = current;
-
+
if (!isBitSet(entry.key, current.bitIndex, lengthInBits)) {
current = current.left;
} else {
@@ -248,7 +248,7 @@ abstract class PatriciaTrieBase<K, V> ex
}
}
}
-
+
/**
* {@inheritDoc}
*/
@@ -262,7 +262,7 @@ abstract class PatriciaTrieBase<K, V> ex
* Returns the entry associated with the specified key in the
* PatriciaTrieBase. Returns null if the map contains no mapping
* for this key.
- *
+ *
* This may throw ClassCastException if the object is not of type K.
*/
TrieEntry<K,V> getEntry(final Object k) {
@@ -270,46 +270,46 @@ abstract class PatriciaTrieBase<K, V> ex
if (key == null) {
return null;
}
-
+
final int lengthInBits = lengthInBits(key);
final TrieEntry<K,V> entry = getNearestEntryForKey(key, lengthInBits);
return !entry.isEmpty() && compareKeys(key, entry.key) ? entry : null;
}
-
+
/**
* {@inheritDoc}
*/
public Map.Entry<K, V> select(final K key) {
final int lengthInBits = lengthInBits(key);
- final Reference<Map.Entry<K, V>> reference
+ final Reference<Map.Entry<K, V>> reference
= new Reference<Map.Entry<K,V>>();
if (!selectR(root.left, -1, key, lengthInBits, reference)) {
return reference.get();
}
return null;
}
-
+
/**
* {@inheritDoc}
*/
public Map.Entry<K,V> select(final K key, final Cursor<? super K, ? super V> cursor) {
final int lengthInBits = lengthInBits(key);
- final Reference<Map.Entry<K, V>> reference
+ final Reference<Map.Entry<K, V>> reference
= new Reference<Map.Entry<K,V>>();
selectR(root.left, -1, key, lengthInBits, cursor, reference);
return reference.get();
}
/**
- * This is equivalent to the other {@link #selectR(TrieEntry, int,
- * Object, int, Cursor, Reference)} method but without its overhead
- * because we're selecting only one best matching Entry from the
+ * This is equivalent to the other {@link #selectR(TrieEntry, int,
+ * Object, int, Cursor, Reference)} method but without its overhead
+ * because we're selecting only one best matching Entry from the
* {@link Trie}.
*/
- private boolean selectR(final TrieEntry<K, V> h, final int bitIndex,
- final K key, final int lengthInBits,
+ private boolean selectR(final TrieEntry<K, V> h, final int bitIndex,
+ final K key, final int lengthInBits,
final Reference<Map.Entry<K, V>> reference) {
-
+
if (h.bitIndex <= bitIndex) {
// If we hit the root Node and it is empty
// we have to look for an alternative best
@@ -332,12 +332,12 @@ abstract class PatriciaTrieBase<K, V> ex
}
return false;
}
-
+
/**
- *
+ *
*/
- private boolean selectR(final TrieEntry<K,V> h, final int bitIndex,
- final K key,
+ private boolean selectR(final TrieEntry<K,V> h, final int bitIndex,
+ final K key,
final int lengthInBits,
final Cursor<? super K, ? super V> cursor,
final Reference<Map.Entry<K, V>> reference) {
@@ -375,7 +375,7 @@ abstract class PatriciaTrieBase<K, V> ex
return selectR(h.left, h.bitIndex, key, lengthInBits, cursor, reference);
}
}
-
+
return false;
}
@@ -386,10 +386,10 @@ abstract class PatriciaTrieBase<K, V> ex
TrieEntry<K, V> entry = nextEntry(null);
while (entry != null) {
final TrieEntry<K, V> current = entry;
-
+
final Decision decision = cursor.select(current);
entry = nextEntry(current);
-
+
switch(decision) {
case EXIT:
return current;
@@ -406,10 +406,10 @@ abstract class PatriciaTrieBase<K, V> ex
break;
}
}
-
+
return null;
}
-
+
/**
* {@inheritDoc}
*/
@@ -418,13 +418,13 @@ abstract class PatriciaTrieBase<K, V> ex
if (k == null) {
return false;
}
-
+
final K key = castKey(k);
final int lengthInBits = lengthInBits(key);
final TrieEntry<K, V> entry = getNearestEntryForKey(key, lengthInBits);
return !entry.isEmpty() && compareKeys(key, entry.key);
}
-
+
/**
* {@inheritDoc}
*/
@@ -435,7 +435,7 @@ abstract class PatriciaTrieBase<K, V> ex
}
return entrySet;
}
-
+
/**
* {@inheritDoc}
*/
@@ -446,7 +446,7 @@ abstract class PatriciaTrieBase<K, V> ex
}
return keySet;
}
-
+
/**
* {@inheritDoc}
*/
@@ -457,20 +457,20 @@ abstract class PatriciaTrieBase<K, V> ex
}
return values;
}
-
+
/**
* {@inheritDoc}
- *
- * @throws ClassCastException if provided key is of an incompatible type
+ *
+ * @throws ClassCastException if provided key is of an incompatible type
*/
@Override
public V remove(final Object k) {
if (k == null) {
return null;
}
-
+
final K key = castKey(k);
- final int lengthInBits = lengthInBits(key);
+ final int lengthInBits = lengthInBits(key);
TrieEntry<K, V> current = root.left;
TrieEntry<K, V> path = root;
while (true) {
@@ -481,9 +481,9 @@ abstract class PatriciaTrieBase<K, V> ex
return null;
}
}
-
+
path = current;
-
+
if (!isBitSet(key, current.bitIndex, lengthInBits)) {
current = current.left;
} else {
@@ -491,12 +491,12 @@ abstract class PatriciaTrieBase<K, V> ex
}
}
}
-
+
/**
* Returns the nearest entry for a given key. This is useful
* for finding knowing if a given key exists (and finding the value
* for it), or for inserting the key.
- *
+ *
* The actual get implementation. This is very similar to
* selectR but with the exception that it might return the
* root Entry even if it's empty.
@@ -508,7 +508,7 @@ abstract class PatriciaTrieBase<K, V> ex
if (current.bitIndex <= path.bitIndex) {
return current;
}
-
+
path = current;
if (!isBitSet(key, current.bitIndex, lengthInBits)) {
current = current.left;
@@ -517,12 +517,12 @@ abstract class PatriciaTrieBase<K, V> ex
}
}
}
-
+
/**
* Removes a single entry from the {@link Trie}.
- *
+ *
* If we found a Key (Entry h) then figure out if it's
- * an internal (hard to remove) or external Entry (easy
+ * an internal (hard to remove) or external Entry (easy
* to remove)
*/
V removeEntry(final TrieEntry<K, V> h) {
@@ -533,14 +533,14 @@ abstract class PatriciaTrieBase<K, V> ex
removeExternalEntry(h);
}
}
-
+
decrementSize();
return h.setKeyValue(null, null);
}
-
+
/**
* Removes an external entry from the {@link Trie}.
- *
+ *
* If it's an external Entry then just remove it.
* This is very easy and straight forward.
*/
@@ -549,29 +549,29 @@ abstract class PatriciaTrieBase<K, V> ex
throw new IllegalArgumentException("Cannot delete root Entry!");
} else if (!h.isExternalNode()) {
throw new IllegalArgumentException(h + " is not an external Entry!");
- }
-
+ }
+
final TrieEntry<K, V> parent = h.parent;
final TrieEntry<K, V> child = h.left == h ? h.right : h.left;
-
+
if (parent.left == h) {
parent.left = child;
} else {
parent.right = child;
}
-
+
// either the parent is changing, or the predecessor is changing.
if (child.bitIndex > parent.bitIndex) {
child.parent = parent;
} else {
child.predecessor = parent;
}
-
+
}
-
+
/**
* Removes an internal entry from the {@link Trie}.
- *
+ *
* If it's an internal Entry then "good luck" with understanding
* this code. The Idea is essentially that Entry p takes Entry h's
* place in the trie which requires some re-wiring.
@@ -581,18 +581,18 @@ abstract class PatriciaTrieBase<K, V> ex
throw new IllegalArgumentException("Cannot delete root Entry!");
} else if (!h.isInternalNode()) {
throw new IllegalArgumentException(h + " is not an internal Entry!");
- }
-
+ }
+
final TrieEntry<K, V> p = h.predecessor;
-
+
// Set P's bitIndex
p.bitIndex = h.bitIndex;
-
+
// Fix P's parent, predecessor and child Nodes
{
final TrieEntry<K, V> parent = p.parent;
final TrieEntry<K, V> child = p.left == h ? p.right : p.left;
-
+
// if it was looping to itself previously,
// it will now be pointed from it's parent
// (if we aren't removing it's parent --
@@ -602,30 +602,30 @@ abstract class PatriciaTrieBase<K, V> ex
if (p.predecessor == p && p.parent != h) {
p.predecessor = p.parent;
}
-
+
if (parent.left == p) {
parent.left = child;
} else {
parent.right = child;
}
-
+
if (child.bitIndex > parent.bitIndex) {
child.parent = parent;
}
}
-
+
// Fix H's parent and child Nodes
- {
- // If H is a parent of its left and right child
+ {
+ // If H is a parent of its left and right child
// then change them to P
if (h.left.parent == h) {
h.left.parent = p;
}
-
+
if (h.right.parent == h) {
h.right.parent = p;
}
-
+
// Change H's parent
if (h.parent.left == h) {
h.parent.left = p;
@@ -633,24 +633,24 @@ abstract class PatriciaTrieBase<K, V> ex
h.parent.right = p;
}
}
-
+
// Copy the remaining fields from H to P
//p.bitIndex = h.bitIndex;
p.parent = h.parent;
p.left = h.left;
p.right = h.right;
-
+
// Make sure that if h was pointing to any uplinks,
// p now points to them.
if (isValidUplink(p.left, p)) {
p.left.predecessor = p;
}
-
+
if (isValidUplink(p.right, p)) {
p.right.predecessor = p;
- }
+ }
}
-
+
/**
* Returns the entry lexicographically after the given entry.
* If the given entry is null, returns the first node.
@@ -662,43 +662,43 @@ abstract class PatriciaTrieBase<K, V> ex
return nextEntryImpl(node.predecessor, node, null);
}
}
-
+
/**
* Scans for the next node, starting at the specified point, and using 'previous'
* as a hint that the last node we returned was 'previous' (so we know not to return
* it again). If 'tree' is non-null, this will limit the search to the given tree.
- *
+ *
* The basic premise is that each iteration can follow the following steps:
- *
+ *
* 1) Scan all the way to the left.
* a) If we already started from this node last time, proceed to Step 2.
* b) If a valid uplink is found, use it.
* c) If the result is an empty node (root not set), break the scan.
* d) If we already returned the left node, break the scan.
- *
+ *
* 2) Check the right.
* a) If we already returned the right node, proceed to Step 3.
* b) If it is a valid uplink, use it.
* c) Do Step 1 from the right node.
- *
+ *
* 3) Back up through the parents until we encounter find a parent
* that we're not the right child of.
- *
+ *
* 4) If there's no right child of that parent, the iteration is finished.
* Otherwise continue to Step 5.
- *
+ *
* 5) Check to see if the right child is a valid uplink.
* a) If we already returned that child, proceed to Step 6.
* Otherwise, use it.
- *
+ *
* 6) If the right child of the parent is the parent itself, we've
* already found & returned the end of the Trie, so exit.
- *
+ *
* 7) Do Step 1 on the parent's right child.
*/
- TrieEntry<K, V> nextEntryImpl(final TrieEntry<K, V> start,
+ TrieEntry<K, V> nextEntryImpl(final TrieEntry<K, V> start,
final TrieEntry<K, V> previous, final TrieEntry<K, V> tree) {
-
+
TrieEntry<K, V> current = start;
// Only look at the left if this was a recursive or
@@ -711,20 +711,20 @@ abstract class PatriciaTrieBase<K, V> ex
if (previous == current.left) {
break;
}
-
+
if (isValidUplink(current.left, current)) {
return current.left;
}
-
+
current = current.left;
}
}
-
+
// If there's no data at all, exit.
if (current.isEmpty()) {
return null;
}
-
+
// If we've already returned the left,
// and the immediate right is null,
// there's only one entry in the Trie
@@ -737,18 +737,18 @@ abstract class PatriciaTrieBase<K, V> ex
if (current.right == null) {
return null;
}
-
+
// If nothing valid on the left, try the right.
if (previous != current.right) {
// See if it immediately is valid.
if (isValidUplink(current.right, current)) {
return current.right;
}
-
+
// Must search on the right's side if it wasn't initially valid.
return nextEntryImpl(current.right, previous, tree);
}
-
+
// Neither left nor right are valid, find the first parent
// whose child did not come from the right & traverse it.
while (current == current.parent.right) {
@@ -756,7 +756,7 @@ abstract class PatriciaTrieBase<K, V> ex
if (current == tree) {
return null;
}
-
+
current = current.parent;
}
@@ -764,30 +764,30 @@ abstract class PatriciaTrieBase<K, V> ex
if (current == tree) {
return null;
}
-
+
// If there's no right, the parent must be root, so we're done.
if (current.parent.right == null) {
return null;
}
-
+
// If the parent's right points to itself, we've found one.
- if (previous != current.parent.right
+ if (previous != current.parent.right
&& isValidUplink(current.parent.right, current.parent)) {
return current.parent.right;
}
-
+
// If the parent's right is itself, there can't be any more nodes.
if (current.parent.right == current.parent) {
return null;
}
-
+
// We need to traverse down the parent's right's path.
return nextEntryImpl(current.parent.right, previous, tree);
}
-
+
/**
* Returns the first entry the {@link Trie} is storing.
- *
+ *
* This is implemented by going always to the left until
* we encounter a valid uplink. That uplink is the first key.
*/
@@ -796,12 +796,12 @@ abstract class PatriciaTrieBase<K, V> ex
if (isEmpty()) {
return null;
}
-
+
return followLeft(root);
}
-
- /**
- * Goes left through the tree until it finds a valid node.
+
+ /**
+ * Goes left through the tree until it finds a valid node.
*/
TrieEntry<K, V> followLeft(TrieEntry<K, V> node) {
while(true) {
@@ -810,75 +810,75 @@ abstract class PatriciaTrieBase<K, V> ex
if (child.isEmpty()) {
child = node.right;
}
-
+
if (child.bitIndex <= node.bitIndex) {
return child;
}
-
+
node = child;
}
}
-
- /**
- * Returns true if 'next' is a valid uplink coming from 'from'.
+
+ /**
+ * Returns true if 'next' is a valid uplink coming from 'from'.
*/
- static boolean isValidUplink(final TrieEntry<?, ?> next, final TrieEntry<?, ?> from) {
+ static boolean isValidUplink(final TrieEntry<?, ?> next, final TrieEntry<?, ?> from) {
return next != null && next.bitIndex <= from.bitIndex && !next.isEmpty();
}
-
+
/**
- * A {@link Reference} allows us to return something through a Method's
- * argument list. An alternative would be to an Array with a length of
+ * A {@link Reference} allows us to return something through a Method's
+ * argument list. An alternative would be to an Array with a length of
* one (1) but that leads to compiler warnings. Computationally and memory
- * wise there's no difference (except for the need to load the
+ * wise there's no difference (except for the need to load the
* {@link Reference} Class but that happens only once).
*/
private static class Reference<E> {
-
+
private E item;
-
+
public void set(final E item) {
this.item = item;
}
-
+
public E get() {
return item;
}
}
-
+
/**
* A {@link Trie} is a set of {@link TrieEntry} nodes
*/
static class TrieEntry<K,V> extends BasicEntry<K, V> {
-
+
private static final long serialVersionUID = 4596023148184140013L;
-
+
/** The index this entry is comparing. */
protected int bitIndex;
-
+
/** The parent of this entry. */
protected TrieEntry<K,V> parent;
-
+
/** The left child of this entry. */
protected TrieEntry<K,V> left;
-
+
/** The right child of this entry. */
protected TrieEntry<K,V> right;
-
- /** The entry who uplinks to this entry. */
+
+ /** The entry who uplinks to this entry. */
protected TrieEntry<K,V> predecessor;
-
+
public TrieEntry(final K key, final V value, final int bitIndex) {
super(key, value);
-
+
this.bitIndex = bitIndex;
-
+
this.parent = null;
this.left = this;
this.right = null;
this.predecessor = this;
}
-
+
/**
* Whether or not the entry is storing a key.
* Only the root can potentially be empty, all other
@@ -887,16 +887,16 @@ abstract class PatriciaTrieBase<K, V> ex
public boolean isEmpty() {
return key == null;
}
-
- /**
- * Neither the left nor right child is a loopback
+
+ /**
+ * Neither the left nor right child is a loopback
*/
public boolean isInternalNode() {
return left != this && right != this;
}
-
- /**
- * Either the left or right child is a loopback
+
+ /**
+ * Either the left or right child is a loopback
*/
public boolean isExternalNode() {
return !isInternalNode();
@@ -908,17 +908,17 @@ abstract class PatriciaTrieBase<K, V> ex
@Override
public String toString() {
final StringBuilder buffer = new StringBuilder();
-
+
if (bitIndex == -1) {
buffer.append("RootEntry(");
} else {
buffer.append("Entry(");
}
-
+
buffer.append("key=").append(getKey()).append(" [").append(bitIndex).append("], ");
buffer.append("value=").append(getValue()).append(", ");
//buffer.append("bitIndex=").append(bitIndex).append(", ");
-
+
if (parent != null) {
if (parent.bitIndex == -1) {
buffer.append("parent=").append("ROOT");
@@ -929,7 +929,7 @@ abstract class PatriciaTrieBase<K, V> ex
buffer.append("parent=").append("null");
}
buffer.append(", ");
-
+
if (left != null) {
if (left.bitIndex == -1) {
buffer.append("left=").append("ROOT");
@@ -940,7 +940,7 @@ abstract class PatriciaTrieBase<K, V> ex
buffer.append("left=").append("null");
}
buffer.append(", ");
-
+
if (right != null) {
if (right.bitIndex == -1) {
buffer.append("right=").append("ROOT");
@@ -951,7 +951,7 @@ abstract class PatriciaTrieBase<K, V> ex
buffer.append("right=").append("null");
}
buffer.append(", ");
-
+
if (predecessor != null) {
if(predecessor.bitIndex == -1) {
buffer.append("predecessor=").append("ROOT");
@@ -960,19 +960,19 @@ abstract class PatriciaTrieBase<K, V> ex
append(predecessor.bitIndex).append("]");
}
}
-
+
buffer.append(")");
return buffer.toString();
}
}
-
+
/**
- * This is a entry set view of the {@link Trie} as returned
+ * This is a entry set view of the {@link Trie} as returned
* by {@link Map#entrySet()}
*/
private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
-
+
/**
* {@inheritDoc}
*/
@@ -980,7 +980,7 @@ abstract class PatriciaTrieBase<K, V> ex
public Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
-
+
/**
* {@inheritDoc}
*/
@@ -989,11 +989,11 @@ abstract class PatriciaTrieBase<K, V> ex
if (!(o instanceof Map.Entry)) {
return false;
}
-
+
final TrieEntry<K,V> candidate = getEntry(((Map.Entry<?, ?>)o).getKey());
return candidate != null && candidate.equals(o);
}
-
+
/**
* {@inheritDoc}
*/
@@ -1003,7 +1003,7 @@ abstract class PatriciaTrieBase<K, V> ex
PatriciaTrieBase.this.remove(o);
return size != size();
}
-
+
/**
* {@inheritDoc}
*/
@@ -1011,7 +1011,7 @@ abstract class PatriciaTrieBase<K, V> ex
public int size() {
return PatriciaTrieBase.this.size();
}
-
+
/**
* {@inheritDoc}
*/
@@ -1019,7 +1019,7 @@ abstract class PatriciaTrieBase<K, V> ex
public void clear() {
PatriciaTrieBase.this.clear();
}
-
+
/**
* An {@link Iterator} that returns {@link Entry} Objects
*/
@@ -1029,13 +1029,13 @@ abstract class PatriciaTrieBase<K, V> ex
}
}
}
-
+
/**
- * This is a key set view of the {@link Trie} as returned
+ * This is a key set view of the {@link Trie} as returned
* by {@link Map#keySet()}
*/
private class KeySet extends AbstractSet<K> {
-
+
/**
* {@inheritDoc}
*/
@@ -1043,7 +1043,7 @@ abstract class PatriciaTrieBase<K, V> ex
public Iterator<K> iterator() {
return new KeyIterator();
}
-
+
/**
* {@inheritDoc}
*/
@@ -1051,7 +1051,7 @@ abstract class PatriciaTrieBase<K, V> ex
public int size() {
return PatriciaTrieBase.this.size();
}
-
+
/**
* {@inheritDoc}
*/
@@ -1059,7 +1059,7 @@ abstract class PatriciaTrieBase<K, V> ex
public boolean contains(final Object o) {
return containsKey(o);
}
-
+
/**
* {@inheritDoc}
*/
@@ -1069,7 +1069,7 @@ abstract class PatriciaTrieBase<K, V> ex
PatriciaTrieBase.this.remove(o);
return size != size();
}
-
+
/**
* {@inheritDoc}
*/
@@ -1077,7 +1077,7 @@ abstract class PatriciaTrieBase<K, V> ex
public void clear() {
PatriciaTrieBase.this.clear();
}
-
+
/**
* An {@link Iterator} that returns Key Objects
*/
@@ -1087,13 +1087,13 @@ abstract class PatriciaTrieBase<K, V> ex
}
}
}
-
+
/**
- * This is a value view of the {@link Trie} as returned
+ * This is a value view of the {@link Trie} as returned
* by {@link Map#values()}
*/
private class Values extends AbstractCollection<V> {
-
+
/**
* {@inheritDoc}
*/
@@ -1101,7 +1101,7 @@ abstract class PatriciaTrieBase<K, V> ex
public Iterator<V> iterator() {
return new ValueIterator();
}
-
+
/**
* {@inheritDoc}
*/
@@ -1109,7 +1109,7 @@ abstract class PatriciaTrieBase<K, V> ex
public int size() {
return PatriciaTrieBase.this.size();
}
-
+
/**
* {@inheritDoc}
*/
@@ -1117,7 +1117,7 @@ abstract class PatriciaTrieBase<K, V> ex
public boolean contains(final Object o) {
return containsValue(o);
}
-
+
/**
* {@inheritDoc}
*/
@@ -1125,7 +1125,7 @@ abstract class PatriciaTrieBase<K, V> ex
public void clear() {
PatriciaTrieBase.this.clear();
}
-
+
/**
* {@inheritDoc}
*/
@@ -1140,7 +1140,7 @@ abstract class PatriciaTrieBase<K, V> ex
}
return false;
}
-
+
/**
* An {@link Iterator} that returns Value Objects
*/
@@ -1150,66 +1150,66 @@ abstract class PatriciaTrieBase<K, V> ex
}
}
}
-
- /**
- * An iterator for the entries.
+
+ /**
+ * An iterator for the entries.
*/
abstract class TrieIterator<E> implements Iterator<E> {
-
+
/**
* For fast-fail
*/
protected int expectedModCount = PatriciaTrieBase.this.modCount;
-
+
protected TrieEntry<K, V> next; // the next node to return
protected TrieEntry<K, V> current; // the current entry we're on
-
+
/**
* Starts iteration from the root
*/
protected TrieIterator() {
next = PatriciaTrieBase.this.nextEntry(null);
}
-
+
/**
* Starts iteration at the given entry
*/
protected TrieIterator(final TrieEntry<K, V> firstEntry) {
next = firstEntry;
}
-
+
/**
* Returns the next {@link TrieEntry}
*/
- protected TrieEntry<K,V> nextEntry() {
+ protected TrieEntry<K,V> nextEntry() {
if (expectedModCount != PatriciaTrieBase.this.modCount) {
throw new ConcurrentModificationException();
}
-
+
final TrieEntry<K,V> e = next;
if (e == null) {
throw new NoSuchElementException();
}
-
+
next = findNext(e);
current = e;
return e;
}
-
+
/**
* @see PatriciaTrie#nextEntry(TrieEntry)
*/
protected TrieEntry<K, V> findNext(final TrieEntry<K, V> prior) {
return PatriciaTrieBase.this.nextEntry(prior);
}
-
+
/**
* {@inheritDoc}
*/
public boolean hasNext() {
return next != null;
}
-
+
/**
* {@inheritDoc}
*/
@@ -1217,15 +1217,15 @@ abstract class PatriciaTrieBase<K, V> ex
if (current == null) {
throw new IllegalStateException();
}
-
+
if (expectedModCount != PatriciaTrieBase.this.modCount) {
throw new ConcurrentModificationException();
}
-
+
final TrieEntry<K, V> node = current;
current = null;
PatriciaTrieBase.this.removeEntry(node);
-
+
expectedModCount = PatriciaTrieBase.this.modCount;
}
}
Modified: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/ShortKeyAnalyzer.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/ShortKeyAnalyzer.java?rev=1477794&r1=1477793&r2=1477794&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/ShortKeyAnalyzer.java (original)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/ShortKeyAnalyzer.java Tue Apr 30 19:42:03 2013
@@ -18,29 +18,29 @@ package org.apache.commons.collections4.
/**
* A {@link KeyAnalyzer} for {@link Short}s.
- *
+ *
* @since 4.0
* @version $Id$
*/
public class ShortKeyAnalyzer implements KeyAnalyzer<Short> {
-
+
private static final long serialVersionUID = -8631376733513512017L;
/**
* A singleton instance of {@link ShortKeyAnalyzer}
*/
public static final ShortKeyAnalyzer INSTANCE = new ShortKeyAnalyzer();
-
+
/**
* The length of an {@link Short} in bits
*/
public static final int LENGTH = Short.SIZE;
-
+
/**
* A bit mask where the first bit is 1 and the others are zero
*/
private static final int MSB = 0x8000;
-
+
/**
* Returns a bit mask where the given bit is set
*/
@@ -54,7 +54,7 @@ public class ShortKeyAnalyzer implements
public int bitsPerElement() {
return 1;
}
-
+
/**
* {@inheritDoc}
*/
@@ -72,21 +72,21 @@ public class ShortKeyAnalyzer implements
/**
* {@inheritDoc}
*/
- public int bitIndex(final Short key, final int offsetInBits, final int lengthInBits,
+ public int bitIndex(final Short key, final int offsetInBits, final int lengthInBits,
final Short other, final int otherOffsetInBits, final int otherLengthInBits) {
-
+
if (offsetInBits != 0 || otherOffsetInBits != 0) {
- throw new IllegalArgumentException("offsetInBits=" + offsetInBits
+ throw new IllegalArgumentException("offsetInBits=" + offsetInBits
+ ", otherOffsetInBits=" + otherOffsetInBits);
}
-
+
final int keyValue = key.shortValue();
if (keyValue == 0) {
return NULL_BIT_KEY;
}
final int otherValue = other != null ? other.shortValue() : 0;
-
+
if (keyValue != otherValue) {
final int xorValue = keyValue ^ otherValue;
for (int i = 0; i < LENGTH; i++) {
@@ -95,7 +95,7 @@ public class ShortKeyAnalyzer implements
}
}
}
-
+
return KeyAnalyzer.EQUAL_BIT_KEY;
}
@@ -105,21 +105,21 @@ public class ShortKeyAnalyzer implements
public int compare(final Short o1, final Short o2) {
return o1.compareTo(o2);
}
-
+
/**
* {@inheritDoc}
*/
- public boolean isPrefix(final Short prefix, final int offsetInBits,
+ public boolean isPrefix(final Short prefix, final int offsetInBits,
final int lengthInBits, final Short key) {
-
+
final int value1 = prefix.shortValue() << offsetInBits;
final int value2 = key.shortValue();
-
+
int mask = 0;
for (int i = 0; i < lengthInBits; i++) {
mask |= 0x1 << i;
}
-
+
return (value1 & mask) == (value2 & mask);
}
}
Modified: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/StringKeyAnalyzer.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/StringKeyAnalyzer.java?rev=1477794&r1=1477793&r2=1477794&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/StringKeyAnalyzer.java (original)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/StringKeyAnalyzer.java Tue Apr 30 19:42:03 2013
@@ -18,72 +18,72 @@ package org.apache.commons.collections4.
/**
* An {@link KeyAnalyzer} for {@link String}s.
- *
+ *
* @since 4.0
* @version $Id$
*/
public class StringKeyAnalyzer extends AbstractKeyAnalyzer<String> {
-
+
private static final long serialVersionUID = -7032449491269434877L;
-
+
/**
* A singleton instance of {@link StringKeyAnalyzer}
*/
public static final StringKeyAnalyzer INSTANCE = new StringKeyAnalyzer();
-
+
/**
* The number of bits per {@link Character}
*/
public static final int LENGTH = Character.SIZE;
-
+
/**
* A bit mask where the first bit is 1 and the others are zero
*/
private static final int MSB = 0x8000;
-
+
/**
* Returns a bit mask where the given bit is set
*/
private static int mask(final int bit) {
return MSB >>> bit;
}
-
+
/**
* {@inheritDoc}
*/
public int bitsPerElement() {
return LENGTH;
}
-
+
/**
* {@inheritDoc}
*/
public int lengthInBits(final String key) {
return key != null ? key.length() * LENGTH : 0;
}
-
+
/**
* {@inheritDoc}
*/
public int bitIndex(final String key, final int offsetInBits, final int lengthInBits,
final String other, final int otherOffsetInBits, final int otherLengthInBits) {
boolean allNull = true;
-
- if (offsetInBits % LENGTH != 0 || otherOffsetInBits % LENGTH != 0
+
+ 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");
}
-
-
+
+
final int beginIndex1 = offsetInBits / LENGTH;
final int beginIndex2 = otherOffsetInBits / LENGTH;
-
+
final int endIndex1 = beginIndex1 + lengthInBits / LENGTH;
final int endIndex2 = beginIndex2 + otherLengthInBits / LENGTH;
-
+
final 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.
@@ -91,38 +91,38 @@ public class StringKeyAnalyzer extends A
for(int i = 0; i < length; i++) {
final int index1 = beginIndex1 + i;
final int index2 = beginIndex2 + i;
-
+
if (index1 >= endIndex1) {
k = 0;
} else {
k = key.charAt(index1);
}
-
+
if (other == null || index2 >= endIndex2) {
f = 0;
} else {
f = other.charAt(index2);
}
-
+
if (k != f) {
final 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}
*/
@@ -130,23 +130,23 @@ public class StringKeyAnalyzer extends A
if (key == null || bitIndex >= lengthInBits) {
return false;
}
-
+
final int index = bitIndex / LENGTH;
final int bit = bitIndex % LENGTH;
-
+
return (key.charAt(index) & mask(bit)) != 0;
}
-
+
/**
* {@inheritDoc}
*/
- public boolean isPrefix(final String prefix, final int offsetInBits,
+ public boolean isPrefix(final String prefix, final int offsetInBits,
final int lengthInBits, final String key) {
if (offsetInBits % LENGTH != 0 || lengthInBits % LENGTH != 0) {
throw new IllegalArgumentException(
"Cannot determine prefix outside of Character boundaries");
}
-
+
final String s1 = prefix.substring(offsetInBits / LENGTH, lengthInBits / LENGTH);
return key.startsWith(s1);
}
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=1477794&r1=1477793&r2=1477794&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 Tue Apr 30 19:42:03 2013
@@ -29,19 +29,19 @@ import org.apache.commons.collections4.c
/**
* A synchronized {@link Trie}.
- *
+ *
* @since 4.0
* @version $Id$
*/
public class SynchronizedTrie<K, V> implements Trie<K, V>, Serializable {
-
+
private static final long serialVersionUID = 3121878833178676939L;
-
+
private final Trie<K, V> delegate;
-
+
/**
* Factory method to create a synchronized trie.
- *
+ *
* @param <K> the key type
* @param <V> the value type
* @param trie the trie to decorate, must not be null
@@ -55,7 +55,7 @@ public class SynchronizedTrie<K, V> impl
//-----------------------------------------------------------------------
/**
* Constructor that wraps (not copies).
- *
+ *
* @param trie the trie to decorate, must not be null
* @throws IllegalArgumentException if set is null
*/
@@ -85,7 +85,7 @@ public class SynchronizedTrie<K, V> impl
public synchronized Entry<K, V> traverse(final Cursor<? super K, ? super V> cursor) {
return delegate.traverse(cursor);
}
-
+
public synchronized Set<Entry<K, V>> entrySet() {
return Collections.synchronizedSet(delegate.entrySet());
}
@@ -129,7 +129,7 @@ public class SynchronizedTrie<K, V> impl
public synchronized V remove(final Object key) {
return delegate.remove(key);
}
-
+
public synchronized K lastKey() {
return delegate.lastKey();
}
@@ -141,7 +141,7 @@ public class SynchronizedTrie<K, V> impl
public synchronized SortedMap<K, V> tailMap(final K fromKey) {
return Collections.synchronizedSortedMap(delegate.tailMap(fromKey));
}
-
+
public synchronized Comparator<? super K> comparator() {
return delegate.comparator();
}
@@ -153,7 +153,7 @@ public class SynchronizedTrie<K, V> impl
public synchronized SortedMap<K, V> headMap(final K toKey) {
return Collections.synchronizedSortedMap(delegate.headMap(toKey));
}
-
+
public synchronized SortedMap<K, V> getPrefixedBy(final K key, final int offset, final int length) {
return Collections.synchronizedSortedMap(delegate.getPrefixedBy(key, offset, length));
}
@@ -170,7 +170,7 @@ public class SynchronizedTrie<K, V> impl
return Collections.synchronizedSortedMap(delegate.getPrefixedByBits(key, lengthInBits));
}
- public synchronized SortedMap<K, V> getPrefixedByBits(final K key,
+ public synchronized SortedMap<K, V> getPrefixedByBits(final K key,
final int offsetInBits, final int lengthInBits) {
return Collections.synchronizedSortedMap(delegate.getPrefixedByBits(key, offsetInBits, lengthInBits));
}
@@ -183,12 +183,12 @@ public class SynchronizedTrie<K, V> impl
public synchronized int hashCode() {
return delegate.hashCode();
}
-
+
@Override
public synchronized boolean equals(final Object obj) {
return delegate.equals(obj);
}
-
+
@Override
public synchronized String toString() {
return delegate.toString();
Modified: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/UnmodifiableTrie.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/UnmodifiableTrie.java?rev=1477794&r1=1477793&r2=1477794&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 Tue Apr 30 19:42:03 2013
@@ -29,19 +29,19 @@ import org.apache.commons.collections4.U
/**
* An unmodifiable {@link Trie}.
- *
+ *
* @since 4.0
* @version $Id$
*/
public class UnmodifiableTrie<K, V> implements Trie<K, V>, Serializable, Unmodifiable {
-
+
private static final long serialVersionUID = -7156426030315945159L;
-
+
private final Trie<K, V> delegate;
-
+
/**
* Factory method to create a unmodifiable trie.
- *
+ *
* @param <K> the key type
* @param <V> the value type
* @param trie the trie to decorate, must not be null
@@ -55,7 +55,7 @@ public class UnmodifiableTrie<K, V> impl
//-----------------------------------------------------------------------
/**
* Constructor that wraps (not copies).
- *
+ *
* @param trie the trie to decorate, must not be null
* @throws IllegalArgumentException if trie is null
*/
@@ -65,7 +65,7 @@ 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) {
@@ -78,11 +78,11 @@ public class UnmodifiableTrie<K, V> impl
// other decisions are fine
break;
}
-
+
return decision;
}
};
-
+
return delegate.select(key, c);
}
@@ -110,18 +110,18 @@ public class UnmodifiableTrie<K, V> impl
// other decisions are fine
break;
}
-
+
return decision;
}
};
-
+
return delegate.traverse(c);
}
public Set<Entry<K, V>> entrySet() {
return Collections.unmodifiableSet(delegate.entrySet());
}
-
+
public Set<K> keySet() {
return Collections.unmodifiableSet(delegate.keySet());
}
@@ -182,7 +182,7 @@ public class UnmodifiableTrie<K, V> impl
public SortedMap<K, V> tailMap(final K fromKey) {
return Collections.unmodifiableSortedMap(delegate.tailMap(fromKey));
}
-
+
public SortedMap<K, V> getPrefixedBy(final K key, final int offset, final int length) {
return Collections.unmodifiableSortedMap(
delegate.getPrefixedBy(key, offset, length));
@@ -202,7 +202,7 @@ public class UnmodifiableTrie<K, V> impl
return Collections.unmodifiableSortedMap(
delegate.getPrefixedByBits(key, lengthInBits));
}
-
+
public SortedMap<K, V> getPrefixedByBits(final K key, final int offsetInBits, final int lengthInBits) {
return Collections.unmodifiableSortedMap(delegate.getPrefixedByBits(key, offsetInBits, lengthInBits));
}
@@ -210,21 +210,21 @@ public class UnmodifiableTrie<K, V> impl
public Comparator<? super K> comparator() {
return delegate.comparator();
}
-
+
public int size() {
return delegate.size();
}
-
+
@Override
public int hashCode() {
return delegate.hashCode();
}
-
+
@Override
public boolean equals(final Object obj) {
return delegate.equals(obj);
}
-
+
@Override
public String toString() {
return delegate.toString();