gt:             if (length >= subtree.bitIndex)
context: /*
   *  PHEX - The pure-java Gnutella-servent.
   *  Copyright (C) 2001 - 2007 Phex Development Group
   *
   *  This program is free software; you can redistribute it and/or modify
   *  it under the terms of the GNU General Public License as published by
   *  the Free Software Foundation; either version 2 of the License, or
   *  (at your option) any later version.
   *
   *  This program is distributed in the hope that it will be useful,
   *  but WITHOUT ANY WARRANTY; without even the implied warranty of
   *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   *  GNU General Public License for more details.
   *
   *  You should have received a copy of the GNU General Public License
   *  along with this program; if not, write to the Free Software
   *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
   *
   *  --- SVN Information ---
   *  $Id: PatriciaTrie.java 4420 2009-03-28 16:21:30Z gregork $
   */
  package phex.common.collections;
  
  // Modified version (1.8 2008-08-13 00:14:58) of org/limewire/collection/PatriciaTrie.java
  // Copyright by Limewire
  
  
  import org.apache.commons.collections4.iterators.EmptyIterator;
  
  import java.io.Serializable;
  import java.util.*;
  
  /**
   * A PATRICIA Trie.
   * <p>
   * PATRICIA = Practical Algorithm to Retrieve Information Coded in Alphanumeric
   * <p>
   * A PATRICIA Trie is a compressed Trie. Instead of storing all data at the
   * edges of the 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 'select' 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 the given key, instead of comparing the entire key to another key.
   * <p>
   * The Trie can return operations in lexicographical order using the 'traverse',
   * 'prefix', 'submap', or 'iterator' methods. The 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 Trie supports both variable length & fixed length keys.
   * Some methods, such as <code>getPrefixedBy(...)</code> are suited only to
   * variable length keys, whereas <code>getPrefixedByBits(...)</code> is suited
   * to fixed-size keys.
   * <p>
   * Additionally see <a
   * href="http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA/">PATRICIA</a>
   * for more information.
   * <p>
   * Any methods here that take an <code>Object</code> may throw a
   * <code>ClassCastException<code> if the method is expecting an instance of K
   * (and it isn't K).
   * <p>
   * <pre>
   * PatriciaTrie&lt;String, String&gt; trie = new PatriciaTrie&lt;String, String&gt;
   * (new CharSequenceKeyAnalyzer());
   *
   * trie.put("Lime", "Lime");
   * trie.put("LimeWire", "LimeWire");
   * trie.put("LimeRadio", "LimeRadio");
   * trie.put("Lax", "Lax");
   * trie.put("Lake", "Lake");
   * trie.put("Lovely", "Lovely");
   *
   * System.out.println(trie.select("Lo"));
   * System.out.println(trie.select("Lime"));
   *
   * System.out.println(trie.getPrefixedBy("La").toString());
   *
   * Output:
   * Lovely
   * Lime
   * {Lake=Lake, Lax=Lax}
   *
   * </pre>
   *
   * @author Roger Kapsi
   * @author Sam Berlin
   */
  public class PatriciaTrie<K, V> extends AbstractMap<K, V> implements Trie<K, V>, Serializable {
  
      private static final long serialVersionUID = 110232526181493307L;
  
      /**
       * The root element of the Trie.
       */
      private final TrieEntry<K, V> root = new TrieEntry<>(null, null, -1);
      /**
       * The keyAnalyzer used to analyze bit values of keys.
       */
      private final KeyAnalyzer<? super K> keyAnalyzer;
      /**
       * The current size (total number of elements) of the Trie.
       */
      private int size = 0;
      /**
       * The number of times this has been modified (to fail-fast the iterators).
       */
      private transient int modCount = 0;
      /**
       * Each of these fields are initialized to contain an instance of the
       * appropriate view the first time this view is requested.  The views are
       * stateless, so there's no reason to create more than one of each.
       */
      private transient volatile Set<K> keySet = null;
      private transient volatile Collection<V> values = null;
      private transient volatile Set<Map.Entry<K, V>> entrySet = null;
  
      /**
       * Constructs a new PatriciaTrie using the given keyAnalyzer.
       */
      public PatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer) {
          this.keyAnalyzer = keyAnalyzer;
      }
  
      /**
       * Returns true if bitIndex is a valid index
       */
      private static boolean isValidBitIndex(int bitIndex) {
          return 0 <= bitIndex && bitIndex <= Integer.MAX_VALUE;
      }
  
      /**
       * Returns true if bitIndex is a NULL_BIT_KEY
       */
      private static boolean isNullBitKey(int bitIndex) {
          return bitIndex == KeyAnalyzer.NULL_BIT_KEY;
      }
  
      /**
       * Returns true if bitIndex is a EQUAL_BIT_KEY
       */
      private static boolean isEqualBitKey(int bitIndex) {
          return bitIndex == KeyAnalyzer.EQUAL_BIT_KEY;
      }
  
      /**
       * Test two values for equality.  Works with null values.
       */
      private static boolean valEquals(Object o1, Object o2) {
          return (o1 == null ? o2 == null : o1.equals(o2));
      }
  
      /**
       * Returns the KeyAnalyzer that constructed the trie.
       */
      public KeyAnalyzer<? super K> getKeyAnalyzer() {
          return keyAnalyzer;
      }
  
      /**
       * Returns the KeyAnalyzer as a comparator.
       */
      public Comparator<? super K> comparator() {
          return keyAnalyzer;
      }
  
      /**
       * Clears the Trie (i.e. removes all elements).
       */
      @Override
      public void clear() {
          root.key = null;
          root.bitIndex = -1;
          root.value = null;
  
          root.parent = null;
          root.left = root;
          root.right = null;
          root.predecessor = root;
  
          size = 0;
          incrementModCount();
      }
  
      /**
       * Returns true if the Trie is empty
       */
      @Override
      public boolean isEmpty() {
          return size == 0;
      }
  
      /**
       * Returns the number items in the Trie
       */
      @Override
      public int size() {
          return size;
      }
  
      /**
       * Increments both the size and mod counter.
       */
      private void incrementSize() {
          size++;
          incrementModCount();
      }
  
      /**
       * Decrements the size and increments the mod counter.
       */
      private void decrementSize() {
          size--;
          incrementModCount();
      }
  
      /**
       * Increments the mod counter.
       */
      private void incrementModCount() {
          modCount++;
      }
  
      /**
       * Adds a new <key, value> pair to the Trie and if a pair already
       * exists it will be replaced. In the latter case it will return
       * the old value.
       */
      @Override
      public V put(K key, V value) {
          if (key == null) {
              throw new NullPointerException("Key cannot be null");
          }
  
          int keyLength = length(key);
  
          // The only place to store a key with a length
          // of zero bits is the root node
          if (keyLength == 0) {
              if (root.isEmpty()) {
                  incrementSize();
              } else {
                  incrementModCount();
              }
              return root.setKeyValue(key, value);
          }
  
          TrieEntry<K, V> found = getNearestEntryForKey(key, keyLength);
          if (key.equals(found.key)) {
              if (found.isEmpty()) { // <- must be the root
                  incrementSize();
              } else {
                  incrementModCount();
              }
              return found.setKeyValue(key, value);
          }
  
          int bitIndex = bitIndex(key, found.key);
          if (isValidBitIndex(bitIndex)) { // in 99.999...9% the case
              /* NEW KEY+VALUE TUPLE */
              TrieEntry<K, V> t = new TrieEntry<>(key, value, bitIndex);
              addEntry(t, keyLength);
              incrementSize();
              return null;
          } else if (isNullBitKey(bitIndex)) {
              // A bits of the Key are zero. The only place to
              // store such a Key is the root Node!
  
              /* NULL BIT KEY */
              if (root.isEmpty()) {
                  incrementSize();
              } else {
                  incrementModCount();
              }
              return root.setKeyValue(key, value);
  
          } else if (isEqualBitKey(bitIndex)) {
              // This is a very special and rare case.
  
              /* REPLACE OLD KEY+VALUE */
              if (found != root) {
                  incrementModCount();
                  return found.setKeyValue(key, value);
              }
          }
  
          throw new IndexOutOfBoundsException("Failed to put: " + key + " -> " + value + ", " + bitIndex);
      }
  
      /**
       * Adds the given entry into the Trie.
       */
      private TrieEntry<K, V> addEntry(TrieEntry<K, V> toAdd, int keyLength) {
          TrieEntry<K, V> current = root.left;
          TrieEntry<K, V> path = root;
          while (true) {
              if (current.bitIndex >= toAdd.bitIndex || current.bitIndex <= path.bitIndex) {
                  toAdd.predecessor = toAdd;
  
                  if (!isBitSet(toAdd.key, keyLength, toAdd.bitIndex)) {
                      toAdd.left = toAdd;
                      toAdd.right = current;
                  } else {
                      toAdd.left = current;
                      toAdd.right = toAdd;
                  }
  
                  toAdd.parent = path;
                  if (current.bitIndex >= toAdd.bitIndex) {
                      current.parent = toAdd;
                  }
  
                  // if we inserted an uplink, set the predecessor on it
                  if (current.bitIndex <= path.bitIndex) {
                      current.predecessor = toAdd;
                  }
  
                  if (path == root || !isBitSet(toAdd.key, keyLength, path.bitIndex))
                      path.left = toAdd;
                  else
                      path.right = toAdd;
                  return toAdd;
              }
  
              path = current;
              if (!isBitSet(toAdd.key, keyLength, current.bitIndex))
                  current = current.left;
              else
                  current = current.right;
          }
      }
  
      @Override
      public Set<Map.Entry<K, V>> entrySet() {
          Set<Map.Entry<K, V>> es = entrySet;
          return (es != null ? es : (entrySet = new EntrySet()));
      }
  
      /**
       * Returns the Value whose Key equals our lookup Key
       * or null if no such key exists.
       */
      @Override
      public V get(Object k) {
          TrieEntry<K, V> entry = getEntry(k);
          return entry != null ? entry.getValue() : null;
      }
  
      /**
       * Returns the entry associated with the specified key in the
       * PatriciaTrie.  Returns null if the map contains no mapping
       * for this key.
       * <p>
       * This may throw ClassCastException if the object is not of type K.
       */
      TrieEntry<K, V> getEntry(Object k) {
          K key = asKey(k);
          if (key == null)
              return null;
  
          int keyLength = length(key);
          TrieEntry<K, V> entry = getNearestEntryForKey(key, keyLength);
          return !entry.isEmpty() && key.equals(entry.key) ? entry : null;
      }
  
      /**
       * Gets the key as a 'K'.
       */
      @SuppressWarnings("unchecked")
      protected final K asKey(Object key) {
          try {
              return (K) key;
          } catch (ClassCastException cce) {
              // Because the type is erased, the cast & return are
              // actually doing nothing, making this CCE impossible.
              // However, it's still here on the off-chance it may
              // work.
              return null;
          }
      }
  
      /**
       * Returns the nearest entry for a given key.  This is useful
       * for finding knowing if a given key exists (and finding the value
       * for it), or for inserting the key.
       * <p>
       * The actual get implementation. This is very similar to
       * selectR but with the exception that it might return the
       * root Entry even if it's empty.
       */
      private TrieEntry<K, V> getNearestEntryForKey(K key, int keyLength) {
          TrieEntry<K, V> current = root.left;
          TrieEntry<K, V> path = root;
          while (true) {
              if (current.bitIndex <= path.bitIndex)
                  return current;
  
              path = current;
              if (!isBitSet(key, keyLength, current.bitIndex))
                  current = current.left;
              else
                  current = current.right;
          }
      }
  
      /**
       * Returns the Value whose Key has the longest prefix
       * in common with our lookup key.
       */
      @SuppressWarnings("unchecked")
      public V select(K key) {
          int keyLength = length(key);
          TrieEntry[] result = new TrieEntry[1];
          if (!selectR(root.left, -1, key, keyLength, result)) {
              TrieEntry<K, V> e = result[0];
              return e.getValue();
          }
          return null;
      }
  
      /**
       * This is equivalent to the other selectR() method but without
       * its overhead because we're selecting only one best matching
       * Entry from the Trie.
       */
      private boolean selectR(final TrieEntry<K, V> h, int bitIndex,
                              final K key, final int keyLength, final TrieEntry[] result) {
  
          int hbi = h.bitIndex;
          if (hbi <= bitIndex) {
              // If we hit the root Node and it is empty
              // we have to look for an alternative best
              // matching node.
              if (!h.isEmpty()) {
                  result[0] = h;
                  return false;
              }
              return true;
          }
  
          if (!isBitSet(key, keyLength, hbi)) {
              if (selectR(h.left, hbi, key, keyLength, result)) {
                  return selectR(h.right, hbi, key, keyLength, result);
              }
          } else {
              if (selectR(h.right, hbi, key, keyLength, result)) {
                  return selectR(h.left, hbi, key, keyLength, result);
              }
          }
          return false;
      }
  
      @SuppressWarnings("unchecked")
      public Map.Entry<K, V> select(K key, Cursor<? super K, ? super V> cursor) {
          int keyLength = length(key);
          TrieEntry[] result = new TrieEntry[]{null};
          selectR(root.left, -1, key, keyLength, cursor, result);
          return result[0];
      }
  
      private boolean selectR(TrieEntry<K, V> h, int bitIndex,
                              final K key,
                              final int keyLength,
                              final Cursor<? super K, ? super V> cursor,
                              final TrieEntry[] result) {
  
          int hbi = h.bitIndex;
          if (hbi <= bitIndex) {
              if (!h.isEmpty()) {
                  Cursor.SelectStatus ret = cursor.select(h);
                  switch (ret) {
                      case REMOVE:
                          throw new UnsupportedOperationException("cannot remove during select");
                      case EXIT:
                          result[0] = h;
                          return false; // exit
                      case REMOVE_AND_EXIT:
                          TrieEntry<K, V> entry = new TrieEntry<>(h.getKey(), h.getValue(), -1);
                          result[0] = entry;
                          removeEntry(h);
                          return false;
                      case CONTINUE:
                          // fall through.
                  }
              }
              return true; // continue
          }
  
          if (!isBitSet(key, keyLength, hbi)) {
              if (selectR(h.left, hbi, key, keyLength, cursor, result)) {
                  return selectR(h.right, hbi, key, keyLength, cursor, result);
              }
          } else {
              if (selectR(h.right, hbi, key, keyLength, cursor, result)) {
                  return selectR(h.left, hbi, key, keyLength, cursor, result);
              }
          }
  
          return false;
      }
  
      /**
       * Returns a view of this Trie of all elements that are
       * prefixed by the given key.
       * <p>
       * In a fixed-keysize Trie, this is essentially a 'get' operation.
       * <p>
       * For example, if the trie contains 'Lime', 'LimeWire',
       * 'LimeRadio', 'Lax', 'Later', 'Lake', and 'Lovely', then
       * a lookup of 'Lime' would return 'Lime', 'LimeRadio', and 'LimeWire'.
       * <p>
       * The view that this returns is optimized to have a very efficient
       * Iterator. The firstKey, lastKey & size methods must iterate
       * over all possible values in order to determine the results. This
       * information is cached until the Patricia tree changes. All other
       * methods (except Iterator) must compare the given key to the prefix
       * to ensure that it is within the range of the view. The 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.
       *
       * @param key
       */
      public SortedMap<K, V> getPrefixedBy(K key) {
          return getPrefixedByBits(key, 0, keyAnalyzer.length(key));
      }
  
      /**
       * Returns a view of this Trie of all elements that are
       * prefixed by the length of the key.
       * <p>
       * Fixed-keysize Tries will not support this operation
       * (because all keys will be the same length).
       * <p>
       * For example, if the trie contains 'Lime', 'LimeWire',
       * 'LimeRadio', 'Lax', 'Later', 'Lake', and 'Lovely', then
       * a lookup of 'LimePlastics' with a length of 4 would
       * return 'Lime', 'LimeRadio', and 'LimeWire'.
       * <p>
       * The view that this returns is optimized to have a very efficient
       * Iterator.  The firstKey, lastKey & size methods must iterate
       * over all possible values in order to determine the results.  This
       * information is cached until the Patricia tree changes.  All other
       * methods (except Iterator) must compare the given key to the prefix
       * to ensure that it is within the range of the view.  The 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.
       *
       * @param key
       * @param length
       */
      public SortedMap<K, V> getPrefixedBy(K key, int length) {
          return getPrefixedByBits(key, 0, length * keyAnalyzer.bitsPerElement());
      }
  
      /**
       * Returns a view of this Trie of all elements that are prefixed
       * by the key, starting at the given offset and for the given length.
       * <p>
       * Fixed-keysize Tries will not support this operation
       * (because all keys are the same length).
       * <p>
       * For example, if the trie contains 'Lime', 'LimeWire',
       * 'LimeRadio', 'Lax', 'Later', 'Lake', and 'Lovely', then
       * a lookup of 'The Lime Plastics' with an offset of 4 and a
       * length of 4 would return 'Lime', 'LimeRadio', and 'LimeWire'.
       * <p>
       * The view that this returns is optimized to have a very efficient
       * Iterator.  The firstKey, lastKey & size methods must iterate
       * over all possible values in order to determine the results.  This
       * information is cached until the Patricia tree changes.  All other
       * methods (except Iterator) must compare the given key to the prefix
       * to ensure that it is within the range of the view.  The 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.
       *
       * @param key
       * @param offset
       * @param length
       */
      public SortedMap<K, V> getPrefixedBy(K key, int offset, int length) {
          return getPrefixedByBits(key, offset * keyAnalyzer.bitsPerElement(), length * keyAnalyzer.bitsPerElement());
      }
  
      /**
       * Returns a view of this Trie of all elements that are prefixed
       * by the number of bits in the given Key.
       * <p>
       * Fixed-keysize Tries can support this operation as a way to do
       * lookups of partial keys.  That is, if the Trie is storing IP
       * addresses, you can lookup all addresses that begin with
       * '192.168' by providing the key '192.168.X.X' and a length of 16
       * would return all addresses that begin with '192.168'.
       * <p>
       * The view that this returns is optimized to have a very efficient
       * Iterator.  The firstKey, lastKey & size methods must iterate
       * over all possible values in order to determine the results.  This
       * information is cached until the Patricia tree changes.  All other
       * methods (except Iterator) must compare the given key to the prefix
       * to ensure that it is within the range of the view.  The 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.
       *
       * @param key
       * @param bitLength
       */
      public SortedMap<K, V> getPrefixedByBits(K key, int bitLength) {
          return getPrefixedByBits(key, 0, bitLength);
      }
  
      /**
       * Returns a view of this map, with entries containing only those that
       * are prefixed by a value whose bits matches the bits between 'offset'
       * and 'length' in the given key.
       * <p>
       * The view that this returns is optimized to have a very efficient
       * Iterator.  The firstKey, lastKey & size methods must iterate
       * over all possible values in order to determine the results.  This
       * information is cached until the Patricia tree changes.  All other
       * methods (except Iterator) must compare the given key to the prefix
       * to ensure that it is within the range of the view.  The 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.
       *
       * @param key
       * @param offset
       * @param length
       */
      private SortedMap<K, V> getPrefixedByBits(K key, int offset, int length) {
          int offsetLength = offset + length;
          if (offsetLength > length(key)) {
              throw new IllegalArgumentException(offset + " + " + length + " > " + length(key));
          }
  
          if (offsetLength == 0)
              return this;
  
          return new PrefixSubMap(key, offset, length);
      }
  
      /**
       * Returns true if this trie contains the specified Key
       * <p>
       * This may throw ClassCastException if the object is not
       * of type K.
       */
      @Override
      public boolean containsKey(Object k) {
          K key = asKey(k);
          if (key == null)
              return false;
  
          int keyLength = length(key);
          TrieEntry entry = getNearestEntryForKey(key, keyLength);
          return !entry.isEmpty() && key.equals(entry.key);
      }
  
      /**
       * Returns true if this Trie contains the specified value.
       */
      @Override
      public boolean containsValue(Object o) {
          for (V v : values())
              if (valEquals(v, o))
                  return true;
          return false;
      }
  
      /**
       * Removes a Key from the Trie if one exists
       * <p>
       * This may throw ClassCastException if the object is not of type K.
       *
       * @param k the Key to delete
       * @return Returns the deleted Value
       */
      @Override
      public V remove(Object k) {
          K key = asKey(k);
          if (key == null)
              return null;
  
          int keyLength = length(key);
          TrieEntry<K, V> current = root.left;
          TrieEntry<K, V> path = root;
          while (true) {
              if (current.bitIndex <= path.bitIndex) {
                  if (!current.isEmpty() && key.equals(current.key))
                      return removeEntry(current);
                  else
                      return null;
              }
  
              path = current;
              if (!isBitSet(key, keyLength, current.bitIndex))
                  current = current.left;
              else
                  current = current.right;
          }
      }
  
      /**
       * Removes a single entry from the Trie.
       * <p>
       * If we found a Key (Entry h) then figure out if it's
       * an internal (hard to remove) or external Entry (easy
       * to remove)
       */
      private V removeEntry(TrieEntry<K, V> h) {
          if (h != root) {
              if (h.isInternalNode()) {
                  removeInternalEntry(h);
              } else {
                  removeExternalEntry(h);
              }
          }
  
          decrementSize();
          return h.setKeyValue(null, null);
      }
  
      /**
       * Removes an external entry from the Trie.
       * <p>
       * If it's an external Entry then just remove it.
       * This is very easy and straight forward.
       */
      private void removeExternalEntry(TrieEntry<K, V> h) {
          if (h == root) {
              throw new IllegalArgumentException("Cannot delete root Entry!");
          } else if (!h.isExternalNode()) {
              throw new IllegalArgumentException(h + " is not an external Entry!");
          }
  
          TrieEntry<K, V> parent = h.parent;
          TrieEntry<K, V> child = (h.left == h) ? h.right : h.left;
  
          if (parent.left == h) {
              parent.left = child;
          } else {
              parent.right = child;
          }
  
          // either the parent is changing, or the predecessor is changing.
          if (child.bitIndex > parent.bitIndex) {
              child.parent = parent;
          } else {
              child.predecessor = parent;
          }
  
      }
  
      /**
       * Removes an internal entry from the Trie.
       * <p>
       * If it's an internal Entry then "good luck" with understanding
       * this code. The Idea is essentially that Entry p takes Entry h's
       * place in the trie which requires some re-wiring.
       */
      private void removeInternalEntry(TrieEntry<K, V> h) {
          if (h == root) {
              throw new IllegalArgumentException("Cannot delete root Entry!");
          } else if (!h.isInternalNode()) {
              throw new IllegalArgumentException(h + " is not an internal Entry!");
          }
  
          TrieEntry<K, V> p = h.predecessor;
  
          // Set P's bitIndex
          p.bitIndex = h.bitIndex;
  
          // Fix P's parent, predecessor and child Nodes
          {
              TrieEntry<K, V> parent = p.parent;
              TrieEntry<K, V> child = (p.left == h) ? p.right : p.left;
  
              // if it was looping to itself previously,
              // it will now be pointed from it's parent
              // (if we aren't removing it's parent --
              //  in that case, it remains looping to itself).
              // otherwise, it will continue to have the same
              // predecessor.
              if (p.predecessor == p && p.parent != h)
                  p.predecessor = p.parent;
  
              if (parent.left == p) {
                  parent.left = child;
              } else {
                  parent.right = child;
              }
  
              if (child.bitIndex > parent.bitIndex) {
                  child.parent = parent;
              }
          }
  
          // Fix H's parent and child Nodes
          {
              // If H is a parent of its left and right child
              // then change them to P
              if (h.left.parent == h) {
                  h.left.parent = p;
              }
  
              if (h.right.parent == h) {
                  h.right.parent = p;
              }
  
              // Change H's parent
              if (h.parent.left == h) {
                  h.parent.left = p;
              } else {
                  h.parent.right = p;
              }
          }
  
          // Copy the remaining fields from H to P
          //p.bitIndex = h.bitIndex;
          p.parent = h.parent;
          p.left = h.left;
          p.right = h.right;
  
          // Make sure that if h was pointing to any uplinks,
          // p now points to them.
          if (isValidUplink(p.left, p))
              p.left.predecessor = p;
          if (isValidUplink(p.right, p))
              p.right.predecessor = p;
  
      }
  
      /**
       * Returns the node lexicographically before the given node (or null if none).
       * <p>
       * 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
       * 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
       *
       * @param start
       */
      private TrieEntry<K, V> previousEntry(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;
              } else {
                  return followRight(start.predecessor.left);
              }
          } else {
              TrieEntry<K, V> node = start.predecessor;
              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())
                          return null;
                      else
                          return root;
                  } else {
                      return node.parent.left;
                  }
              } else {
                  return followRight(node.parent.left);
              }
          }
      }
  
      /**
       * Returns the entry lexicographically after the given entry.
       * If the given entry is null, returns the first node.
       */
      private TrieEntry<K, V> nextEntry(TrieEntry<K, V> node) {
          if (node == null) {
              return firstEntry();
          } else {
              return nextEntryImpl(node.predecessor, node, null);
          }
      }
  
      /**
       * Returns the entry lexicographically after the given entry.
       * If the given entry is null, returns the first node.
       * <p>
       * This will traverse only within the subtree.  If the given node
       * is not within the subtree, this will have undefined results.
       */
      private TrieEntry<K, V> nextEntryInSubtree(TrieEntry<K, V> node, TrieEntry<K, V> parentOfSubtree) {
          if (node == null) {
              return firstEntry();
          } else {
              return nextEntryImpl(node.predecessor, node, parentOfSubtree);
          }
      }
  
      /**
       * Scans for the next node, starting at the specified point, and using 'previous'
       * as a hint that the last node we returned was 'previous' (so we know not to return
       * it again).  If 'tree' is non-null, this will limit the search to the given tree.
       * <p>
       * The basic premise is that each iteration can follow the following steps:
       * <p>
       * 1) Scan all the way to the left.
       * a) If we already started from this node last time, proceed to Step 2.
       * b) If a valid uplink is found, use it.
       * c) If the result is an empty node (root not set), break the scan.
       * d) If we already returned the left node, break the scan.
       * <p>
       * 2) Check the right.
       * a) If we already returned the right node, proceed to Step 3.
       * b) If it is a valid uplink, use it.
       * c) Do Step 1 from the right node.
       * <p>
       * 3) Back up through the parents until we encounter find a parent
       * that we're not the right child of.
       * <p>
       * 4) If there's no right child of that parent, the iteration is finished.
       * Otherwise continue to Step 5.
       * <p>
       * 5) Check to see if the right child is a valid uplink.
       * a) If we already returned that child, proceed to Step 6.
       * Otherwise, use it.
       * <p>
       * 6) If the right child of the parent is the parent itself, we've
       * already found & returned the end of the Trie, so exit.
       * <p>
       * 7) Do Step 1 on the parent's right child.
       */
      private TrieEntry<K, V> nextEntryImpl(TrieEntry<K, V> start, TrieEntry<K, V> previous, TrieEntry<K, V> tree) {
          while (true) {
              TrieEntry<K, V> current = start;
  
              // Only look at the left if this was a recursive or
              // the first check, otherwise we know we've already looked
              // at the left.
              if (previous == null || start != previous.predecessor) {
                  while (!current.left.isEmpty()) {
                      // stop traversing if we've already
                      // returned the left of this node.
                      if (previous == current.left) {
                          break;
                      }
  
                      if (isValidUplink(current.left, current)) {
                          return current.left;
                      }
  
                      current = current.left;
                  }
              }
  
              // If there's no data at all, exit.
              if (current.isEmpty()) {
                  return null;
              }
  
              // If we've already returned the left,
              // and the immediate right is null,
              // there's only one entry in the Trie
              // which is stored at the root.
              //
              //  / ("")   <-- root
              //  \_/  \
              //       null <-- 'current'
              //
              if (current.right == null)
                  return null;
  
              // If nothing valid on the left, try the right.
              if (previous != current.right) {
                  // See if it immediately is valid.
                  if (isValidUplink(current.right, current)) {
                      return current.right;
                  }
  
                  // Must search on the right's side if it wasn't initially valid.
                  start = current.right;
                  continue;
              }
  
              // Neither left nor right are valid, find the first parent
              // whose child did not come from the right & traverse it.
              while (current == current.parent.right) {
                  // If we're going to traverse to above the subtree, stop.
                  if (current == tree)
                      return null;
  
                  current = current.parent;
              }
  
              // If we're on the top of the subtree, we can't go any higher.
              if (current == tree)
                  return null;
  
  
              // If there's no right, the parent must be root, so we're done.
              if (current.parent.right == null) {
                  return null;
              }
  
  
              // If the parent's right points to itself, we've found one.
              if (previous != current.parent.right && isValidUplink(current.parent.right, current.parent)) {
                  return current.parent.right;
              }
  
              // If the parent's right is itself, there can't be any more nodes.
              if (current.parent.right == current.parent) {
                  return null;
              }
  
              // We need to traverse down the parent's right's path.
              start = current.parent.right;
          }
      }
  
      /**
       * Returns each entry as a string.
       */
      @Override
      public String toString() {
          StringBuilder buffer = new StringBuilder();
          buffer.append("Trie[").append(size()).append("]={\n");
          for (Iterator<Map.Entry<K, V>> i = newEntryIterator(); i.hasNext(); ) {
              buffer.append("  ").append(i.next().toString()).append('\n');
          }
          buffer.append("}\n");
          return buffer.toString();
      }
  
      public Map.Entry<K, V> traverse(Cursor<? super K, ? super V> cursor) {
          TrieEntry<K, V> entry = nextEntry(null);
          while (entry != null) {
              TrieEntry<K, V> current = entry;
              Cursor.SelectStatus ret = cursor.select(current);
              entry = nextEntry(current);
              switch (ret) {
                  case EXIT:
                      return current;
                  case REMOVE:
                      removeEntry(current);
                      break; // out of switch, stay in while loop
                  case REMOVE_AND_EXIT:
                      Map.Entry<K, V> value = new TrieEntry<>(current.getKey(), current.getValue(), -1);
                      removeEntry(current);
                      return value;
                  case CONTINUE: // do nothing.
              }
          }
  
          return null;
      }
  
      /**
       * Returns true if 'next' is a valid uplink coming from 'from'.
       */
      private boolean isValidUplink(TrieEntry<K, V> next, TrieEntry<K, V> from) {
          return next != null && next.bitIndex <= from.bitIndex && !next.isEmpty();
      }
  
      /**
       * Returns the length of the key, or 0 if the key is null.
       */
      private int length(K key) {
          if (key == null) {
              return 0;
          }
  
          return keyAnalyzer.length(key);
      }
  
      /**
       * Returns whether or not the given bit on the
       * key is set, or false if the key is null
       */
      private boolean isBitSet(K key, int keyLength, int bitIndex) {
          if (key == null) { // root's might be null!
              return false;
          }
          return keyAnalyzer.isBitSet(key, keyLength, bitIndex);
      }
  
      /**
       * Utility method for calling
       * keyAnalyzer.bitIndex(key, 0, length(key), foundKey, 0, length(foundKey))
       */
      private int bitIndex(K key, K foundKey) {
          return keyAnalyzer.bitIndex(key, 0, length(key), foundKey, 0, length(foundKey));
      }
  
      Iterator<K> newKeyIterator() {
          return new KeyIterator();
      }
  
      Iterator<V> newValueIterator() {
          return new ValueIterator();
      }
  
      Iterator<Map.Entry<K, V>> newEntryIterator() {
          return new EntryIterator();
      }
  
      /**
       * Returns a set view of the keys contained in this map.  The set is
       * backed by the map, so changes to the map are reflected in the set, and
       * vice-versa.  The set supports element removal, which removes the
       * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
       * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
       * <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
       * <tt>addAll</tt> operations.
       *
       * @return a set view of the keys contained in this map.
       */
      @Override
      public Set<K> keySet() {
          Set<K> ks = keySet;
          return (ks != null ? ks : (keySet = new KeySet()));
      }
  
      /**
       * Returns a collection view of the values contained in this map. The
       * collection is backed by the map, so changes to the map are reflected in
       * the collection, and vice-versa. The collection supports element
       * removal, which removes the corresponding mapping from this map, via the
       * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
       * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
       * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
       *
       * @return a collection view of the values contained in this map.
       */
      @Override
      public Collection<V> values() {
          Collection<V> vs = values;
          return (vs != null ? vs : (values = new Values()));
      }
  
      /**
       * Returns the first entry the Trie is storing.
       * <p>
       * This is implemented by going always to the left until
       * we encounter a valid uplink. That uplink is the first key.
       */
      private TrieEntry<K, V> firstEntry() {
          // if Trie is empty, no first node.
          if (isEmpty())
              return null;
  
          return followLeft(root);
      }
  
      /**
       * Goes left through the tree until it finds a valid node.
       */
      private TrieEntry<K, V> followLeft(TrieEntry<K, V> node) {
          while (true) {
              TrieEntry<K, V> child = node.left;
              // if we hit root and it didn't have a node, go right instead.
              if (child.isEmpty())
                  child = node.right;
  
              if (child.bitIndex <= node.bitIndex)
                  return child;
  
              node = child;
          }
      }
  
      /**
       * Returns the last entry the 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.
       */
      private TrieEntry<K, V> lastEntry() {
          return followRight(root.left);
      }
  
      /**
       * Traverses down the right path until it finds an uplink.
       */
      protected TrieEntry<K, V> followRight(TrieEntry<K, V> node) {
          // if Trie is empty, no last entry.
          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;
      }
  
      public K firstKey() {
          return firstEntry().getKey();
      }
  
      public SortedMap<K, V> headMap(K toKey) {
          return new SubMap(null, toKey);
      }
  
      public K lastKey() {
          TrieEntry<K, V> entry = lastEntry();
          if (entry != null)
              return entry.getKey();
          else
              return null;
      }
  
      public SortedMap<K, V> subMap(K fromKey, K toKey) {
          return new SubMap(fromKey, toKey);
      }
  
      public SortedMap<K, V> tailMap(K fromKey) {
          return new SubMap(fromKey, null);
      }
  
      /**
       * Returns an entry strictly higher than the given key,
       * or null if no such entry exists.
       */
      protected TrieEntry<K, V> higherEntry(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
          //       functions to perform the search.)
          int keyLength = length(key);
  
          if (keyLength == 0) {
              if (!root.isEmpty()) {
                  // If data in root, and more after -- return it.
                  if (size() > 1) {
                      return nextEntry(root);
                  } else { // If no more after, no higher entry.
                      return null;
                  }
              } else {
                  // Root is empty & we want something after empty, return first.
                  return firstEntry();
              }
          }
  
          TrieEntry<K, V> found = getNearestEntryForKey(key, keyLength);
          if (key.equals(found.key))
              return nextEntry(found);
  
          int bitIndex = bitIndex(key, found.key);
          if (isValidBitIndex(bitIndex)) {
              TrieEntry<K, V> added = new TrieEntry<>(key, null, bitIndex);
              addEntry(added, keyLength);
              incrementSize(); // must increment because remove will decrement
              TrieEntry<K, V> ceil = nextEntry(added);
              removeEntry(added);
              modCount -= 2; // we didn't really modify it.
              return ceil;
          } else if (isNullBitKey(bitIndex)) {
              if (!root.isEmpty())
                  return firstEntry();
              else if (size() > 1)
                  return nextEntry(firstEntry());
              else
                  return null;
          } else if (isEqualBitKey(bitIndex)) {
              return nextEntry(found);
          }
  
          // 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.
       */
      protected TrieEntry<K, V> ceilingEntry(K key) {
          // Basically:
          // Follow the steps of adding an entry, but instead...
          //
          // - If we ever encounter a situation where we found an equal
          //   key, we return it immediately.
          //
          // - If we hit an empty root, return the first iterable item.
          //
          // - If we have to add a new item, we temporarily add it,
          //   find the successor to it, then remove the added item.
          //
          // 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
          //       functions to perform the search.)
          int keyLength = length(key);
  
          if (keyLength == 0) {
              if (!root.isEmpty())
                  return root;
              else
                  return firstEntry();
          }
  
          TrieEntry<K, V> found = getNearestEntryForKey(key, keyLength);
          if (key.equals(found.key))
              return found;
  
          int bitIndex = bitIndex(key, found.key);
          if (isValidBitIndex(bitIndex)) {
              TrieEntry<K, V> added = new TrieEntry<>(key, null, bitIndex);
              addEntry(added, keyLength);
              incrementSize(); // must increment because remove will decrement
              TrieEntry<K, V> ceil = nextEntry(added);
              removeEntry(added);
              modCount -= 2; // we didn't really modify it.
              return ceil;
          } else if (isNullBitKey(bitIndex)) {
              if (!root.isEmpty())
                  return root;
              else
                  return firstEntry();
          } else if (isEqualBitKey(bitIndex)) {
              return found;
          }
  
          // 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.
       */
      protected TrieEntry<K, V> lowerEntry(K key) {
          // Basically:
          // Follow the steps of adding an entry, but instead...
          //
          // - If we ever encounter a situation where we found an equal
          //   key, we return it's previousEntry immediately.
          //
          // - If we hit root (empty or not), return null.
          //
          // - If we have to add a new item, we temporarily add it,
          //   find the previousEntry to it, then remove the added item.
          //
          // 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
          //       functions to perform the search.)
          int keyLength = length(key);
  
          if (keyLength == 0) {
              return null; // there can never be anything before root.
          }
  
          TrieEntry<K, V> found = getNearestEntryForKey(key, keyLength);
          if (key.equals(found.key))
              return previousEntry(found);
  
          int bitIndex = bitIndex(key, found.key);
          if (isValidBitIndex(bitIndex)) {
              TrieEntry<K, V> added = new TrieEntry<>(key, null, bitIndex);
              addEntry(added, keyLength);
              incrementSize(); // must increment because remove will decrement
              TrieEntry<K, V> prior = previousEntry(added);
              removeEntry(added);
              modCount -= 2; // we didn't really modify it.
              return prior;
          } else if (isNullBitKey(bitIndex)) {
              return null;
          } else if (isEqualBitKey(bitIndex)) {
              return previousEntry(found);
          }
  
          // 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.
       */
      protected TrieEntry<K, V> floorEntry(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
          //       functions to perform the search.)
          int keyLength = length(key);
  
          if (keyLength == 0) {
              if (!root.isEmpty())
                  return root;
              else
                  return null;
          }
  
          TrieEntry<K, V> found = getNearestEntryForKey(key, keyLength);
          if (key.equals(found.key))
              return found;
  
          int bitIndex = bitIndex(key, found.key);
          if (isValidBitIndex(bitIndex)) {
              TrieEntry<K, V> added = new TrieEntry<>(key, null, bitIndex);
              addEntry(added, keyLength);
              incrementSize(); // must increment because remove will decrement
              TrieEntry<K, V> floor = previousEntry(added);
              removeEntry(added);
              modCount -= 2; // we didn't really modify it.
              return floor;
          } else if (isNullBitKey(bitIndex)) {
              if (!root.isEmpty())
                  return root;
              else
                  return null;
          } else if (isEqualBitKey(bitIndex)) {
              return found;
          }
  
          // we should have exited above.
          throw new IllegalStateException("invalid lookup: " + key);
      }
  
      /**
       * Finds the subtree that contains the prefix.
       * <p>
       * This is very similar to getR but with the difference that
       * we stop the lookup if h.bitIndex > keyLength.
       */
      private TrieEntry<K, V> subtree(K prefix, int offset, int length) {
          TrieEntry<K, V> current = root.left;
          TrieEntry<K, V> path = root;
          while (true) {
              if (current.bitIndex <= path.bitIndex || length < current.bitIndex)
                  break;
  
              path = current;
              if (!isBitSet(prefix, length + offset, current.bitIndex + offset)) {
                  current = current.left;
              } else {
                  current = current.right;
              }
          }
  
          // Make sure the entry is valid for a subtree.
          TrieEntry<K, V> entry = current.isEmpty() ? path : current;
  
          // If entry is root, it can't be empty.
          if (entry.isEmpty())
              return null;
  
          int offsetLength = offset + length;
  
          // 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
          //  string and we want to lookup things with "\0")
          if (entry == root && length(entry.getKey()) < offsetLength)
              return null;
  
          // Found key's length-th bit differs from our key
          // which means it cannot be the prefix...
          if (isBitSet(prefix, offsetLength, offsetLength) !=
                  isBitSet(entry.key, length(entry.key), length)) {
              return null;
          }
  
          // ... or there are less than 'length' equal bits
          int bitIndex = keyAnalyzer.bitIndex(prefix, offset, length,
                  entry.key, 0, length(entry.getKey()));
          if (bitIndex >= 0 && bitIndex < length)
              return null;
  
          return entry;
      }
  
      /**
       * Defines the interface to analyze {@link Trie} keys on a bit
       * level. <code>KeyAnalyzer</code>'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 EQUAL_BIT_KEY).
       * <p>
       * <code>KeyAnalyzer</code> defines:<br>
       * <table cellspace="5">
       * <tr><td>NULL_BIT_KEY</td><td>When key's bits are all zero</td></tr>
       * <tr><td> EQUAL_BIT_KEY </td><td>When keys are the same </td></tr>
       * </table>
       */
      public interface KeyAnalyzer<K> extends Comparator<K>, Serializable {
  
          /**
           * Returned by bitIndex if key's bits are all 0
           */
          int NULL_BIT_KEY = -1;
  
          /**
           * Returned by bitIndex if key and found key are
           * equal. This is a very very specific case and
           * shouldn't happen on a regular basis
           */
          int EQUAL_BIT_KEY = -2;
  
          /**
           * Returns the length of the Key in bits.
           */
          int length(K key);
  
          /**
           * Returns whether or not a bit is set
           */
          boolean isBitSet(K key, int keyLength, int bitIndex);
  
          /**
           * Returns the n-th different bit between key and found.
           * This starts the comparison in key at 'keyStart' and goes
           * for 'keyLength' bits, and compares to the found key
           * starting at 'foundStart' and going for 'foundLength' bits.
           */
          int bitIndex(K key, int keyStart, int keyLength,
                       K found, int foundStart, int foundLength);
  
          /**
           * Returns the number of bits per element in the key.
           * This is only useful for variable-length keys, such as Strings.
           */
          int bitsPerElement();
  
          /**
           * Determines whether or not the given prefix (from offset to length)
           * is a prefix of the given key.
           */
          boolean isPrefix(K prefix, int offset, int length, K key);
      }
  
      /**
       * The actual Trie nodes.
       */
      private static class TrieEntry<K, V> implements Map.Entry<K, V>, Serializable {
  
          private static final long serialVersionUID = 4596023148184140013L;
  
          private K key;
          private V value;
  
          /**
           * The index this entry is comparing.
           */
          private int bitIndex;
  
          /**
           * The parent of this entry.
           */
          private TrieEntry<K, V> parent;
          /**
           * The left child of this entry.
           */
          private TrieEntry<K, V> left;
          /**
           * The right child of this entry.
           */
          private TrieEntry<K, V> right;
          /**
           * The entry who uplinks to this entry.
           */
          private TrieEntry<K, V> predecessor;
  
          private TrieEntry(K key, V value, int bitIndex) {
              this.key = key;
              this.value = value;
  
              this.bitIndex = bitIndex;
  
              this.parent = null;
              this.left = this;
              this.right = null;
              this.predecessor = this;
          }
  
          @Override
          public boolean equals(Object o) {
              if (o == this) {
                  return true;
              } else if (o instanceof Map.Entry) {
                  Map.Entry e = (Map.Entry) o;
                  Object k1 = getKey();
                  Object k2 = e.getKey();
                  if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                      Object v1 = getValue();
                      Object v2 = e.getValue();
                      if (v1 == v2 || (v1 != null && v1.equals(v2)))
                          return true;
                  }
                  return false;
              } else {
                  return false;
              }
          }
  
          /**
           * Whether or not the entry is storing a key.
           * Only the root can potentially be empty, all other
           * nodes must have a key.
           */
          public boolean isEmpty() {
              return key == null;
          }
  
          public K getKey() {
              return key;
          }
  
          public V getValue() {
              return value;
          }
  
          public V setValue(V value) {
              V o = this.value;
              this.value = value;
              return o;
          }
  
          /**
           * Replaces the old key and value with the new ones.
           * Returns the old vlaue.
           */
          private V setKeyValue(K key, V value) {
              this.key = key;
              return setValue(value);
          }
  
          /**
           * Neither the left nor right child is a loopback
           */
          private boolean isInternalNode() {
              return left != this && right != this;
          }
  
          /**
           * Either the left or right child is a loopback
           */
          private boolean isExternalNode() {
              return !isInternalNode();
          }
  
          @Override
          public String toString() {
              StringBuilder buffer = new StringBuilder();
  
              if (bitIndex == -1) {
                  buffer.append("RootEntry(");
              } else {
                  buffer.append("Entry(");
              }
  
              buffer.append("key=").append(getKey()).append(" [").append(bitIndex).append("], ");
              buffer.append("value=").append(getValue()).append(", ");
              //buffer.append("bitIndex=").append(bitIndex).append(", ");
  
              if (parent != null) {
                  if (parent.bitIndex == -1) {
                      buffer.append("parent=").append("ROOT");
                  } else {
                      buffer.append("parent=").append(parent.getKey()).append(" [").append(parent.bitIndex).append(']');
                  }
              } else {
                  buffer.append("parent=").append("null");
              }
              buffer.append(", ");
  
              if (left != null) {
                  if (left.bitIndex == -1) {
                      buffer.append("left=").append("ROOT");
                  } else {
                      buffer.append("left=").append(left.getKey()).append(" [").append(left.bitIndex).append(']');
                  }
              } else {
                  buffer.append("left=").append("null");
              }
              buffer.append(", ");
  
              if (right != null) {
                  if (right.bitIndex == -1) {
                      buffer.append("right=").append("ROOT");
                  } else {
                      buffer.append("right=").append(right.getKey()).append(" [").append(right.bitIndex).append(']');
                  }
              } else {
                  buffer.append("right=").append("null");
              }
              buffer.append(", ");
  
              if (predecessor != null) {
                  if (predecessor.bitIndex == -1) {
                      buffer.append("predecessor=").append("ROOT");
                  } else {
                      buffer.append("predecessor=").append(predecessor.getKey()).append(" [").append(predecessor.bitIndex).append(']');
                  }
              }
  
              buffer.append(')');
              return buffer.toString();
          }
      }
  
      /**
       * An iterator that stores a single TrieEntry.
       */
      private class SingletonIterator implements Iterator<Map.Entry<K, V>> {
          private final TrieEntry<K, V> entry;
          private int hit = 0;
  
          public SingletonIterator(TrieEntry<K, V> entry) {
              this.entry = entry;
          }
  
          public boolean hasNext() {
              return hit == 0;
          }
  
          public Map.Entry<K, V> next() {
              if (hit != 0)
                  throw new NoSuchElementException();
              hit++;
              return entry;
          }
  
          public void remove() {
              if (hit != 1)
                  throw new IllegalStateException();
              hit++;
              PatriciaTrie.this.removeEntry(entry);
          }
  
      }
  
      /**
       * An iterator for the entries.
       */
      private abstract class NodeIterator<E> implements Iterator<E> {
          protected int expectedModCount = modCount;   // For fast-fail
          protected TrieEntry<K, V> next; // the next node to return
          protected TrieEntry<K, V> current; // the current entry we're on
  
          // Starts iteration from the beginning.
          protected NodeIterator() {
              next = PatriciaTrie.this.nextEntry(null);
          }
  
          // Starts iteration at the given entry.
          protected NodeIterator(TrieEntry<K, V> firstEntry) {
              next = firstEntry;
          }
  
          public boolean hasNext() {
              return next != null;
          }
  
          TrieEntry<K, V> nextEntry() {
              if (modCount != expectedModCount)
                  throw new ConcurrentModificationException();
              TrieEntry<K, V> e = next;
              if (e == null)
                  throw new NoSuchElementException();
  
              next = findNext(e);
              current = e;
              return e;
          }
  
          protected TrieEntry<K, V> findNext(TrieEntry<K, V> prior) {
              return PatriciaTrie.this.nextEntry(prior);
          }
  
          public void remove() {
              if (current == null)
                  throw new IllegalStateException();
              if (modCount != expectedModCount)
                  throw new ConcurrentModificationException();
  
              TrieEntry<K, V> node = current;
              current = null;
              PatriciaTrie.this.removeEntry(node);
  
              expectedModCount = modCount;
          }
      }
  
      private class ValueIterator extends NodeIterator<V> {
          public V next() {
              return nextEntry().value;
          }
      }
  
      private class KeyIterator extends NodeIterator<K> {
          public K next() {
              return nextEntry().getKey();
          }
      }
  
      private class EntryIterator extends NodeIterator<Map.Entry<K, V>> {
          public Map.Entry<K, V> next() {
              return nextEntry();
          }
      }
  
      /**
       * An iterator for iterating over a prefix search.
       */
      private class PrefixEntryIterator extends NodeIterator<Map.Entry<K, V>> {
          // values to reset the subtree if we remove it.
          protected final K prefix;
          protected final int offset;
          protected final int length;
          protected boolean lastOne;
  
          protected TrieEntry<K, V> subtree; // the subtree to search within
  
          // Starts iteration at the given entry & search only within the given subtree.
          PrefixEntryIterator(TrieEntry<K, V> startScan, K prefix, int offset, int length) {
              subtree = startScan;
              next = PatriciaTrie.this.followLeft(startScan);
              this.prefix = prefix;
              this.offset = offset;
              this.length = length;
          }
  
          public Map.Entry<K, V> next() {
              Map.Entry<K, V> entry = nextEntry();
              if (lastOne)
                  next = null;
              return entry;
          }
  
          @Override
          protected TrieEntry<K, V> findNext(TrieEntry<K, V> prior) {
              return PatriciaTrie.this.nextEntryInSubtree(prior, subtree);
          }
  
          @Override
          public void remove() {
              // If the current entry we're removing is the subtree
              // then we need to find a new subtree parent.
              boolean needsFixing = false;
              int bitIdx = subtree.bitIndex;
              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, length);
  
              // If the subtree's bitIndex is less than the
              // length of our prefix, it's the last item
              // in the prefix tree.
  