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 [1/2] -
/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/
Author: tn
Date: Tue Apr 30 19:42:03 2013
New Revision: 1477794
URL: http://svn.apache.org/r1477794
Log:
Remove trailing spaces.
Modified:
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractKeyAnalyzer.java
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractTrie.java
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/ByteArrayKeyAnalyzer.java
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/ByteKeyAnalyzer.java
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/CharArrayKeyAnalyzer.java
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/IntegerKeyAnalyzer.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/LongKeyAnalyzer.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/ShortKeyAnalyzer.java
commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/StringKeyAnalyzer.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/AbstractKeyAnalyzer.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractKeyAnalyzer.java?rev=1477794&r1=1477793&r2=1477794&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractKeyAnalyzer.java (original)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/AbstractKeyAnalyzer.java Tue Apr 30 19:42:03 2013
@@ -18,12 +18,12 @@ package org.apache.commons.collections4.
/**
* TODO: add javadoc
- *
+ *
* @since 4.0
* @version $Id$
*/
public abstract class AbstractKeyAnalyzer<K> implements KeyAnalyzer<K> {
-
+
private static final long serialVersionUID = -20497563720380683L;
/**
@@ -36,34 +36,34 @@ public abstract class AbstractKeyAnalyze
} else if (o2 == null) {
return 1;
}
-
+
return ((Comparable<K>)o1).compareTo(o2);
}
-
- /**
+
+ /**
* 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}
*/
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
+ /**
+ * 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) {
Modified: 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/AbstractTrie.java?rev=1477794&r1=1477793&r2=1477794&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/AbstractTrie.java Tue Apr 30 19:42:03 2013
@@ -23,43 +23,43 @@ import java.util.Map;
import org.apache.commons.collections4.Trie;
/**
- * This class provides some basic {@link Trie} functionality and
+ * 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>
+abstract class AbstractTrie<K, V> extends AbstractMap<K, V>
implements Trie<K, V>, Serializable {
-
+
private static final long serialVersionUID = 5826987063535505652L;
// TODO Privatise fields?
/**
- * The {@link KeyAnalyzer} that's being used to build the
+ * 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) {
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}
*/
@@ -70,7 +70,7 @@ abstract class AbstractTrie<K, V> extend
}
return entry.getKey();
}
-
+
/**
* {@inheritDoc}
*/
@@ -81,7 +81,7 @@ abstract class AbstractTrie<K, V> extend
}
return entry.getValue();
}
-
+
@Override
public String toString() {
final StringBuilder buffer = new StringBuilder();
@@ -92,7 +92,7 @@ abstract class AbstractTrie<K, V> extend
buffer.append("}\n");
return buffer.toString();
}
-
+
/**
* A utility method to cast keys. It actually doesn't
* cast anything. It's just fooling the compiler!
@@ -101,33 +101,33 @@ abstract class AbstractTrie<K, V> extend
final K castKey(final Object key) {
return (K)key;
}
-
+
/**
* Returns the length of the given key in bits
- *
+ *
* @see KeyAnalyzer#lengthInBits(Object)
*/
final int lengthInBits(final 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
+ * 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(final K key, final int bitIndex, final int lengthInBits) {
@@ -136,15 +136,15 @@ abstract class AbstractTrie<K, V> extend
}
return keyAnalyzer.isBitSet(key, bitIndex, lengthInBits);
}
-
+
/**
* Utility method for calling {@link KeyAnalyzer#bitIndex(Object, int, int, Object, int, int)}
*/
final int bitIndex(final K key, final K foundKey) {
- return keyAnalyzer.bitIndex(key, 0, lengthInBits(key),
+ return keyAnalyzer.bitIndex(key, 0, lengthInBits(key),
foundKey, 0, lengthInBits(foundKey));
}
-
+
/**
* An utility method for calling {@link KeyAnalyzer#compare(Object, Object)}
*/
@@ -154,43 +154,43 @@ abstract class AbstractTrie<K, V> extend
} else if (other == null) {
return false;
}
-
+
return keyAnalyzer.compare(key, other) == 0;
}
-
+
/**
* Returns true if both values are either null or equal
*/
static boolean compare(final Object a, final 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(final K key) {
this.key = key;
this.hashCode = key != null ? key.hashCode() : 0;
}
-
+
public BasicEntry(final K key, final 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
@@ -199,14 +199,14 @@ abstract class AbstractTrie<K, V> extend
this.key = key;
return setValue(value);
}
-
+
/**
* {@inheritDoc}
*/
public K getKey() {
return key;
}
-
+
/**
* {@inheritDoc}
*/
@@ -222,12 +222,12 @@ abstract class AbstractTrie<K, V> extend
this.value = value;
return previous;
}
-
+
@Override
public int hashCode() {
return hashCode;
}
-
+
@Override
public boolean equals(final Object o) {
if (o == this) {
@@ -235,15 +235,15 @@ abstract class AbstractTrie<K, V> extend
} else if (!(o instanceof Map.Entry)) {
return false;
}
-
+
final Map.Entry<?, ?> other = (Map.Entry<?, ?>)o;
- if (compare(key, other.getKey())
+ if (compare(key, other.getKey())
&& compare(value, other.getValue())) {
return true;
}
return false;
}
-
+
@Override
public String toString() {
return key + "=" + value;
Modified: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/ByteArrayKeyAnalyzer.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/ByteArrayKeyAnalyzer.java?rev=1477794&r1=1477793&r2=1477794&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/ByteArrayKeyAnalyzer.java (original)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/ByteArrayKeyAnalyzer.java Tue Apr 30 19:42:03 2013
@@ -18,49 +18,49 @@ package org.apache.commons.collections4.
/**
* 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
+ 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(final int maxLengthInBits) {
if (maxLengthInBits < 0) {
throw new IllegalArgumentException(
"maxLengthInBits=" + maxLengthInBits);
}
-
+
this.maxLengthInBits = maxLengthInBits;
}
-
+
/**
* Returns a bit mask where the given bit is set
*/
@@ -75,36 +75,36 @@ public class ByteArrayKeyAnalyzer extend
public int getMaxLengthInBits() {
return maxLengthInBits;
}
-
+
/**
* {@inheritDoc}
*/
public int bitsPerElement() {
return LENGTH;
}
-
+
/**
* {@inheritDoc}
*/
public int lengthInBits(final byte[] key) {
return key != null ? key.length * bitsPerElement() : 0;
}
-
+
/**
* {@inheritDoc}
*/
public boolean isBitSet(final byte[] key, final int bitIndex, final int lengthInBits) {
- if (key == null) {
+ if (key == null) {
return false;
}
-
+
final int prefix = maxLengthInBits - lengthInBits;
final int keyBitIndex = bitIndex - prefix;
-
+
if (keyBitIndex >= lengthInBits || keyBitIndex < 0) {
return false;
}
-
+
final int index = keyBitIndex / LENGTH;
final int bit = keyBitIndex % LENGTH;
return (key[index] & mask(bit)) != 0;
@@ -113,66 +113,66 @@ public class ByteArrayKeyAnalyzer extend
/**
* {@inheritDoc}
*/
- public int bitIndex(final byte[] key, final int offsetInBits, final int lengthInBits,
+ public int bitIndex(final byte[] key, final int offsetInBits, final int lengthInBits,
byte[] other, final int otherOffsetInBits, final int otherLengthInBits) {
-
+
if (other == null) {
other = NULL;
}
-
+
boolean allNull = true;
final int length = Math.max(lengthInBits, otherLengthInBits);
final int prefix = maxLengthInBits - length;
-
+
if (prefix < 0) {
return KeyAnalyzer.OUT_OF_BOUNDS_BIT_KEY;
}
-
+
for (int i = 0; i < length; i++) {
final int index = prefix + offsetInBits + i;
final boolean value = isBitSet(key, index, lengthInBits);
-
+
if (value) {
allNull = false;
}
-
+
final int otherIndex = prefix + otherOffsetInBits + i;
final 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(final byte[] prefix, final int offsetInBits,
+ public boolean isPrefix(final byte[] prefix, final int offsetInBits,
final int lengthInBits, final byte[] key) {
-
+
final int keyLength = lengthInBits(key);
if (lengthInBits > keyLength) {
return false;
}
-
+
final int elements = lengthInBits - offsetInBits;
for (int i = 0; i < elements; i++) {
- if (isBitSet(prefix, i+offsetInBits, lengthInBits)
+ if (isBitSet(prefix, i+offsetInBits, lengthInBits)
!= isBitSet(key, i, keyLength)) {
return false;
}
}
-
+
return true;
}
-
+
/**
* {@inheritDoc}
*/
@@ -183,11 +183,11 @@ public class ByteArrayKeyAnalyzer extend
} else if (o2 == null) {
return 1;
}
-
+
if (o1.length != o2.length) {
return o1.length - o2.length;
}
-
+
for (int i = 0; i < o1.length; i++) {
final int diff = (o1[i] & 0xFF) - (o2[i] & 0xFF);
if (diff != 0) {
Modified: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/ByteKeyAnalyzer.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/ByteKeyAnalyzer.java?rev=1477794&r1=1477793&r2=1477794&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/ByteKeyAnalyzer.java (original)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/ByteKeyAnalyzer.java Tue Apr 30 19:42:03 2013
@@ -18,29 +18,29 @@ package org.apache.commons.collections4.
/**
* 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
*/
@@ -54,7 +54,7 @@ public class ByteKeyAnalyzer extends Abs
public int bitsPerElement() {
return 1;
}
-
+
/**
* {@inheritDoc}
*/
@@ -72,21 +72,21 @@ public class ByteKeyAnalyzer extends Abs
/**
* {@inheritDoc}
*/
- public int bitIndex(final Byte key, final int offsetInBits, final int lengthInBits,
+ public int bitIndex(final Byte key, final int offsetInBits, final int lengthInBits,
final Byte 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 byte keyValue = key.byteValue();
if (keyValue == 0) {
return NULL_BIT_KEY;
}
final byte otherValue = other != null ? other.byteValue() : 0;
-
+
if (keyValue != otherValue) {
final int xorValue = keyValue ^ otherValue;
for (int i = 0; i < LENGTH; i++) {
@@ -95,24 +95,24 @@ public class ByteKeyAnalyzer extends Abs
}
}
}
-
+
return KeyAnalyzer.EQUAL_BIT_KEY;
}
-
+
/**
* {@inheritDoc}
*/
- public boolean isPrefix(final Byte prefix, final int offsetInBits,
+ public boolean isPrefix(final Byte prefix, final int offsetInBits,
final int lengthInBits, final Byte key) {
-
+
final int value1 = prefix.byteValue() << offsetInBits;
final int value2 = key.byteValue();
-
+
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/CharArrayKeyAnalyzer.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/CharArrayKeyAnalyzer.java?rev=1477794&r1=1477793&r2=1477794&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/CharArrayKeyAnalyzer.java (original)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/CharArrayKeyAnalyzer.java Tue Apr 30 19:42:03 2013
@@ -18,12 +18,12 @@ package org.apache.commons.collections4.
/**
* An {@link KeyAnalyzer} for {@code char[]}s.
- *
+ *
* @since 4.0
* @version $Id$
*/
public class CharArrayKeyAnalyzer extends AbstractKeyAnalyzer<char[]> {
-
+
private static final long serialVersionUID = -8167897361549463457L;
/**
Modified: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/IntegerKeyAnalyzer.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/IntegerKeyAnalyzer.java?rev=1477794&r1=1477793&r2=1477794&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/IntegerKeyAnalyzer.java (original)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/IntegerKeyAnalyzer.java Tue Apr 30 19:42:03 2013
@@ -18,29 +18,29 @@ package org.apache.commons.collections4.
/**
* 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
*/
@@ -54,7 +54,7 @@ public class IntegerKeyAnalyzer extends
public int bitsPerElement() {
return 1;
}
-
+
/**
* {@inheritDoc}
*/
@@ -72,21 +72,21 @@ public class IntegerKeyAnalyzer extends
/**
* {@inheritDoc}
*/
- public int bitIndex(final Integer key, final int offsetInBits, final int lengthInBits,
+ public int bitIndex(final Integer key, final int offsetInBits, final int lengthInBits,
final Integer 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.intValue();
if (keyValue == 0) {
return NULL_BIT_KEY;
}
final int otherValue = other != null ? other.intValue() : 0;
-
+
if (keyValue != otherValue) {
final int xorValue = keyValue ^ otherValue;
for (int i = 0; i < LENGTH; i++) {
@@ -95,24 +95,24 @@ public class IntegerKeyAnalyzer extends
}
}
}
-
+
return KeyAnalyzer.EQUAL_BIT_KEY;
}
-
+
/**
* {@inheritDoc}
*/
- public boolean isPrefix(final Integer prefix, final int offsetInBits,
+ public boolean isPrefix(final Integer prefix, final int offsetInBits,
final int lengthInBits, final Integer key) {
-
+
final int value1 = prefix.intValue() << offsetInBits;
final int value2 = key.intValue();
-
+
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/KeyAnalyzer.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/KeyAnalyzer.java?rev=1477794&r1=1477793&r2=1477794&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 Tue Apr 30 19:42:03 2013
@@ -19,57 +19,57 @@ package org.apache.commons.collections4.
import java.io.Serializable;
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.
+/**
+ * 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.
* <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
+ * 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
+
+ /**
+ * 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
+
+ /**
+ * 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.
- *
+ *
* @return the number of bits per element
*/
public int bitsPerElement();
-
- /**
+
+ /**
* Returns the length of the Key in bits.
- *
+ *
* @param key the key
* @return the bit length of the key
*/
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
@@ -77,7 +77,7 @@ public interface KeyAnalyzer<K> extends
*/
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.
*/
Modified: commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/LongKeyAnalyzer.java
URL: http://svn.apache.org/viewvc/commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/LongKeyAnalyzer.java?rev=1477794&r1=1477793&r2=1477794&view=diff
==============================================================================
--- commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/LongKeyAnalyzer.java (original)
+++ commons/proper/collections/trunk/src/main/java/org/apache/commons/collections4/trie/LongKeyAnalyzer.java Tue Apr 30 19:42:03 2013
@@ -18,29 +18,29 @@ package org.apache.commons.collections4.
/**
* 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
*/
@@ -54,7 +54,7 @@ public class LongKeyAnalyzer extends Abs
public int bitsPerElement() {
return 1;
}
-
+
/**
* {@inheritDoc}
*/
@@ -72,21 +72,21 @@ public class LongKeyAnalyzer extends Abs
/**
* {@inheritDoc}
*/
- public int bitIndex(final Long key, final int offsetInBits, final int lengthInBits,
+ public int bitIndex(final Long key, final int offsetInBits, final int lengthInBits,
final Long 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 long keyValue = key.longValue();
if (keyValue == 0L) {
return NULL_BIT_KEY;
}
final long otherValue = other != null ? other.longValue() : 0L;
-
+
if (keyValue != otherValue) {
final long xorValue = keyValue ^ otherValue;
for (int i = 0; i < LENGTH; i++) {
@@ -95,24 +95,24 @@ public class LongKeyAnalyzer extends Abs
}
}
}
-
+
return KeyAnalyzer.EQUAL_BIT_KEY;
}
-
+
/**
* {@inheritDoc}
*/
- public boolean isPrefix(final Long prefix, final int offsetInBits,
+ public boolean isPrefix(final Long prefix, final int offsetInBits,
final int lengthInBits, final Long key) {
-
+
final long value1 = prefix.longValue() << offsetInBits;
final long value2 = key.longValue();
-
+
long mask = 0L;
for (int i = 0; i < lengthInBits; i++) {
mask |= 0x1L << i;
}
-
+
return (value1 & mask) == (value2 & mask);
}
}
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=1477794&r1=1477793&r2=1477794&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 Tue Apr 30 19:42:03 2013
@@ -30,39 +30,39 @@ import org.apache.commons.collections4.T
/**
* <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
- * 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)}
- * operations. All operations are performed at worst in O(K) time, where K
- * 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
+ *
+ * <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)}
+ * operations. All operations are performed at worst in O(K) time, where K
+ * 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
- * doing any operation. While performing a lookup, each comparison (at most
- * K of them, described above) will perform a single bit comparison against
+ * 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
- * {@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
+ *
+ * <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
- * keys. Some methods, such as {@link #getPrefixedBy(Object)} are suited only
- * to variable length keys, whereas {@link #getPrefixedByBits(Object, int)} is
+ *
+ * <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
- * {@link ClassCastException} if the method is expecting an instance of K
+ *
+ * <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.
- *
+ *
* @see <a href="http://en.wikipedia.org/wiki/Radix_tree">Radix Tree</a>
* @see <a href="http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA">PATRICIA</a>
* @see <a href="http://www.imperialviolet.org/binary/critbit.pdf">Crit-Bit Tree</a>
@@ -70,7 +70,7 @@ import org.apache.commons.collections4.T
* @version $Id$
*/
public class PatriciaTrie<K, V> extends PatriciaTrieBase<K, V> implements Trie<K, V> {
-
+
private static final long serialVersionUID = 4446367780901817838L;
public PatriciaTrie(final KeyAnalyzer<? super K> keyAnalyzer) {
@@ -81,14 +81,14 @@ public class PatriciaTrie<K, V> extends
final Map<? extends K, ? extends V> m) {
super(keyAnalyzer, m);
}
-
+
/**
* {@inheritDoc}
*/
public Comparator<? super K> comparator() {
return keyAnalyzer;
}
-
+
/**
* {@inheritDoc}
*/
@@ -117,7 +117,7 @@ public class PatriciaTrie<K, V> extends
public SortedMap<K, V> getPrefixedByBits(final K key, final int lengthInBits) {
return getPrefixedByBits(key, 0, lengthInBits);
}
-
+
/**
* {@inheritDoc}
*/
@@ -135,36 +135,36 @@ public class PatriciaTrie<K, V> extends
}
return null;
}
-
+
/**
* {@inheritDoc}
- *
+ *
* The view that this returns is optimized to have a very efficient
- * {@link Iterator}. The {@link SortedMap#firstKey()},
- * {@link SortedMap#lastKey()} & {@link Map#size()} methods must
- * iterate over all possible values in order to determine the results.
- * This information is cached until the PATRICIA {@link Trie} changes.
- * All other methods (except {@link Iterator}) must compare the given
- * key to the prefix to ensure that it is within the range of the view.
- * The {@link Iterator}'s remove method must also relocate the subtree
- * that contains the prefixes if the entry holding the subtree is
+ * {@link Iterator}. The {@link SortedMap#firstKey()},
+ * {@link SortedMap#lastKey()} & {@link Map#size()} methods must
+ * iterate over all possible values in order to determine the results.
+ * This information is cached until the PATRICIA {@link Trie} changes.
+ * All other methods (except {@link Iterator}) must compare the given
+ * key to the prefix to ensure that it is within the range of the view.
+ * The {@link Iterator}'s remove method must also relocate the subtree
+ * that contains the prefixes if the entry holding the subtree is
* removed or changes. Changing the subtree takes O(K) time.
*/
public SortedMap<K, V> getPrefixedByBits(final K key, final int offsetInBits, final int lengthInBits) {
-
+
final int offsetLength = offsetInBits + lengthInBits;
if (offsetLength > lengthInBits(key)) {
- throw new IllegalArgumentException(offsetInBits + " + "
+ throw new IllegalArgumentException(offsetInBits + " + "
+ lengthInBits + " > " + lengthInBits(key));
}
-
+
if (offsetLength == 0) {
return this;
}
-
+
return new PrefixRangeMap(key, offsetInBits, lengthInBits);
}
-
+
/**
* {@inheritDoc}
*/
@@ -184,18 +184,18 @@ public class PatriciaTrie<K, V> extends
*/
public SortedMap<K, V> tailMap(final K fromKey) {
return new RangeEntryMap(fromKey, null);
- }
-
+ }
+
/**
* Returns an entry strictly higher than the given key,
* or null if no such entry exists.
*/
TrieEntry<K,V> higherEntry(final K key) {
// TODO: Cleanup so that we don't actually have to add/remove from the
- // tree. (We do it here because there are other well-defined
+ // tree. (We do it here because there are other well-defined
// functions to perform the search.)
final int lengthInBits = lengthInBits(key);
-
+
if (lengthInBits == 0) {
if (!root.isEmpty()) {
// If data in root, and more after -- return it.
@@ -209,12 +209,12 @@ public class PatriciaTrie<K, V> extends
return firstEntry();
}
}
-
+
final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
if (compareKeys(key, found.key)) {
return nextEntry(found);
}
-
+
final int bitIndex = bitIndex(key, found.key);
if (AbstractKeyAnalyzer.isValidBitIndex(bitIndex)) {
final TrieEntry<K, V> added = new TrieEntry<K, V>(key, null, bitIndex);
@@ -239,7 +239,7 @@ public class PatriciaTrie<K, V> extends
// we should have exited above.
throw new IllegalStateException("invalid lookup: " + key);
}
-
+
/**
* Returns a key-value mapping associated with the least key greater
* than or equal to the given key, or null if there is no such key.
@@ -259,12 +259,12 @@ public class PatriciaTrie<K, V> extends
// These steps ensure that the returned value is either the
// entry for the key itself, or the first entry directly after
// the key.
-
+
// TODO: Cleanup so that we don't actually have to add/remove from the
- // tree. (We do it here because there are other well-defined
+ // tree. (We do it here because there are other well-defined
// functions to perform the search.)
final int lengthInBits = lengthInBits(key);
-
+
if (lengthInBits == 0) {
if (!root.isEmpty()) {
return root;
@@ -272,12 +272,12 @@ public class PatriciaTrie<K, V> extends
return firstEntry();
}
}
-
+
final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
if (compareKeys(key, found.key)) {
return found;
}
-
+
final int bitIndex = bitIndex(key, found.key);
if (AbstractKeyAnalyzer.isValidBitIndex(bitIndex)) {
final TrieEntry<K, V> added = new TrieEntry<K, V>(key, null, bitIndex);
@@ -300,7 +300,7 @@ public class PatriciaTrie<K, V> extends
// we should have exited above.
throw new IllegalStateException("invalid lookup: " + key);
}
-
+
/**
* Returns a key-value mapping associated with the greatest key
* strictly less than the given key, or null if there is no such key.
@@ -319,21 +319,21 @@ public class PatriciaTrie<K, V> extends
//
// These steps ensure that the returned value is always just before
// the key or null (if there was nothing before it).
-
+
// TODO: Cleanup so that we don't actually have to add/remove from the
- // tree. (We do it here because there are other well-defined
+ // tree. (We do it here because there are other well-defined
// functions to perform the search.)
final int lengthInBits = lengthInBits(key);
-
+
if (lengthInBits == 0) {
return null; // there can never be anything before root.
}
-
+
final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
if (compareKeys(key, found.key)) {
return previousEntry(found);
}
-
+
final int bitIndex = bitIndex(key, found.key);
if (AbstractKeyAnalyzer.isValidBitIndex(bitIndex)) {
final TrieEntry<K, V> added = new TrieEntry<K, V>(key, null, bitIndex);
@@ -352,17 +352,17 @@ public class PatriciaTrie<K, V> extends
// we should have exited above.
throw new IllegalStateException("invalid lookup: " + key);
}
-
+
/**
* Returns a key-value mapping associated with the greatest key
* less than or equal to the given key, or null if there is no such key.
*/
- TrieEntry<K,V> floorEntry(final K key) {
+ TrieEntry<K,V> floorEntry(final K key) {
// TODO: Cleanup so that we don't actually have to add/remove from the
- // tree. (We do it here because there are other well-defined
+ // tree. (We do it here because there are other well-defined
// functions to perform the search.)
final int lengthInBits = lengthInBits(key);
-
+
if (lengthInBits == 0) {
if (!root.isEmpty()) {
return root;
@@ -370,12 +370,12 @@ public class PatriciaTrie<K, V> extends
return null;
}
}
-
+
final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
if (compareKeys(key, found.key)) {
return found;
}
-
+
final int bitIndex = bitIndex(key, found.key);
if (AbstractKeyAnalyzer.isValidBitIndex(bitIndex)) {
final TrieEntry<K, V> added = new TrieEntry<K, V>(key, null, bitIndex);
@@ -398,10 +398,10 @@ public class PatriciaTrie<K, V> extends
// we should have exited above.
throw new IllegalStateException("invalid lookup: " + key);
}
-
+
/**
* Finds the subtree that contains the prefix.
- *
+ *
* This is very similar to getR but with the difference that
* we stop the lookup if h.bitIndex > lengthInBits.
*/
@@ -409,30 +409,30 @@ public class PatriciaTrie<K, V> extends
TrieEntry<K, V> current = root.left;
TrieEntry<K, V> path = root;
while(true) {
- if (current.bitIndex <= path.bitIndex
+ if (current.bitIndex <= path.bitIndex
|| lengthInBits < current.bitIndex) {
break;
}
-
+
path = current;
- if (!isBitSet(prefix, offsetInBits + current.bitIndex,
+ if (!isBitSet(prefix, offsetInBits + current.bitIndex,
offsetInBits + lengthInBits)) {
current = current.left;
} else {
current = current.right;
}
- }
+ }
// Make sure the entry is valid for a subtree.
final TrieEntry<K, V> entry = current.isEmpty() ? path : current;
-
+
// If entry is root, it can't be empty.
if (entry.isEmpty()) {
return null;
}
-
+
final int endIndexInBits = offsetInBits + lengthInBits;
-
+
// if root && length of root is less than length of lookup,
// there's nothing.
// (this prevents returning the whole subtree if root has an empty
@@ -440,35 +440,35 @@ public class PatriciaTrie<K, V> extends
if (entry == root && lengthInBits(entry.getKey()) < endIndexInBits) {
return null;
}
-
+
// Found key's length-th bit differs from our key
// which means it cannot be the prefix...
- if (isBitSet(prefix, endIndexInBits, endIndexInBits)
+ if (isBitSet(prefix, endIndexInBits, endIndexInBits)
!= isBitSet(entry.key, lengthInBits, lengthInBits(entry.key))) {
return null;
}
-
+
// ... or there are less than 'length' equal bits
- final int bitIndex = keyAnalyzer.bitIndex(prefix, offsetInBits,
+ final int bitIndex = keyAnalyzer.bitIndex(prefix, offsetInBits,
lengthInBits, entry.key, 0, lengthInBits(entry.getKey()));
-
+
if (bitIndex >= 0 && bitIndex < lengthInBits) {
return null;
}
-
+
return entry;
}
-
+
/**
* Returns the last entry the {@link Trie} is storing.
- *
+ *
* <p>This is implemented by going always to the right until
* we encounter a valid uplink. That uplink is the last key.
*/
TrieEntry<K, V> lastEntry() {
return followRight(root.left);
}
-
+
/**
* Traverses down the right path until it finds an uplink.
*/
@@ -477,39 +477,39 @@ public class PatriciaTrie<K, V> extends
if (node.right == null) {
return null;
}
-
+
// Go as far right as possible, until we encounter an uplink.
while (node.right.bitIndex > node.bitIndex) {
node = node.right;
}
-
+
return node.right;
}
-
+
/**
* Returns the node lexicographically before the given node (or null if none).
- *
+ *
* This follows four simple branches:
* - If the uplink that returned us was a right uplink:
* - If predecessor's left is a valid uplink from predecessor, return it.
* - Else, follow the right path from the predecessor's left.
* - If the uplink that returned us was a left uplink:
- * - Loop back through parents until we encounter a node where
+ * - Loop back through parents until we encounter a node where
* node != node.parent.left.
* - If node.parent.left is uplink from node.parent:
* - If node.parent.left is not root, return it.
* - If it is root & root isEmpty, return null.
* - If it is root & root !isEmpty, return root.
* - If node.parent.left is not uplink from node.parent:
- * - Follow right path for first right child from node.parent.left
- *
+ * - Follow right path for first right child from node.parent.left
+ *
* @param start
*/
TrieEntry<K, V> previousEntry(final TrieEntry<K, V> start) {
if (start.predecessor == null) {
throw new IllegalArgumentException("must have come from somewhere!");
}
-
+
if (start.predecessor.right == start) {
if (isValidUplink(start.predecessor.left, start.predecessor)) {
return start.predecessor.left;
@@ -521,11 +521,11 @@ public class PatriciaTrie<K, V> extends
while (node.parent != null && node == node.parent.left) {
node = node.parent;
}
-
+
if (node.parent == null) { // can be null if we're looking up root.
return null;
}
-
+
if (isValidUplink(node.parent.left, node.parent)) {
if (node.parent.left == root) {
if (root.isEmpty()) {
@@ -533,7 +533,7 @@ public class PatriciaTrie<K, V> extends
} else {
return root;
}
-
+
} else {
return node.parent.left;
}
@@ -542,15 +542,15 @@ public class PatriciaTrie<K, V> extends
}
}
}
-
+
/**
* Returns the entry lexicographically after the given entry.
* If the given entry is null, returns the first node.
- *
+ *
* This will traverse only within the subtree. If the given node
* is not within the subtree, this will have undefined results.
*/
- TrieEntry<K, V> nextEntryInSubtree(final TrieEntry<K, V> node,
+ TrieEntry<K, V> nextEntryInSubtree(final TrieEntry<K, V> node,
final TrieEntry<K, V> parentOfSubtree) {
if (node == null) {
return firstEntry();
@@ -558,11 +558,11 @@ public class PatriciaTrie<K, V> extends
return nextEntryImpl(node.predecessor, node, parentOfSubtree);
}
}
-
+
/**
* A range view of the {@link Trie}
*/
- private abstract class RangeMap extends AbstractMap<K, V>
+ private abstract class RangeMap extends AbstractMap<K, V>
implements SortedMap<K, V> {
/**
@@ -571,7 +571,7 @@ public class PatriciaTrie<K, V> extends
private transient volatile Set<Map.Entry<K, V>> entrySet;
/**
- * Creates and returns an {@link #entrySet()}
+ * Creates and returns an {@link #entrySet()}
* view of the {@link RangeMap}
*/
protected abstract Set<Map.Entry<K, V>> createEntrySet();
@@ -580,22 +580,22 @@ public class PatriciaTrie<K, V> extends
* Returns the FROM Key
*/
protected abstract K getFromKey();
-
+
/**
* Whether or not the {@link #getFromKey()} is in the range
*/
protected abstract boolean isFromInclusive();
-
+
/**
* Returns the TO Key
*/
protected abstract K getToKey();
-
+
/**
* Whether or not the {@link #getToKey()} is in the range
*/
protected abstract boolean isToInclusive();
-
+
/**
* {@inheritDoc}
*/
@@ -677,7 +677,7 @@ public class PatriciaTrie<K, V> extends
"ToKey is out of range: " + toKey);
}
- return createRangeMap(fromKey, isFromInclusive(),
+ return createRangeMap(fromKey, isFromInclusive(),
toKey, isToInclusive());
}
@@ -690,7 +690,7 @@ public class PatriciaTrie<K, V> extends
"ToKey is out of range: " + toKey);
}
- return createRangeMap(getFromKey(), isFromInclusive(),
+ return createRangeMap(getFromKey(), isFromInclusive(),
toKey, isToInclusive());
}
@@ -703,7 +703,7 @@ public class PatriciaTrie<K, V> extends
"FromKey is out of range: " + fromKey);
}
- return createRangeMap(fromKey, isFromInclusive(),
+ return createRangeMap(fromKey, isFromInclusive(),
getToKey(), isToInclusive());
}
@@ -733,7 +733,7 @@ public class PatriciaTrie<K, V> extends
}
/**
- * Returns true if the provided key is in the FROM range
+ * Returns true if the provided key is in the FROM range
* of the {@link RangeMap}
*/
protected boolean inFromRange(final K key, final boolean forceInclusive) {
@@ -750,7 +750,7 @@ public class PatriciaTrie<K, V> extends
}
/**
- * Returns true if the provided key is in the TO range
+ * Returns true if the provided key is in the TO range
* of the {@link RangeMap}
*/
protected boolean inToRange(final K key, final boolean forceInclusive) {
@@ -772,32 +772,32 @@ public class PatriciaTrie<K, V> extends
protected abstract SortedMap<K, V> createRangeMap(K fromKey,
boolean fromInclusive, K toKey, boolean toInclusive);
}
-
+
/**
* A {@link RangeMap} that deals with {@link Entry}s
*/
private class RangeEntryMap extends RangeMap {
-
- /**
- * The key to start from, null if the beginning.
+
+ /**
+ * The key to start from, null if the beginning.
*/
private final K fromKey;
-
- /**
- * The key to end at, null if till the end.
+
+ /**
+ * The key to end at, null if till the end.
*/
private final K toKey;
-
- /**
- * Whether or not the 'from' is inclusive.
+
+ /**
+ * Whether or not the 'from' is inclusive.
*/
private final boolean fromInclusive;
-
- /**
- * Whether or not the 'to' is inclusive.
+
+ /**
+ * Whether or not the 'to' is inclusive.
*/
private final boolean toInclusive;
-
+
/**
* Creates a {@link RangeEntryMap} with the fromKey included and
* the toKey excluded from the range
@@ -805,28 +805,28 @@ public class PatriciaTrie<K, V> extends
protected RangeEntryMap(final K fromKey, final K toKey) {
this(fromKey, true, toKey, false);
}
-
+
/**
* Creates a {@link RangeEntryMap}
*/
- protected RangeEntryMap(final K fromKey, final boolean fromInclusive,
+ protected RangeEntryMap(final K fromKey, final boolean fromInclusive,
final K toKey, final boolean toInclusive) {
-
+
if (fromKey == null && toKey == null) {
throw new IllegalArgumentException("must have a from or to!");
}
-
- if (fromKey != null && toKey != null
+
+ if (fromKey != null && toKey != null
&& keyAnalyzer.compare(fromKey, toKey) > 0) {
throw new IllegalArgumentException("fromKey > toKey");
}
-
+
this.fromKey = fromKey;
this.fromInclusive = fromInclusive;
this.toKey = toKey;
this.toInclusive = toInclusive;
}
-
+
/**
* {@inheritDoc}
*/
@@ -841,7 +841,7 @@ public class PatriciaTrie<K, V> extends
e = higherEntry(fromKey);
}
}
-
+
final K first = e != null ? e.getKey() : null;
if (e == null || toKey != null && !inToRange(first, false)) {
throw new NoSuchElementException();
@@ -863,14 +863,14 @@ public class PatriciaTrie<K, V> extends
e = lowerEntry(toKey);
}
}
-
+
final K last = e != null ? e.getKey() : null;
if (e == null || fromKey != null && !inFromRange(last, false)) {
throw new NoSuchElementException();
}
return last;
}
-
+
/**
* {@inheritDoc}
*/
@@ -878,7 +878,7 @@ public class PatriciaTrie<K, V> extends
protected Set<Entry<K, V>> createEntrySet() {
return new RangeEntrySet(this);
}
-
+
/**
* {@inheritDoc}
*/
@@ -920,7 +920,7 @@ public class PatriciaTrie<K, V> extends
return new RangeEntryMap(fromKey, fromInclusive, toKey, toInclusive);
}
}
-
+
/**
* A {@link Set} view of a {@link RangeMap}
*/
@@ -1034,22 +1034,22 @@ public class PatriciaTrie<K, V> extends
}
return false;
}
-
- /**
- * An {@link Iterator} for {@link RangeEntrySet}s.
+
+ /**
+ * An {@link Iterator} for {@link RangeEntrySet}s.
*/
private final class EntryIterator extends TrieIterator<Map.Entry<K,V>> {
-
+
private final K excludedKey;
/**
* Creates a {@link EntryIterator}
*/
private EntryIterator(
- final TrieEntry<K,V> first,
+ final TrieEntry<K,V> first,
final TrieEntry<K,V> last) {
super(first);
-
+
this.excludedKey = last != null ? last.getKey() : null;
}
@@ -1068,31 +1068,31 @@ public class PatriciaTrie<K, V> extends
if (next == null || compare(next.key, excludedKey)) {
throw new NoSuchElementException();
}
-
+
return nextEntry();
}
}
- }
-
- /**
- * A submap used for prefix views over the {@link Trie}.
+ }
+
+ /**
+ * A submap used for prefix views over the {@link Trie}.
*/
private class PrefixRangeMap extends RangeMap {
-
+
private final K prefix;
-
+
private final int offsetInBits;
-
+
private final int lengthInBits;
-
+
private K fromKey = null;
-
+
private K toKey = null;
-
+
private transient int expectedModCount = 0;
-
+
private int size = -1;
-
+
/**
* Creates a {@link PrefixRangeMap}
*/
@@ -1101,11 +1101,11 @@ public class PatriciaTrie<K, V> extends
this.offsetInBits = offsetInBits;
this.lengthInBits = lengthInBits;
}
-
+
/**
* This method does two things. It determinates the FROM
* and TO range of the {@link PrefixRangeMap} and the number
- * of elements in the range. This method must be called every
+ * of elements in the range. This method must be called every
* time the {@link Trie} has changed.
*/
private int fixup() {
@@ -1114,58 +1114,58 @@ public class PatriciaTrie<K, V> extends
if (size == - 1 || PatriciaTrie.this.modCount != expectedModCount) {
final Iterator<Map.Entry<K, V>> it = entrySet().iterator();
size = 0;
-
+
Map.Entry<K, V> entry = null;
if (it.hasNext()) {
entry = it.next();
size = 1;
}
-
+
fromKey = entry == null ? null : entry.getKey();
if (fromKey != null) {
final TrieEntry<K, V> prior = previousEntry((TrieEntry<K, V>)entry);
fromKey = prior == null ? null : prior.getKey();
}
-
+
toKey = fromKey;
-
+
while (it.hasNext()) {
++size;
entry = it.next();
}
-
+
toKey = entry == null ? null : entry.getKey();
-
+
if (toKey != null) {
entry = nextEntry((TrieEntry<K, V>)entry);
toKey = entry == null ? null : entry.getKey();
}
-
+
expectedModCount = PatriciaTrie.this.modCount;
}
-
+
return size;
}
-
+
/**
* {@inheritDoc}
*/
public K firstKey() {
fixup();
-
+
Map.Entry<K,V> e = null;
if (fromKey == null) {
e = firstEntry();
} else {
e = higherEntry(fromKey);
}
-
+
final K first = e != null ? e.getKey() : null;
- if (e == null || !keyAnalyzer.isPrefix(prefix,
+ if (e == null || !keyAnalyzer.isPrefix(prefix,
offsetInBits, lengthInBits, first)) {
throw new NoSuchElementException();
}
-
+
return first;
}
@@ -1174,23 +1174,23 @@ public class PatriciaTrie<K, V> extends
*/
public K lastKey() {
fixup();
-
+
Map.Entry<K,V> e = null;
if (toKey == null) {
e = lastEntry();
} else {
e = lowerEntry(toKey);
}
-
+
final K last = e != null ? e.getKey() : null;
- if (e == null || !keyAnalyzer.isPrefix(prefix,
+ if (e == null || !keyAnalyzer.isPrefix(prefix,
offsetInBits, lengthInBits, last)) {
throw new NoSuchElementException();
}
-
+
return last;
}
-
+
/**
* Returns true if this {@link PrefixRangeMap}'s key is a prefix
* of the provided key.
@@ -1207,7 +1207,7 @@ public class PatriciaTrie<K, V> extends
protected boolean inRange2(final K key) {
return inRange(key);
}
-
+
/**
* Returns true if the provided Key is in the FROM range
* of the {@link PrefixRangeMap}
@@ -1216,7 +1216,7 @@ public class PatriciaTrie<K, V> extends
protected boolean inFromRange(final K key, final boolean forceInclusive) {
return keyAnalyzer.isPrefix(prefix, offsetInBits, lengthInBits, key);
}
-
+
/**
* Returns true if the provided Key is in the TO range
* of the {@link PrefixRangeMap}
@@ -1225,7 +1225,7 @@ public class PatriciaTrie<K, V> extends
protected boolean inToRange(final K key, final boolean forceInclusive) {
return keyAnalyzer.isPrefix(prefix, offsetInBits, lengthInBits, key);
}
-
+
/**
* {@inheritDoc}
*/
@@ -1276,18 +1276,18 @@ public class PatriciaTrie<K, V> extends
return new RangeEntryMap(fromKey, fromInclusive, toKey, toInclusive);
}
}
-
+
/**
* A prefix {@link RangeEntrySet} view of the {@link Trie}
*/
private final class PrefixRangeEntrySet extends RangeEntrySet {
-
+
private final PrefixRangeMap delegate;
-
+
private TrieEntry<K, V> prefixStart;
-
+
private int expectedModCount = 0;
-
+
/**
* Creates a {@link PrefixRangeEntrySet}
*/
@@ -1295,7 +1295,7 @@ public class PatriciaTrie<K, V> extends
super(delegate);
this.delegate = delegate;
}
-
+
/**
* {@inheritDoc}
*/
@@ -1313,7 +1313,7 @@ public class PatriciaTrie<K, V> extends
prefixStart = subtree(delegate.prefix, delegate.offsetInBits, delegate.lengthInBits);
expectedModCount = PatriciaTrie.this.modCount;
}
-
+
if (prefixStart == null) {
final Set<Map.Entry<K,V>> empty = Collections.emptySet();
return empty.iterator();
@@ -1323,20 +1323,20 @@ public class PatriciaTrie<K, V> extends
return new EntryIterator(prefixStart, delegate.prefix, delegate.offsetInBits, delegate.lengthInBits);
}
}
-
- /**
- * An {@link Iterator} that holds a single {@link TrieEntry}.
+
+ /**
+ * An {@link Iterator} that holds a single {@link TrieEntry}.
*/
private final class SingletonIterator implements Iterator<Map.Entry<K, V>> {
-
+
private final TrieEntry<K, V> entry;
-
+
private int hit = 0;
-
+
public SingletonIterator(final TrieEntry<K, V> entry) {
this.entry = entry;
}
-
+
/**
* {@inheritDoc}
*/
@@ -1351,7 +1351,7 @@ public class PatriciaTrie<K, V> extends
if (hit != 0) {
throw new NoSuchElementException();
}
-
+
++hit;
return entry;
}
@@ -1363,30 +1363,30 @@ public class PatriciaTrie<K, V> extends
if (hit != 1) {
throw new IllegalStateException();
}
-
+
++hit;
PatriciaTrie.this.removeEntry(entry);
}
}
-
- /**
- * An {@link Iterator} for iterating over a prefix search.
+
+ /**
+ * An {@link Iterator} for iterating over a prefix search.
*/
private final class EntryIterator extends TrieIterator<Map.Entry<K, V>> {
-
+
// values to reset the subtree if we remove it.
- private final K prefix;
+ private final K prefix;
private final int offset;
private final int lengthInBits;
private boolean lastOne;
-
+
private TrieEntry<K, V> subtree; // the subtree to search within
-
+
/**
- * Starts iteration at the given entry & search only
+ * Starts iteration at the given entry & search only
* within the given subtree.
*/
- EntryIterator(final TrieEntry<K, V> startScan, final K prefix,
+ EntryIterator(final TrieEntry<K, V> startScan, final K prefix,
final int offset, final int lengthInBits) {
subtree = startScan;
next = PatriciaTrie.this.followLeft(startScan);
@@ -1405,7 +1405,7 @@ public class PatriciaTrie<K, V> extends
}
return entry;
}
-
+
/**
* {@inheritDoc}
*/
@@ -1413,7 +1413,7 @@ public class PatriciaTrie<K, V> extends
protected TrieEntry<K, V> findNext(final TrieEntry<K, V> prior) {
return PatriciaTrie.this.nextEntryInSubtree(prior, subtree);
}
-
+
/**
* {@inheritDoc}
*/
@@ -1426,15 +1426,15 @@ public class PatriciaTrie<K, V> extends
if (current == subtree) {
needsFixing = true;
}
-
+
super.remove();
-
+
// If the subtree changed its bitIndex or we
// removed the old subtree, get a new one.
if (bitIdx != subtree.bitIndex || needsFixing) {
subtree = subtree(prefix, offset, lengthInBits);
}
-
+
// If the subtree's bitIndex is less than the
// length of our prefix, it's the last item
// in the prefix tree.