AbstractPatriciaTrie.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You 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.commons.collections4.trie;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.AbstractCollection;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.Set;
import java.util.SortedMap;

import org.apache.commons.collections4.OrderedMapIterator;
import org.apache.commons.collections4.Trie;

/**
 * This class implements the base PATRICIA algorithm and everything that
 * is related to the {@link Map} interface.
 *
 * @param <K> the type of the keys in this map
 * @param <V> the type of the values in this map
 * @since 4.0
 */
public abstract class AbstractPatriciaTrie<K, V> extends AbstractBitwiseTrie<K, V> {

    /**
     * A range view of the {@link org.apache.commons.collections4.Trie}.
     */
    private abstract class AbstractRangeMap extends AbstractMap<K, V>
            implements SortedMap<K, V> {

        /** The {@link #entrySet()} view. */
        private transient volatile Set<Map.Entry<K, V>> entrySet;

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

        @Override
        public boolean containsKey(final Object key) {
            if (!inRange(castKey(key))) {
                return false;
            }

            return AbstractPatriciaTrie.this.containsKey(key);
        }

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

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

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

        @Override
        public V get(final Object key) {
            if (!inRange(castKey(key))) {
                return null;
            }

            return AbstractPatriciaTrie.this.get(key);
        }

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

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

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

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

            final int ret = getKeyAnalyzer().compare(key, fromKey);
            if (fromInclusive || forceInclusive) {
                return ret >= 0;
            }
            return ret > 0;
        }

        /**
         * Returns true if the provided key is greater than TO and less than FROM.
         */
        protected boolean inRange(final K key) {
            final K fromKey = getFromKey();
            final 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(final K key) {
            final K fromKey = getFromKey();
            final K toKey = getToKey();

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

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

            final int ret = getKeyAnalyzer().compare(key, toKey);
            if (toInclusive || forceInclusive) {
                return ret <= 0;
            }
            return ret < 0;
        }

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

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

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

        @Override
        public V remove(final Object key) {
            if (!inRange(castKey(key))) {
                return null;
            }

            return AbstractPatriciaTrie.this.remove(key);
        }

        @Override
        public SortedMap<K, V> subMap(final K fromKey, final 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> tailMap(final K fromKey) {
            if (!inRange2(fromKey)) {
                throw new IllegalArgumentException("FromKey is out of range: " + fromKey);
            }
            return createRangeMap(fromKey, isFromInclusive(), getToKey(), isToInclusive());
        }
    }

    /**
     * An iterator for the entries.
     */
    abstract class AbstractTrieIterator<E> implements Iterator<E> {

        /** For fast-fail. */
        protected int expectedModCount = AbstractPatriciaTrie.this.modCount;

        protected TrieEntry<K, V> next; // the next node to return
        protected TrieEntry<K, V> current; // the current entry we're on

        /**
         * Starts iteration from the root.
         */
        protected AbstractTrieIterator() {
            next = AbstractPatriciaTrie.this.nextEntry(null);
        }

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

        /**
         * @see PatriciaTrie#nextEntry(TrieEntry)
         */
        protected TrieEntry<K, V> findNext(final TrieEntry<K, V> prior) {
            return AbstractPatriciaTrie.this.nextEntry(prior);
        }

        @Override
        public boolean hasNext() {
            return next != null;
        }

        /**
         * Returns the next {@link TrieEntry}.
         */
        protected TrieEntry<K, V> nextEntry() {
            if (expectedModCount != AbstractPatriciaTrie.this.modCount) {
                throw new ConcurrentModificationException();
            }

            final TrieEntry<K, V> e = next;
            if (e == null) {
                throw new NoSuchElementException();
            }

            next = findNext(e);
            current = e;
            return e;
        }

        @Override
        public void remove() {
            if (current == null) {
                throw new IllegalStateException();
            }

            if (expectedModCount != AbstractPatriciaTrie.this.modCount) {
                throw new ConcurrentModificationException();
            }

            final TrieEntry<K, V> node = current;
            current = null;
            AbstractPatriciaTrie.this.removeEntry(node);

            expectedModCount = AbstractPatriciaTrie.this.modCount;
        }
    }

    /**
     * This is an entry set view of the {@link org.apache.commons.collections4.Trie} as returned by {@link Map#entrySet()}.
     */
    private final class EntrySet extends AbstractSet<Map.Entry<K, V>> {

        /**
         * An {@link Iterator} that returns {@link Entry} Objects.
         */
        private final class EntryIterator extends AbstractTrieIterator<Map.Entry<K, V>> {
            @Override
            public Map.Entry<K, V> next() {
                return nextEntry();
            }
        }

        @Override
        public void clear() {
            AbstractPatriciaTrie.this.clear();
        }

        @Override
        public boolean contains(final Object o) {
            if (!(o instanceof Map.Entry)) {
                return false;
            }

            final TrieEntry<K, V> candidate = getEntry(((Map.Entry<?, ?>) o).getKey());
            return candidate != null && candidate.equals(o);
        }

        @Override
        public Iterator<Map.Entry<K, V>> iterator() {
            return new EntryIterator();
        }

        @Override
        public boolean remove(final Object obj) {
            if (!(obj instanceof Map.Entry)) {
                return false;
            }
            if (!contains(obj)) {
                return false;
            }
            final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
            AbstractPatriciaTrie.this.remove(entry.getKey());
            return true;
        }

        @Override
        public int size() {
            return AbstractPatriciaTrie.this.size();
        }
    }
    /**
     * This is a key set view of the {@link org.apache.commons.collections4.Trie} as returned by {@link Map#keySet()}.
     */
    private final class KeySet extends AbstractSet<K> {

        /**
         * An {@link Iterator} that returns Key Objects.
         */
        private final class KeyIterator extends AbstractTrieIterator<K> {
            @Override
            public K next() {
                return nextEntry().getKey();
            }
        }

        @Override
        public void clear() {
            AbstractPatriciaTrie.this.clear();
        }

        @Override
        public boolean contains(final Object o) {
            return containsKey(o);
        }

        @Override
        public Iterator<K> iterator() {
            return new KeyIterator();
        }

        @Override
        public boolean remove(final Object o) {
            final int size = size();
            AbstractPatriciaTrie.this.remove(o);
            return size != size();
        }

        @Override
        public int size() {
            return AbstractPatriciaTrie.this.size();
        }
    }
    /**
     * A prefix {@link RangeEntrySet} view of the {@link org.apache.commons.collections4.Trie}.
     */
    private final class PrefixRangeEntrySet extends RangeEntrySet {

        /**
         * An {@link Iterator} for iterating over a prefix search.
         */
        private final class EntryIterator extends AbstractTrieIterator<Map.Entry<K, V>> {

            // values to reset the subtree if we remove it.
            private final K prefix;
            private final int offset;
            private final int lengthInBits;
            private boolean lastOne;

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

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

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

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

            @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;
                final 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, offset, lengthInBits);
                }

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

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

            SingletonIterator(final 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;
                AbstractPatriciaTrie.this.removeEntry(entry);
            }
        }

