View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.collections4.trie;
18  
19  import java.io.IOException;
20  import java.io.ObjectInputStream;
21  import java.io.ObjectOutputStream;
22  import java.util.AbstractCollection;
23  import java.util.AbstractMap;
24  import java.util.AbstractSet;
25  import java.util.Collection;
26  import java.util.Collections;
27  import java.util.Comparator;
28  import java.util.ConcurrentModificationException;
29  import java.util.Iterator;
30  import java.util.Map;
31  import java.util.NoSuchElementException;
32  import java.util.Objects;
33  import java.util.Set;
34  import java.util.SortedMap;
35  
36  import org.apache.commons.collections4.OrderedMapIterator;
37  import org.apache.commons.collections4.Trie;
38  
39  /**
40   * This class implements the base PATRICIA algorithm and everything that
41   * is related to the {@link Map} interface.
42   *
43   * @param <K> the type of the keys in this map
44   * @param <V> the type of the values in this map
45   * @since 4.0
46   */
47  public abstract class AbstractPatriciaTrie<K, V> extends AbstractBitwiseTrie<K, V> {
48  
49      /**
50       * A range view of the {@link org.apache.commons.collections4.Trie}.
51       */
52      private abstract class AbstractRangeMap extends AbstractMap<K, V>
53              implements SortedMap<K, V> {
54  
55          /** The {@link #entrySet()} view. */
56          private transient volatile Set<Map.Entry<K, V>> entrySet;
57  
58          @Override
59          public Comparator<? super K> comparator() {
60              return AbstractPatriciaTrie.this.comparator();
61          }
62  
63          @Override
64          public boolean containsKey(final Object key) {
65              if (!inRange(castKey(key))) {
66                  return false;
67              }
68  
69              return AbstractPatriciaTrie.this.containsKey(key);
70          }
71  
72          /**
73           * Creates and returns an {@link #entrySet()} view of the {@link AbstractRangeMap}.
74           */
75          protected abstract Set<Map.Entry<K, V>> createEntrySet();
76  
77          /**
78           * Creates and returns a sub-range view of the current {@link AbstractRangeMap}.
79           */
80          protected abstract SortedMap<K, V> createRangeMap(K fromKey, boolean fromInclusive,
81                                                            K toKey, boolean toInclusive);
82  
83          @Override
84          public Set<Map.Entry<K, V>> entrySet() {
85              if (entrySet == null) {
86                  entrySet = createEntrySet();
87              }
88              return entrySet;
89          }
90  
91          @Override
92          public V get(final Object key) {
93              if (!inRange(castKey(key))) {
94                  return null;
95              }
96  
97              return AbstractPatriciaTrie.this.get(key);
98          }
99  
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 }