1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
41
42
43
44
45
46
47 public abstract class AbstractPatriciaTrie<K, V> extends AbstractBitwiseTrie<K, V> {
48
49
50
51
52 private abstract class AbstractRangeMap extends AbstractMap<K, V>
53 implements SortedMap<K, V> {
54
55
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
74
75 protected abstract Set<Map.Entry<K, V>> createEntrySet();
76
77
78
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
102
103 protected abstract K getFromKey();
104
105
106
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
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
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
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
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
168
169 protected abstract boolean isFromInclusive();
170
171
172
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
217
218 abstract class AbstractTrieIterator<E> implements Iterator<E> {
219
220
221 protected int expectedModCount = AbstractPatriciaTrie.this.modCount;
222
223 protected TrieEntry<K, V> next;
224 protected TrieEntry<K, V> current;
225
226
227
228
229 protected AbstractTrieIterator() {
230 next = AbstractPatriciaTrie.this.nextEntry(null);
231 }
232
233
234
235
236 protected AbstractTrieIterator(final TrieEntry<K, V> firstEntry) {
237 next = firstEntry;
238 }
239
240
241
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
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
290
291 private final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
292
293
294
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
343
344 private final class KeySet extends AbstractSet<K> {
345
346
347
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
385
386 private final class PrefixRangeEntrySet extends RangeEntrySet {
387
388
389
390
391 private final class EntryIterator extends AbstractTrieIterator<Map.Entry<K, V>> {
392
393
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;
400
401
402
403
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
431
432 boolean needsFixing = false;
433 final int bitIdx = subtree.bitIndex;
434 if (current == subtree) {
435 needsFixing = true;
436 }
437
438 super.remove();
439
440
441
442 if (bitIdx != subtree.bitIndex || needsFixing) {
443 subtree = subtree(prefix, offset, lengthInBits);
444 }
445
446
447
448
449 if (lengthInBits >= subtree.bitIndex) {
450 lastOne = true;
451 }
452 }
453 }
454
455
456
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
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
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
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
602
603
604
605
606 private int fixup() {
607
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
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
664
665 @Override
666 protected boolean inRange(final K key) {
667 return getKeyAnalyzer().isPrefix(prefix, offsetInBits, lengthInBits, key);
668 }
669
670
671
672
673 @Override
674 protected boolean inRange2(final K key) {
675 return inRange(key);
676 }
677
678
679
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
718
719 private final class RangeEntryMap extends AbstractRangeMap {
720
721
722 private final K fromKey;
723
724
725 private final K toKey;
726
727
728 private final boolean fromInclusive;
729
730
731 private final boolean toInclusive;
732
733
734
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
755
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
831
832 private class RangeEntrySet extends AbstractSet<Map.Entry<K, V>> {
833
834
835
836
837 private final class EntryIterator extends AbstractTrieIterator<Map.Entry<K, V>> {
838
839 private final K excludedKey;
840
841
842
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
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
956
957
958
959
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
976
977
978
979
980 protected static class TrieEntry<K, V> extends BasicEntry<K, V> {
981
982 private static final long serialVersionUID = 4596023148184140013L;
983
984
985 protected int bitIndex;
986
987
988 protected TrieEntry<K, V> parent;
989
990
991 protected TrieEntry<K, V> left;
992
993
994 protected TrieEntry<K, V> right;
995
996
997 protected TrieEntry<K, V> predecessor;
998
999
1000
1001
1002
1003
1004
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
1017
1018
1019
1020
1021
1022 public boolean isEmpty() {
1023 return key == null;
1024 }
1025
1026
1027
1028
1029
1030
1031 public boolean isExternalNode() {
1032 return !isInternalNode();
1033 }
1034
1035
1036
1037
1038
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
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
1107
1108 private final class TrieMapIterator extends AbstractTrieIterator<K> implements OrderedMapIterator<K, V> {
1109
1110 protected TrieEntry<K, V> previous;
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
1178
1179 private final class Values extends AbstractCollection<V> {
1180
1181
1182
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
1228
1229 static boolean isValidUplink(final TrieEntry<?, ?> next, final TrieEntry<?, ?> from) {
1230 return next != null && next.bitIndex <= from.bitIndex && !next.isEmpty();
1231 }
1232
1233
1234 private transient TrieEntry<K, V> root = new TrieEntry<>(null, null, -1);
1235
1236
1237
1238
1239
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
1248 private transient int size;
1249
1250
1251
1252
1253
1254 protected transient int modCount;
1255
1256
1257
1258
1259
1260
1261 protected AbstractPatriciaTrie(final KeyAnalyzer<? super K> keyAnalyzer) {
1262 super(keyAnalyzer);
1263 }
1264
1265
1266
1267
1268
1269
1270
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
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
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
1327
1328
1329 TrieEntry<K, V> ceilingEntry(final K key) {
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
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();
1367 final TrieEntry<K, V> ceil = nextEntry(added);
1368 removeEntry(added);
1369 modCount -= 2;
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
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
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
1436
1437
1438
1439
1440 TrieEntry<K, V> firstEntry() {
1441
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
1459
1460
1461 TrieEntry<K, V> floorEntry(final K key) {
1462
1463
1464
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();
1484 final TrieEntry<K, V> floor = previousEntry(added);
1485 removeEntry(added);
1486 modCount -= 2;
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
1500 throw new IllegalStateException("invalid lookup: " + key);
1501 }
1502
1503
1504
1505
1506 TrieEntry<K, V> followLeft(TrieEntry<K, V> node) {
1507 while (true) {
1508 TrieEntry<K, V> child = node.left;
1509
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
1524
1525 TrieEntry<K, V> followRight(TrieEntry<K, V> node) {
1526
1527 if (node.right == null) {
1528 return null;
1529 }
1530
1531
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
1547
1548
1549
1550
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
1565
1566
1567
1568
1569
1570
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
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
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
1632
1633
1634 TrieEntry<K, V> higherEntry(final K key) {
1635
1636
1637
1638 final int lengthInBits = lengthInBits(key);
1639
1640 if (lengthInBits == 0) {
1641 if (!root.isEmpty()) {
1642
1643 if (size() > 1) {
1644 return nextEntry(root);
1645 }
1646
1647 return null;
1648 }
1649
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();
1663 final TrieEntry<K, V> ceil = nextEntry(added);
1664 removeEntry(added);
1665 modCount -= 2;
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
1682 throw new IllegalStateException("invalid lookup: " + key);
1683 }
1684
1685
1686
1687
1688 private void incrementModCount() {
1689 ++modCount;
1690 }
1691
1692
1693
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
1710
1711
1712
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
1729
1730
1731 TrieEntry<K, V> lowerEntry(final K key) {
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749 final int lengthInBits = lengthInBits(key);
1750
1751 if (lengthInBits == 0) {
1752 return null;
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();
1765 final TrieEntry<K, V> prior = previousEntry(added);
1766 removeEntry(added);
1767 modCount -= 2;
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
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
1788
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
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
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
1836
1837
1838 if (previous == null || start != previous.predecessor) {
1839 while (!current.left.isEmpty()) {
1840
1841
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
1855 if (current.isEmpty()) {
1856 return null;
1857 }
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868 if (current.right == null) {
1869 return null;
1870 }
1871
1872
1873 if (previous != current.right) {
1874
1875 if (isValidUplink(current.right, current)) {
1876 return current.right;
1877 }
1878
1879
1880 return nextEntryImpl(current.right, previous, tree);
1881 }
1882
1883
1884
1885 while (current == current.parent.right) {
1886
1887 if (current == tree) {
1888 return null;
1889 }
1890
1891 current = current.parent;
1892 }
1893
1894
1895 if (current == tree) {
1896 return null;
1897 }
1898
1899
1900 if (current.parent.right == null) {
1901 return null;
1902 }
1903
1904
1905 if (previous != current.parent.right
1906 && isValidUplink(current.parent.right, current.parent)) {
1907 return current.parent.right;
1908 }
1909
1910
1911 if (current.parent.right == current.parent) {
1912 return null;
1913 }
1914
1915
1916 return nextEntryImpl(current.parent.right, previous, tree);
1917 }
1918
1919
1920
1921
1922
1923
1924
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
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
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) {
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
2020
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()) {
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)) {
2043
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
2051
2052
2053
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) {
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
2073
2074
2075
2076
2077
2078 @SuppressWarnings("unchecked")
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
2092
2093
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
2125
2126
2127
2128
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
2145
2146
2147
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
2167 if (child.bitIndex > parent.bitIndex) {
2168 child.parent = parent;
2169 } else {
2170 child.predecessor = parent;
2171 }
2172
2173 }
2174
2175
2176
2177
2178
2179
2180
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
2193 p.bitIndex = h.bitIndex;
2194
2195
2196 {
2197 final TrieEntry<K, V> parent = p.parent;
2198 final TrieEntry<K, V> child = p.left == h ? p.right : p.left;
2199
2200
2201
2202
2203
2204
2205
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
2222 {
2223
2224
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
2234 if (h.parent.left == h) {
2235 h.parent.left = p;
2236 } else {
2237 h.parent.right = p;
2238 }
2239 }
2240
2241
2242
2243 p.parent = h.parent;
2244 p.left = h.left;
2245 p.right = h.right;
2246
2247
2248
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
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
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
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
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
2319
2320
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
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
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
2378
2379
2380
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
2399 final TrieEntry<K, V> entry = current.isEmpty() ? path : current;
2400
2401
2402 if (entry.isEmpty()) {
2403 return null;
2404 }
2405
2406 final int endIndexInBits = offsetInBits + lengthInBits;
2407
2408
2409
2410
2411
2412 if (entry == root && lengthInBits(entry.getKey()) < endIndexInBits) {
2413 return null;
2414 }
2415
2416
2417
2418 if (isBitSet(prefix, endIndexInBits - 1, endIndexInBits)
2419 != isBitSet(entry.key, lengthInBits - 1, lengthInBits(entry.key))) {
2420 return null;
2421 }
2422
2423
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
2449
2450
2451
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 }