/*
 * 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.
/**
 * 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 Map interface. /**
 * 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 Trie. /**
     * 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.
/**
     * 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 Trie /**
     * The current size of the {@link Trie}
     */
    private int size = 0;

    
The number of times this Trie has been modified. It's used to detect concurrent modifications and fail-fast the Iterators. /**
     * 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 Trie size and the modification counter. /**
     * A helper method to increment the {@link Trie} size
     * and the modification counter.
     */
    void incrementSize()
    {
        size++;
        incrementModCount();
    }

    
A helper method to decrement the Trie size and increment the modification counter. /**
     * 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.
/**
     * 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 TrieEntry to the Trie /**
     * 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.
/**
     * 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 selectR(TrieEntry, int, Object, Cursor, Reference) method but without its overhead because we're selecting only one best matching Entry from the Trie. /**
     * 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/**
     * {@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.
/**
     * 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 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) /**
     * 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 Trie. If it's an external Entry then just remove it. This is very easy and straight forward. /**
     * 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 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. /**
     * 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.
/**
     * 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.
/**
     * 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 Trie is storing. This is implemented by going always to the left until we encounter a valid uplink. That uplink is the first key. /**
     * 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.
/**
     * 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'.
/**
     * 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 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 Reference Class but that happens only once). /**
     * 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 Trie is a set of TrieEntry nodes /**
     *  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. /** The index this entry is comparing. */
        protected int bitIndex;

        
The parent of this entry. /** The parent of this entry. */
        protected TrieEntry<K,V> parent;

        
The left child of this entry. /** The left child of this entry. */
        protected TrieEntry<K,V> left;

        
The right child of this entry. /** The right child of this entry. */
        protected TrieEntry<K,V> right;

        
The entry who uplinks to this entry. /** 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.
/**
         * 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
/**
         * 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
/**
         * Either the left or right child is a loopback
         */
        public boolean isExternalNode()
        {
            return !isInternalNode();
        }
    }


    
This is a entry set view of the Trie as returned by Map.entrySet() /**
     * 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 Iterator that returns Entry Objects /**
         * 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 Trie as returned by Map.keySet() /**
     * 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 Iterator that returns Key Objects /**
         * 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 Trie as returned by Map.values() /**
     * 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 Iterator that returns Value Objects /**
         * 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.
/**
     * An iterator for the entries.
     */
    abstract class TrieIterator<E> implements Iterator<E>
    {
        
For fast-fail
/**
         * 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
/**
         * Starts iteration from the root
         */
        protected TrieIterator()
        {
            next = AbstractPatriciaTrie.this.nextEntry(null);
        }

        
Starts iteration at the given entry
/**
         * Starts iteration at the given entry
         */
        protected TrieIterator(TrieEntry<K, V> firstEntry)
        {
            next = firstEntry;
        }

        
Returns the next TrieEntry /**
         * 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 Also:
nextEntry.nextEntry(TrieEntry)/**
         * @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;
        }
    }
}