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 &amp; 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()} &amp; {@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()} &amp; {@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.