        private final PrefixRangeMap delegate;

        private TrieEntry<K, V> prefixStart;

        private int expectedModCount;

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

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

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

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

    /**
     * A submap used for prefix views over the {@link org.apache.commons.collections4.Trie}.
     */
    private final class PrefixRangeMap extends AbstractRangeMap {

        private final K prefix;

        private final int offsetInBits;

        private final int lengthInBits;

        private K fromKey;

        private K toKey;

        private transient int expectedModCount;

        private int size = -1;

        /**
         * Creates a {@link PrefixRangeMap}.
         */
        private PrefixRangeMap(final K prefix, final int offsetInBits, final int lengthInBits) {
            this.prefix = prefix;
            this.offsetInBits = offsetInBits;
            this.lengthInBits = lengthInBits;
        }

        @Override
        public void clear() {
            final Iterator<Map.Entry<K, V>> it = AbstractPatriciaTrie.this.entrySet().iterator();
            final Set<K> currentKeys = keySet();
            while (it.hasNext()) {
                if (currentKeys.contains(it.next().getKey())) {
                    it.remove();
                }
            }
        }

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

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

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

            Map.Entry<K, V> e = null;
            if (fromKey == null) {
                e = firstEntry();
            } else {
                e = higherEntry(fromKey);
            }

            final K first = e != null ? e.getKey() : null;
            if (e == null || !getKeyAnalyzer().isPrefix(prefix, offsetInBits, lengthInBits, first)) {
                throw new NoSuchElementException();
            }

            return first;
        }

        /**
         * This method does two things. It determines 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 org.apache.commons.collections4.Trie} has changed.
         */
        private int fixup() {
            // The trie has changed since we last found our toKey / fromKey
            if (size == - 1 || AbstractPatriciaTrie.this.modCount != expectedModCount) {
                final Iterator<Map.Entry<K, V>> it = super.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) {
                    final 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 = AbstractPatriciaTrie.this.modCount;
            }

            return size;
        }

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

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

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

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

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

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

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

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

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

            Map.Entry<K, V> e = null;
            if (toKey == null) {
                e = lastEntry();
            } else {
                e = lowerEntry(toKey);
            }

            final K last = e != null ? e.getKey() : null;
            if (e == null || !getKeyAnalyzer().isPrefix(prefix, offsetInBits, lengthInBits, last)) {
                throw new NoSuchElementException();
            }

