src/java/org/apache/cassandra/index/sasi/utils/trie/PatriciaTrie.java

/*
 * Copyright 2005-2010 Roger Kapsi, Sam Berlin
 *
 *   Licensed under the Apache License, Version 2.0 (the "License");
 *   you may not use this file except in compliance with the License.
 *   You may obtain a copy of the License at
 *
 *       http://www.apache.org/licenses/LICENSE-2.0
 *
 *   Unless required by applicable law or agreed to in writing, software
 *   distributed under the License is distributed on an "AS IS" BASIS,
 *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *   See the License for the specific language governing permissions and
 *   limitations under the License.
 */

package org.apache.cassandra.index.sasi.utils.trie;

import java.io.Serializable;
import java.util.*;

/**
 * This class is taken from https://github.com/rkapsi/patricia-trie (v0.6), and slightly modified
 * to correspond to Cassandra code style, as the only Patricia Trie implementation,
 * which supports pluggable key comparators (e.g. commons-collections PatriciaTrie (which is based
 * on rkapsi/patricia-trie project) only supports String keys)
 * but unfortunately is not deployed to the maven central as a downloadable artifact.
 */

/**
 * <h3>PATRICIA {@link Trie}</h3>
 *
 * <i>Practical Algorithm to Retrieve Information Coded in Alphanumeric</i>
 *
 * <p>A PATRICIA {@link Trie} is a compressed {@link Trie}. Instead of storing
 * all data at the edges of the {@link Trie} (and having empty internal nodes),
 * PATRICIA stores data in every node. This allows for very efficient traversal,
 * insert, delete, predecessor, successor, prefix, range, and {@link #select(Object)}
 * operations. All operations are performed at worst in O(K) time, where K
 * is the number of bits in the largest item in the tree. In practice,
 * operations actually take O(A(K)) time, where A(K) is the average number of
 * bits of all items in the tree.
 *
 * <p>Most importantly, PATRICIA requires very few comparisons to keys while
 * doing any operation. While performing a lookup, each comparison (at most
 * K of them, described above) will perform a single bit comparison against
 * the given key, instead of comparing the entire key to another key.
 *
 * <p>The {@link Trie} can return operations in lexicographical order using the
 * {@link #traverse(Cursor)}, 'prefix', 'submap', or 'iterator' methods. The
 * {@link Trie} can also scan for items that are 'bitwise' (using an XOR
 * metric) by the 'select' method. Bitwise closeness is determined by the
 * {@link KeyAnalyzer} returning true or false for a bit being set or not in
 * a given key.
 *
 * <p>Any methods here that take an {@link Object} argument may throw a
 * {@link ClassCastException} if the method is expecting an instance of K
 * and it isn't K.
 *
 * @see <a href="http://en.wikipedia.org/wiki/Radix_tree">Radix Tree</a>
 * @see <a href="http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA">PATRICIA</a>
 * @see <a href="http://www.imperialviolet.org/binary/critbit.pdf">Crit-Bit Tree</a>
 *
 * @author Roger Kapsi
 * @author Sam Berlin
 */
