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.
   */
  
  /**
   * 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.
   */
  
  package org.apache.cassandra.index.sasi.utils.trie;
  
  import java.util.AbstractCollection;
  import java.util.AbstractSet;
  import java.util.Collection;
  import java.util.ConcurrentModificationException;
  import java.util.Iterator;
  import java.util.Map;
  import java.util.NoSuchElementException;
  import java.util.Set;
  
  import org.apache.cassandra.index.sasi.utils.trie.Cursor.Decision;
  
  /**
   * This class implements the base PATRICIA algorithm and everything that
   * is related to the {@link Map} interface.
   */
  abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V>
  {
      private static final long serialVersionUID = -2303909182832019043L;
  
      /**
       * The root node of the {@link Trie}.
       */
      final TrieEntry<K, V> root = new TrieEntry<>(null, null, -1);
  
      /**
       * Each of these fields are initialized to contain an instance of the
       * appropriate view the first time this view is requested. The views are
       * stateless, so there's no reason to create more than one of each.
       */
      private transient volatile Set<K> keySet;
      private transient volatile Collection<V> values;
      private transient volatile Set<Map.Entry<K,V>> entrySet;
  
      /**
       * The current size of the {@link Trie}
       */
      private int size = 0;
  
      /**
       * The number of times this {@link Trie} has been modified.
       * It's used to detect concurrent modifications and fail-fast
       * the {@link Iterator}s.
       */
      transient int modCount = 0;
  
      public AbstractPatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer)
      {
          super(keyAnalyzer);
      }
  
      public AbstractPatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer, Map<? extends K, ? extends V> m)
      {
          super(keyAnalyzer);
          putAll(m);
      }
  
      @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();
      }
  
      @Override
      public int size()
      {
          return size;
      }
  
      /**
       * A helper method to increment the {@link Trie} size
       * and the modification counter.
       */
      void incrementSize()
      {
          size++;
          incrementModCount();
      }
  
      /**
       * A helper method to decrement the {@link Trie} size
       * and increment the modification counter.
       */
      void decrementSize()
      {
          size--;
          incrementModCount();
      }
  
      /**
       * A helper method to increment the modification counter.
       */
      private void incrementModCount()
      {
          ++modCount;
      }
  
      @Override
      public V put(K key, V value)
      {
          if (key == null)
              throw new NullPointerException("Key cannot be null");
  
          int lengthInBits = lengthInBits(key);
  
          // The only place to store a key with a length
          // of zero bits is the root node
          if (lengthInBits == 0)
          {
              if (root.isEmpty())
                  incrementSize();
              else
                  incrementModCount();
  
              return root.setKeyValue(key, value);
          }
  
          TrieEntry<K, V> found = getNearestEntryForKey(key);
          if (compareKeys(key, found.key))
          {
              if (found.isEmpty()) // <- must be the root
                  incrementSize();
              else
                  incrementModCount();
  
              return found.setKeyValue(key, value);
          }
  
          int bitIndex = bitIndex(key, found.key);
          if (!Tries.isOutOfBoundsIndex(bitIndex))
          {
              if (Tries.isValidBitIndex(bitIndex)) // in 99.999...9% the case
              {
                  /* NEW KEY+VALUE TUPLE */
                  TrieEntry<K, V> t = new TrieEntry<>(key, value, bitIndex);
                  addEntry(t);
                  incrementSize();
                  return null;
              }
              else if (Tries.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 (Tries.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 {@link TrieEntry} to the {@link Trie}
       */
      TrieEntry<K, V> addEntry(TrieEntry<K, V> entry)
      {
          TrieEntry<K, V> current = root.left;
          TrieEntry<K, V> path = root;
  
          while(true)
          {
              if (current.bitIndex >= entry.bitIndex || current.bitIndex <= path.bitIndex)
              {
                  entry.predecessor = entry;
  
                  if (!isBitSet(entry.key, entry.bitIndex))
                  {
                      entry.left = entry;
                      entry.right = current;
                  }
                  else
                  {
                      entry.left = current;
                      entry.right = entry;
                  }
  
                  entry.parent = path;
                  if (current.bitIndex >= entry.bitIndex)
                      current.parent = entry;
  
                  // if we inserted an uplink, set the predecessor on it
                  if (current.bitIndex <= path.bitIndex)
                      current.predecessor = entry;
  
                  if (path == root || !isBitSet(entry.key, path.bitIndex))
                      path.left = entry;
                  else
                      path.right = entry;
  
                  return entry;
              }
  
              path = current;
  
              current = !isBitSet(entry.key, current.bitIndex)
                         ? current.left : current.right;
          }
      }
  
      @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
       * AbstractPatriciaTrie.  Returns null if the map contains no mapping
       * for this key.
       *
       * This may throw ClassCastException if the object is not of type K.
       */
      TrieEntry<K,V> getEntry(Object k)
      {
          K key = Tries.cast(k);
          if (key == null)
              return null;
  
          TrieEntry<K,V> entry = getNearestEntryForKey(key);
          return !entry.isEmpty() && compareKeys(key, entry.key) ? entry : null;
      }
  
      @Override
      public Map.Entry<K, V> select(K key)
      {
          Reference<Map.Entry<K, V>> reference = new Reference<>();
          return !selectR(root.left, -1, key, reference) ? reference.get() : null;
      }
  
      @Override
      public Map.Entry<K,V> select(K key, Cursor<? super K, ? super V> cursor)
      {
          Reference<Map.Entry<K, V>> reference = new Reference<>();
          selectR(root.left, -1, key, cursor, reference);
          return reference.get();
      }
  
      /**
       * This is equivalent to the other {@link #selectR(TrieEntry, int,
       * K, Cursor, Reference)} method but without its overhead
       * because we're selecting only one best matching Entry from the
       * {@link Trie}.
       */
      private boolean selectR(TrieEntry<K, V> h, int bitIndex, final K key, final Reference<Map.Entry<K, V>> reference)
      {
          if (h.bitIndex <= bitIndex)
          {
              // If we hit the root Node and it is empty
              // we have to look for an alternative best
              // matching node.
              if (!h.isEmpty())
              {
                  reference.set(h);
                  return false;
              }
              return true;
          }
  
          if (!isBitSet(key, h.bitIndex))
          {
              if (selectR(h.left, h.bitIndex, key, reference))
              {
                  return selectR(h.right, h.bitIndex, key, reference);
              }
          }
          else
          {
              if (selectR(h.right, h.bitIndex, key, reference))
              {
                  return selectR(h.left, h.bitIndex, key, reference);
              }
          }
  
          return false;
      }
  
      /**
       *
       */
      private boolean selectR(TrieEntry<K,V> h, int bitIndex,
                              final K key, final Cursor<? super K, ? super V> cursor,
                              final Reference<Map.Entry<K, V>> reference)
      {
          if (h.bitIndex <= bitIndex)
          {
              if (!h.isEmpty())
              {
                  Decision decision = cursor.select(h);
                  switch(decision)
                  {
                      case REMOVE:
                          throw new UnsupportedOperationException("Cannot remove during select");
  
                      case EXIT:
                          reference.set(h);
                          return false; // exit
  
                      case REMOVE_AND_EXIT:
                          TrieEntry<K, V> entry = new TrieEntry<>(h.getKey(), h.getValue(), -1);
                          reference.set(entry);
                          removeEntry(h);
                          return false;
  
                      case CONTINUE:
                          // fall through.
                  }
              }
  
              return true; // continue
          }
  
          if (!isBitSet(key, h.bitIndex))
          {
              if (selectR(h.left, h.bitIndex, key, cursor, reference))
              {
                  return selectR(h.right, h.bitIndex, key, cursor, reference);
              }
          }
          else
          {
              if (selectR(h.right, h.bitIndex, key, cursor, reference))
              {
                  return selectR(h.left, h.bitIndex, key, cursor, reference);
              }
          }
  
          return false;
      }
  
      @Override
      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;
  
              Decision decision = cursor.select(current);
              entry = nextEntry(current);
  
              switch(decision)
              {
                  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;
      }
  
      @Override
      public boolean containsKey(Object k)
      {
          if (k == null)
              return false;
  
          K key = Tries.cast(k);
          TrieEntry<K, V> entry = getNearestEntryForKey(key);
          return !entry.isEmpty() && compareKeys(key, entry.key);
      }
  
      @Override
      public Set<Map.Entry<K,V>> entrySet()
      {
          if (entrySet == null)
              entrySet = new EntrySet();
  
          return entrySet;
      }
  
      @Override
      public Set<K> keySet()
      {
          if (keySet == null)
              keySet = new KeySet();
          return keySet;
      }
  
      @Override
      public Collection<V> values()
      {
          if (values == null)
              values = new Values();
          return values;
      }
  
      /**
       * {@inheritDoc}
       *
       * @throws ClassCastException if provided key is of an incompatible type
       */
      @Override
      public V remove(Object k)
      {
          if (k == null)
              return null;
  
          K key = Tries.cast(k);
          TrieEntry<K, V> current = root.left;
          TrieEntry<K, V> path = root;
          while (true)
          {
              if (current.bitIndex <= path.bitIndex)
              {
                  if (!current.isEmpty() && compareKeys(key, current.key))
                  {
                      return removeEntry(current);
                  }
                  else
                  {
                      return null;
                  }
              }
  
              path = current;
              current = !isBitSet(key, current.bitIndex) ? current.left : current.right;
          }
      }
  
      /**
       * Returns the nearest entry for a given key.  This is useful
       * for finding knowing if a given key exists (and finding the value
       * for it), or for inserting the key.
       *
       * The actual get implementation. This is very similar to
       * selectR but with the exception that it might return the
       * root Entry even if it's empty.
       */
      TrieEntry<K, V> getNearestEntryForKey(K key)
      {
          TrieEntry<K, V> current = root.left;
          TrieEntry<K, V> path = root;
  
          while(true)
          {
              if (current.bitIndex <= path.bitIndex)
                  return current;
  
              path = current;
              current = !isBitSet(key, current.bitIndex) ? current.left : current.right;
          }
      }
  
      /**
       * Removes a single entry from the {@link Trie}.
       *
       * If we found a Key (Entry h) then figure out if it's
       * an internal (hard to remove) or external Entry (easy
       * to remove)
       */
      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 {@link Trie}.
       *
       * 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 {@link Trie}.
       *
       * If it's an internal Entry then "good luck" with understanding
       * this code. The Idea is essentially that Entry p takes Entry h's
       * place in the trie which requires some re-wiring.
       */
      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 entry lexicographically after the given entry.
       * If the given entry is null, returns the first node.
       */
      TrieEntry<K, V> nextEntry(TrieEntry<K, V> node)
      {
          return (node == null) ? firstEntry() : nextEntryImpl(node.predecessor, node, null);
      }
  
      /**
       * Scans for the next node, starting at the specified point, and using 'previous'
       * as a hint that the last node we returned was 'previous' (so we know not to return
       * it again).  If 'tree' is non-null, this will limit the search to the given tree.
       *
       * The basic premise is that each iteration can follow the following steps:
       *
       * 1) Scan all the way to the left.
       *   a) If we already started from this node last time, proceed to Step 2.
       *   b) If a valid uplink is found, use it.
       *   c) If the result is an empty node (root not set), break the scan.
       *   d) If we already returned the left node, break the scan.
       *
       * 2) Check the right.
       *   a) If we already returned the right node, proceed to Step 3.
       *   b) If it is a valid uplink, use it.
       *   c) Do Step 1 from the right node.
       *
       * 3) Back up through the parents until we encounter find a parent
       *    that we're not the right child of.
       *
       * 4) If there's no right child of that parent, the iteration is finished.
       *    Otherwise continue to Step 5.
       *
       * 5) Check to see if the right child is a valid uplink.
       *    a) If we already returned that child, proceed to Step 6.
       *       Otherwise, use it.
       *
       * 6) If the right child of the parent is the parent itself, we've
       *    already found & returned the end of the Trie, so exit.
       *
       * 7) Do Step 1 on the parent's right child.
       */
      TrieEntry<K, V> nextEntryImpl(TrieEntry<K, V> start, TrieEntry<K, V> previous, TrieEntry<K, V> tree)
      {
          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.
              return nextEntryImpl(current.right, previous, tree);
          }
  
          // Neither left nor right are valid, find the first parent
          // whose child did not come from the right & traverse it.
          while (current == current.parent.right)
          {
              // 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.
          return nextEntryImpl(current.parent.right, previous, tree);
      }
  
      /**
       * Returns the first entry the {@link Trie} is storing.
       *
       * This is implemented by going always to the left until
       * we encounter a valid uplink. That uplink is the first key.
       */
      TrieEntry<K, V> firstEntry()
      {
          // if Trie is empty, no first node.
          return isEmpty() ? null : followLeft(root);
      }
  
      /**
       * Goes left through the tree until it finds a valid node.
       */
      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 true if 'next' is a valid uplink coming from 'from'.
       */
      static boolean isValidUplink(TrieEntry<?, ?> next, TrieEntry<?, ?> from)
      {
          return next != null && next.bitIndex <= from.bitIndex && !next.isEmpty();
      }
  
      /**
       * A {@link Reference} allows us to return something through a Method's
       * argument list. An alternative would be to an Array with a length of
       * one (1) but that leads to compiler warnings. Computationally and memory
       * wise there's no difference (except for the need to load the
       * {@link Reference} Class but that happens only once).
       */
      private static class Reference<E>
      {
  
          private E item;
  
          public void set(E item)
          {
              this.item = item;
          }
  
          public E get()
          {
              return item;
          }
      }
  
      /**
       *  A {@link Trie} is a set of {@link TrieEntry} nodes
       */
      static class TrieEntry<K,V> extends BasicEntry<K, V>
      {
  
          private static final long serialVersionUID = 4596023148184140013L;
  
          /** The index this entry is comparing. */
          protected int bitIndex;
  
          /** The parent of this entry. */
          protected TrieEntry<K,V> parent;
  
          /** The left child of this entry. */
          protected TrieEntry<K,V> left;
  
          /** The right child of this entry. */
          protected TrieEntry<K,V> right;
  
          /** The entry who uplinks to this entry. */
          protected TrieEntry<K,V> predecessor;
  
          public TrieEntry(K key, V value, int bitIndex)
          {
              super(key, value);
  
              this.bitIndex = bitIndex;
  
              this.parent = null;
              this.left = this;
              this.right = null;
              this.predecessor = this;
          }
  
          /**
           * Whether or not the entry is storing a key.
           * Only the root can potentially be empty, all other
           * nodes must have a key.
           */
          public boolean isEmpty()
          {
              return key == null;
          }
  
          /**
           * Neither the left nor right child is a loopback
           */
          public boolean isInternalNode()
          {
              return left != this && right != this;
          }
  
          /**
           * Either the left or right child is a loopback
           */
          public boolean isExternalNode()
          {
              return !isInternalNode();
          }
      }
  
  
      /**
       * This is a entry set view of the {@link Trie} as returned
       * by {@link Map#entrySet()}
       */
      private class EntrySet extends AbstractSet<Map.Entry<K,V>>
      {
          @Override
          public Iterator<Map.Entry<K,V>> iterator()
          {
              return new EntryIterator();
          }
  
          @Override
          public boolean contains(Object o)
          {
              if (!(o instanceof Map.Entry))
                  return false;
  
              TrieEntry<K,V> candidate = getEntry(((Map.Entry<?, ?>)o).getKey());
              return candidate != null && candidate.equals(o);
          }
  
          @Override
          public boolean remove(Object o)
          {
              int size = size();
              AbstractPatriciaTrie.this.remove(o);
              return size != size();
          }
  
          @Override
          public int size()
          {
              return AbstractPatriciaTrie.this.size();
          }
  
          @Override
          public void clear()
          {
              AbstractPatriciaTrie.this.clear();
          }
  
          /**
           * An {@link Iterator} that returns {@link Entry} Objects
           */
          private class EntryIterator extends TrieIterator<Map.Entry<K,V>>
          {
              @Override
              public Map.Entry<K,V> next()
              {
                  return nextEntry();
              }
          }
      }
  
      /**
       * This is a key set view of the {@link Trie} as returned
       * by {@link Map#keySet()}
       */
      private class KeySet extends AbstractSet<K>
      {
          @Override
          public Iterator<K> iterator()
          {
              return new KeyIterator();
          }
  
          @Override
          public int size()
          {
              return AbstractPatriciaTrie.this.size();
          }
  
          @Override
          public boolean contains(Object o)
          {
              return containsKey(o);
          }
  
          @Override
          public boolean remove(Object o)
          {
              int size = size();
              AbstractPatriciaTrie.this.remove(o);
              return size != size();
          }
  
          @Override
          public void clear()
          {
              AbstractPatriciaTrie.this.clear();
          }
  
          /**
           * An {@link Iterator} that returns Key Objects
           */
          private class KeyIterator extends TrieIterator<K>
          {
              @Override
              public K next()
              {
                  return nextEntry().getKey();
              }
          }
      }
  
      /**
       * This is a value view of the {@link Trie} as returned
       * by {@link Map#values()}
       */
      private class Values extends AbstractCollection<V>
      {
          @Override
          public Iterator<V> iterator()
          {
              return new ValueIterator();
          }
  
          @Override
          public int size()
          {
              return AbstractPatriciaTrie.this.size();
          }
  
          @Override
          public boolean contains(Object o)
          {
              return containsValue(o);
          }
  
          @Override
          public void clear()
          {
              AbstractPatriciaTrie.this.clear();
          }
  
          @Override
          public boolean remove(Object o)
          {
              for (Iterator<V> it = iterator(); it.hasNext(); )
              {
                  V value = it.next();
                  if (Tries.areEqual(value, o))
                  {
                      it.remove();
                      return true;
                  }
              }
              return false;
          }
  
          /**
           * An {@link Iterator} that returns Value Objects
           */
          private class ValueIterator extends TrieIterator<V>
          {
              @Override
              public V next()
              {
                  return nextEntry().getValue();
              }
          }
      }
  
      /**
       * An iterator for the entries.
       */
      abstract class TrieIterator<E> implements Iterator<E>
      {
          /**
           * For fast-fail
           */
          protected int expectedModCount = AbstractPatriciaTrie.this.modCount;
  
          protected TrieEntry<K, V> next; // the next node to return
          protected TrieEntry<K, V> current; // the current entry we're on
  
          /**
           * Starts iteration from the root
           */
          protected TrieIterator()
          {
              next = AbstractPatriciaTrie.this.nextEntry(null);
          }
  
          /**
           * Starts iteration at the given entry
           */
          protected TrieIterator(TrieEntry<K, V> firstEntry)
          {
              next = firstEntry;
          }
  
          /**
           * Returns the next {@link TrieEntry}
           */
          protected TrieEntry<K,V> nextEntry()
          {
              if (expectedModCount != AbstractPatriciaTrie.this.modCount)
                  throw new ConcurrentModificationException();
  
              TrieEntry<K,V> e = next;
              if (e == null)
                  throw new NoSuchElementException();
  
              next = findNext(e);
              current = e;
              return e;
          }
  
          /**
           * @see PatriciaTrie#nextEntry(TrieEntry)
           */
          protected TrieEntry<K, V> findNext(TrieEntry<K, V> prior)
          {
              return AbstractPatriciaTrie.this.nextEntry(prior);
          }
  
          @Override
          public boolean hasNext()
          {
              return next != null;
          }
  
          @Override
          public void remove()
          {
              if (current == null)
                  throw new IllegalStateException();
  
              if (expectedModCount != AbstractPatriciaTrie.this.modCount)
                  throw new ConcurrentModificationException();
  
              TrieEntry<K, V> node = current;
              current = null;
              AbstractPatriciaTrie.this.removeEntry(node);
  
              expectedModCount = AbstractPatriciaTrie.this.modCount;
          }
      }
  }
  