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