    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one or more
    003 * contributor license agreements.  See the NOTICE file distributed with
    004 * this work for additional information regarding copyright ownership.
    005 * The ASF licenses this file to You under the Apache License, Version 2.0
    006 * (the "License"); you may not use this file except in compliance with
    007 * the License.  You may obtain a copy of the License at
    008 *
    009 *      https://www.apache.org/licenses/LICENSE-2.0
    010 *
    011 * Unless required by applicable law or agreed to in writing, software
    012 * distributed under the License is distributed on an "AS IS" BASIS,
    013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014 * See the License for the specific language governing permissions and
    015 * limitations under the License.
    016 */
    017package org.apache.commons.collections4.trie;
    018
    019import java.io.IOException;
    020import java.io.ObjectInputStream;
    021import java.io.ObjectOutputStream;
    022import java.util.AbstractCollection;
    023import java.util.AbstractMap;
    024import java.util.AbstractSet;
    025import java.util.Collection;
    026import java.util.Collections;
    027import java.util.Comparator;
    028import java.util.ConcurrentModificationException;
    029import java.util.Iterator;
    030import java.util.Map;
    031import java.util.NoSuchElementException;
    032import java.util.Objects;
    033import java.util.Set;
    034import java.util.SortedMap;
    035
    036import org.apache.commons.collections4.OrderedMapIterator;
    037import org.apache.commons.collections4.Trie;
    038
    039/**
    040 * This class implements the base PATRICIA algorithm and everything that
    041 * is related to the {@link Map} interface.
    042 *
    043 * @param <K> The type of the keys in this map
    044 * @param <V> The type of the values in this map
    045 * @since 4.0
    046 */
    047public abstract class AbstractPatriciaTrie<K, V> extends AbstractBitwiseTrie<K, V> {
    048
    049    /**
    050     * A range view of the {@link Trie}.
    051     */
    052    private abstract class AbstractRangeMap extends AbstractMap<K, V>
    053            implements SortedMap<K, V> {
    054
    055        /** The {@link #entrySet()} view. */
    056        private transient volatile Set<Map.Entry<K, V>> entrySet;
    057
    058        @Override
    059        public Comparator<? super K> comparator() {
    060            return AbstractPatriciaTrie.this.comparator();
    061        }
    062
    063        @Override
    064        public boolean containsKey(final Object key) {
    065            if (!inRange(castKey(key))) {
    066                return false;
    067            }
    068
    069            return AbstractPatriciaTrie.this.containsKey(key);
    070        }
    071
    072        /**
    073         * Creates and returns an {@link #entrySet()} view of the {@link AbstractRangeMap}.
    074         */
    075        protected abstract Set<Map.Entry<K, V>> createEntrySet();
    076
    077        /**
    078         * Creates and returns a sub-range view of the current {@link AbstractRangeMap}.
    079         */
    080        protected abstract SortedMap<K, V> createRangeMap(K fromKey, boolean fromInclusive,
    081                                                          K toKey, boolean toInclusive);
    082
    083        @Override
    084        public Set<Map.Entry<K, V>> entrySet() {
    085            if (entrySet == null) {
    086                entrySet = createEntrySet();
    087            }
    088            return entrySet;
    089        }
    090
    091        @Override
    092        public V get(final Object key) {
    093            if (!inRange(castKey(key))) {
    094                return null;
    095            }
    096
    097            return AbstractPatriciaTrie.this.get(key);
    098        }
    099
    100        /**
    101         * Gets the FROM Key.
    102         */
    103        protected abstract K getFromKey();
    104
    105        /**
    106         * Gets the TO Key.
    107         */
    108        protected abstract K getToKey();
    109
    110        @Override
    111        public SortedMap<K, V> headMap(final K toKey) {
    112            if (!inRange2(toKey)) {
    113                throw new IllegalArgumentException("ToKey is out of range: " + toKey);
    114            }
    115            return createRangeMap(getFromKey(), isFromInclusive(), toKey, isToInclusive());
    116        }
    117
    118        /**
    119         * Returns true if the provided key is in the FROM range of the {@link AbstractRangeMap}.
    120         */
    121        protected boolean inFromRange(final K key, final boolean forceInclusive) {
    122            final K fromKey = getFromKey();
    123            final boolean fromInclusive = isFromInclusive();
    124
    125            final int ret = getKeyAnalyzer().compare(key, fromKey);
    126            if (fromInclusive || forceInclusive) {
    127                return ret >= 0;
    128            }
    129            return ret > 0;
    130        }
    131
    132        /**
    133         * Returns true if the provided key is greater than TO and less than FROM.
    134         */
    135        protected boolean inRange(final K key) {
    136            final K fromKey = getFromKey();
    137            final K toKey = getToKey();
    138
    139            return (fromKey == null || inFromRange(key, false)) && (toKey == null || inToRange(key, false));
    140        }
    141
    142        /**
    143         * This form allows the high endpoint (as well as all legit keys).
    144         */
    145        protected boolean inRange2(final K key) {
    146            final K fromKey = getFromKey();
    147            final K toKey = getToKey();
    148
    149            return (fromKey == null || inFromRange(key, false)) && (toKey == null || inToRange(key, true));
    150        }
    151
    152        /**
    153         * Returns true if the provided key is in the TO range of the {@link AbstractRangeMap}.
    154         */
    155        protected boolean inToRange(final K key, final boolean forceInclusive) {
    156            final K toKey = getToKey();
    157            final boolean toInclusive = isToInclusive();
    158
    159            final int ret = getKeyAnalyzer().compare(key, toKey);
    160            if (toInclusive || forceInclusive) {
    161                return ret <= 0;
    162            }
    163            return ret < 0;
    164        }
    165
    166        /**
    167         * Tests whether or not the {@link #getFromKey()} is in the range.
    168         *
    169         * @return whether or not the {@link #getFromKey()} is in the range.
    170         */
    171        protected abstract boolean isFromInclusive();
    172
    173        /**
    174         * Tests whether or not the {@link #getToKey()} is in the range.
    175         *
    176         * @return whether or not the {@link #getToKey()} is in the range.
    177         */
    178        protected abstract boolean isToInclusive();
    179
    180        @Override
    181        public V put(final K key, final V value) {
    182            if (!inRange(key)) {
    183                throw new IllegalArgumentException("Key is out of range: " + key);
    184            }
    185            return AbstractPatriciaTrie.this.put(key, value);
    186        }
    187
    188        @Override
    189        public V remove(final Object key) {
    190            if (!inRange(castKey(key))) {
    191                return null;
    192            }
    193
    194            return AbstractPatriciaTrie.this.remove(key);
    195        }
    196
    197        @Override
    198        public SortedMap<K, V> subMap(final K fromKey, final K toKey) {
    199            if (!inRange2(fromKey)) {
    200                throw new IllegalArgumentException("FromKey is out of range: " + fromKey);
    201            }
    202
    203            if (!inRange2(toKey)) {
    204                throw new IllegalArgumentException("ToKey is out of range: " + toKey);
    205            }
    206
    207            return createRangeMap(fromKey, isFromInclusive(), toKey, isToInclusive());
    208        }
    209
    210        @Override
    211        public SortedMap<K, V> tailMap(final K fromKey) {
    212            if (!inRange2(fromKey)) {
    213                throw new IllegalArgumentException("FromKey is out of range: " + fromKey);
    214            }
    215            return createRangeMap(fromKey, isFromInclusive(), getToKey(), isToInclusive());
    216        }
    217    }
    218
    219    /**
    220     * An iterator for the entries.
    221     */
    222    abstract class AbstractTrieIterator<E> implements Iterator<E> {
    223
    224        /** For fast-fail. */
    225        protected int expectedModCount = AbstractPatriciaTrie.this.modCount;
    226
    227        protected TrieEntry<K, V> next; // the next node to return
    228        protected TrieEntry<K, V> current; // the current entry we're on
    229
    230        /**
    231         * Starts iteration from the root.
    232         */
    233        protected AbstractTrieIterator() {
    234            next = AbstractPatriciaTrie.this.nextEntry(null);
    235        }
    236
    237        /**
    238         * Starts iteration at the given entry.
    239         */
    240        protected AbstractTrieIterator(final TrieEntry<K, V> firstEntry) {
    241            next = firstEntry;
    242        }
    243
    244        /**
    245         * @see PatriciaTrie#nextEntry(TrieEntry)
    246         */
    247        protected TrieEntry<K, V> findNext(final TrieEntry<K, V> prior) {
    248            return AbstractPatriciaTrie.this.nextEntry(prior);
    249        }
    250
    251        @Override
    252        public boolean hasNext() {
    253            return next != null;
    254        }
    255
    256        /**
    257         * Returns the next {@link TrieEntry}.
    258         */
    259        protected TrieEntry<K, V> nextEntry() {
    260            if (expectedModCount != AbstractPatriciaTrie.this.modCount) {
    261                throw new ConcurrentModificationException();
    262            }
    263
    264            final TrieEntry<K, V> e = next;
    265            if (e == null) {
    266                throw new NoSuchElementException();
    267            }
    268
    269            next = findNext(e);
    270            current = e;
    271            return e;
    272        }
    273
    274        @Override
    275        public void remove() {
    276            if (current == null) {
    277                throw new IllegalStateException();
    278            }
    279
    280            if (expectedModCount != AbstractPatriciaTrie.this.modCount) {
    281                throw new ConcurrentModificationException();
    282            }
    283
    284            final TrieEntry<K, V> node = current;
    285            current = null;
    286            AbstractPatriciaTrie.this.removeEntry(node);
    287
    288            expectedModCount = AbstractPatriciaTrie.this.modCount;
    289        }
    290    }
    291
    292    /**
    293     * This is an entry set view of the {@link Trie} as returned by {@link Map#entrySet()}.
    294     */
    295    private final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
    296
    297        /**
    298         * An {@link Iterator} that returns {@link Entry} Objects.
    299         */
    300        private final class EntryIterator extends AbstractTrieIterator<Map.Entry<K, V>> {
    301            @Override
    302            public Map.Entry<K, V> next() {
    303                return nextEntry();
    304            }
    305        }
    306
    307        @Override
    308        public void clear() {
    309            AbstractPatriciaTrie.this.clear();
    310        }
    311
    312        @Override
    313        public boolean contains(final Object o) {
    314            if (!(o instanceof Map.Entry)) {
    315                return false;
    316            }
    317
    318            final TrieEntry<K, V> candidate = getEntry(((Map.Entry<?, ?>) o).getKey());
    319            return candidate != null && candidate.equals(o);
    320        }
    321
    322        @Override
    323        public Iterator<Map.Entry<K, V>> iterator() {
    324            return new EntryIterator();
    325        }
    326
    327        @Override
    328        public boolean remove(final Object obj) {
    329            if (!(obj instanceof Map.Entry)) {
    330                return false;
    331            }
    332            if (!contains(obj)) {
    333                return false;
    334            }
    335            final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
    336            AbstractPatriciaTrie.this.remove(entry.getKey());
    337            return true;
    338        }
    339
    340        @Override
    341        public int size() {
    342            return AbstractPatriciaTrie.this.size();
    343        }
    344    }
    345
    346    /**
    347     * This is a key set view of the {@link Trie} as returned by {@link Map#keySet()}.
    348     */
    349    private final class KeySet extends AbstractSet<K> {
    350
    351        /**
    352         * An {@link Iterator} that returns Key Objects.
    353         */
    354        private final class KeyIterator extends AbstractTrieIterator<K> {
    355            @Override
    356            public K next() {
    357                return nextEntry().getKey();
    358            }
    359        }
    360
    361        @Override
    362        public void clear() {
    363            AbstractPatriciaTrie.this.clear();
    364        }
    365
    366        @Override
    367        public boolean contains(final Object o) {
    368            return containsKey(o);
    369        }
    370
    371        @Override
    372        public Iterator<K> iterator() {
    373            return new KeyIterator();
    374        }
    375
    376        @Override
    377        public boolean remove(final Object o) {
    378            final int size = size();
    379            AbstractPatriciaTrie.this.remove(o);
    380            return size != size();
    381        }
    382
    383        @Override
    384        public int size() {
    385            return AbstractPatriciaTrie.this.size();
    386        }
    387    }
    388
    389    /**
    390     * A prefix {@link RangeEntrySet} view of the {@link Trie}.
    391     */
    392    private final class PrefixRangeEntrySet extends RangeEntrySet {
    393
    394        /**
    395         * An {@link Iterator} for iterating over a prefix search.
    396         */
    397        private final class EntryIterator extends AbstractTrieIterator<Map.Entry<K, V>> {
    398
    399            // values to reset the subtree if we remove it.
    400            private final K prefix;
    401            private final int offset;
    402            private final int lengthInBits;
    403            private boolean lastOne;
    404
    405            private TrieEntry<K, V> subtree; // the subtree to search within
    406
    407            /**
    408             * Starts iteration at the given entry &amp; search only
    409             * within the given subtree.
    410             */
    411            EntryIterator(final TrieEntry<K, V> startScan, final K prefix,
    412                    final int offset, final int lengthInBits) {
    413                subtree = startScan;
    414                next = AbstractPatriciaTrie.this.followLeft(startScan);
    415                this.prefix = prefix;
    416                this.offset = offset;
    417                this.lengthInBits = lengthInBits;
    418            }
    419
    420            @Override
    421            protected TrieEntry<K, V> findNext(final TrieEntry<K, V> prior) {
    422                return AbstractPatriciaTrie.this.nextEntryInSubtree(prior, subtree);
    423            }
    424
    425            @Override
    426            public Map.Entry<K, V> next() {
    427                final Map.Entry<K, V> entry = nextEntry();
    428                if (lastOne) {
    429                    next = null;
    430                }
    431                return entry;
    432            }
    433
    434            @Override
    435            public void remove() {
    436                // If the current entry we're removing is the subtree
    437                // then we need to find a new subtree parent.
    438                boolean needsFixing = false;
    439                final int bitIdx = subtree.bitIndex;
    440                if (current == subtree) {
    441                    needsFixing = true;
    442                }
    443
    444                super.remove();
    445
    446                // If the subtree changed its bitIndex or we
    447                // removed the old subtree, get a new one.
    448                if (bitIdx != subtree.bitIndex || needsFixing) {
    449                    subtree = subtree(prefix, offset, lengthInBits);
    450                }
    451
    452                // If the subtree's bitIndex is less than the
    453                // length of our prefix, it's the last item
    454                // in the prefix tree.
    455                if (lengthInBits >= subtree.bitIndex) {
    456                    lastOne = true;
    457                }
    458            }
    459        }
    460
    461        /**
    462         * An {@link Iterator} that holds a single {@link TrieEntry}.
    463         */
    464        private final class SingletonIterator implements Iterator<Map.Entry<K, V>> {
    465
    466            private final TrieEntry<K, V> entry;
    467
    468            private int hit;
    469
    470            SingletonIterator(final TrieEntry<K, V> entry) {
    471                this.entry = entry;
    472            }
    473
    474            @Override
    475            public boolean hasNext() {
    476                return hit == 0;
    477            }
    478
    479            @Override
    480            public Map.Entry<K, V> next() {
    481                if (hit != 0) {
    482                    throw new NoSuchElementException();
    483                }
    484
    485                ++hit;
    486                return entry;
    487            }
    488
    489            @Override
    490            public void remove() {
    491                if (hit != 1) {
    492                    throw new IllegalStateException();
    493                }
    494
    495                ++hit;
    496                AbstractPatriciaTrie.this.removeEntry(entry);
    497            }
    498        }
    499
    500        private final PrefixRangeMap delegate;
    501
    502        private TrieEntry<K, V> prefixStart;
    503
    504        private int expectedModCount;
    505
    506        /**
    507         * Creates a {@link PrefixRangeEntrySet}.
    508         */
    509        PrefixRangeEntrySet(final PrefixRangeMap delegate) {
    510            super(delegate);
    511            this.delegate = delegate;
    512        }
    513
    514        @Override
    515        public Iterator<Map.Entry<K, V>> iterator() {
    516            if (AbstractPatriciaTrie.this.modCount != expectedModCount) {
    517                prefixStart = subtree(delegate.prefix, delegate.offsetInBits, delegate.lengthInBits);
    518                expectedModCount = AbstractPatriciaTrie.this.modCount;
    519            }
    520
    521            if (prefixStart == null) {
    522                final Set<Map.Entry<K, V>> empty = Collections.emptySet();
    523                return empty.iterator();
    524            }
    525            if (delegate.lengthInBits > prefixStart.bitIndex) {
    526                return new SingletonIterator(prefixStart);
    527            }
    528            return new EntryIterator(prefixStart, delegate.prefix, delegate.offsetInBits, delegate.lengthInBits);
    529        }
    530
    531        @Override
    532        public int size() {
    533            return delegate.fixup();
    534        }
    535    }
    536
    537    /**
    538     * A submap used for prefix views over the {@link Trie}.
    539     */
    540    private final class PrefixRangeMap extends AbstractRangeMap {
    541
    542        private final K prefix;
    543
    544        private final int offsetInBits;
    545
    546        private final int lengthInBits;
    547
    548        private K fromKey;
    549
    550        private K toKey;
    551
    552        private transient int expectedModCount;
    553
    554        private int size = -1;
    555
    556        /**
    557         * Creates a {@link PrefixRangeMap}.
    558         */
    559        private PrefixRangeMap(final K prefix, final int offsetInBits, final int lengthInBits) {
    560            this.prefix = prefix;
    561            this.offsetInBits = offsetInBits;
    562            this.lengthInBits = lengthInBits;
    563        }
    564
    565        @Override
    566        public void clear() {
    567            final Iterator<Map.Entry<K, V>> it = AbstractPatriciaTrie.this.entrySet().iterator();
    568            final Set<K> currentKeys = keySet();
    569            while (it.hasNext()) {
    570                if (currentKeys.contains(it.next().getKey())) {
    571                    it.remove();
    572                }
    573            }
    574        }
    575
    576        @Override
    577        protected Set<Map.Entry<K, V>> createEntrySet() {
    578            return new PrefixRangeEntrySet(this);
    579        }
    580
    581        @Override
    582        protected SortedMap<K, V> createRangeMap(final K fromKey, final boolean fromInclusive,
    583                                                 final K toKey, final boolean toInclusive) {
    584            return new RangeEntryMap(fromKey, fromInclusive, toKey, toInclusive);
    585        }
    586
    587        @Override
    588        public K firstKey() {
    589            fixup();
    590
    591            Map.Entry<K, V> e = null;
    592            if (fromKey == null) {
    593                e = firstEntry();
    594            } else {
    595                e = higherEntry(fromKey);
    596            }
    597
    598            final K first = e != null ? e.getKey() : null;
    599            if (e == null || !getKeyAnalyzer().isPrefix(prefix, offsetInBits, lengthInBits, first)) {
    600                throw new NoSuchElementException();
    601            }
    602
    603            return first;
    604        }
    605
    606        /**
    607         * This method does two things. It determines the FROM
    608         * and TO range of the {@link PrefixRangeMap} and the number
    609         * of elements in the range. This method must be called every
    610         * time the {@link Trie} has changed.
    611         */
    612        private int fixup() {
    613            // The trie has changed since we last found our toKey / fromKey
    614            if (size == - 1 || AbstractPatriciaTrie.this.modCount != expectedModCount) {
    615                final Iterator<Map.Entry<K, V>> it = super.entrySet().iterator();
    616                size = 0;
    617
    618                Map.Entry<K, V> entry = null;
    619                if (it.hasNext()) {
    620                    entry = it.next();
    621                    size = 1;
    622                }
    623
    624                fromKey = entry == null ? null : entry.getKey();
    625                if (fromKey != null) {
    626                    final TrieEntry<K, V> prior = previousEntry((TrieEntry<K, V>) entry);
    627                    fromKey = prior == null ? null : prior.getKey();
    628                }
    629
    630                toKey = fromKey;
    631
    632                while (it.hasNext()) {
    633                    ++size;
    634                    entry = it.next();
    635                }
    636
    637                toKey = entry == null ? null : entry.getKey();
    638
    639                if (toKey != null) {
    640                    entry = nextEntry((TrieEntry<K, V>) entry);
    641                    toKey = entry == null ? null : entry.getKey();
    642                }
    643
    644                expectedModCount = AbstractPatriciaTrie.this.modCount;
    645            }
    646
    647            return size;
    648        }
    649
    650        @Override
    651        public K getFromKey() {
    652            return fromKey;
    653        }
    654
    655        @Override
    656        public K getToKey() {
    657            return toKey;
    658        }
    659
    660        /**
    661         * Returns true if the provided Key is in the FROM range of the {@link PrefixRangeMap}.
    662         */
    663        @Override
    664        protected boolean inFromRange(final K key, final boolean forceInclusive) {
    665            return getKeyAnalyzer().isPrefix(prefix, offsetInBits, lengthInBits, key);
    666        }
    667
    668        /**
    669         * Returns true if this {@link PrefixRangeMap}'s key is a prefix of the provided key.
    670         */
    671        @Override
    672        protected boolean inRange(final K key) {
    673            return getKeyAnalyzer().isPrefix(prefix, offsetInBits, lengthInBits, key);
    674        }
    675
    676        /**
    677         * Same as {@link #inRange(Object)}.
    678         */
    679        @Override
    680        protected boolean inRange2(final K key) {
    681            return inRange(key);
    682        }
    683
    684        /**
    685         * Returns true if the provided Key is in the TO range of the {@link PrefixRangeMap}.
    686         */
    687        @Override
    688        protected boolean inToRange(final K key, final boolean forceInclusive) {
    689            return getKeyAnalyzer().isPrefix(prefix, offsetInBits, lengthInBits, key);
    690        }
    691
    692        @Override
    693        public boolean isFromInclusive() {
    694            return false;
    695        }
    696
    697        @Override
    698        public boolean isToInclusive() {
    699            return false;
    700        }
    701
    702        @Override
    703        public K lastKey() {
    704            fixup();
    705
    706            Map.Entry<K, V> e = null;
    707            if (toKey == null) {
    708                e = lastEntry();
    709            } else {
    710                e = lowerEntry(toKey);
    711            }
    712
    713            final K last = e != null ? e.getKey() : null;
    714            if (e == null || !getKeyAnalyzer().isPrefix(prefix, offsetInBits, lengthInBits, last)) {
    715                throw new NoSuchElementException();
    716            }
    717
    718            return last;
    719        }
    720    }
    721
    722    /**
    723     * A {@link AbstractRangeMap} that deals with {@link Entry}s.
    724     */
    725    private final class RangeEntryMap extends AbstractRangeMap {
    726
    727        /** The key to start from, null if the beginning. */
    728        private final K fromKey;
    729
    730        /** The key to end at, null if till the end. */
    731        private final K toKey;
    732
    733        /** Whether or not the 'from' is inclusive. */
    734        private final boolean fromInclusive;
    735
    736        /** Whether or not the 'to' is inclusive. */
    737        private final boolean toInclusive;
    738
    739        /**
    740         * Creates a {@link RangeEntryMap}.
    741         */
    742        protected RangeEntryMap(final K fromKey, final boolean fromInclusive,
    743                                final K toKey, final boolean toInclusive) {
    744
    745            if (fromKey == null && toKey == null) {
    746                throw new IllegalArgumentException("must have a from or to.");
    747            }
    748
    749            if (fromKey != null && toKey != null && getKeyAnalyzer().compare(fromKey, toKey) > 0) {
    750                throw new IllegalArgumentException("fromKey > toKey");
    751            }
    752
    753            this.fromKey = fromKey;
    754            this.fromInclusive = fromInclusive;
    755            this.toKey = toKey;
    756            this.toInclusive = toInclusive;
    757        }
    758
    759        /**
    760         * Creates a {@link RangeEntryMap} with the fromKey included and
    761         * the toKey excluded from the range.
    762         */
    763        protected RangeEntryMap(final K fromKey, final K toKey) {
    764            this(fromKey, true, toKey, false);
    765        }
    766
    767        @Override
    768        protected Set<Entry<K, V>> createEntrySet() {
    769            return new RangeEntrySet(this);
    770        }
    771
    772        @Override
    773        protected SortedMap<K, V> createRangeMap(final K fromKey, final boolean fromInclusive,
    774                                                 final K toKey, final boolean toInclusive) {
    775            return new RangeEntryMap(fromKey, fromInclusive, toKey, toInclusive);
    776        }
    777
    778        @Override
    779        public K firstKey() {
    780            Map.Entry<K, V> e = null;
    781            if (fromKey == null) {
    782                e = firstEntry();
    783            } else if (fromInclusive) {
    784                e = ceilingEntry(fromKey);
    785            } else {
    786                e = higherEntry(fromKey);
    787            }
    788
    789            final K first = e != null ? e.getKey() : null;
    790            if (e == null || toKey != null && !inToRange(first, false)) {
    791                throw new NoSuchElementException();
    792            }
    793            return first;
    794        }
    795
    796        @Override
    797        public K getFromKey() {
    798            return fromKey;
    799        }
    800
    801        @Override
    802        public K getToKey() {
    803            return toKey;
    804        }
    805
    806        @Override
    807        public boolean isFromInclusive() {
    808            return fromInclusive;
    809        }
    810
    811        @Override
    812        public boolean isToInclusive() {
    813            return toInclusive;
    814        }
    815
    816        @Override
    817        public K lastKey() {
    818            final Map.Entry<K, V> e;
    819            if (toKey == null) {
    820                e = lastEntry();
    821            } else if (toInclusive) {
    822                e = floorEntry(toKey);
    823            } else {
    824                e = lowerEntry(toKey);
    825            }
    826
    827            final K last = e != null ? e.getKey() : null;
    828            if (e == null || fromKey != null && !inFromRange(last, false)) {
    829                throw new NoSuchElementException();
    830            }
    831            return last;
    832        }
    833    }
    834
    835    /**
    836     * A {@link Set} view of a {@link AbstractRangeMap}.
    837     */
    838    private class RangeEntrySet extends AbstractSet<Map.Entry<K, V>> {
    839
    840        /**
    841         * An {@link Iterator} for {@link RangeEntrySet}s.
    842         */
    843        private final class EntryIterator extends AbstractTrieIterator<Map.Entry<K, V>> {
    844
    845            private final K excludedKey;
    846
    847            /**
    848             * Creates a {@link EntryIterator}.
    849             */
    850            private EntryIterator(final TrieEntry<K, V> first, final TrieEntry<K, V> last) {
    851                super(first);
    852                this.excludedKey = last != null ? last.getKey() : null;
    853            }
    854
    855            @Override
    856            public boolean hasNext() {
    857                return next != null && !compare(next.key, excludedKey);
    858            }
    859
    860            @Override
    861            public Map.Entry<K, V> next() {
    862                if (next == null || compare(next.key, excludedKey)) {
    863                    throw new NoSuchElementException();
    864                }
    865                return nextEntry();
    866            }
    867        }
    868
    869        private final AbstractRangeMap delegate;
    870
    871        private transient int size = -1;
    872
    873        private transient int expectedModCount;
    874
    875        /**
    876         * Creates a {@link RangeEntrySet}.
    877         */
    878        RangeEntrySet(final AbstractRangeMap delegate) {
    879            this.delegate = Objects.requireNonNull(delegate, "delegate");
    880        }
    881
    882        @SuppressWarnings("unchecked")
    883        @Override
    884        public boolean contains(final Object o) {
    885            if (!(o instanceof Map.Entry)) {
    886                return false;
    887            }
    888
    889            final Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
    890            final K key = entry.getKey();
    891            if (!delegate.inRange(key)) {
    892                return false;
    893            }
    894
    895            final TrieEntry<K, V> node = getEntry(key);
    896            return node != null && compare(node.getValue(), entry.getValue());
    897        }
    898
    899        @Override
    900        public boolean isEmpty() {
    901            return !iterator().hasNext();
    902        }
    903
    904        @Override
    905        public Iterator<Map.Entry<K, V>> iterator() {
    906            final K fromKey = delegate.getFromKey();
    907            final K toKey = delegate.getToKey();
    908
    909            TrieEntry<K, V> first = null;
    910            if (fromKey == null) {
    911                first = firstEntry();
    912            } else {
    913                first = ceilingEntry(fromKey);
    914            }
    915
    916            TrieEntry<K, V> last = null;
    917            if (toKey != null) {
    918                last = ceilingEntry(toKey);
    919            }
    920
    921            return new EntryIterator(first, last);
    922        }
    923
    924        @SuppressWarnings("unchecked")
    925        @Override
    926        public boolean remove(final Object o) {
    927            if (!(o instanceof Map.Entry)) {
    928                return false;
    929            }
    930
    931            final Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
    932            final K key = entry.getKey();
    933            if (!delegate.inRange(key)) {
    934                return false;
    935            }
    936
    937            final TrieEntry<K, V> node = getEntry(key);
    938            if (node != null && compare(node.getValue(), entry.getValue())) {
    939                removeEntry(node);
    940                return true;
    941            }
    942            return false;
    943        }
    944
    945        @Override
    946        public int size() {
    947            if (size == -1 || expectedModCount != AbstractPatriciaTrie.this.modCount) {
    948                size = 0;
    949
    950                for (final Iterator<?> it = iterator(); it.hasNext(); it.next()) {
    951                    ++size;
    952                }
    953
    954                expectedModCount = AbstractPatriciaTrie.this.modCount;
    955            }
    956            return size;
    957        }
    958    }
    959
    960    /**
    961     * A {@link Reference} allows us to return something through a Method's
    962     * argument list. An alternative would be to an Array with a length of
    963     * one (1) but that leads to compiler warnings. Computationally and memory
    964     * wise there's no difference (except for the need to load the
    965     * {@link Reference} Class but that happens only once).
    966     */
    967    private static final class Reference<E> {
    968
    969        private E item;
    970
    971        public E get() {
    972            return item;
    973        }
    974
    975        public void set(final E item) {
    976            this.item = item;
    977        }
    978    }
    979
    980    /**
    981     * A {@link Trie} is a set of {@link TrieEntry} nodes.
    982     *
    983     * @param <K> The key type.
    984     * @param <V> The value type.
    985     */
    986    protected static class TrieEntry<K, V> extends BasicEntry<K, V> {
    987
    988        private static final long serialVersionUID = 4596023148184140013L;
    989
    990        /** The index this entry is comparing. */
    991        protected int bitIndex;
    992
    993        /** The parent of this entry. */
    994        protected TrieEntry<K, V> parent;
    995
    996        /** The left child of this entry. */
    997        protected TrieEntry<K, V> left;
    998
    999        /** The right child of this entry. */
    1000        protected TrieEntry<K, V> right;
    1001
    1002        /** The entry who uplinks to this entry. */
    1003        protected TrieEntry<K, V> predecessor;
    1004
    1005        /**
    1006         * Constructs a new instance.
    1007         *
    1008         * @param key The entry's key.
    1009         * @param value The entry's value.
    1010         * @param bitIndex The entry's bitIndex.
    1011         */
    1012        public TrieEntry(final K key, final V value, final int bitIndex) {
    1013            super(key, value);
    1014            this.bitIndex = bitIndex;
    1015            this.parent = null;
    1016            this.left = this;
    1017            this.right = null;
    1018            this.predecessor = this;
    1019        }
    1020
    1021        /**
    1022         * Tests whether the entry is storing a key. Only the root can potentially be empty, all other nodes must have a key.
    1023         *
    1024         * @return Whether the entry is storing a key
    1025         */
    1026        public boolean isEmpty() {
    1027            return key == null;
    1028        }
    1029
    1030        /**
    1031         * Tests whether the left or right child is a loopback.
    1032         *
    1033         * @return Whether the left or right child is a loopback.
    1034         */
    1035        public boolean isExternalNode() {
    1036            return !isInternalNode();
    1037        }
    1038
    1039        /**
    1040         * Tests that neither the left nor right child is a loopback.
    1041         *
    1042         * @return That neither the left nor right child is a loopback.
    1043         */
    1044        public boolean isInternalNode() {
    1045            return left != this && right != this;
    1046        }
    1047
    1048        @Override
    1049        public String toString() {
    1050            final StringBuilder buffer = new StringBuilder();
    1051
    1052            if (bitIndex == -1) {
    1053                buffer.append("RootEntry(");
    1054            } else {
    1055                buffer.append("Entry(");
    1056            }
    1057
    1058            buffer.append("key=").append(getKey()).append(" [").append(bitIndex).append("], ");
    1059            buffer.append("value=").append(getValue()).append(", ");
    1060            //buffer.append("bitIndex=").append(bitIndex).append(", ");
    1061
    1062            if (parent != null) {
    1063                if (parent.bitIndex == -1) {
    1064                    buffer.append("parent=").append("ROOT");
    1065                } else {
    1066                    buffer.append("parent=").append(parent.getKey()).append(" [").append(parent.bitIndex).append("]");
    1067                }
    1068            } else {
    1069                buffer.append("parent=").append("null");
    1070            }
    1071            buffer.append(", ");
    1072
    1073            if (left != null) {
    1074                if (left.bitIndex == -1) {
    1075                    buffer.append("left=").append("ROOT");
    1076                } else {
    1077                    buffer.append("left=").append(left.getKey()).append(" [").append(left.bitIndex).append("]");
    1078                }
    1079            } else {
    1080                buffer.append("left=").append("null");
    1081            }
    1082            buffer.append(", ");
    1083
    1084            if (right != null) {
    1085                if (right.bitIndex == -1) {
    1086                    buffer.append("right=").append("ROOT");
    1087                } else {
    1088                    buffer.append("right=").append(right.getKey()).append(" [").append(right.bitIndex).append("]");
    1089                }
    1090            } else {
    1091                buffer.append("right=").append("null");
    1092            }
    1093            buffer.append(", ");
    1094
    1095            if (predecessor != null) {
    1096                if (predecessor.bitIndex == -1) {
    1097                    buffer.append("predecessor=").append("ROOT");
    1098                } else {
    1099                    buffer.append("predecessor=").append(predecessor.getKey()).append(" [").
    1100                           append(predecessor.bitIndex).append("]");
    1101                }
    1102            }
    1103
    1104            buffer.append(")");
    1105            return buffer.toString();
    1106        }
    1107    }
    1108
    1109    /**
    1110     * An {@link OrderedMapIterator} for a {@link Trie}.
    1111     */
    1112    private final class TrieMapIterator extends AbstractTrieIterator<K> implements OrderedMapIterator<K, V> {
    1113
    1114        protected TrieEntry<K, V> previous; // the previous node to return
    1115
    1116        @Override
    1117        public K getKey() {
    1118            if (current == null) {
    1119                throw new IllegalStateException();
    1120            }
    1121            return current.getKey();
    1122        }
    1123
    1124        @Override
    1125        public V getValue() {
    1126            if (current == null) {
    1127                throw new IllegalStateException();
    1128            }
    1129            return current.getValue();
    1130        }
    1131
    1132        @Override
    1133        public boolean hasPrevious() {
    1134            return previous != null;
    1135        }
    1136
    1137        @Override
    1138        public K next() {
    1139            return nextEntry().getKey();
    1140        }
    1141
    1142        @Override
    1143        protected TrieEntry<K, V> nextEntry() {
    1144            final TrieEntry<K, V> nextEntry = super.nextEntry();
    1145            previous = nextEntry;
    1146            return nextEntry;
    1147        }
    1148
    1149        @Override
    1150        public K previous() {
    1151            return previousEntry().getKey();
    1152        }
    1153
    1154        protected TrieEntry<K, V> previousEntry() {
    1155            if (expectedModCount != AbstractPatriciaTrie.this.modCount) {
    1156                throw new ConcurrentModificationException();
    1157            }
    1158
    1159            final TrieEntry<K, V> e = previous;
    1160            if (e == null) {
    1161                throw new NoSuchElementException();
    1162            }
    1163
    1164            previous = AbstractPatriciaTrie.this.previousEntry(e);
    1165            next = current;
    1166            current = e;
    1167            return current;
    1168        }
    1169
    1170        @Override
    1171        public V setValue(final V value) {
    1172            if (current == null) {
    1173                throw new IllegalStateException();
    1174            }
    1175            return current.setValue(value);
    1176        }
    1177
    1178    }
    1179
    1180    /**
    1181     * This is a value view of the {@link Trie} as returned by {@link Map#values()}.
    1182     */
    1183    private final class Values extends AbstractCollection<V> {
    1184
    1185        /**
    1186         * An {@link Iterator} that returns Value Objects.
    1187         */
    1188        private final class ValueIterator extends AbstractTrieIterator<V> {
    1189            @Override
    1190            public V next() {
    1191                return nextEntry().getValue();
    1192            }
    1193        }
    1194
    1195        @Override
    1196        public void clear() {
    1197            AbstractPatriciaTrie.this.clear();
    1198        }
    1199
    1200        @Override
    1201        public boolean contains(final Object o) {
    1202            return containsValue(o);
    1203        }
    1204
    1205        @Override
    1206        public Iterator<V> iterator() {
    1207            return new ValueIterator();
    1208        }
    1209
    1210        @Override
    1211        public boolean remove(final Object o) {
    1212            for (final Iterator<V> it = iterator(); it.hasNext(); ) {
    1213                final V value = it.next();
    1214                if (compare(value, o)) {
    1215                    it.remove();
    1216                    return true;
    1217                }
    1218            }
    1219            return false;
    1220        }
    1221
    1222        @Override
    1223        public int size() {
    1224            return AbstractPatriciaTrie.this.size();
    1225        }
    1226    }
    1227
    1228    private static final long serialVersionUID = 5155253417231339498L;
    1229
    1230    /**
    1231     * Returns true if 'next' is a valid uplink coming from 'from'.
    1232     */
    1233    static boolean isValidUplink(final TrieEntry<?, ?> next, final TrieEntry<?, ?> from) {
    1234        return next != null && next.bitIndex <= from.bitIndex && !next.isEmpty();
    1235    }
    1236
    1237    /** The root node of the {@link Trie}. */
    1238    private transient TrieEntry<K, V> root = new TrieEntry<>(null, null, -1);
    1239
    1240    /**
    1241     * Each of these fields are initialized to contain an instance of the
    1242     * appropriate view the first time this view is requested. The views are
    1243     * stateless, so there's no reason to create more than one of each.
    1244     */
    1245    private transient volatile Set<K> keySet;
    1246
    1247    private transient volatile Collection<V> values;
    1248
    1249    private transient volatile Set<Map.Entry<K, V>> entrySet;
    1250
    1251    /** The current size of the {@link Trie}. */
    1252    private transient int size;
    1253
    1254    /**
    1255     * The number of times this {@link Trie} has been modified.
    1256     * It's used to detect concurrent modifications and fail-fast the {@link Iterator}s.
    1257     */
    1258    protected transient int modCount;
    1259
    1260    /**
    1261     * Constructs a new {@link Trie} using the given {@link KeyAnalyzer}.
    1262     *
    1263     * @param keyAnalyzer  The {@link KeyAnalyzer}.
    1264     */
    1265    protected AbstractPatriciaTrie(final KeyAnalyzer<? super K> keyAnalyzer) {
    1266        super(keyAnalyzer);
    1267    }
    1268
    1269    /**
    1270     * Constructs a new {@link Trie} using the given {@link KeyAnalyzer} and initializes the
    1271     * {@link Trie} with the values from the provided {@link Map}.
    1272     *
    1273     * @param keyAnalyzer  The {@link KeyAnalyzer}.
    1274     * @param map The source map.
    1275     */
    1276    protected AbstractPatriciaTrie(final KeyAnalyzer<? super K> keyAnalyzer, final Map<? extends K, ? extends V> map) {
    1277        super(keyAnalyzer);
    1278        putAll(map);
    1279    }
    1280
    1281    /**
    1282     * Adds the given {@link TrieEntry} to the {@link Trie}.
    1283     */
    1284    TrieEntry<K, V> addEntry(final TrieEntry<K, V> entry, final int lengthInBits) {
    1285        TrieEntry<K, V> current = root.left;
    1286        TrieEntry<K, V> path = root;
    1287        while (true) {
    1288            if (current.bitIndex >= entry.bitIndex
    1289                    || current.bitIndex <= path.bitIndex) {
    1290                entry.predecessor = entry;
    1291
    1292                if (!isBitSet(entry.key, entry.bitIndex, lengthInBits)) {
    1293                    entry.left = entry;
    1294                    entry.right = current;
    1295                } else {
    1296                    entry.left = current;
    1297                    entry.right = entry;
    1298                }
    1299
    1300                entry.parent = path;
    1301                if (current.bitIndex >= entry.bitIndex) {
    1302                    current.parent = entry;
    1303                }
    1304
    1305                // if we inserted an uplink, set the predecessor on it
    1306                if (current.bitIndex <= path.bitIndex) {
    1307                    current.predecessor = entry;
    1308                }
    1309
    1310                if (path == root || !isBitSet(entry.key, path.bitIndex, lengthInBits)) {
    1311                    path.left = entry;
    1312                } else {
    1313                    path.right = entry;
    1314                }
    1315
    1316                return entry;
    1317            }
    1318
    1319            path = current;
    1320
    1321            if (!isBitSet(entry.key, current.bitIndex, lengthInBits)) {
    1322                current = current.left;
    1323            } else {
    1324                current = current.right;
    1325            }
    1326        }
    1327    }
    1328
    1329    /**
    1330     * Returns a key-value mapping associated with the least key greater
    1331     * than or equal to the given key, or null if there is no such key.
    1332     */
    1333    TrieEntry<K, V> ceilingEntry(final K key) {
    1334        final int lengthInBits = lengthInBits(key);
    1335
    1336        if (lengthInBits == 0) {
    1337            if (!root.isEmpty()) {
    1338                return root;
    1339            }
    1340            return firstEntry();
    1341        }
    1342
    1343        final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
    1344        if (keysAreEqual(key, found.key)) {
    1345            return found;
    1346        }
    1347
    1348        final int bitIndex = bitIndex(key, found.key);
    1349        if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
    1350            if (!isBitSet(key, bitIndex, lengthInBits)) {
    1351                // search key < found.key
    1352                // found is a ceiling candidate, walk backward to find the smallest entry still >= key
    1353                TrieEntry<K, V> ceiling = found;
    1354                TrieEntry<K, V> prev = previousEntry(found);
    1355                while (prev != null && !prev.isEmpty() && getKeyAnalyzer().compare(key, prev.key) <= 0) {
    1356                    ceiling = prev;
    1357                    prev = previousEntry(prev);
    1358                }
    1359                return ceiling;
    1360            } else {
    1361                // search key > found.key
    1362                // walk forward to find the first entry.key > key
    1363                TrieEntry<K, V> next = nextEntry(found);
    1364                while (next != null && getKeyAnalyzer().compare(key, next.key) > 0) {
    1365                    next = nextEntry(next);
    1366                }
    1367                return next;
    1368            }
    1369        }
    1370        if (KeyAnalyzer.isNullBitKey(bitIndex)) {
    1371            if (!root.isEmpty()) {
    1372                return root;
    1373            }
    1374            return firstEntry();
    1375        }
    1376        if (KeyAnalyzer.isEqualBitKey(bitIndex)) {
    1377            return found;
    1378        }
    1379
    1380        // we should have exited above.
    1381        throw new IllegalStateException("invalid lookup: " + key);
    1382    }
    1383
    1384    @Override
    1385    public void clear() {
    1386        root.key = null;
    1387        root.bitIndex = -1;
    1388        root.value = null;
    1389
    1390        root.parent = null;
    1391        root.left = root;
    1392        root.right = null;
    1393        root.predecessor = root;
    1394
    1395        size = 0;
    1396        incrementModCount();
    1397    }
    1398
    1399    @Override
    1400    public Comparator<? super K> comparator() {
    1401        return getKeyAnalyzer();
    1402    }
    1403
    1404    @Override
    1405    public boolean containsKey(final Object k) {
    1406        if (k == null) {
    1407            return false;
    1408        }
    1409
    1410        final K key = castKey(k);
    1411        final int lengthInBits = lengthInBits(key);
    1412        final TrieEntry<K, V> entry = getNearestEntryForKey(key, lengthInBits);
    1413        return !entry.isEmpty() && keysAreEqual(key, entry.key);
    1414    }
    1415
    1416    /**
    1417     * A helper method to decrement the {@link Trie} size and increment the modification counter.
    1418     */
    1419    void decrementSize() {
    1420        size--;
    1421        incrementModCount();
    1422    }
    1423
    1424    @Override
    1425    public Set<Map.Entry<K, V>> entrySet() {
    1426        if (entrySet == null) {
    1427            entrySet = new EntrySet();
    1428        }
    1429        return entrySet;
    1430    }
    1431
    1432    /**
    1433     * Returns the first entry the {@link Trie} is storing.
    1434     * <p>
    1435     * This is implemented by going always to the left until we encounter a valid uplink. That uplink is the first key.
    1436     * </p>
    1437     *
    1438     * @return The first entry the {@link Trie} is storing.
    1439     * @since 4.6.0
    1440     */
    1441    public TrieEntry<K, V> firstEntry() {
    1442        // if Trie is empty, no first node.
    1443        if (isEmpty()) {
    1444            return null;
    1445        }
    1446
    1447        return followLeft(root);
    1448    }
    1449
    1450    @Override
    1451    public K firstKey() {
    1452        if (isEmpty()) {
    1453            throw new NoSuchElementException();
    1454        }
    1455        return firstEntry().getKey();
    1456    }
    1457
    1458    /**
    1459     * Returns a key-value mapping associated with the greatest key
    1460     * less than or equal to the given key, or null if there is no such key.
    1461     */
    1462    TrieEntry<K, V> floorEntry(final K key) {
    1463        final int lengthInBits = lengthInBits(key);
    1464
    1465        if (lengthInBits == 0) {
    1466            if (!root.isEmpty()) {
    1467                return root;
    1468            }
    1469            return null;
    1470        }
    1471
    1472        final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
    1473        if (keysAreEqual(key, found.key)) {
    1474            return found;
    1475        }
    1476
    1477        final int bitIndex = bitIndex(key, found.key);
    1478        if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
    1479            if (isBitSet(key, bitIndex, lengthInBits)) {
    1480                TrieEntry<K, V> floor = found;
    1481                TrieEntry<K, V> next = nextEntry(found);
    1482                while (next != null && getKeyAnalyzer().compare(key, next.key) >= 0) {
    1483                    floor = next;
    1484                    next = nextEntry(next);
    1485                }
    1486                return floor;
    1487            } else {
    1488                TrieEntry<K, V> prev = previousEntry(found);
    1489                while (prev != null && !prev.isEmpty() && getKeyAnalyzer().compare(key, prev.key) < 0) {
    1490                    prev = previousEntry(prev);
    1491                }
    1492                if (prev == null || prev.isEmpty()) {
    1493                    return null;
    1494                }
    1495                return prev;
    1496            }
    1497        }
    1498        if (KeyAnalyzer.isNullBitKey(bitIndex)) {
    1499            if (!root.isEmpty()) {
    1500                return root;
    1501            }
    1502            return null;
    1503        }
    1504        if (KeyAnalyzer.isEqualBitKey(bitIndex)) {
    1505            return found;
    1506        }
    1507
    1508        // we should have exited above.
    1509        throw new IllegalStateException("invalid lookup: " + key);
    1510    }
    1511
    1512    /**
    1513     * Goes left through the tree until it finds a valid node.
    1514     */
    1515    TrieEntry<K, V> followLeft(TrieEntry<K, V> node) {
    1516        while (true) {
    1517            TrieEntry<K, V> child = node.left;
    1518            // if we hit root and it didn't have a node, go right instead.
    1519            if (child.isEmpty()) {
    1520                child = node.right;
    1521            }
    1522
    1523            if (child.bitIndex <= node.bitIndex) {
    1524                return child;
    1525            }
    1526
    1527            node = child;
    1528        }
    1529    }
    1530
    1531    /**
    1532     * Traverses down the right path until it finds an uplink.
    1533     */
    1534    TrieEntry<K, V> followRight(TrieEntry<K, V> node) {
    1535        // if Trie is empty, no last entry.
    1536        if (node.right == null) {
    1537            return null;
    1538        }
    1539
    1540        // Go as far right as possible, until we encounter an uplink.
    1541        while (node.right.bitIndex > node.bitIndex) {
    1542            node = node.right;
    1543        }
    1544
    1545        return node.right;
    1546    }
    1547
    1548    @Override
    1549    public V get(final Object k) {
    1550        final TrieEntry<K, V> entry = getEntry(k);
    1551        return entry != null ? entry.getValue() : null;
    1552    }
    1553
    1554    /**
    1555     * Gets the entry associated with the specified key in the
    1556     * PatriciaTrieBase.  Returns null if the map contains no mapping
    1557     * for this key.
    1558     * <p>
    1559     * This may throw ClassCastException if the object is not of type K.
    1560     */
    1561    TrieEntry<K, V> getEntry(final Object k) {
    1562        final K key = castKey(k);
    1563        if (key == null) {
    1564            return null;
    1565        }
    1566
    1567        final int lengthInBits = lengthInBits(key);
    1568        final TrieEntry<K, V> entry = getNearestEntryForKey(key, lengthInBits);
    1569        return !entry.isEmpty() && keysAreEqual(key, entry.key) ? entry : null;
    1570    }
    1571
    1572    /**
    1573     * Gets the nearest entry for a given key.  This is useful
    1574     * for finding knowing if a given key exists (and finding the value
    1575     * for it), or for inserting the key.
    1576     *
    1577     * The actual get implementation. This is very similar to
    1578     * selectR but with the exception that it might return the
    1579     * root Entry even if it's empty.
    1580     */
    1581    TrieEntry<K, V> getNearestEntryForKey(final K key, final int lengthInBits) {
    1582        TrieEntry<K, V> current = root.left;
    1583        TrieEntry<K, V> path = root;
    1584        while (true) {
    1585            if (current.bitIndex <= path.bitIndex) {
    1586                return current;
    1587            }
    1588
    1589            path = current;
    1590            if (!isBitSet(key, current.bitIndex, lengthInBits)) {
    1591                current = current.left;
    1592            } else {
    1593                current = current.right;
    1594            }
    1595        }
    1596    }
    1597
    1598    /**
    1599     * Gets a view of this {@link Trie} of all elements that are prefixed
    1600     * by the number of bits in the given Key.
    1601     * <p>
    1602     * The view that this returns is optimized to have a very efficient
    1603     * {@link Iterator}. The {@link SortedMap#firstKey()},
    1604     * {@link SortedMap#lastKey()} &amp; {@link Map#size()} methods must
    1605     * iterate over all possible values in order to determine the results.
    1606     * This information is cached until the PATRICIA {@link Trie} changes.
    1607     * All other methods (except {@link Iterator}) must compare the given
    1608     * key to the prefix to ensure that it is within the range of the view.
    1609     * The {@link Iterator}'s remove method must also relocate the subtree
    1610     * that contains the prefixes if the entry holding the subtree is
    1611     * removed or changes. Changing the subtree takes O(K) time.
    1612     *
    1613     * @param key  The key to use in the search
    1614     * @param offsetInBits  The prefix offset
    1615     * @param lengthInBits  The number of significant prefix bits
    1616     * @return A {@link SortedMap} view of this {@link Trie} with all elements whose
    1617     *   key is prefixed by the search key
    1618     */
    1619    private SortedMap<K, V> getPrefixMapByBits(final K key, final int offsetInBits, final int lengthInBits) {
    1620        final int offsetLength = offsetInBits + lengthInBits;
    1621        if (offsetLength > lengthInBits(key)) {
    1622            throw new IllegalArgumentException(offsetInBits + " + " + lengthInBits + " > " + lengthInBits(key));
    1623        }
    1624        if (offsetLength == 0) {
    1625            return this;
    1626        }
    1627        return new PrefixRangeMap(key, offsetInBits, lengthInBits);
    1628    }
    1629
    1630    @Override
    1631    public SortedMap<K, V> headMap(final K toKey) {
    1632        return new RangeEntryMap(null, toKey);
    1633    }
    1634
    1635    /**
    1636     * Returns an entry strictly higher than the given key,
    1637     * or null if no such entry exists.
    1638     */
    1639    TrieEntry<K, V> higherEntry(final K key) {
    1640        final int lengthInBits = lengthInBits(key);
    1641
    1642        if (lengthInBits == 0) {
    1643            if (!root.isEmpty()) {
    1644                // If data in root, and more after -- return it.
    1645                if (size() > 1) {
    1646                    return nextEntry(root);
    1647                }
    1648                // If no more after, no higher entry.
    1649                return null;
    1650            }
    1651            // Root is empty & we want something after empty, return first.
    1652            return firstEntry();
    1653        }
    1654
    1655        final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
    1656        if (keysAreEqual(key, found.key)) {
    1657            return nextEntry(found);
    1658        }
    1659
    1660        final int bitIndex = bitIndex(key, found.key);
    1661        if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
    1662            if (!isBitSet(key, bitIndex, lengthInBits)) {
    1663                TrieEntry<K, V> ceiling = found;
    1664                TrieEntry<K, V> prev = previousEntry(found);
    1665                while (prev != null && !prev.isEmpty() && getKeyAnalyzer().compare(key, prev.key) <= 0) {
    1666                    ceiling = prev;
    1667                    prev = previousEntry(prev);
    1668                }
    1669                return ceiling;
    1670            } else {
    1671                TrieEntry<K, V> next = nextEntry(found);
    1672                while (next != null && getKeyAnalyzer().compare(key, next.key) > 0) {
    1673                    next = nextEntry(next);
    1674                }
    1675                return next;
    1676            }
    1677        }
    1678        if (KeyAnalyzer.isNullBitKey(bitIndex)) {
    1679            if (!root.isEmpty()) {
    1680                return firstEntry();
    1681            }
    1682            if (size() > 1) {
    1683                return nextEntry(firstEntry());
    1684            }
    1685            return null;
    1686        }
    1687        if (KeyAnalyzer.isEqualBitKey(bitIndex)) {
    1688            return nextEntry(found);
    1689        }
    1690
    1691        // we should have exited above.
    1692        throw new IllegalStateException("invalid lookup: " + key);
    1693    }
    1694
    1695    /**
    1696     * A helper method to increment the modification counter.
    1697     */
    1698    private void incrementModCount() {
    1699        ++modCount;
    1700    }
    1701
    1702    /**
    1703     * A helper method to increment the {@link Trie} size and the modification counter.
    1704     */
    1705    void incrementSize() {
    1706        size++;
    1707        incrementModCount();
    1708    }
    1709
    1710    @Override
    1711    public Set<K> keySet() {
    1712        if (keySet == null) {
    1713            keySet = new KeySet();
    1714        }
    1715        return keySet;
    1716    }
    1717
    1718    /**
    1719     * Returns the last entry the {@link Trie} is storing.
    1720     *
    1721     * <p>
    1722     * This is implemented by going always to the right until we encounter a valid uplink. That uplink is the last key.
    1723     * </p>
    1724     *
    1725     * @return The last entry the {@link Trie} is storing.
    1726     * @since 4.6.0
    1727     */
    1728    public TrieEntry<K, V> lastEntry() {
    1729        return followRight(root.left);
    1730    }
    1731
    1732    @Override
    1733    public K lastKey() {
    1734        final TrieEntry<K, V> entry = lastEntry();
    1735        if (entry != null) {
    1736            return entry.getKey();
    1737        }
    1738        throw new NoSuchElementException();
    1739    }
    1740
    1741    /**
    1742     * Returns a key-value mapping associated with the greatest key
    1743     * strictly less than the given key, or null if there is no such key.
    1744     */
    1745    TrieEntry<K, V> lowerEntry(final K key) {
    1746        final int lengthInBits = lengthInBits(key);
    1747
    1748        if (lengthInBits == 0) {
    1749            return null; // there can never be anything before root.
    1750        }
    1751
    1752        final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
    1753        if (keysAreEqual(key, found.key)) {
    1754            return previousEntry(found);
    1755        }
    1756
    1757        final int bitIndex = bitIndex(key, found.key);
    1758        if (KeyAnalyzer.isValidBitIndex(bitIndex)) {
    1759            if (isBitSet(key, bitIndex, lengthInBits)) {
    1760                TrieEntry<K, V> floor = found;
    1761                TrieEntry<K, V> next = nextEntry(found);
    1762                while (next != null && getKeyAnalyzer().compare(key, next.key) >= 0) {
    1763                    floor = next;
    1764                    next = nextEntry(next);
    1765                }
    1766                return floor;
    1767            } else {
    1768                TrieEntry<K, V> prev = previousEntry(found);
    1769                while (prev != null && !prev.isEmpty() && getKeyAnalyzer().compare(key, prev.key) < 0) {
    1770                    prev = previousEntry(prev);
    1771                }
    1772                if (prev == null || prev.isEmpty()) {
    1773                    return null;
    1774                }
    1775                return prev;
    1776            }
    1777        }
    1778        if (KeyAnalyzer.isNullBitKey(bitIndex)) {
    1779            return null;
    1780        }
    1781        if (KeyAnalyzer.isEqualBitKey(bitIndex)) {
    1782            return previousEntry(found);
    1783        }
    1784
    1785        // we should have exited above.
    1786        throw new IllegalStateException("invalid lookup: " + key);
    1787    }
    1788
    1789    @Override
    1790    public OrderedMapIterator<K, V> mapIterator() {
    1791        return new TrieMapIterator();
    1792    }
    1793
    1794    /**
    1795     * Returns the entry lexicographically after the given entry.
    1796     * If the given entry is null, returns the first node.
    1797     */
    1798    TrieEntry<K, V> nextEntry(final TrieEntry<K, V> node) {
    1799        if (node == null) {
    1800            return firstEntry();
    1801        }
    1802        return nextEntryImpl(node.predecessor, node, null);
    1803    }
    1804
    1805    /**
    1806     * Scans for the next node, starting at the specified point, and using 'previous'
    1807     * as a hint that the last node we returned was 'previous' (so we know not to return
    1808     * it again).  If 'tree' is non-null, this will limit the search to the given tree.
    1809     *
    1810     * The basic premise is that each iteration can follow the following steps:
    1811     *
    1812     * 1) Scan all the way to the left.
    1813     *   a) If we already started from this node last time, proceed to Step 2.
    1814     *   b) If a valid uplink is found, use it.
    1815     *   c) If the result is an empty node (root not set), break the scan.
    1816     *   d) If we already returned the left node, break the scan.
    1817     *
    1818     * 2) Check the right.
    1819     *   a) If we already returned the right node, proceed to Step 3.
    1820     *   b) If it is a valid uplink, use it.
    1821     *   c) Do Step 1 from the right node.
    1822     *
    1823     * 3) Back up through the parents until we encounter find a parent
    1824     *    that we're not the right child of.
    1825     *
    1826     * 4) If there's no right child of that parent, the iteration is finished.
    1827     *    Otherwise continue to Step 5.
    1828     *
    1829     * 5) Check to see if the right child is a valid uplink.
    1830     *    a) If we already returned that child, proceed to Step 6.
    1831     *       Otherwise, use it.
    1832     *
    1833     * 6) If the right child of the parent is the parent itself, we've
    1834     *    already found &amp; returned the end of the Trie, so exit.
    1835     *
    1836     * 7) Do Step 1 on the parent's right child.
    1837     */
    1838    TrieEntry<K, V> nextEntryImpl(final TrieEntry<K, V> start,
    1839            final TrieEntry<K, V> previous, final TrieEntry<K, V> tree) {
    1840
    1841        TrieEntry<K, V> current = start;
    1842
    1843        // Only look at the left if this was a recursive or
    1844        // the first check, otherwise we know we've already looked
    1845        // at the left.
    1846        if (previous == null || start != previous.predecessor) {
    1847            while (!current.left.isEmpty()) {
    1848                // stop traversing if we've already
    1849                // returned the left of this node.
    1850                if (previous == current.left) {
    1851                    break;
    1852                }
    1853
    1854                if (isValidUplink(current.left, current)) {
    1855                    return current.left;
    1856                }
    1857
    1858                current = current.left;
    1859            }
    1860        }
    1861
    1862        // If there's no data at all, exit.
    1863        if (current.isEmpty()) {
    1864            return null;
    1865        }
    1866
    1867        // If we've already returned the left,
    1868        // and the immediate right is null,
    1869        // there's only one entry in the Trie
    1870        // which is stored at the root.
    1871        //
    1872        //  / ("")   <-- root
    1873        //  \_/  \
    1874        //       null <-- 'current'
    1875        //
    1876        if (current.right == null) {
    1877            return null;
    1878        }
    1879
    1880        // If nothing valid on the left, try the right.
    1881        if (previous != current.right) {
    1882            // See if it immediately is valid.
    1883            if (isValidUplink(current.right, current)) {
    1884                return current.right;
    1885            }
    1886
    1887            // Must search on the right's side if it wasn't initially valid.
    1888            return nextEntryImpl(current.right, previous, tree);
    1889        }
    1890
    1891        // Neither left nor right are valid, find the first parent
    1892        // whose child did not come from the right & traverse it.
    1893        while (current == current.parent.right) {
    1894            // If we're going to traverse to above the subtree, stop.
    1895            if (current == tree) {
    1896                return null;
    1897            }
    1898
    1899            current = current.parent;
    1900        }
    1901
    1902        // If we're on the top of the subtree, we can't go any higher.
    1903        if (current == tree) {
    1904            return null;
    1905        }
    1906
    1907        // If there's no right, the parent must be root, so we're done.
    1908        if (current.parent.right == null) {
    1909            return null;
    1910        }
    1911
    1912        // If the parent's right points to itself, we've found one.
    1913        if (previous != current.parent.right
    1914                && isValidUplink(current.parent.right, current.parent)) {
    1915            return current.parent.right;
    1916        }
    1917
    1918        // If the parent's right is itself, there can't be any more nodes.
    1919        if (current.parent.right == current.parent) {
    1920            return null;
    1921        }
    1922
    1923        // We need to traverse down the parent's right's path.
    1924        return nextEntryImpl(current.parent.right, previous, tree);
    1925    }
    1926
    1927    /**
    1928     * Returns the entry lexicographically after the given entry.
    1929     * If the given entry is null, returns the first node.
    1930     *
    1931     * This will traverse only within the subtree.  If the given node
    1932     * is not within the subtree, this will have undefined results.
    1933     */
    1934    TrieEntry<K, V> nextEntryInSubtree(final TrieEntry<K, V> node,
    1935            final TrieEntry<K, V> parentOfSubtree) {
    1936        if (node == null) {
    1937            return firstEntry();
    1938        }
    1939        return nextEntryImpl(node.predecessor, node, parentOfSubtree);
    1940    }
    1941
    1942    @Override
    1943    public K nextKey(final K key) {
    1944        Objects.requireNonNull(key, "key");
    1945        final TrieEntry<K, V> entry = getEntry(key);
    1946        if (entry != null) {
    1947            final TrieEntry<K, V> nextEntry = nextEntry(entry);
    1948            return nextEntry != null ? nextEntry.getKey() : null;
    1949        }
    1950        return null;
    1951    }
    1952
    1953    @Override
    1954    public SortedMap<K, V> prefixMap(final K key) {
    1955        return getPrefixMapByBits(key, 0, lengthInBits(key));
    1956    }
    1957
    1958    /**
    1959     * Returns the node lexicographically before the given node (or null if none).
    1960     *
    1961     * This follows four simple branches:
    1962     *  - If the uplink that returned us was a right uplink:
    1963     *      - If predecessor's left is a valid uplink from predecessor, return it.
    1964     *      - Else, follow the right path from the predecessor's left.
    1965     *  - If the uplink that returned us was a left uplink:
    1966     *      - Loop back through parents until we encounter a node where
    1967     *        node != node.parent.left.
    1968     *          - If node.parent.left is uplink from node.parent:
    1969     *              - If node.parent.left is not root, return it.
    1970     *              - If it is root &amp; root isEmpty, return null.
    1971     *              - If it is root &amp; root !isEmpty, return root.
    1972     *          - If node.parent.left is not uplink from node.parent:
    1973     *              - Follow right path for first right child from node.parent.left
    1974     *
    1975     * @param start  The start entry
    1976     */
    1977    TrieEntry<K, V> previousEntry(final TrieEntry<K, V> start) {
    1978        if (start.predecessor == null) {
    1979            throw new IllegalArgumentException("must have come from somewhere.");
    1980        }
    1981
    1982        if (start.predecessor.right == start) {
    1983            if (isValidUplink(start.predecessor.left, start.predecessor)) {
    1984                return start.predecessor.left;
    1985            }
    1986            return followRight(start.predecessor.left);
    1987        }
    1988        TrieEntry<K, V> node = start.predecessor;
    1989        while (node.parent != null && node == node.parent.left) {
    1990            node = node.parent;
    1991        }
    1992
    1993        if (node.parent == null) { // can be null if we're looking up root.
    1994            return null;
    1995        }
    1996
    1997        if (isValidUplink(node.parent.left, node.parent)) {
    1998            if (node.parent.left == root) {
    1999                if (root.isEmpty()) {
    2000                    return null;
    2001                }
    2002                return root;
    2003
    2004            }
    2005            return node.parent.left;
    2006        }
    2007        return followRight(node.parent.left);
    2008    }
    2009
    2010    @Override
    2011    public K previousKey(final K key) {
    2012        Objects.requireNonNull(key, "key");
    2013        final TrieEntry<K, V> entry = getEntry(key);
    2014        if (entry != null) {
    2015            final TrieEntry<K, V> prevEntry = previousEntry(entry);
    2016            return prevEntry != null ? prevEntry.getKey() : null;
    2017        }
    2018        return null;
    2019    }
    2020
    2021    @Override
    2022    public V put(final K key, final V value) {
    2023        Objects.requireNonNull(key, "key");
    2024
    2025        final int lengthInBits = lengthInBits(key);
    2026
    2027        // The only place to store a key with a length
    2028        // of zero bits is the root node
    2029        if (lengthInBits == 0) {
    2030            if (root.isEmpty()) {
    2031                incrementSize();
    2032            } else {
    2033                incrementModCount();
    2034            }
    2035            return root.setKeyValue(key, value);
    2036        }
    2037
    2038        final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits);
    2039        if (keysAreEqual(key, found.key)) {
    2040            if (found.isEmpty()) { // <- must be the root
    2041                incrementSize();
    2042            } else {
    2043                incrementModCount();
    2044            }
    2045            return found.setKeyValue(key, value);
    2046        }
    2047
    2048        final int bitIndex = bitIndex(key, found.key);
    2049        if (!KeyAnalyzer.isOutOfBoundsIndex(bitIndex)) {
    2050            if (KeyAnalyzer.isValidBitIndex(bitIndex)) { // in 99.999...9% the case
    2051                /* NEW KEY+VALUE TUPLE */
    2052                final TrieEntry<K, V> t = new TrieEntry<>(key, value, bitIndex);
    2053                addEntry(t, lengthInBits);
    2054                incrementSize();
    2055                return null;
    2056            }
    2057            if (KeyAnalyzer.isNullBitKey(bitIndex)) {
    2058                // A bits of the Key are zero. The only place to
    2059                // store such a Key is the root Node!
    2060
    2061                /* NULL BIT KEY */
    2062                if (root.isEmpty()) {
    2063                    incrementSize();
    2064                } else {
    2065                    incrementModCount();
    2066                }
    2067                return root.setKeyValue(key, value);
    2068
    2069            }
    2070            if (KeyAnalyzer.isEqualBitKey(bitIndex) && found != root) { // NOPMD
    2071                incrementModCount();
    2072                return found.setKeyValue(key, value);
    2073            }
    2074        }
    2075
    2076        throw new IllegalArgumentException("Failed to put: " + key + " -> " + value + ", " + bitIndex);
    2077    }
    2078
    2079    /**
    2080     * Deserializes an instance from an ObjectInputStream.
    2081     *
    2082     * @param in The source ObjectInputStream.
    2083     * @throws IOException            Any of the usual Input/Output related exceptions.
    2084     * @throws ClassNotFoundException A class of a serialized object cannot be found.
    2085     */
    2086    @SuppressWarnings("unchecked") // This will fail at runtime if the stream is incorrect
    2087    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
    2088        in.defaultReadObject();
    2089        root = new TrieEntry<>(null, null, -1);
    2090        final int size = in.readInt();
    2091        for (int i = 0; i < size; i++) {
    2092            final K k = (K) in.readObject();
    2093            final V v = (V) in.readObject();
    2094            put(k, v);
    2095        }
    2096    }
    2097
    2098    /**
    2099     * {@inheritDoc}
    2100     *
    2101     * @throws ClassCastException if provided key is of an incompatible type
    2102     */
    2103    @Override
    2104    public V remove(final Object k) {
    2105        if (k == null) {
    2106            return null;
    2107        }
    2108
    2109        final K key = castKey(k);
    2110        final int lengthInBits = lengthInBits(key);
    2111        TrieEntry<K, V> current = root.left;
    2112        TrieEntry<K, V> path = root;
    2113        while (true) {
    2114            if (current.bitIndex <= path.bitIndex) {
    2115                if (!current.isEmpty() && keysAreEqual(key, current.key)) {
    2116                    return removeEntry(current);
    2117                }
    2118                return null;
    2119            }
    2120
    2121            path = current;
    2122
    2123            if (!isBitSet(key, current.bitIndex, lengthInBits)) {
    2124                current = current.left;
    2125            } else {
    2126                current = current.right;
    2127            }
    2128        }
    2129    }
    2130
    2131    /**
    2132     * Removes a single entry from the {@link Trie}.
    2133     *
    2134     * If we found a Key (Entry h) then figure out if it's
    2135     * an internal (hard to remove) or external Entry (easy
    2136     * to remove)
    2137     */
    2138    V removeEntry(final TrieEntry<K, V> h) {
    2139        if (h != root) {
    2140            if (h.isInternalNode()) {
    2141                removeInternalEntry(h);
    2142            } else {
    2143                removeExternalEntry(h);
    2144            }
    2145        }
    2146
    2147        decrementSize();
    2148        return h.setKeyValue(null, null);
    2149    }
    2150
    2151    /**
    2152     * Removes an external entry from the {@link Trie}.
    2153     *
    2154     * If it's an external Entry then just remove it.
    2155     * This is very easy and straight forward.
    2156     */
    2157    private void removeExternalEntry(final TrieEntry<K, V> h) {
    2158        if (h == root) {
    2159            throw new IllegalArgumentException("Cannot delete root Entry.");
    2160        }
    2161        if (!h.isExternalNode()) {
    2162            throw new IllegalArgumentException(h + " is not an external Entry.");
    2163        }
    2164
    2165        final TrieEntry<K, V> parent = h.parent;
    2166        final TrieEntry<K, V> child = h.left == h ? h.right : h.left;
    2167
    2168        if (parent.left == h) {
    2169            parent.left = child;
    2170        } else {
    2171            parent.right = child;
    2172        }
    2173
    2174        // either the parent is changing, or the predecessor is changing.
    2175        if (child.bitIndex > parent.bitIndex) {
    2176            child.parent = parent;
    2177        } else {
    2178            child.predecessor = parent;
    2179        }
    2180
    2181    }
    2182
    2183    /**
    2184     * Removes an internal entry from the {@link Trie}.
    2185     *
    2186     * If it's an internal Entry then "good luck" with understanding
    2187     * this code. The Idea is essentially that Entry p takes Entry h's
    2188     * place in the trie which requires some re-wiring.
    2189     */
    2190    private void removeInternalEntry(final TrieEntry<K, V> h) {
    2191        if (h == root) {
    2192            throw new IllegalArgumentException("Cannot delete root Entry.");
    2193        }
    2194        if (!h.isInternalNode()) {
    2195            throw new IllegalArgumentException(h + " is not an internal Entry.");
    2196        }
    2197
    2198        final TrieEntry<K, V> p = h.predecessor;
    2199
    2200        // Set P's bitIndex
    2201        p.bitIndex = h.bitIndex;
    2202
    2203        // Fix P's parent, predecessor and child Nodes
    2204        {
    2205            final TrieEntry<K, V> parent = p.parent;
    2206            final TrieEntry<K, V> child = p.left == h ? p.right : p.left;
    2207
    2208            // if it was looping to itself previously,
    2209            // it will now be pointed from its parent
    2210            // (if we aren't removing its parent --
    2211            //  in that case, it remains looping to itself).
    2212            // otherwise, it will continue to have the same
    2213            // predecessor.
    2214            if (p.predecessor == p && p.parent != h) {
    2215                p.predecessor = p.parent;
    2216            }
    2217
    2218            if (parent.left == p) {
    2219                parent.left = child;
    2220            } else {
    2221                parent.right = child;
    2222            }
    2223
    2224            if (child.bitIndex > parent.bitIndex) {
    2225                child.parent = parent;
    2226            }
    2227        }
    2228
    2229        // Fix H's parent and child Nodes
    2230        {
    2231            // If H is a parent of its left and right child
    2232            // then change them to P
    2233            if (h.left.parent == h) {
    2234                h.left.parent = p;
    2235            }
    2236
    2237            if (h.right.parent == h) {
    2238                h.right.parent = p;
    2239            }
    2240
    2241            // Change H's parent
    2242            if (h.parent.left == h) {
    2243                h.parent.left = p;
    2244            } else {
    2245                h.parent.right = p;
    2246            }
    2247        }
    2248
    2249        // Copy the remaining fields from H to P
    2250        //p.bitIndex = h.bitIndex;
    2251        p.parent = h.parent;
    2252        p.left = h.left;
    2253        p.right = h.right;
    2254
    2255        // Make sure that if h was pointing to any uplinks,
    2256        // p now points to them.
    2257        if (isValidUplink(p.left, p)) {
    2258            p.left.predecessor = p;
    2259        }
    2260
    2261        if (isValidUplink(p.right, p)) {
    2262            p.right.predecessor = p;
    2263        }
    2264    }
    2265
    2266    /**
    2267     * Returns the {@link Entry} whose key is closest in a bitwise XOR
    2268     * metric to the given key. This is NOT lexicographic closeness.
    2269     * For example, given the keys:
    2270     *
    2271     * <ol>
    2272     * <li>D = 1000100</li>
    2273     * <li>H = 1001000</li>
    2274     * <li>L = 1001100</li>
    2275     * </ol>
    2276     *
    2277     * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would
    2278     * return 'L', because the XOR distance between D &amp; L is smaller
    2279     * than the XOR distance between D &amp; H.
    2280     *
    2281     * @param key  The key to use in the search
    2282     * @return The {@link Entry} whose key is closest in a bitwise XOR metric
    2283     *   to the provided key
    2284     */
    2285    public Map.Entry<K, V> select(final K key) {
    2286        final int lengthInBits = lengthInBits(key);
    2287        final Reference<Map.Entry<K, V>> reference = new Reference<>();
    2288        if (!selectR(root.left, -1, key, lengthInBits, reference)) {
    2289            return reference.get();
    2290        }
    2291        return null;
    2292    }
    2293
    2294    /**
    2295     * Returns the key that is closest in a bitwise XOR metric to the
    2296     * provided key. This is NOT lexicographic closeness!
    2297     *
    2298     * For example, given the keys:
    2299     *
    2300     * <ol>
    2301     * <li>D = 1000100</li>
    2302     * <li>H = 1001000</li>
    2303     * <li>L = 1001100</li>
    2304     * </ol>
    2305     *
    2306     * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would
    2307     * return 'L', because the XOR distance between D &amp; L is smaller
    2308     * than the XOR distance between D &amp; H.
    2309     *
    2310     * @param key  The key to use in the search
    2311     * @return The key that is closest in a bitwise XOR metric to the provided key
    2312     */
    2313    public K selectKey(final K key) {
    2314        final Map.Entry<K, V> entry = select(key);
    2315        if (entry == null) {
    2316            return null;
    2317        }
    2318        return entry.getKey();
    2319    }
    2320
    2321    private boolean selectR(final TrieEntry<K, V> h, final int bitIndex,
    2322                            final K key, final int lengthInBits,
    2323                            final Reference<Map.Entry<K, V>> reference) {
    2324
    2325        if (h.bitIndex <= bitIndex) {
    2326            // If we hit the root Node and it is empty
    2327            // we have to look for an alternative best
    2328            // matching node.
    2329            if (!h.isEmpty()) {
    2330                reference.set(h);
    2331                return false;
    2332            }
    2333            return true;
    2334        }
    2335
    2336        if (!isBitSet(key, h.bitIndex, lengthInBits)) {
    2337            if (selectR(h.left, h.bitIndex, key, lengthInBits, reference)) {
    2338                return selectR(h.right, h.bitIndex, key, lengthInBits, reference);
    2339            }
    2340        } else if (selectR(h.right, h.bitIndex, key, lengthInBits, reference)) {
    2341            return selectR(h.left, h.bitIndex, key, lengthInBits, reference);
    2342        }
    2343        return false;
    2344    }
    2345
    2346    /**
    2347     * Returns the value whose key is closest in a bitwise XOR metric to
    2348     * the provided key. This is NOT lexicographic closeness!
    2349     *
    2350     * For example, given the keys:
    2351     *
    2352     * <ol>
    2353     * <li>D = 1000100</li>
    2354     * <li>H = 1001000</li>
    2355     * <li>L = 1001100</li>
    2356     * </ol>
    2357     *
    2358     * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would
    2359     * return 'L', because the XOR distance between D &amp; L is smaller
    2360     * than the XOR distance between D &amp; H.
    2361     *
    2362     * @param key  The key to use in the search
    2363     * @return The value whose key is closest in a bitwise XOR metric
    2364     * to the provided key
    2365     */
    2366    public V selectValue(final K key) {
    2367        final Map.Entry<K, V> entry = select(key);
    2368        if (entry == null) {
    2369            return null;
    2370        }
    2371        return entry.getValue();
    2372    }
    2373
    2374    @Override
    2375    public int size() {
    2376        return size;
    2377    }
    2378
    2379    @Override
    2380    public SortedMap<K, V> subMap(final K fromKey, final K toKey) {
    2381        return new RangeEntryMap(fromKey, toKey);
    2382    }
    2383
    2384    /**
    2385     * Finds the subtree that contains the prefix.
    2386     *
    2387     * This is very similar to getR but with the difference that
    2388     * we stop the lookup if h.bitIndex > lengthInBits.
    2389     */
    2390    TrieEntry<K, V> subtree(final K prefix, final int offsetInBits, final int lengthInBits) {
    2391        TrieEntry<K, V> current = root.left;
    2392        TrieEntry<K, V> path = root;
    2393        while (true) {
    2394            if (current.bitIndex <= path.bitIndex || lengthInBits <= current.bitIndex) {
    2395                break;
    2396            }
    2397
    2398            path = current;
    2399            if (!isBitSet(prefix, offsetInBits + current.bitIndex, offsetInBits + lengthInBits)) {
    2400                current = current.left;
    2401            } else {
    2402                current = current.right;
    2403            }
    2404        }
    2405
    2406        // Make sure the entry is valid for a subtree.
    2407        final TrieEntry<K, V> entry = current.isEmpty() ? path : current;
    2408
    2409        // If entry is root, it can't be empty.
    2410        if (entry.isEmpty()) {
    2411            return null;
    2412        }
    2413
    2414        final int endIndexInBits = offsetInBits + lengthInBits;
    2415
    2416        // if root && length of root is less than length of lookup,
    2417        // there's nothing.
    2418        // (this prevents returning the whole subtree if root has an empty
    2419        //  string and we want to lookup things with "\0")
    2420        if (entry == root && lengthInBits(entry.getKey()) < endIndexInBits) {
    2421            return null;
    2422        }
    2423
    2424        // Found key's length-th bit differs from our key
    2425        // which means it cannot be the prefix...
    2426        if (isBitSet(prefix, endIndexInBits - 1, endIndexInBits)
    2427                != isBitSet(entry.key, lengthInBits - 1, lengthInBits(entry.key))) {
    2428            return null;
    2429        }
    2430
    2431        // ... or there are less than 'length' equal bits
    2432        final int bitIndex = getKeyAnalyzer().bitIndex(prefix, offsetInBits, lengthInBits,
    2433                                                       entry.key, 0, lengthInBits(entry.getKey()));
    2434
    2435        if (bitIndex >= 0 && bitIndex < lengthInBits) {
    2436            return null;
    2437        }
    2438
    2439        return entry;
    2440    }
    2441
    2442    @Override
    2443    public SortedMap<K, V> tailMap(final K fromKey) {
    2444        return new RangeEntryMap(fromKey, null);
    2445    }
    2446
    2447    @Override
    2448    public Collection<V> values() {
    2449        if (values == null) {
    2450            values = new Values();
    2451        }
    2452        return values;
    2453    }
    2454
    2455    /**
    2456     * Serializes this object to an ObjectOutputStream.
    2457     *
    2458     * @param out The target ObjectOutputStream.
    2459     * @throws IOException thrown when an I/O errors occur writing to the target stream.
    2460     */
    2461    private void writeObject(final ObjectOutputStream out) throws IOException {
    2462        out.defaultWriteObject();
    2463        out.writeInt(this.size());
    2464        for (final Entry<K, V> entry : entrySet()) {
    2465            out.writeObject(entry.getKey());
    2466            out.writeObject(entry.getValue());
    2467        }
    2468    }
    2469
    2470}