/*
 * 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.
 */

PATRICIA Trie
Practical Algorithm to Retrieve Information Coded in Alphanumeric
A PATRICIA Trie is a compressed Trie. Instead of storing all data at the edges of the Trie (and having empty internal nodes), PATRICIA stores data in every node. This allows for very efficient traversal, insert, delete, predecessor, successor, prefix, range, and AbstractPatriciaTrie.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. 
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.
The Trie can return operations in lexicographical order using the AbstractPatriciaTrie.traverse(Cursor), 'prefix', 'submap', or 'iterator' methods. The Trie can also scan for items that are 'bitwise' (using an XOR metric) by the 'select' method. Bitwise closeness is determined by the KeyAnalyzer returning true or false for a bit being set or not in a given key. 
Any methods here that take an Object argument may throw a ClassCastException if the method is expecting an instance of K and it isn't K. 
Author:
Roger Kapsi, Sam Berlin
See Also:
Radix Tree
PATRICIA
Crit-Bit Tree/**
 * <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.
/**
     * 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.
/**
     * 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.
/**
     * 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.
/**
     * 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.
/**
     * 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 Trie is storing. 
This is implemented by going always to the right until
we encounter a valid uplink. That uplink is the last key.
/**
     * 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.
/**
     * 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
Params:
start – the start entry/**
     * 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.
/**
     * 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 Trie /**
     * A range view of the {@link Trie}
     */
    private abstract class RangeMap extends AbstractMap<K, V> implements SortedMap<K, V>
    {
        
The entrySet() view /**
         * The {@link #entrySet()} view
         */
        private transient volatile Set<Map.Entry<K, V>> entrySet;

        
Creates and returns an entrySet() view of the RangeMap /**
         * Creates and returns an {@link #entrySet()}
         * view of the {@link RangeMap}
         */
        protected abstract Set<Map.Entry<K, V>> createEntrySet();

        
Returns the FROM Key
/**
         * Returns the FROM Key
         */
        protected abstract K getFromKey();

        
Whether or not the getFromKey() is in the range /**
         * Whether or not the {@link #getFromKey()} is in the range
         */
        protected abstract boolean isFromInclusive();

        
Returns the TO Key
/**
         * Returns the TO Key
         */
        protected abstract K getToKey();

        
Whether or not the getToKey() is in the range /**
         * 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
/**
         * 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)
/**
         * 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 RangeMap /**
         * 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 RangeMap /**
         * 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 RangeMap /**
         * 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 RangeMap that deals with Entrys /**
    * A {@link RangeMap} that deals with {@link Entry}s
    */
   private class RangeEntryMap extends RangeMap
   {
       
The key to start from, null if the beginning.
/**
        * The key to start from, null if the beginning.
        */
       protected final K fromKey;

       
The key to end at, null if till the end.
/**
        * The key to end at, null if till the end.
        */
       protected final K toKey;

       
Whether or not the 'from' is inclusive.
/**
        * Whether or not the 'from' is inclusive.
        */
       protected final boolean fromInclusive;

       
Whether or not the 'to' is inclusive.
/**
        * Whether or not the 'to' is inclusive.
        */
       protected final boolean toInclusive;

       
Creates a RangeEntryMap with the fromKey included and the toKey excluded from the range /**
        * 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 RangeEntryMap /**
        * 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 Set view of a RangeMap /**
     * 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 RangeEntrySet /**
         * 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 Iterator for RangeEntrySets. /**
         * An {@link Iterator} for {@link RangeEntrySet}s.
         */
        private final class EntryIterator extends TrieIterator<Map.Entry<K,V>>
        {
            private final K excludedKey;

            
Creates a EntryIterator /**
             * 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 Trie. /**
     * 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 PrefixRangeMap /**
         * 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 PrefixRangeMap and the number of elements in the range. This method must be called every time the Trie has changed. /**
         * 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 PrefixRangeMap's key is a prefix of the provided key. /**
         * 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 inRange(Object) /**
         * 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 PrefixRangeMap /**
         * 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 PrefixRangeMap /**
         * 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 RangeEntrySet view of the Trie /**
     * 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 PrefixRangeEntrySet /**
         * 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 Iterator that holds a single TrieEntry. /**
         * An {@link Iterator} that holds a single {@link TrieEntry}.
         */
        private final class SingletonIterator implements Iterator<Map.Entry<K, V>>
        {
            private final TrieEntry<K, V> entry;

            private int hit = 0;

            public SingletonIterator(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 Iterator for iterating over a prefix search. /**
         * An {@link Iterator} for iterating over a prefix search.
         */
        private final class EntryIterator extends TrieIterator<Map.Entry<K, V>>
        {
            // values to reset the subtree if we remove it.
            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.
/**
             * 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;
            }
        }
    }
}