public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Serializable
{
    private static final long serialVersionUID = -2246014692353432660L;

    public PatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer)
    {
        super(keyAnalyzer);
    }

    public PatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer, Map<? extends K, ? extends V> m)
    {
        super(keyAnalyzer, m);
    }

    @Override
    public Comparator<? super K> comparator()
    {
        return keyAnalyzer;
    }

    @Override
    public SortedMap<K, V> prefixMap(K prefix)
    {
        return lengthInBits(prefix) == 0 ? this : new PrefixRangeMap(prefix);
    }

    @Override
    public K firstKey()
    {
        return firstEntry().getKey();
    }

    @Override
    public K lastKey()
    {
        TrieEntry<K, V> entry = lastEntry();
        return entry != null ? entry.getKey() : null;
    }

    @Override
    public SortedMap<K, V> headMap(K toKey)
    {
        return new RangeEntryMap(null, toKey);
    }

    @Override
    public SortedMap<K, V> subMap(K fromKey, K toKey)
    {
        return new RangeEntryMap(fromKey, toKey);
    }

    @Override
    public SortedMap<K, V> tailMap(K fromKey)
    {
        return new RangeEntryMap(fromKey, null);
    }

    /**
     * Returns an entry strictly higher than the given key,
     * or null if no such entry exists.
     */
    private TrieEntry<K,V> higherEntry(K key)
    {
        // TODO: Cleanup so that we don't actually have to add/remove from the
        //       tree.  (We do it here because there are other well-defined
        //       functions to perform the search.)
        int lengthInBits = lengthInBits(key);

        if (lengthInBits == 0)
        {
            if (!root.isEmpty())
            {
                // If data in root, and more after -- return it.
                return size() > 1 ? nextEntry(root) : null;
            }
            else
            {
                // Root is empty & we want something after empty, return first.
                return firstEntry();
            }
        }

        TrieEntry<K, V> found = getNearestEntryForKey(key);
        if (compareKeys(key, found.key))
            return nextEntry(found);

        int bitIndex = bitIndex(key, found.key);
        if (Tries.isValidBitIndex(bitIndex))
        {
            return replaceCeil(key, bitIndex);
        }
        else if (Tries.isNullBitKey(bitIndex))
        {
            if (!root.isEmpty())
            {
                return firstEntry();
            }
            else if (size() > 1)
            {
                return nextEntry(firstEntry());
            }
            else
            {
                return null;
            }
        }
        else if (Tries.isEqualBitKey(bitIndex))
        {
            return nextEntry(found);
        }

        // we should have exited above.
        throw new IllegalStateException("invalid lookup: " + key);
    }

    /**
     * Returns a key-value mapping associated with the least key greater
     * than or equal to the given key, or null if there is no such key.
     */
    TrieEntry<K,V> ceilingEntry(K key)
    {
        // Basically:
        // Follow the steps of adding an entry, but instead...
        //
        // - If we ever encounter a situation where we found an equal
        //   key, we return it immediately.
        //
        // - If we hit an empty root, return the first iterable item.
        //
        // - If we have to add a new item, we temporarily add it,
        //   find the successor to it, then remove the added item.
        //
        // These steps ensure that the returned value is either the
        // entry for the key itself, or the first entry directly after
        // the key.

        // TODO: Cleanup so that we don't actually have to add/remove from the
        //       tree.  (We do it here because there are other well-defined
        //       functions to perform the search.)
        int lengthInBits = lengthInBits(key);

        if (lengthInBits == 0)
        {
            if (!root.isEmpty())
            {
                return root;
            }
            else
            {
                return firstEntry();
            }
        }

        TrieEntry<K, V> found = getNearestEntryForKey(key);
        if (compareKeys(key, found.key))
            return found;

        int bitIndex = bitIndex(key, found.key);
        if (Tries.isValidBitIndex(bitIndex))
        {
            return replaceCeil(key, bitIndex);
        }
        else if (Tries.isNullBitKey(bitIndex))
        {
            if (!root.isEmpty())
            {
                return root;
            }
            else
            {
                return firstEntry();
            }
        }
        else if (Tries.isEqualBitKey(bitIndex))
        {
            return found;
        }

        // we should have exited above.
        throw new IllegalStateException("invalid lookup: " + key);
    }

    private TrieEntry<K, V> replaceCeil(K key, int bitIndex)
    {
        TrieEntry<K, V> added = new TrieEntry<>(key, null, bitIndex);
        addEntry(added);
        incrementSize(); // must increment because remove will decrement
        TrieEntry<K, V> ceil = nextEntry(added);
        removeEntry(added);
        modCount -= 2; // we didn't really modify it.
        return ceil;
    }

    private TrieEntry<K, V> replaceLower(K key, int bitIndex)
    {
        TrieEntry<K, V> added = new TrieEntry<>(key, null, bitIndex);
        addEntry(added);
        incrementSize(); // must increment because remove will decrement
        TrieEntry<K, V> prior = previousEntry(added);
        removeEntry(added);
        modCount -= 2; // we didn't really modify it.
        return prior;
    }

    /**
     * Returns a key-value mapping associated with the greatest key
     * strictly less than the given key, or null if there is no such key.
     */
    TrieEntry<K,V> lowerEntry(K key)
    {
        // Basically:
        // Follow the steps of adding an entry, but instead...
        //
        // - If we ever encounter a situation where we found an equal
        //   key, we return it's previousEntry immediately.
        //
        // - If we hit root (empty or not), return null.
        //
        // - If we have to add a new item, we temporarily add it,
        //   find the previousEntry to it, then remove the added item.
        //
        // These steps ensure that the returned value is always just before
        // the key or null (if there was nothing before it).

        // TODO: Cleanup so that we don't actually have to add/remove from the
        //       tree.  (We do it here because there are other well-defined
        //       functions to perform the search.)
        int lengthInBits = lengthInBits(key);

        if (lengthInBits == 0)
            return null; // there can never be anything before root.

        TrieEntry<K, V> found = getNearestEntryForKey(key);
        if (compareKeys(key, found.key))
            return previousEntry(found);

        int bitIndex = bitIndex(key, found.key);
        if (Tries.isValidBitIndex(bitIndex))
        {
            return replaceLower(key, bitIndex);
        }
        else if (Tries.isNullBitKey(bitIndex))
        {
            return null;
        }
        else if (Tries.isEqualBitKey(bitIndex))
        {
            return previousEntry(found);
        }

        // we should have exited above.
        throw new IllegalStateException("invalid lookup: " + key);
    }

    /**
     * Returns a key-value mapping associated with the greatest key
     * less than or equal to the given key, or null if there is no such key.
     */
    TrieEntry<K,V> floorEntry(K key) {
        // TODO: Cleanup so that we don't actually have to add/remove from the
        //       tree.  (We do it here because there are other well-defined
        //       functions to perform the search.)
        int lengthInBits = lengthInBits(key);

        if (lengthInBits == 0)
        {
            return !root.isEmpty() ? root : null;
        }

        TrieEntry<K, V> found = getNearestEntryForKey(key);
        if (compareKeys(key, found.key))
            return found;

        int bitIndex = bitIndex(key, found.key);
        if (Tries.isValidBitIndex(bitIndex))
        {
            return replaceLower(key, bitIndex);
        }
        else if (Tries.isNullBitKey(bitIndex))
        {
            if (!root.isEmpty())
            {
                return root;
            }
            else
            {
                return null;
            }
        }
        else if (Tries.isEqualBitKey(bitIndex))
        {
            return found;
        }

        // we should have exited above.
        throw new IllegalStateException("invalid lookup: " + key);
    }

    /**
     * Finds the subtree that contains the prefix.
     *
     * This is very similar to getR but with the difference that
     * we stop the lookup if h.bitIndex > lengthInBits.
     */
    private TrieEntry<K, V> subtree(K prefix)
    {
        int lengthInBits = lengthInBits(prefix);

        TrieEntry<K, V> current = root.left;
        TrieEntry<K, V> path = root;
        while(true)
        {
            if (current.bitIndex <= path.bitIndex || lengthInBits < current.bitIndex)
                break;

            path = current;
            current = !isBitSet(prefix, current.bitIndex)
                    ? current.left : current.right;
        }

        // Make sure the entry is valid for a subtree.
        TrieEntry<K, V> entry = current.isEmpty() ? path : current;

        // If entry is root, it can't be empty.
        if (entry.isEmpty())
            return null;

        // if root && length of root is less than length of lookup,
        // there's nothing.
        // (this prevents returning the whole subtree if root has an empty
        //  string and we want to lookup things with "\0")
        if (entry == root && lengthInBits(entry.getKey()) < lengthInBits)
            return null;

        // Found key's length-th bit differs from our key
        // which means it cannot be the prefix...
        if (isBitSet(prefix, lengthInBits) != isBitSet(entry.key, lengthInBits))
            return null;

        // ... or there are less than 'length' equal bits
        int bitIndex = bitIndex(prefix, entry.key);
        return (bitIndex >= 0 && bitIndex < lengthInBits) ? null : entry;
    }

    /**
     * Returns the last entry the {@link Trie} is storing.
     *
     * <p>This is implemented by going always to the right until
     * we encounter a valid uplink. That uplink is the last key.
     */
    private TrieEntry<K, V> lastEntry()
    {
        return followRight(root.left);
    }

    /**
     * Traverses down the right path until it finds an uplink.
     */
    private TrieEntry<K, V> followRight(TrieEntry<K, V> node)
    {
        // if Trie is empty, no last entry.
        if (node.right == null)
            return null;

        // Go as far right as possible, until we encounter an uplink.
        while (node.right.bitIndex > node.bitIndex)
        {
            node = node.right;
        }

        return node.right;
    }

    /**
     * Returns the node lexicographically before the given node (or null if none).
     *
     * This follows four simple branches:
     *  - If the uplink that returned us was a right uplink:
     *      - If predecessor's left is a valid uplink from predecessor, return it.
     *      - Else, follow the right path from the predecessor's left.
     *  - If the uplink that returned us was a left uplink:
     *      - Loop back through parents until we encounter a node where
     *        node != node.parent.left.
     *          - If node.parent.left is uplink from node.parent:
     *              - If node.parent.left is not root, return it.
     *              - If it is root & root isEmpty, return null.
     *              - If it is root & root !isEmpty, return root.
     *          - If node.parent.left is not uplink from node.parent:
     *              - Follow right path for first right child from node.parent.left
     *
     * @param start the start entry
     */
    private TrieEntry<K, V> previousEntry(TrieEntry<K, V> start)
    {
        if (start.predecessor == null)
            throw new IllegalArgumentException("must have come from somewhere!");

        if (start.predecessor.right == start)
        {
            return isValidUplink(start.predecessor.left, start.predecessor)
                    ? start.predecessor.left
                    : followRight(start.predecessor.left);
        }

        TrieEntry<K, V> node = start.predecessor;
        while (node.parent != null && node == node.parent.left)
        {
            node = node.parent;
        }

        if (node.parent == null) // can be null if we're looking up root.
            return null;

        if (isValidUplink(node.parent.left, node.parent))
        {
            if (node.parent.left == root)
            {
                return root.isEmpty() ? null : root;
            }
            else
            {
                return node.parent.left;
            }
        }
        else
        {
            return followRight(node.parent.left);
        }
    }

    /**
     * Returns the entry lexicographically after the given entry.
     * If the given entry is null, returns the first node.
     *
     * This will traverse only within the subtree.  If the given node
     * is not within the subtree, this will have undefined results.
     */
    private TrieEntry<K, V> nextEntryInSubtree(TrieEntry<K, V> node, TrieEntry<K, V> parentOfSubtree)
    {
        return (node == null) ? firstEntry() : nextEntryImpl(node.predecessor, node, parentOfSubtree);
    }

    private boolean isPrefix(K key, K prefix)
    {
        return keyAnalyzer.isPrefix(key, prefix);
    }

    /**
     * A range view of the {@link Trie}
     */
    private abstract class RangeMap extends AbstractMap<K, V> implements SortedMap<K, V>
    {
        /**
         * The {@link #entrySet()} view
         */
        private transient volatile Set<Map.Entry<K, V>> entrySet;

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

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

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

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

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


        @Override
        public Comparator<? super K> comparator()
        {
            return PatriciaTrie.this.comparator();
        }

        @Override
        public boolean containsKey(Object key)
        {
            return inRange(Tries.<K>cast(key)) && PatriciaTrie.this.containsKey(key);
        }

        @Override
        public V remove(Object key)
        {
            return (!inRange(Tries.<K>cast(key))) ? null : PatriciaTrie.this.remove(key);
        }

        @Override
        public V get(Object key)
        {
            return (!inRange(Tries.<K>cast(key))) ? null : PatriciaTrie.this.get(key);
        }

        @Override
        public V put(K key, V value)
        {
            if (!inRange(key))
                throw new IllegalArgumentException("Key is out of range: " + key);

            return PatriciaTrie.this.put(key, value);
        }

        @Override
        public Set<Map.Entry<K, V>> entrySet()
        {
            if (entrySet == null)
                entrySet = createEntrySet();
            return entrySet;
        }

        @Override
        public SortedMap<K, V> subMap(K fromKey, K toKey)
        {
            if (!inRange2(fromKey))
                throw new IllegalArgumentException("FromKey is out of range: " + fromKey);

            if (!inRange2(toKey))
                throw new IllegalArgumentException("ToKey is out of range: " + toKey);

            return createRangeMap(fromKey, isFromInclusive(), toKey, isToInclusive());
        }

        @Override
        public SortedMap<K, V> headMap(K toKey)
        {
            if (!inRange2(toKey))
                throw new IllegalArgumentException("ToKey is out of range: " + toKey);

            return createRangeMap(getFromKey(), isFromInclusive(), toKey, isToInclusive());
        }

        @Override
        public SortedMap<K, V> tailMap(K fromKey)
        {
            if (!inRange2(fromKey))
                throw new IllegalArgumentException("FromKey is out of range: " + fromKey);

            return createRangeMap(fromKey, isFromInclusive(), getToKey(), isToInclusive());
        }

        /**
         * Returns true if the provided key is greater than TO and
         * less than FROM
         */
        protected boolean inRange(K key)
        {
            K fromKey = getFromKey();
            K toKey = getToKey();

            return (fromKey == null || inFromRange(key, false))
                    && (toKey == null || inToRange(key, false));
        }

        /**
         * This form allows the high endpoint (as well as all legit keys)
         */
        protected boolean inRange2(K key)
        {
            K fromKey = getFromKey();
            K toKey = getToKey();

            return (fromKey == null || inFromRange(key, false))
                    && (toKey == null || inToRange(key, true));
        }

        /**
         * Returns true if the provided key is in the FROM range
         * of the {@link RangeMap}
         */
        protected boolean inFromRange(K key, boolean forceInclusive)
        {
            K fromKey = getFromKey();
            boolean fromInclusive = isFromInclusive();

            int ret = keyAnalyzer.compare(key, fromKey);
            return (fromInclusive || forceInclusive) ? ret >= 0 : ret > 0;
        }

        /**
         * Returns true if the provided key is in the TO range
         * of the {@link RangeMap}
         */
        protected boolean inToRange(K key, boolean forceInclusive)
        {
            K toKey = getToKey();
            boolean toInclusive = isToInclusive();

            int ret = keyAnalyzer.compare(key, toKey);
            return (toInclusive || forceInclusive) ? ret <= 0 : ret < 0;
        }

        /**
         * Creates and returns a sub-range view of the current {@link RangeMap}
         */
        protected abstract SortedMap<K, V> createRangeMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive);
    }

   /**
    * A {@link RangeMap} that deals with {@link Entry}s
    */
   private class RangeEntryMap extends RangeMap
   {
       /**
        * The key to start from, null if the beginning.
        */
       protected final K fromKey;

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

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

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

       /**
        * Creates a {@link RangeEntryMap} with the fromKey included and
        * the toKey excluded from the range
        */
       protected RangeEntryMap(K fromKey, K toKey)
       {
           this(fromKey, true, toKey, false);
       }

       /**
        * Creates a {@link RangeEntryMap}
        */
       protected RangeEntryMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
       {
           if (fromKey == null && toKey == null)
               throw new IllegalArgumentException("must have a from or to!");

           if (fromKey != null && toKey != null && keyAnalyzer.compare(fromKey, toKey) > 0)
               throw new IllegalArgumentException("fromKey > toKey");

           this.fromKey = fromKey;
           this.fromInclusive = fromInclusive;
           this.toKey = toKey;
           this.toInclusive = toInclusive;
       }


       @Override
       public K firstKey()
       {
           Map.Entry<K,V> e  = fromKey == null
                ? firstEntry()
                : fromInclusive ? ceilingEntry(fromKey) : higherEntry(fromKey);

           K first = e != null ? e.getKey() : null;
           if (e == null || toKey != null && !inToRange(first, false))
               throw new NoSuchElementException();

           return first;
       }


       @Override
       public K lastKey()
       {
           Map.Entry<K,V> e = toKey == null
                ? lastEntry()
                : toInclusive ? floorEntry(toKey) : lowerEntry(toKey);

           K last = e != null ? e.getKey() : null;
           if (e == null || fromKey != null && !inFromRange(last, false))
               throw new NoSuchElementException();

           return last;
       }

       @Override
       protected Set<Entry<K, V>> createEntrySet()
       {
           return new RangeEntrySet(this);
       }

       @Override
       public K getFromKey()
       {
           return fromKey;
       }

       @Override
       public K getToKey()
       {
           return toKey;
       }

       @Override
       public boolean isFromInclusive()
       {
           return fromInclusive;
       }

       @Override
       public boolean isToInclusive()
       {
           return toInclusive;
       }

       @Override
       protected SortedMap<K, V> createRangeMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
       {
           return new RangeEntryMap(fromKey, fromInclusive, toKey, toInclusive);
       }
   }

    /**
     * A {@link Set} view of a {@link RangeMap}
     */
    private class RangeEntrySet extends AbstractSet<Map.Entry<K, V>>
    {

        private final RangeMap delegate;

        private int size = -1;

        private int expectedModCount = -1;

        /**
         * Creates a {@link RangeEntrySet}
         */
        public RangeEntrySet(RangeMap delegate)
        {
            if (delegate == null)
                throw new NullPointerException("delegate");

            this.delegate = delegate;
        }

        @Override
        public Iterator<Map.Entry<K, V>> iterator()
        {
            K fromKey = delegate.getFromKey();
            K toKey = delegate.getToKey();

            TrieEntry<K, V> first = fromKey == null ? firstEntry() : ceilingEntry(fromKey);
            TrieEntry<K, V> last = null;
            if (toKey != null)
                last = ceilingEntry(toKey);

            return new EntryIterator(first, last);
        }

        @Override
        public int size()
        {
            if (size == -1 || expectedModCount != PatriciaTrie.this.modCount)
            {
                size = 0;

                for (Iterator<?> it = iterator(); it.hasNext(); it.next())
                {
                    ++size;
                }

                expectedModCount = PatriciaTrie.this.modCount;
            }

            return size;
        }

        @Override
        public boolean isEmpty()
        {
            return !iterator().hasNext();
        }

        @Override
        public boolean contains(Object o)
        {
            if (!(o instanceof Map.Entry<?, ?>))
                return false;

            @SuppressWarnings("unchecked")
            Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
            K key = entry.getKey();
            if (!delegate.inRange(key))
                return false;

            TrieEntry<K, V> node = getEntry(key);
            return node != null && Tries.areEqual(node.getValue(), entry.getValue());
        }

        @Override
        public boolean remove(Object o)
        {
            if (!(o instanceof Map.Entry<?, ?>))
                return false;

            @SuppressWarnings("unchecked")
            Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
            K key = entry.getKey();
            if (!delegate.inRange(key))
                return false;

            TrieEntry<K, V> node = getEntry(key);
            if (node != null && Tries.areEqual(node.getValue(), entry.getValue()))
            {
                removeEntry(node);
                return true;
            }

            return false;
        }

        /**
         * An {@link Iterator} for {@link RangeEntrySet}s.
         */
        private final class EntryIterator extends TrieIterator<Map.Entry<K,V>>
        {
            private final K excludedKey;

            /**
             * Creates a {@link EntryIterator}
             */
            private EntryIterator(TrieEntry<K,V> first, TrieEntry<K,V> last)
            {
                super(first);
                this.excludedKey = (last != null ? last.getKey() : null);
            }

            @Override
            public boolean hasNext()
            {
                return next != null && !Tries.areEqual(next.key, excludedKey);
            }

            @Override
            public Map.Entry<K,V> next()
            {
                if (next == null || Tries.areEqual(next.key, excludedKey))
                    throw new NoSuchElementException();

                return nextEntry();
            }
        }
    }

    /**
     * A submap used for prefix views over the {@link Trie}.
     */
    private class PrefixRangeMap extends RangeMap
    {

        private final K prefix;

        private K fromKey = null;

        private K toKey = null;

        private int expectedModCount = -1;

        private int size = -1;

        /**
         * Creates a {@link PrefixRangeMap}
         */
        private PrefixRangeMap(K prefix)
        {
            this.prefix = prefix;
        }

        /**
         * This method does two things. It determinates the FROM
         * and TO range of the {@link PrefixRangeMap} and the number
         * of elements in the range. This method must be called every
         * time the {@link Trie} has changed.
         */
        private int fixup()
        {
            // The trie has changed since we last
            // found our toKey / fromKey
            if (size == - 1 || PatriciaTrie.this.modCount != expectedModCount)
            {
                Iterator<Map.Entry<K, V>> it = entrySet().iterator();
                size = 0;

                Map.Entry<K, V> entry = null;
                if (it.hasNext())
                {
                    entry = it.next();
                    size = 1;
                }

                fromKey = entry == null ? null : entry.getKey();
                if (fromKey != null)
                {
                    TrieEntry<K, V> prior = previousEntry((TrieEntry<K, V>)entry);
                    fromKey = prior == null ? null : prior.getKey();
                }

                toKey = fromKey;

                while (it.hasNext())
                {
                    ++size;
                    entry = it.next();
                }

                toKey = entry == null ? null : entry.getKey();

                if (toKey != null)
                {
                    entry = nextEntry((TrieEntry<K, V>)entry);
                    toKey = entry == null ? null : entry.getKey();
                }

                expectedModCount = PatriciaTrie.this.modCount;
            }

            return size;
        }

        @Override
        public K firstKey()
        {
            fixup();

            Map.Entry<K,V> e = fromKey == null ? firstEntry() : higherEntry(fromKey);
            K first = e != null ? e.getKey() : null;
            if (e == null || !isPrefix(first, prefix))
                throw new NoSuchElementException();

            return first;
        }

        @Override
        public K lastKey()
        {
            fixup();

            Map.Entry<K,V> e = toKey == null ? lastEntry() : lowerEntry(toKey);
            K last = e != null ? e.getKey() : null;
            if (e == null || !isPrefix(last, prefix))
                throw new NoSuchElementException();

            return last;
        }

        /**
         * Returns true if this {@link PrefixRangeMap}'s key is a prefix
         * of the provided key.
         */
        @Override
        protected boolean inRange(K key)
        {
            return isPrefix(key, prefix);
        }

        /**
         * Same as {@link #inRange(Object)}
         */
        @Override
        protected boolean inRange2(K key)
        {
            return inRange(key);
        }

        /**
         * Returns true if the provided Key is in the FROM range
         * of the {@link PrefixRangeMap}
         */
        @Override
        protected boolean inFromRange(K key, boolean forceInclusive)
        {
            return isPrefix(key, prefix);
        }

        /**
         * Returns true if the provided Key is in the TO range
         * of the {@link PrefixRangeMap}
         */
        @Override
        protected boolean inToRange(K key, boolean forceInclusive)
        {
            return isPrefix(key, prefix);
        }

        @Override
        protected Set<Map.Entry<K, V>> createEntrySet()
        {
            return new PrefixRangeEntrySet(this);
        }

        @Override
        public K getFromKey()
        {
            return fromKey;
        }

        @Override
        public K getToKey()
        {
            return toKey;
        }

        @Override
        public boolean isFromInclusive()
        {
            return false;
        }

        @Override
        public boolean isToInclusive()
        {
            return false;
        }

        @Override
        protected SortedMap<K, V> createRangeMap(K fromKey, boolean fromInclusive,
                                                 K toKey, boolean toInclusive)
        {
            return new RangeEntryMap(fromKey, fromInclusive, toKey, toInclusive);
        }
    }

    /**
     * A prefix {@link RangeEntrySet} view of the {@link Trie}
     */
    private final class PrefixRangeEntrySet extends RangeEntrySet
    {
        private final PrefixRangeMap delegate;

        private TrieEntry<K, V> prefixStart;

        private int expectedModCount = -1;

        /**
         * Creates a {@link PrefixRangeEntrySet}
         */
        public PrefixRangeEntrySet(PrefixRangeMap delegate)
        {
            super(delegate);
            this.delegate = delegate;
        }

        @Override
        public int size()
        {
            return delegate.fixup();
        }

        @Override
        public Iterator<Map.Entry<K,V>> iterator()
        {
            if (PatriciaTrie.this.modCount != expectedModCount)
            {
                prefixStart = subtree(delegate.prefix);
                expectedModCount = PatriciaTrie.this.modCount;
            }

            if (prefixStart == null)
            {
                Set<Map.Entry<K,V>> empty = Collections.emptySet();
                return empty.iterator();
            }
            else if (lengthInBits(delegate.prefix) >= prefixStart.bitIndex)
            {
                return new SingletonIterator(prefixStart);
            }
            else
            {
                return new EntryIterator(prefixStart, delegate.prefix);
            }
        }

        /**
         * An {@link Iterator} that holds a single {@link TrieEntry}.
         */
        private final class SingletonIterator implements Iterator<Map.Entry<K, V>>
        {
            private final TrieEntry<K, V> entry;

            private int hit = 0;

            public SingletonIterator(TrieEntry<K, V> entry)
            {
                this.entry = entry;
            }

            @Override
            public boolean hasNext()
            {
                return hit == 0;
            }

            @Override
            public Map.Entry<K, V> next()
            {
                if (hit != 0)
                    throw new NoSuchElementException();

                ++hit;
                return entry;
            }


            @Override
            public void remove()
            {
                if (hit != 1)
                    throw new IllegalStateException();

                ++hit;
                PatriciaTrie.this.removeEntry(entry);
            }
        }

        /**
         * An {@link Iterator} for iterating over a prefix search.
         */
        private final class EntryIterator extends TrieIterator<Map.Entry<K, V>>
        {
            // values to reset the subtree if we remove it.
            protected final K prefix;
            protected boolean lastOne;

            protected TrieEntry<K, V> subtree; // the subtree to search within

            /**
             * Starts iteration at the given entry & search only
             * within the given subtree.
             */
            EntryIterator(TrieEntry<K, V> startScan, K prefix)
            {
                subtree = startScan;
                next = PatriciaTrie.this.followLeft(startScan);
                this.prefix = prefix;
            }

            @Override
            public Map.Entry<K,V> next()
            {
                Map.Entry<K, V> entry = nextEntry();
                if (lastOne)
                    next = null;
                return entry;
            }

            @Override
            protected TrieEntry<K, V> findNext(TrieEntry<K, V> prior)
            {
                return PatriciaTrie.this.nextEntryInSubtree(prior, subtree);
            }

            @Override
            public void remove()
            {
                // If the current entry we're removing is the subtree
                // then we need to find a new subtree parent.
                boolean needsFixing = false;
                int bitIdx = subtree.bitIndex;
                if (current == subtree)
                    needsFixing = true;

                super.remove();

                // If the subtree changed its bitIndex or we
                // removed the old subtree, get a new one.
                if (bitIdx != subtree.bitIndex || needsFixing)
                    subtree = subtree(prefix);

                // If the subtree's bitIndex is less than the
                // length of our prefix, it's the last item
                // in the prefix tree.
                if (lengthInBits(prefix) >= subtree.bitIndex)
                    lastOne = true;
            }
        }
    }
}