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