            return last;
        }
    }

    /**
     * A {@link AbstractRangeMap} that deals with {@link Entry}s.
     */
    private final class RangeEntryMap extends AbstractRangeMap {

        /** The key to start from, null if the beginning. */
        private final K fromKey;

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

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

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

        /**
         * Creates a {@link RangeEntryMap}.
         */
        protected RangeEntryMap(final K fromKey, final boolean fromInclusive,
                                final K toKey, final boolean toInclusive) {

            if (fromKey == null && toKey == null) {
                throw new IllegalArgumentException("must have a from or to!");
            }

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

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

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

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

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

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

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

        @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
        public K lastKey() {
            final Map.Entry<K, V> e;
            if (toKey == null) {
                e = lastEntry();
            } else if (toInclusive) {
                e = floorEntry(toKey);
            } else {
                e = lowerEntry(toKey);
            }

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

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

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

            private final K excludedKey;

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

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

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

        private final AbstractRangeMap delegate;

        private transient int size = -1;

        private transient int expectedModCount;

        /**
         * Creates a {@link RangeEntrySet}.
         */
        RangeEntrySet(final AbstractRangeMap delegate) {
            this.delegate = Objects.requireNonNull(delegate, "delegate");
        }

        @SuppressWarnings("unchecked")
        @Override
        public boolean contains(final Object o) {
            if (!(o instanceof Map.Entry)) {
                return false;
            }

            final Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
            final K key = entry.getKey();
            if (!delegate.inRange(key)) {
                return false;
            }

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

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

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

            TrieEntry<K, V> first = null;
            if (fromKey == null) {
                first = firstEntry();
            } else {
                first = ceilingEntry(fromKey);
            }

            TrieEntry<K, V> last = null;
            if (toKey != null) {
                last = ceilingEntry(toKey);
            }

            return new EntryIterator(first, last);
        }

        @SuppressWarnings("unchecked")
        @Override
        public boolean remove(final Object o) {
            if (!(o instanceof Map.Entry)) {
                return false;
            }

            final Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
            final K key = entry.getKey();
            if (!delegate.inRange(key)) {
                return false;
            }

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

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

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

                expectedModCount = AbstractPatriciaTrie.this.modCount;
            }
            return size;
        }
    }

    /**
     * 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 final class Reference<E> {

        private E item;

        public E get() {
            return item;
        }

        public void set(final E item) {
            this.item = item;
        }
    }

    /**
     * A {@link org.apache.commons.collections4.Trie} is a set of {@link TrieEntry} nodes.
     *
     * @param <K> the key type.
     * @param <V> the value type.
     */
    protected static class TrieEntry<K, V> extends BasicEntry<K, V> {

        private static final long serialVersionUID = 4596023148184140013L;

        /** The index this entry is comparing. */
        protected int bitIndex;

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

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

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

        /** The entry who uplinks to this entry. */
        protected TrieEntry<K, V> predecessor;

        /**
         * Constructs a new instance.
         *
         * @param key The entry's key.
         * @param value The entry's value.
         * @param bitIndex The entry's bitIndex.
         */
        public TrieEntry(final K key, final V value, final int bitIndex) {
            super(key, value);
            this.bitIndex = bitIndex;
            this.parent = null;
            this.left = this;
            this.right = null;
            this.predecessor = this;
        }

        /**
         * Tests whether the entry is storing a key. Only the root can potentially be empty, all other nodes must have a key.
         *
         * @return Whether the entry is storing a key
         */
        public boolean isEmpty() {
            return key == null;
        }

        /**
         * Tests whether the left or right child is a loopback.
         *
         * @return Whether the left or right child is a loopback.
         */
        public boolean isExternalNode() {
            return !isInternalNode();
        }

        /**
         * Tests that neither the left nor right child is a loopback.
         *
         * @return That neither the left nor right child is a loopback.
         */
        public boolean isInternalNode() {
            return left != this && right != this;
        }

        @Override
        public String toString() {
            final StringBuilder buffer = new StringBuilder();

            if (bitIndex == -1) {
                buffer.append("RootEntry(");
            } else {
                buffer.append("Entry(");
            }

            buffer.append("key=").append(getKey()).append(" [").append(bitIndex).append("], ");
            buffer.append("value=").append(getValue()).append(", ");
            //buffer.append("bitIndex=").append(bitIndex).append(", ");

            if (parent != null) {
                if (parent.bitIndex == -1) {
                    buffer.append("parent=").append("ROOT");
                } else {
                    buffer.append("parent=").append(parent.getKey()).append(" [").append(parent.bitIndex).append("]");
                }
            } else {
                buffer.append("parent=").append("null");
            }
            buffer.append(", ");

            if (left != null) {
                if (left.bitIndex == -1) {
                    buffer.append("left=").append("ROOT");
                } else {
                    buffer.append("left=").append(left.getKey()).append(" [").append(left.bitIndex).append("]");
                }
            } else {
                buffer.append("left=").append("null");
            }
            buffer.append(", ");

            if (right != null) {
                if (right.bitIndex == -1) {
                    buffer.append("right=").append("ROOT");
                } else {
                    buffer.append("right=").append(right.getKey()).append(" [").append(right.bitIndex).append("]");
                }
            } else {
                buffer.append("right=").append("null");
            }
            buffer.append(", ");

            if (predecessor != null) {
                if (predecessor.bitIndex == -1) {
                    buffer.append("predecessor=").append("ROOT");
                } else {
                    buffer.append("predecessor=").append(predecessor.getKey()).append(" [").
                           append(predecessor.bitIndex).append("]");
                }
            }

            buffer.append(")");
            return buffer.toString();
        }
    }

    /**
     * An {@link OrderedMapIterator} for a {@link org.apache.commons.collections4.Trie}.
     */
    private final class TrieMapIterator extends AbstractTrieIterator<K> implements OrderedMapIterator<K, V> {

        protected TrieEntry<K, V> previous; // the previous node to return

        @Override
        public K getKey() {
            if (current == null) {
                throw new IllegalStateException();
            }
            return current.getKey();
        }

        @Override
        public V getValue() {
            if (current == null) {
                throw new IllegalStateException();
            }
            return current.getValue();
        }

        @Override
        public boolean hasPrevious() {
            return previous != null;
        }

        @Override
        public K next() {
            return nextEntry().getKey();
        }

        @Override
        protected TrieEntry<K, V> nextEntry() {
            final TrieEntry<K, V> nextEntry = super.nextEntry();
            previous = nextEntry;
            return nextEntry;
        }

        @Override
        public K previous() {
            return previousEntry().getKey();
        }

        protected TrieEntry<K, V> previousEntry() {
            if (expectedModCount != AbstractPatriciaTrie.this.modCount) {
                throw new ConcurrentModificationException();
            }

            final TrieEntry<K, V> e = previous;
            if (e == null) {
                throw new NoSuchElementException();
            }

            previous = AbstractPatriciaTrie.this.previousEntry(e);
            next = current;
            current = e;
            return current;
        }

        @Override
        public V setValue(final V value) {
            if (current == null) {
                throw new IllegalStateException();
            }
            return current.setValue(value);
        }

    }

    /**
     * This is a value view of the {@link org.apache.commons.collections4.Trie} as returned by {@link Map#values()}.
     */
    private final class Values extends AbstractCollection<V> {

        /**
         * An {@link Iterator} that returns Value Objects.
         */
        private final class ValueIterator extends AbstractTrieIterator<V> {
            @Override
            public V next() {
                return nextEntry().getValue();
            }
        }

        @Override
        public void clear() {
            AbstractPatriciaTrie.this.clear();
        }

        @Override
        public boolean contains(final Object o) {
            return containsValue(o);
        }

        @Override
        public Iterator<V> iterator() {
            return new ValueIterator();
        }

        @Override
        public boolean remove(final Object o) {
            for (final Iterator<V> it = iterator(); it.hasNext(); ) {
                final V value = it.next();
                if (compare(value, o)) {
                    it.remove();
                    return true;
                }
            }
            return false;
        }

        @Override
        public int size() {
            return AbstractPatriciaTrie.this.size();
        }
    }

    private static final long serialVersionUID = 5155253417231339498L;

    /**
     * Returns true if 'next' is a valid uplink coming from 'from'.
     */
    static boolean isValidUplink(final TrieEntry<?, ?> next, final TrieEntry<?, ?> from) {
        return next != null && next.bitIndex <= from.bitIndex && !next.isEmpty();
    }

    /** The root node of the {@link org.apache.commons.collections4.Trie}. */
    private transient TrieEntry<K, V> root = new TrieEntry<>(null, null, -1);

    /**
     * Each of these fields are initialized to contain an instance of the
     * appropriate view the first time this view is requested. The views are
     * stateless, so there's no reason to create more than one of each.
     */
    private transient volatile Set<K> keySet;

    private transient volatile Collection<V> values;

    private transient volatile Set<Map.Entry<K, V>> entrySet;

    /** The current size of the {@link org.apache.commons.collections4.Trie}. */
    private transient int size;

    /**
     * The number of times this {@link org.apache.commons.collections4.Trie} has been modified.
     * It's used to detect concurrent modifications and fail-fast the {@link Iterator}s.
     */
    protected transient int modCount;

    /**
     * Constructs a new {@link Trie} using the given {@link KeyAnalyzer}.
     *
     * @param keyAnalyzer  the {@link KeyAnalyzer}.
     */
    protected AbstractPatriciaTrie(final KeyAnalyzer<? super K> keyAnalyzer) {
        super(keyAnalyzer);
    }

    /**
     * Constructs a new {@link org.apache.commons.collections4.Trie} using the given {@link KeyAnalyzer} and initializes the
     * {@link org.apache.commons.collections4.Trie} with the values from the provided {@link Map}.
     *
     * @param keyAnalyzer  the {@link KeyAnalyzer}.
     * @param map The source map.
     */
    protected AbstractPatriciaTrie(final KeyAnalyzer<? super K> keyAnalyzer, final Map<? extends K, ? extends V> map) {
        super(keyAnalyzer);
        putAll(map);
    }

    /**
     * Adds the given {@link TrieEntry} to the {@link org.apache.commons.collections4.Trie}.
     */
    TrieEntry<K, V> addEntry(final TrieEntry<K, V> entry, final int lengthInBits) {
        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, lengthInBits)) {
                    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, lengthInBits)) {
                    path.left = entry;
                } else {
                    path.right = entry;
                }

                return entry;
            }

            path = current;

            if (!isBitSet(entry.key, current.bitIndex, lengthInBits)) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
    }

    /**
     * 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(final 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.)
        final int lengthInBits = lengthInBits(key);

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

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

        final int bitIndex = bitIndex(key, found.key);
        if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
            final TrieEntry<K, V> added = new TrieEntry<>(key, null, bitIndex);
            addEntry(added, lengthInBits);
            incrementSize(); // must increment because remove will decrement
            final TrieEntry<K, V> ceil = nextEntry(added);
            removeEntry(added);
            modCount -= 2; // we didn't really modify it.
            return ceil;
        }
        if (KeyAnalyzer.isNullBitKey(bitIndex)) {
            if (!root.isEmpty()) {
                return root;
            }
            return firstEntry();
        }
        if (KeyAnalyzer.isEqualBitKey(bitIndex)) {
            return found;
        }

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

    @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 Comparator<? super K> comparator() {
        return getKeyAnalyzer();
    }

    @Override
    public boolean containsKey(final Object k) {
        if (k == null) {
            return false;
        }

        final K key = castKey(k);
        final int lengthInBits = lengthInBits(key);
        final TrieEntry<K, V> entry = getNearestEntryForKey(key, lengthInBits);
        return !entry.isEmpty() && compareKeys(key, entry.key);
    }

    /**
     * A helper method to decrement the {@link org.apache.commons.collections4.Trie} size and increment the modification counter.
     */
    void decrementSize() {
        size--;
        incrementModCount();
    }

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

    /**
     * Returns the first entry the {@link org.apache.commons.collections4.Trie} is storing.
     * <p>
     * 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.
        if (isEmpty()) {
            return null;
        }

        return followLeft(root);
    }

    @Override
    public K firstKey() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return firstEntry().getKey();
    }

    /**
     * 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(final 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.)
        final int lengthInBits = lengthInBits(key);

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

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

        final int bitIndex = bitIndex(key, found.key);
        if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
            final TrieEntry<K, V> added = new TrieEntry<>(key, null, bitIndex);
            addEntry(added, lengthInBits);
            incrementSize(); // must increment because remove will decrement
            final TrieEntry<K, V> floor = previousEntry(added);
            removeEntry(added);
            modCount -= 2; // we didn't really modify it.
            return floor;
        }
        if (KeyAnalyzer.isNullBitKey(bitIndex)) {
            if (!root.isEmpty()) {
                return root;
            }
            return null;
        }
        if (KeyAnalyzer.isEqualBitKey(bitIndex)) {
            return found;
        }

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

    /**
     * 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;
        }
    }

    /**
     * Traverses down the right path until it finds an uplink.
     */
    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;
    }

    @Override
    public V get(final Object k) {
        final TrieEntry<K, V> entry = getEntry(k);
        return entry != null ? entry.getValue() : null;
    }

    /**
     * Gets the entry associated with the specified key in the
     * PatriciaTrieBase.  Returns null if the map contains no mapping
     * for this key.
     * <p>
     * This may throw ClassCastException if the object is not of type K.
     */
    TrieEntry<K, V> getEntry(final Object k) {
        final K key = castKey(k);
        if (key == null) {
            return null;
        }

        final int lengthInBits = lengthInBits(key);
        final TrieEntry<K, V> entry = getNearestEntryForKey(key, lengthInBits);
        return !entry.isEmpty() && compareKeys(key, entry.key) ? entry : null;
    }

    /**
     * Gets 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(final K key, final int lengthInBits) {
        TrieEntry<K, V> current = root.left;
        TrieEntry<K, V> path = root;
        while (true) {
            if (current.bitIndex <= path.bitIndex) {
                return current;
            }

            path = current;
            if (!isBitSet(key, current.bitIndex, lengthInBits)) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
    }

    /**
     * Gets a view of this {@link org.apache.commons.collections4.Trie} of all elements that are prefixed
     * by the number of bits in the given Key.
     * <p>
     * The view that this returns is optimized to have a very efficient
     * {@link Iterator}. The {@link SortedMap#firstKey()},
     * {@link SortedMap#lastKey()} &amp; {@link Map#size()} methods must
     * iterate over all possible values in order to determine the results.
     * This information is cached until the PATRICIA {@link org.apache.commons.collections4.Trie} changes.
     * All other methods (except {@link Iterator}) must compare the given
     * key to the prefix to ensure that it is within the range of the view.
     * The {@link Iterator}'s remove method must also relocate the subtree
     * that contains the prefixes if the entry holding the subtree is
     * removed or changes. Changing the subtree takes O(K) time.
     *
     * @param key  the key to use in the search
     * @param offsetInBits  the prefix offset
     * @param lengthInBits  the number of significant prefix bits
     * @return a {@link SortedMap} view of this {@link org.apache.commons.collections4.Trie} with all elements whose
     *   key is prefixed by the search key
     */
    private SortedMap<K, V> getPrefixMapByBits(final K key, final int offsetInBits, final int lengthInBits) {

        final int offsetLength = offsetInBits + lengthInBits;
        if (offsetLength > lengthInBits(key)) {
            throw new IllegalArgumentException(offsetInBits + " + "
                    + lengthInBits + " > " + lengthInBits(key));
        }

        if (offsetLength == 0) {
            return this;
        }

        return new PrefixRangeMap(key, offsetInBits, lengthInBits);
    }

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

    /**
     * Returns an entry strictly higher than the given key,
     * or null if no such entry exists.
     */
    TrieEntry<K, V> higherEntry(final 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.)
        final int lengthInBits = lengthInBits(key);

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

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

        final int bitIndex = bitIndex(key, found.key);
        if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
            final TrieEntry<K, V> added = new TrieEntry<>(key, null, bitIndex);
            addEntry(added, lengthInBits);
            incrementSize(); // must increment because remove will decrement
            final TrieEntry<K, V> ceil = nextEntry(added);
            removeEntry(added);
            modCount -= 2; // we didn't really modify it.
            return ceil;
        }
        if (KeyAnalyzer.isNullBitKey(bitIndex)) {
            if (!root.isEmpty()) {
                return firstEntry();
            }
            if (size() > 1) {
                return nextEntry(firstEntry());
            }
            return null;
        }
        if (KeyAnalyzer.isEqualBitKey(bitIndex)) {
            return nextEntry(found);
        }

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

    /**
     * A helper method to increment the modification counter.
     */
    private void incrementModCount() {
        ++modCount;
    }

    /**
     * A helper method to increment the {@link org.apache.commons.collections4.Trie} size and the modification counter.
     */
    void incrementSize() {
        size++;
        incrementModCount();
    }

    @Override
    public Set<K> keySet() {
        if (keySet == null) {
            keySet = new KeySet();
        }
        return keySet;
    }

    /**
     * Returns the last entry the {@link org.apache.commons.collections4.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.
     */
    TrieEntry<K, V> lastEntry() {
        return followRight(root.left);
    }

    @Override
    public K lastKey() {
        final TrieEntry<K, V> entry = lastEntry();
        if (entry != null) {
            return entry.getKey();
        }
        throw new NoSuchElementException();
    }

    /**
     * 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(final 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.)
        final int lengthInBits = lengthInBits(key);

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

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

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

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

    @Override
    public OrderedMapIterator<K, V> mapIterator() {
        return new TrieMapIterator();
    }

    /**
     * Returns the entry lexicographically after the given entry.
     * If the given entry is null, returns the first node.
     */
    TrieEntry<K, V> nextEntry(final TrieEntry<K, V> node) {
        if (node == null) {
            return firstEntry();
        }
        return 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 &amp; returned the end of the Trie, so exit.
     *
     * 7) Do Step 1 on the parent's right child.
     */
    TrieEntry<K, V> nextEntryImpl(final TrieEntry<K, V> start,
            final TrieEntry<K, V> previous, final 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 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.
     */
    TrieEntry<K, V> nextEntryInSubtree(final TrieEntry<K, V> node,
            final TrieEntry<K, V> parentOfSubtree) {
        if (node == null) {
            return firstEntry();
        }
        return nextEntryImpl(node.predecessor, node, parentOfSubtree);
    }

    @Override
    public K nextKey(final K key) {
        Objects.requireNonNull(key, "key");
        final TrieEntry<K, V> entry = getEntry(key);
        if (entry != null) {
            final TrieEntry<K, V> nextEntry = nextEntry(entry);
            return nextEntry != null ? nextEntry.getKey() : null;
        }
        return null;
    }

    @Override
    public SortedMap<K, V> prefixMap(final K key) {
        return getPrefixMapByBits(key, 0, lengthInBits(key));
    }

    /**
     * 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 &amp; root isEmpty, return null.
     *              - If it is root &amp; 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
     */
    TrieEntry<K, V> previousEntry(final TrieEntry<K, V> start) {
        if (start.predecessor == null) {
            throw new IllegalArgumentException("must have come from somewhere!");
        }

        if (start.predecessor.right == start) {
            if (isValidUplink(start.predecessor.left, start.predecessor)) {
                return start.predecessor.left;
            }
            return 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) {
                if (root.isEmpty()) {
                    return null;
                }
                return root;

            }
            return node.parent.left;
        }
        return followRight(node.parent.left);
    }

    @Override
    public K previousKey(final K key) {
        Objects.requireNonNull(key, "key");
        final TrieEntry<K, V> entry = getEntry(key);
        if (entry != null) {
            final TrieEntry<K, V> prevEntry = previousEntry(entry);
            return prevEntry != null ? prevEntry.getKey() : null;
        }
        return null;
    }

    @Override
    public V put(final K key, final V value) {
        Objects.requireNonNull(key, "key");

        final 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);
        }

        final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
        if (compareKeys(key, found.key)) {
            if (found.isEmpty()) { // <- must be the root
                incrementSize();
            } else {
                incrementModCount();
            }
            return found.setKeyValue(key, value);
        }

        final int bitIndex = bitIndex(key, found.key);
        if (!KeyAnalyzer.isOutOfBoundsIndex(bitIndex)) {
            if (KeyAnalyzer.isValidBitIndex(bitIndex)) { // in 99.999...9% the case
                /* NEW KEY+VALUE TUPLE */
                final TrieEntry<K, V> t = new TrieEntry<>(key, value, bitIndex);
                addEntry(t, lengthInBits);
                incrementSize();
                return null;
            }
            if (KeyAnalyzer.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);

            }
            if (KeyAnalyzer.isEqualBitKey(bitIndex) && found != root) { // NOPMD
                incrementModCount();
                return found.setKeyValue(key, value);
            }
        }

        throw new IllegalArgumentException("Failed to put: " + key + " -> " + value + ", " + bitIndex);
    }

    /**
     * Deserializes an instance from an ObjectInputStream.
     *
     * @param in The source ObjectInputStream.
     * @throws IOException            Any of the usual Input/Output related exceptions.
     * @throws ClassNotFoundException A class of a serialized object cannot be found.
     */
    @SuppressWarnings("unchecked") // This will fail at runtime if the stream is incorrect
    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
        in.defaultReadObject();
        root = new TrieEntry<>(null, null, -1);
        final int size = in.readInt();
        for (int i = 0; i < size; i++) {
            final K k = (K) in.readObject();
            final V v = (V) in.readObject();
            put(k, v);
        }
    }

    /**
     * {@inheritDoc}
     *
     * @throws ClassCastException if provided key is of an incompatible type
     */
    @Override
    public V remove(final Object k) {
        if (k == null) {
            return null;
        }

        final K key = castKey(k);
        final int lengthInBits = lengthInBits(key);
        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);
                }
                return null;
            }

            path = current;

            if (!isBitSet(key, current.bitIndex, lengthInBits)) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
    }

    /**
     * Removes a single entry from the {@link org.apache.commons.collections4.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(final TrieEntry<K, V> h) {
        if (h != root) {
            if (h.isInternalNode()) {
                removeInternalEntry(h);
            } else {
                removeExternalEntry(h);
            }
        }

        decrementSize();
        return h.setKeyValue(null, null);
    }

    /**
     * Removes an external entry from the {@link org.apache.commons.collections4.Trie}.
     *
     * If it's an external Entry then just remove it.
     * This is very easy and straight forward.
     */
    private void removeExternalEntry(final TrieEntry<K, V> h) {
        if (h == root) {
            throw new IllegalArgumentException("Cannot delete root Entry!");
        }
        if (!h.isExternalNode()) {
            throw new IllegalArgumentException(h + " is not an external Entry!");
        }

        final TrieEntry<K, V> parent = h.parent;
        final TrieEntry<K, V> child = h.left == h ? h.right : h.left;

        if (parent.left == h) {
            parent.left = child;
        } else {
            parent.right = child;
        }

        // either the parent is changing, or the predecessor is changing.
        if (child.bitIndex > parent.bitIndex) {
            child.parent = parent;
        } else {
            child.predecessor = parent;
        }

    }

    /**
     * Removes an internal entry from the {@link org.apache.commons.collections4.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(final TrieEntry<K, V> h) {
        if (h == root) {
            throw new IllegalArgumentException("Cannot delete root Entry!");
        }
        if (!h.isInternalNode()) {
            throw new IllegalArgumentException(h + " is not an internal Entry!");
        }

        final TrieEntry<K, V> p = h.predecessor;

        // Set P's bitIndex
        p.bitIndex = h.bitIndex;

        // Fix P's parent, predecessor and child Nodes
        {
            final TrieEntry<K, V> parent = p.parent;
            final TrieEntry<K, V> child = p.left == h ? p.right : p.left;

            // if it was looping to itself previously,
            // it will now be pointed from its parent
            // (if we aren't removing its 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 {@link java.util.Map.Entry} whose key is closest in a bitwise XOR
     * metric to the given key. This is NOT lexicographic closeness.
     * For example, given the keys:
     *
     * <ol>
     * <li>D = 1000100
     * <li>H = 1001000
     * <li>L = 1001100
     * </ol>
     *
     * If the {@link org.apache.commons.collections4.Trie} contained 'H' and 'L', a lookup of 'D' would
     * return 'L', because the XOR distance between D &amp; L is smaller
     * than the XOR distance between D &amp; H.
     *
     * @param key  the key to use in the search
     * @return the {@link java.util.Map.Entry} whose key is closest in a bitwise XOR metric
     *   to the provided key
     */
    public Map.Entry<K, V> select(final K key) {
        final int lengthInBits = lengthInBits(key);
        final Reference<Map.Entry<K, V>> reference = new Reference<>();
        if (!selectR(root.left, -1, key, lengthInBits, reference)) {
            return reference.get();
        }
        return null;
    }

    /**
     * Returns the key that is closest in a bitwise XOR metric to the
     * provided key. This is NOT lexicographic closeness!
     *
     * For example, given the keys:
     *
     * <ol>
     * <li>D = 1000100
     * <li>H = 1001000
     * <li>L = 1001100
     * </ol>
     *
     * If the {@link org.apache.commons.collections4.Trie} contained 'H' and 'L', a lookup of 'D' would
     * return 'L', because the XOR distance between D &amp; L is smaller
     * than the XOR distance between D &amp; H.
     *
     * @param key  the key to use in the search
     * @return the key that is closest in a bitwise XOR metric to the provided key
     */
    public K selectKey(final K key) {
        final Map.Entry<K, V> entry = select(key);
        if (entry == null) {
            return null;
        }
        return entry.getKey();
    }

    private boolean selectR(final TrieEntry<K, V> h, final int bitIndex,
                            final K key, final int lengthInBits,
                            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, lengthInBits)) {
            if (selectR(h.left, h.bitIndex, key, lengthInBits, reference)) {
                return selectR(h.right, h.bitIndex, key, lengthInBits, reference);
            }
        } else if (selectR(h.right, h.bitIndex, key, lengthInBits, reference)) {
            return selectR(h.left, h.bitIndex, key, lengthInBits, reference);
        }
        return false;
    }

    /**
     * Returns the value whose key is closest in a bitwise XOR metric to
     * the provided key. This is NOT lexicographic closeness!
     *
     * For example, given the keys:
     *
     * <ol>
     * <li>D = 1000100
     * <li>H = 1001000
     * <li>L = 1001100
     * </ol>
     *
     * If the {@link org.apache.commons.collections4.Trie} contained 'H' and 'L', a lookup of 'D' would
     * return 'L', because the XOR distance between D &amp; L is smaller
     * than the XOR distance between D &amp; H.
     *
     * @param key  the key to use in the search
     * @return the value whose key is closest in a bitwise XOR metric
     * to the provided key
     */
    public V selectValue(final K key) {
        final Map.Entry<K, V> entry = select(key);
        if (entry == null) {
            return null;
        }
        return entry.getValue();
    }

    @Override
    public int size() {
        return size;
    }

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

    /**
     * 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.
     */
    TrieEntry<K, V> subtree(final K prefix, final int offsetInBits, final int lengthInBits) {
        TrieEntry<K, V> current = root.left;
        TrieEntry<K, V> path = root;
        while (true) {
            if (current.bitIndex <= path.bitIndex || lengthInBits <= current.bitIndex) {
                break;
            }

            path = current;
            if (!isBitSet(prefix, offsetInBits + current.bitIndex, offsetInBits + lengthInBits)) {
                current = current.left;
            } else {
                current = current.right;
            }
        }

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

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

        final int endIndexInBits = offsetInBits + lengthInBits;

        // 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()) < endIndexInBits) {
            return null;
        }

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

        // ... or there are less than 'length' equal bits
        final int bitIndex = getKeyAnalyzer().bitIndex(prefix, offsetInBits, lengthInBits,
                                                       entry.key, 0, lengthInBits(entry.getKey()));

        if (bitIndex >= 0 && bitIndex < lengthInBits) {
            return null;
        }

        return entry;
    }

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

    @Override
    public Collection<V> values() {
        if (values == null) {
            values = new Values();
        }
        return values;
    }

    /**
     * Serializes this object to an ObjectOutputStream.
     *
     * @param out the target ObjectOutputStream.
     * @throws IOException thrown when an I/O errors occur writing to the target stream.
     */
    private void writeObject(final ObjectOutputStream out) throws IOException {
        out.defaultWriteObject();
        out.writeInt(this.size());
        for (final Entry<K, V> entry : entrySet()) {
            out.writeObject(entry.getKey());
            out.writeObject(entry.getValue());
        }
    }

}