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