content: /*
   * Copyright 2005-2010 Roger Kapsi, Sam Berlin
   *
   *   Licensed under the Apache License, Version 2.0 (the "License");
   *   you may not use this file except in compliance with the License.
   *   You may obtain a copy of the License at
   *
   *       http://www.apache.org/licenses/LICENSE-2.0
   *
   *   Unless required by applicable law or agreed to in writing, software
   *   distributed under the License is distributed on an "AS IS" BASIS,
   *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   *   See the License for the specific language governing permissions and
   *   limitations under the License.
   */
  
  package org.apache.cassandra.index.sasi.utils.trie;
  
  import java.io.Serializable;
  import java.util.*;
  
  /**
   * This class is taken from https://github.com/rkapsi/patricia-trie (v0.6), and slightly modified
   * to correspond to Cassandra code style, as the only Patricia Trie implementation,
   * which supports pluggable key comparators (e.g. commons-collections PatriciaTrie (which is based
   * on rkapsi/patricia-trie project) only supports String keys)
   * but unfortunately is not deployed to the maven central as a downloadable artifact.
   */
  
  /**
   * <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
   * 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 {@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>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>
   *
   * @author Roger Kapsi
   * @author Sam Berlin
   */
  public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Serializable
  {
      private static final long serialVersionUID = -2246014692353432660L;
  
      public PatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer)
      {
          super(keyAnalyzer);
      }
  
      public PatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer, Map<? extends K, ? extends V> m)
      {
          super(keyAnalyzer, m);
      }
  
      @Override
      public Comparator<? super K> comparator()
      {
          return keyAnalyzer;
      }
  
      @Override
      public SortedMap<K, V> prefixMap(K prefix)
      {
          return lengthInBits(prefix) == 0 ? this : new PrefixRangeMap(prefix);
      }
  
      @Override
      public K firstKey()
      {
          return firstEntry().getKey();
      }
  
      @Override
      public K lastKey()
      {
          TrieEntry<K, V> entry = lastEntry();
          return entry != null ? entry.getKey() : null;
      }
  
      @Override
      public SortedMap<K, V> headMap(K toKey)
      {
          return new RangeEntryMap(null, toKey);
      }
  
      @Override
      public SortedMap<K, V> subMap(K fromKey, K toKey)
      {
          return new RangeEntryMap(fromKey, toKey);
      }
  
      @Override
      public SortedMap<K, V> tailMap(K fromKey)
      {
          return new RangeEntryMap(fromKey, null);
      }
  
      /**
       * Returns an entry strictly higher than the given key,
       * or null if no such entry exists.
       */
      private 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 lengthInBits = lengthInBits(key);
  
          if (lengthInBits == 0)
          {
              if (!root.isEmpty())
              {
                  // If data in root, and more after -- return it.
                  return size() > 1 ? nextEntry(root) : null;
              }
              else
              {
                  // Root is empty & we want something after empty, return first.
                  return firstEntry();
              }
          }
  
          TrieEntry<K, V> found = getNearestEntryForKey(key);
          if (compareKeys(key, found.key))
              return nextEntry(found);
  
          int bitIndex = bitIndex(key, found.key);
          if (Tries.isValidBitIndex(bitIndex))
          {
              return replaceCeil(key, bitIndex);
          }
          else if (Tries.isNullBitKey(bitIndex))
          {
              if (!root.isEmpty())
              {
                  return firstEntry();
              }
              else if (size() > 1)
              {
                  return nextEntry(firstEntry());
              }
              else
              {
                  return null;
              }
          }
          else if (Tries.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.
       */
      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 lengthInBits = lengthInBits(key);
  
          if (lengthInBits == 0)
          {
              if (!root.isEmpty())
              {
                  return root;
              }
              else
              {
                  return firstEntry();
              }
          }
  
          TrieEntry<K, V> found = getNearestEntryForKey(key);
          if (compareKeys(key, found.key))
              return found;
  
          int bitIndex = bitIndex(key, found.key);
          if (Tries.isValidBitIndex(bitIndex))
          {
              return replaceCeil(key, bitIndex);
          }
          else if (Tries.isNullBitKey(bitIndex))
          {
              if (!root.isEmpty())
              {
                  return root;
              }
              else
              {
                  return firstEntry();
              }
          }
          else if (Tries.isEqualBitKey(bitIndex))
          {
              return found;
          }
  
          // we should have exited above.
          throw new IllegalStateException("invalid lookup: " + key);
      }
  
      private TrieEntry<K, V> replaceCeil(K key, int bitIndex)
      {
          TrieEntry<K, V> added = new TrieEntry<>(key, null, bitIndex);
          addEntry(added);
          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;
      }
  
      private TrieEntry<K, V> replaceLower(K key, int bitIndex)
      {
          TrieEntry<K, V> added = new TrieEntry<>(key, null, bitIndex);
          addEntry(added);
          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;
      }
  
      /**
       * Returns a key-value mapping associated with the greatest key
       * strictly less than the given key, or null if there is no such key.
       */
      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 lengthInBits = lengthInBits(key);
  
          if (lengthInBits == 0)
              return null; // there can never be anything before root.
  
          TrieEntry<K, V> found = getNearestEntryForKey(key);
          if (compareKeys(key, found.key))
              return previousEntry(found);
  
          int bitIndex = bitIndex(key, found.key);
          if (Tries.isValidBitIndex(bitIndex))
          {
              return replaceLower(key, bitIndex);
          }
          else if (Tries.isNullBitKey(bitIndex))
          {
              return null;
          }
          else if (Tries.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.
       */
      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 lengthInBits = lengthInBits(key);
  
          if (lengthInBits == 0)
          {
              return !root.isEmpty() ? root : null;
          }
  
          TrieEntry<K, V> found = getNearestEntryForKey(key);
          if (compareKeys(key, found.key))
              return found;
  
          int bitIndex = bitIndex(key, found.key);
          if (Tries.isValidBitIndex(bitIndex))
          {
              return replaceLower(key, bitIndex);
          }
          else if (Tries.isNullBitKey(bitIndex))
          {
              if (!root.isEmpty())
              {
                  return root;
              }
              else
              {
                  return null;
              }
          }
          else if (Tries.isEqualBitKey(bitIndex))
          {
              return found;
          }
  
          // 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.
       */
      private TrieEntry<K, V> subtree(K prefix)
      {
          int lengthInBits = lengthInBits(prefix);
  
          TrieEntry<K, V> current = root.left;
          TrieEntry<K, V> path = root;
          while(true)
          {
              if (current.bitIndex <= path.bitIndex || lengthInBits < current.bitIndex)
                  break;
  
              path = current;
              current = !isBitSet(prefix, current.bitIndex)
                      ? current.left : 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;
  
          // 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 && lengthInBits(entry.getKey()) < lengthInBits)
              return null;
  
          // Found key's length-th bit differs from our key
          // which means it cannot be the prefix...
          if (isBitSet(prefix, lengthInBits) != isBitSet(entry.key, lengthInBits))
              return null;
  
          // ... or there are less than 'length' equal bits
          int bitIndex = bitIndex(prefix, entry.key);
          return (bitIndex >= 0 && bitIndex < lengthInBits) ? null : 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.
       */
      private TrieEntry<K, V> lastEntry()
      {
          return followRight(root.left);
      }
  
      /**
       * Traverses down the right path until it finds an uplink.
       */
      private 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;
      }
  
      /**
       * 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
       *        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 the start entry
       */
      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)
          {
              return isValidUplink(start.predecessor.left, start.predecessor)
                      ? start.predecessor.left
                      : followRight(start.predecessor.left);
          }
  
          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)
              {
                  return root.isEmpty() ? null : 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.
       *
       * 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)
      {
          return (node == null) ? firstEntry() : nextEntryImpl(node.predecessor, node, parentOfSubtree);
      }
  
      private boolean isPrefix(K key, K prefix)
      {
          return keyAnalyzer.isPrefix(key, prefix);
      }
  
      /**
       * A range view of the {@link Trie}
       */
      private abstract class RangeMap extends AbstractMap<K, V> implements SortedMap<K, V>
      {
          /**
           * The {@link #entrySet()} view
           */
          private transient volatile Set<Map.Entry<K, V>> entrySet;
  
          /**
           * Creates and returns an {@link #entrySet()}
           * view of the {@link RangeMap}
           */
          protected abstract Set<Map.Entry<K, V>> createEntrySet();
  
          /**
           * 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();
  
  
          @Override
          public Comparator<? super K> comparator()
          {
              return PatriciaTrie.this.comparator();
          }
  
          @Override
          public boolean containsKey(Object key)
          {
              return inRange(Tries.<K>cast(key)) && PatriciaTrie.this.containsKey(key);
          }
  
          @Override
          public V remove(Object key)
          {
              return (!inRange(Tries.<K>cast(key))) ? null : PatriciaTrie.this.remove(key);
          }
  
          @Override
          public V get(Object key)
          {
              return (!inRange(Tries.<K>cast(key))) ? null : PatriciaTrie.this.get(key);
          }
  
          @Override
          public V put(K key, V value)
          {
              if (!inRange(key))
                  throw new IllegalArgumentException("Key is out of range: " + key);
  
              return PatriciaTrie.this.put(key, value);
          }
  
          @Override
          public Set<Map.Entry<K, V>> entrySet()
          {
              if (entrySet == null)
                  entrySet = createEntrySet();
              return entrySet;
          }
  
          @Override
          public SortedMap<K, V> subMap(K fromKey, K toKey)
          {
              if (!inRange2(fromKey))
                  throw new IllegalArgumentException("FromKey is out of range: " + fromKey);
  
              if (!inRange2(toKey))
                  throw new IllegalArgumentException("ToKey is out of range: " + toKey);
  
              return createRangeMap(fromKey, isFromInclusive(), toKey, isToInclusive());
          }
  
          @Override
          public SortedMap<K, V> headMap(K toKey)
          {
              if (!inRange2(toKey))
                  throw new IllegalArgumentException("ToKey is out of range: " + toKey);
  
              return createRangeMap(getFromKey(), isFromInclusive(), toKey, isToInclusive());
          }
  
          @Override
          public SortedMap<K, V> tailMap(K fromKey)
          {
              if (!inRange2(fromKey))
                  throw new IllegalArgumentException("FromKey is out of range: " + fromKey);
  
              return createRangeMap(fromKey, isFromInclusive(), getToKey(), isToInclusive());
          }
  
          /**
           * Returns true if the provided key is greater than TO and
           * less than FROM
           */
          protected boolean inRange(K key)
          {
              K fromKey = getFromKey();
              K toKey = getToKey();
  
              return (fromKey == null || inFromRange(key, false))
                      && (toKey == null || inToRange(key, false));
          }
  
          /**
           * This form allows the high endpoint (as well as all legit keys)
           */
          protected boolean inRange2(K key)
          {
              K fromKey = getFromKey();
              K toKey = getToKey();
  
              return (fromKey == null || inFromRange(key, false))
                      && (toKey == null || inToRange(key, true));
          }
  
          /**
           * Returns true if the provided key is in the FROM range
           * of the {@link RangeMap}
           */
          protected boolean inFromRange(K key, boolean forceInclusive)
          {
              K fromKey = getFromKey();
              boolean fromInclusive = isFromInclusive();
  
              int ret = keyAnalyzer.compare(key, fromKey);
              return (fromInclusive || forceInclusive) ? ret >= 0 : ret > 0;
          }
  
          /**
           * Returns true if the provided key is in the TO range
           * of the {@link RangeMap}
           */
          protected boolean inToRange(K key, boolean forceInclusive)
          {
              K toKey = getToKey();
              boolean toInclusive = isToInclusive();
  
              int ret = keyAnalyzer.compare(key, toKey);
              return (toInclusive || forceInclusive) ? ret <= 0 : ret < 0;
          }
  
          /**
           * Creates and returns a sub-range view of the current {@link RangeMap}
           */
          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.
          */
         protected final K fromKey;
  
         /**
          * The key to end at, null if till the end.
          */
         protected final K toKey;
  
         /**
          * Whether or not the 'from' is inclusive.
          */
         protected final boolean fromInclusive;
  
         /**
          * Whether or not the 'to' is inclusive.
          */
         protected final boolean toInclusive;
  
         /**
          * Creates a {@link RangeEntryMap} with the fromKey included and
          * the toKey excluded from the range
          */
         protected RangeEntryMap(K fromKey, K toKey)
         {
             this(fromKey, true, toKey, false);
         }
  
         /**
          * Creates a {@link RangeEntryMap}
          */
         protected RangeEntryMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
         {
             if (fromKey == null && toKey == null)
                 throw new IllegalArgumentException("must have a from or to!");
  
             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;
         }
  
  
         @Override
         public K firstKey()
         {
             Map.Entry<K,V> e  = fromKey == null
                  ? firstEntry()
                  : fromInclusive ? ceilingEntry(fromKey) : higherEntry(fromKey);
  
             K first = e != null ? e.getKey() : null;
             if (e == null || toKey != null && !inToRange(first, false))
                 throw new NoSuchElementException();
  
             return first;
         }
  
  
         @Override
         public K lastKey()
         {
             Map.Entry<K,V> e = toKey == null
                  ? lastEntry()
                  : toInclusive ? floorEntry(toKey) : lowerEntry(toKey);
  
             K last = e != null ? e.getKey() : null;
             if (e == null || fromKey != null && !inFromRange(last, false))
                 throw new NoSuchElementException();
  
             return last;
         }
  
         @Override
         protected Set<Entry<K, V>> createEntrySet()
         {
             return new RangeEntrySet(this);
         }
  
         @Override
         public K getFromKey()
         {
             return fromKey;
         }
  
         @Override
         public K getToKey()
         {
             return toKey;
         }
  
         @Override
         public boolean isFromInclusive()
         {
             return fromInclusive;
         }
  
         @Override
         public boolean isToInclusive()
         {
             return toInclusive;
         }
  
         @Override
         protected SortedMap<K, V> createRangeMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
         {
             return new RangeEntryMap(fromKey, fromInclusive, toKey, toInclusive);
         }
     }
  
      /**
       * A {@link Set} view of a {@link RangeMap}
       */
      private class RangeEntrySet extends AbstractSet<Map.Entry<K, V>>
      {
  
          private final RangeMap delegate;
  
          private int size = -1;
  
          private int expectedModCount = -1;
  
          /**
           * Creates a {@link RangeEntrySet}
           */
          public RangeEntrySet(RangeMap delegate)
          {
              if (delegate == null)
                  throw new NullPointerException("delegate");
  
              this.delegate = delegate;
          }
  
          @Override
          public Iterator<Map.Entry<K, V>> iterator()
          {
              K fromKey = delegate.getFromKey();
              K toKey = delegate.getToKey();
  
              TrieEntry<K, V> first = fromKey == null ? firstEntry() : ceilingEntry(fromKey);
              TrieEntry<K, V> last = null;
              if (toKey != null)
                  last = ceilingEntry(toKey);
  
              return new EntryIterator(first, last);
          }
  
          @Override
          public int size()
          {
              if (size == -1 || expectedModCount != PatriciaTrie.this.modCount)
              {
                  size = 0;
  
                  for (Iterator<?> it = iterator(); it.hasNext(); it.next())
                  {
                      ++size;
                  }
  
                  expectedModCount = PatriciaTrie.this.modCount;
              }
  
              return size;
          }
  
          @Override
          public boolean isEmpty()
          {
              return !iterator().hasNext();
          }
  
          @Override
          public boolean contains(Object o)
          {
              if (!(o instanceof Map.Entry<?, ?>))
                  return false;
  
              @SuppressWarnings("unchecked")
              Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
              K key = entry.getKey();
              if (!delegate.inRange(key))
                  return false;
  
              TrieEntry<K, V> node = getEntry(key);
              return node != null && Tries.areEqual(node.getValue(), entry.getValue());
          }
  
          @Override
          public boolean remove(Object o)
          {
              if (!(o instanceof Map.Entry<?, ?>))
                  return false;
  
              @SuppressWarnings("unchecked")
              Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
              K key = entry.getKey();
              if (!delegate.inRange(key))
                  return false;
  
              TrieEntry<K, V> node = getEntry(key);
              if (node != null && Tries.areEqual(node.getValue(), entry.getValue()))
              {
                  removeEntry(node);
                  return true;
              }
  
              return false;
          }
  
          /**
           * 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(TrieEntry<K,V> first, TrieEntry<K,V> last)
              {
                  super(first);
                  this.excludedKey = (last != null ? last.getKey() : null);
              }
  
              @Override
              public boolean hasNext()
              {
                  return next != null && !Tries.areEqual(next.key, excludedKey);
              }
  
              @Override
              public Map.Entry<K,V> next()
              {
                  if (next == null || Tries.areEqual(next.key, excludedKey))
                      throw new NoSuchElementException();
  
                  return nextEntry();
              }
          }
      }
  
      /**
       * A submap used for prefix views over the {@link Trie}.
       */
      private class PrefixRangeMap extends RangeMap
      {
  
          private final K prefix;
  
          private K fromKey = null;
  
          private K toKey = null;
  
          private int expectedModCount = -1;
  
          private int size = -1;
  
          /**
           * Creates a {@link PrefixRangeMap}
           */
          private PrefixRangeMap(K prefix)
          {
              this.prefix = prefix;
          }
  
          /**
           * 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
           * time the {@link Trie} has changed.
           */
          private int fixup()
          {
              // The trie has changed since we last
              // found our toKey / fromKey
              if (size == - 1 || PatriciaTrie.this.modCount != expectedModCount)
              {
                  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)
                  {
                      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;
          }
  
          @Override
          public K firstKey()
          {
              fixup();
  
              Map.Entry<K,V> e = fromKey == null ? firstEntry() : higherEntry(fromKey);
              K first = e != null ? e.getKey() : null;
              if (e == null || !isPrefix(first, prefix))
                  throw new NoSuchElementException();
  
              return first;
          }
  
          @Override
          public K lastKey()
          {
              fixup();
  
              Map.Entry<K,V> e = toKey == null ? lastEntry() : lowerEntry(toKey);
              K last = e != null ? e.getKey() : null;
              if (e == null || !isPrefix(last, prefix))
                  throw new NoSuchElementException();
  
              return last;
          }
  
          /**
           * Returns true if this {@link PrefixRangeMap}'s key is a prefix
           * of the provided key.
           */
          @Override
          protected boolean inRange(K key)
          {
              return isPrefix(key, prefix);
          }
  
          /**
           * Same as {@link #inRange(Object)}
           */
          @Override
          protected boolean inRange2(K key)
          {
              return inRange(key);
          }
  
          /**
           * Returns true if the provided Key is in the FROM range
           * of the {@link PrefixRangeMap}
           */
          @Override
          protected boolean inFromRange(K key, boolean forceInclusive)
          {
              return isPrefix(key, prefix);
          }
  
          /**
           * Returns true if the provided Key is in the TO range
           * of the {@link PrefixRangeMap}
           */
          @Override
          protected boolean inToRange(K key, boolean forceInclusive)
          {
              return isPrefix(key, prefix);
          }
  
          @Override
          protected Set<Map.Entry<K, V>> createEntrySet()
          {
              return new PrefixRangeEntrySet(this);
          }
  
          @Override
          public K getFromKey()
          {
              return fromKey;
          }
  
          @Override
          public K getToKey()
          {
              return toKey;
          }
  
          @Override
          public boolean isFromInclusive()
          {
              return false;
          }
  
          @Override
          public boolean isToInclusive()
          {
              return false;
          }
  
          @Override
          protected SortedMap<K, V> createRangeMap(K fromKey, boolean fromInclusive,
                                                   K toKey, boolean toInclusive)
          {
              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 = -1;
  
          /**
           * Creates a {@link PrefixRangeEntrySet}
           */
          public PrefixRangeEntrySet(PrefixRangeMap delegate)
          {
              super(delegate);
              this.delegate = delegate;
          }
  
          @Override
          public int size()
          {
              return delegate.fixup();
          }
  
          @Override
          public Iterator<Map.Entry<K,V>> iterator()
          {
              if (PatriciaTrie.this.modCount != expectedModCount)
              {
                  prefixStart = subtree(delegate.prefix);
                  expectedModCount = PatriciaTrie.this.modCount;
              }
  
              if (prefixStart == null)
              {
                  Set<Map.Entry<K,V>> empty = Collections.emptySet();
                  return empty.iterator();
              }
              else if (lengthInBits(delegate.prefix) >= prefixStart.bitIndex)
              {
                  return new SingletonIterator(prefixStart);
              }
              else
              {
                  return new EntryIterator(prefixStart, delegate.prefix);
              }
          }
  
          /**
           * 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(TrieEntry<K, V> entry)
              {
                  this.entry = entry;
              }
  
              @Override
              public boolean hasNext()
              {
                  return hit == 0;
              }
  
              @Override
              public Map.Entry<K, V> next()
              {
                  if (hit != 0)
                      throw new NoSuchElementException();
  
                  ++hit;
                  return entry;
              }
  
  
              @Override
              public void remove()
              {
                  if (hit != 1)
                      throw new IllegalStateException();
  
                  ++hit;
                  PatriciaTrie.this.removeEntry(entry);
              }
          }
  
          /**
           * 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.
              protected final K prefix;
              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.
               */
              EntryIterator(TrieEntry<K, V> startScan, K prefix)
              {
                  subtree = startScan;
                  next = PatriciaTrie.this.followLeft(startScan);
                  this.prefix = prefix;
              }
  
              @Override
              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);
  
                  // If the subtree's bitIndex is less than the
                  // length of our prefix, it's the last item
                  // in the prefix tree.
                  if (lengthInBits(prefix) >= subtree.bitIndex)
                      lastOne = true;
              }
          }
      }
  }
  