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