1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.collections4.bidimap;
18
19 import static org.apache.commons.collections4.bidimap.TreeBidiMap.DataElement.KEY;
20 import static org.apache.commons.collections4.bidimap.TreeBidiMap.DataElement.VALUE;
21
22 import java.io.IOException;
23 import java.io.ObjectInputStream;
24 import java.io.ObjectOutputStream;
25 import java.io.Serializable;
26 import java.util.AbstractSet;
27 import java.util.ConcurrentModificationException;
28 import java.util.Iterator;
29 import java.util.Map;
30 import java.util.NoSuchElementException;
31 import java.util.Objects;
32 import java.util.Set;
33
34 import org.apache.commons.collections4.KeyValue;
35 import org.apache.commons.collections4.MapIterator;
36 import org.apache.commons.collections4.OrderedBidiMap;
37 import org.apache.commons.collections4.OrderedIterator;
38 import org.apache.commons.collections4.OrderedMapIterator;
39 import org.apache.commons.collections4.iterators.EmptyOrderedMapIterator;
40 import org.apache.commons.collections4.keyvalue.UnmodifiableMapEntry;
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86 public class TreeBidiMap<K extends Comparable<K>, V extends Comparable<V>>
87 implements OrderedBidiMap<K, V>, Serializable {
88
89
90
91
92 abstract class AbstractView<E> extends AbstractSet<E> {
93
94
95 final DataElement orderType;
96
97
98
99
100
101 AbstractView(final DataElement orderType) {
102 this.orderType = orderType;
103 }
104
105 @Override
106 public void clear() {
107 TreeBidiMap.this.clear();
108 }
109
110 @Override
111 public int size() {
112 return TreeBidiMap.this.size();
113 }
114 }
115
116
117
118
119 abstract class AbstractViewIterator {
120
121
122 private final DataElement orderType;
123
124 Node<K, V> lastReturnedNode;
125
126 private Node<K, V> nextNode;
127
128 private Node<K, V> previousNode;
129
130 private int expectedModifications;
131
132
133
134
135
136 AbstractViewIterator(final DataElement orderType) {
137 this.orderType = orderType;
138 expectedModifications = modifications;
139 nextNode = leastNode(rootNode[orderType.ordinal()], orderType);
140 lastReturnedNode = null;
141 previousNode = null;
142 }
143
144 public final boolean hasNext() {
145 return nextNode != null;
146 }
147
148 public boolean hasPrevious() {
149 return previousNode != null;
150 }
151
152 protected Node<K, V> navigateNext() {
153 if (nextNode == null) {
154 throw new NoSuchElementException();
155 }
156 if (modifications != expectedModifications) {
157 throw new ConcurrentModificationException();
158 }
159 lastReturnedNode = nextNode;
160 previousNode = nextNode;
161 nextNode = nextGreater(nextNode, orderType);
162 return lastReturnedNode;
163 }
164
165 protected Node<K, V> navigatePrevious() {
166 if (previousNode == null) {
167 throw new NoSuchElementException();
168 }
169 if (modifications != expectedModifications) {
170 throw new ConcurrentModificationException();
171 }
172 nextNode = lastReturnedNode;
173 if (nextNode == null) {
174 nextNode = nextGreater(previousNode, orderType);
175 }
176 lastReturnedNode = previousNode;
177 previousNode = nextSmaller(previousNode, orderType);
178 return lastReturnedNode;
179 }
180
181 public final void remove() {
182 if (lastReturnedNode == null) {
183 throw new IllegalStateException();
184 }
185 if (modifications != expectedModifications) {
186 throw new ConcurrentModificationException();
187 }
188 doRedBlackDelete(lastReturnedNode);
189 expectedModifications++;
190 lastReturnedNode = null;
191 if (nextNode == null) {
192 previousNode = greatestNode(rootNode[orderType.ordinal()], orderType);
193 } else {
194 previousNode = nextSmaller(nextNode, orderType);
195 }
196 }
197 }
198
199 enum DataElement {
200 KEY("key"), VALUE("value");
201
202 private final String description;
203
204
205
206
207
208
209 DataElement(final String description) {
210 this.description = description;
211 }
212
213 @Override
214 public String toString() {
215 return description;
216 }
217 }
218
219
220
221 final class EntryView extends AbstractView<Map.Entry<K, V>> {
222
223 EntryView() {
224 super(KEY);
225 }
226
227 @Override
228 public boolean contains(final Object obj) {
229 if (!(obj instanceof Map.Entry)) {
230 return false;
231 }
232 final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
233 final Object value = entry.getValue();
234 final Node<K, V> node = lookupKey(entry.getKey());
235 return node != null && node.getValue().equals(value);
236 }
237
238 @Override
239 public Iterator<Map.Entry<K, V>> iterator() {
240 return new ViewMapEntryIterator();
241 }
242
243 @Override
244 public boolean remove(final Object obj) {
245 if (!(obj instanceof Map.Entry)) {
246 return false;
247 }
248 final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
249 final Object value = entry.getValue();
250 final Node<K, V> node = lookupKey(entry.getKey());
251 if (node != null && node.getValue().equals(value)) {
252 doRedBlackDelete(node);
253 return true;
254 }
255 return false;
256 }
257 }
258
259
260
261 final class Inverse implements OrderedBidiMap<V, K> {
262
263
264 private Set<V> inverseKeySet;
265
266 private Set<K> inverseValuesSet;
267
268 private Set<Map.Entry<V, K>> inverseEntrySet;
269
270 @Override
271 public void clear() {
272 TreeBidiMap.this.clear();
273 }
274
275 @Override
276 public boolean containsKey(final Object key) {
277 return TreeBidiMap.this.containsValue(key);
278 }
279
280 @Override
281 public boolean containsValue(final Object value) {
282 return TreeBidiMap.this.containsKey(value);
283 }
284
285 @Override
286 public Set<Map.Entry<V, K>> entrySet() {
287 if (inverseEntrySet == null) {
288 inverseEntrySet = new InverseEntryView();
289 }
290 return inverseEntrySet;
291 }
292
293 @Override
294 public boolean equals(final Object obj) {
295 return TreeBidiMap.this.doEquals(obj, VALUE);
296 }
297
298 @Override
299 public V firstKey() {
300 if (TreeBidiMap.this.nodeCount == 0) {
301 throw new NoSuchElementException("Map is empty");
302 }
303 return leastNode(TreeBidiMap.this.rootNode[VALUE.ordinal()], VALUE).getValue();
304 }
305
306 @Override
307 public K get(final Object key) {
308 return TreeBidiMap.this.getKey(key);
309 }
310
311 @Override
312 public V getKey(final Object value) {
313 return TreeBidiMap.this.get(value);
314 }
315
316 @Override
317 public int hashCode() {
318 return TreeBidiMap.this.doHashCode(VALUE);
319 }
320
321 @Override
322 public OrderedBidiMap<K, V> inverseBidiMap() {
323 return TreeBidiMap.this;
324 }
325
326 @Override
327 public boolean isEmpty() {
328 return TreeBidiMap.this.isEmpty();
329 }
330
331 @Override
332 public Set<V> keySet() {
333 if (inverseKeySet == null) {
334 inverseKeySet = new ValueView(VALUE);
335 }
336 return inverseKeySet;
337 }
338
339 @Override
340 public V lastKey() {
341 if (TreeBidiMap.this.nodeCount == 0) {
342 throw new NoSuchElementException("Map is empty");
343 }
344 return greatestNode(TreeBidiMap.this.rootNode[VALUE.ordinal()], VALUE).getValue();
345 }
346
347 @Override
348 public OrderedMapIterator<V, K> mapIterator() {
349 if (isEmpty()) {
350 return EmptyOrderedMapIterator.<V, K>emptyOrderedMapIterator();
351 }
352 return new InverseViewMapIterator(VALUE);
353 }
354
355 @Override
356 public V nextKey(final V key) {
357 checkKey(key);
358 final Node<K, V> node = nextGreater(TreeBidiMap.this.<V>lookup(key, VALUE), VALUE);
359 return node == null ? null : node.getValue();
360 }
361
362 @Override
363 public V previousKey(final V key) {
364 checkKey(key);
365 final Node<K, V> node = TreeBidiMap.this.nextSmaller(TreeBidiMap.this.<V>lookup(key, VALUE), VALUE);
366 return node == null ? null : node.getValue();
367 }
368
369 @Override
370 public K put(final V key, final K value) {
371 final K result = get(key);
372 TreeBidiMap.this.doPut(value, key);
373 return result;
374 }
375
376 @Override
377 public void putAll(final Map<? extends V, ? extends K> map) {
378 for (final Map.Entry<? extends V, ? extends K> e : map.entrySet()) {
379 put(e.getKey(), e.getValue());
380 }
381 }
382
383 @Override
384 public K remove(final Object key) {
385 return TreeBidiMap.this.removeValue(key);
386 }
387
388 @Override
389 public V removeValue(final Object value) {
390 return TreeBidiMap.this.remove(value);
391 }
392
393 @Override
394 public int size() {
395 return TreeBidiMap.this.size();
396 }
397
398 @Override
399 public String toString() {
400 return TreeBidiMap.this.doToString(VALUE);
401 }
402
403 @Override
404 public Set<K> values() {
405 if (inverseValuesSet == null) {
406 inverseValuesSet = new KeyView(VALUE);
407 }
408 return inverseValuesSet;
409 }
410 }
411
412
413
414 final class InverseEntryView extends AbstractView<Map.Entry<V, K>> {
415
416 InverseEntryView() {
417 super(VALUE);
418 }
419
420 @Override
421 public boolean contains(final Object obj) {
422 if (!(obj instanceof Map.Entry)) {
423 return false;
424 }
425 final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
426 final Object value = entry.getValue();
427 final Node<K, V> node = lookupValue(entry.getKey());
428 return node != null && node.getKey().equals(value);
429 }
430
431 @Override
432 public Iterator<Map.Entry<V, K>> iterator() {
433 return new InverseViewMapEntryIterator();
434 }
435
436 @Override
437 public boolean remove(final Object obj) {
438 if (!(obj instanceof Map.Entry)) {
439 return false;
440 }
441 final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
442 final Object value = entry.getValue();
443 final Node<K, V> node = lookupValue(entry.getKey());
444 if (node != null && node.getKey().equals(value)) {
445 doRedBlackDelete(node);
446 return true;
447 }
448 return false;
449 }
450 }
451
452
453
454 final class InverseViewMapEntryIterator extends AbstractViewIterator implements OrderedIterator<Map.Entry<V, K>> {
455
456
457
458
459 InverseViewMapEntryIterator() {
460 super(VALUE);
461 }
462
463 private Map.Entry<V, K> createEntry(final Node<K, V> node) {
464 return new UnmodifiableMapEntry<>(node.getValue(), node.getKey());
465 }
466
467 @Override
468 public Map.Entry<V, K> next() {
469 return createEntry(navigateNext());
470 }
471
472 @Override
473 public Map.Entry<V, K> previous() {
474 return createEntry(navigatePrevious());
475 }
476 }
477
478
479
480 final class InverseViewMapIterator extends AbstractViewIterator implements OrderedMapIterator<V, K> {
481
482
483
484
485 InverseViewMapIterator(final DataElement orderType) {
486 super(orderType);
487 }
488
489 @Override
490 public V getKey() {
491 if (lastReturnedNode == null) {
492 throw new IllegalStateException(
493 "Iterator getKey() can only be called after next() and before remove()");
494 }
495 return lastReturnedNode.getValue();
496 }
497
498 @Override
499 public K getValue() {
500 if (lastReturnedNode == null) {
501 throw new IllegalStateException(
502 "Iterator getValue() can only be called after next() and before remove()");
503 }
504 return lastReturnedNode.getKey();
505 }
506
507 @Override
508 public V next() {
509 return navigateNext().getValue();
510 }
511
512 @Override
513 public V previous() {
514 return navigatePrevious().getValue();
515 }
516
517 @Override
518 public K setValue(final K obj) {
519 throw new UnsupportedOperationException();
520 }
521 }
522 final class KeyView extends AbstractView<K> {
523
524
525
526
527 KeyView(final DataElement orderType) {
528 super(orderType);
529 }
530
531 @Override
532 public boolean contains(final Object obj) {
533 checkNonNullComparable(obj, KEY);
534 return lookupKey(obj) != null;
535 }
536
537 @Override
538 public Iterator<K> iterator() {
539 return new ViewMapIterator(orderType);
540 }
541
542 @Override
543 public boolean remove(final Object o) {
544 return doRemoveKey(o) != null;
545 }
546
547 }
548
549
550
551
552 static class Node<K extends Comparable<K>, V extends Comparable<V>> implements Map.Entry<K, V>, KeyValue<K, V> {
553
554 private final K key;
555 private final V value;
556 private final Node<K, V>[] leftNode;
557 private final Node<K, V>[] rightNode;
558 private final Node<K, V>[] parentNode;
559 private final boolean[] blackColor;
560 private int hashCodeValue;
561 private boolean calculatedHashCode;
562
563
564
565
566
567
568
569
570 @SuppressWarnings("unchecked")
571 Node(final K key, final V value) {
572 this.key = key;
573 this.value = value;
574 leftNode = new Node[2];
575 rightNode = new Node[2];
576 parentNode = new Node[2];
577 blackColor = new boolean[] { true, true };
578 calculatedHashCode = false;
579 }
580
581
582
583
584
585
586
587
588 private void copyColor(final Node<K, V> node, final DataElement dataElement) {
589 blackColor[dataElement.ordinal()] = node.blackColor[dataElement.ordinal()];
590 }
591
592
593
594
595
596
597
598
599
600 @Override
601 public boolean equals(final Object obj) {
602 if (obj == this) {
603 return true;
604 }
605 if (!(obj instanceof Map.Entry)) {
606 return false;
607 }
608 final Map.Entry<?, ?> e = (Map.Entry<?, ?>) obj;
609 return getKey().equals(e.getKey()) && getValue().equals(e.getValue());
610 }
611
612 private Object getData(final DataElement dataElement) {
613 switch (dataElement) {
614 case KEY:
615 return getKey();
616 case VALUE:
617 return getValue();
618 default:
619 throw new IllegalArgumentException();
620 }
621 }
622
623
624
625
626
627
628 @Override
629 public K getKey() {
630 return key;
631 }
632
633 private Node<K, V> getLeft(final DataElement dataElement) {
634 return leftNode[dataElement.ordinal()];
635 }
636
637
638
639
640
641
642
643
644 private Node<K, V> getParent(final DataElement dataElement) {
645 return parentNode[dataElement.ordinal()];
646 }
647
648 private Node<K, V> getRight(final DataElement dataElement) {
649 return rightNode[dataElement.ordinal()];
650 }
651
652
653
654
655
656
657 @Override
658 public V getValue() {
659 return value;
660 }
661
662
663
664
665 @Override
666 public int hashCode() {
667 if (!calculatedHashCode) {
668 hashCodeValue = getKey().hashCode() ^ getValue().hashCode();
669 calculatedHashCode = true;
670 }
671 return hashCodeValue;
672 }
673
674
675
676
677
678
679
680
681 private boolean isBlack(final DataElement dataElement) {
682 return blackColor[dataElement.ordinal()];
683 }
684
685 private boolean isLeftChild(final DataElement dataElement) {
686 return parentNode[dataElement.ordinal()] != null
687 && parentNode[dataElement.ordinal()].leftNode[dataElement.ordinal()] == this;
688 }
689
690
691
692
693
694
695
696
697 private boolean isRed(final DataElement dataElement) {
698 return !blackColor[dataElement.ordinal()];
699 }
700
701 private boolean isRightChild(final DataElement dataElement) {
702 return parentNode[dataElement.ordinal()] != null
703 && parentNode[dataElement.ordinal()].rightNode[dataElement.ordinal()] == this;
704 }
705
706
707
708
709
710
711
712 private void setBlack(final DataElement dataElement) {
713 blackColor[dataElement.ordinal()] = true;
714 }
715
716 private void setLeft(final Node<K, V> node, final DataElement dataElement) {
717 leftNode[dataElement.ordinal()] = node;
718 }
719
720
721
722
723
724
725
726
727 private void setParent(final Node<K, V> node, final DataElement dataElement) {
728 parentNode[dataElement.ordinal()] = node;
729 }
730
731
732
733
734
735
736
737 private void setRed(final DataElement dataElement) {
738 blackColor[dataElement.ordinal()] = false;
739 }
740
741 private void setRight(final Node<K, V> node, final DataElement dataElement) {
742 rightNode[dataElement.ordinal()] = node;
743 }
744
745
746
747
748
749
750
751
752 @Override
753 public V setValue(final V ignored) throws UnsupportedOperationException {
754 throw new UnsupportedOperationException("Map.Entry.setValue is not supported");
755 }
756
757
758
759
760
761
762
763
764 private void swapColors(final Node<K, V> node, final DataElement dataElement) {
765
766 blackColor[dataElement.ordinal()] ^= node.blackColor[dataElement.ordinal()];
767 node.blackColor[dataElement.ordinal()] ^= blackColor[dataElement.ordinal()];
768 blackColor[dataElement.ordinal()] ^= node.blackColor[dataElement.ordinal()];
769 }
770 }
771
772 final class ValueView extends AbstractView<V> {
773
774
775
776
777 ValueView(final DataElement orderType) {
778 super(orderType);
779 }
780
781 @Override
782 public boolean contains(final Object obj) {
783 checkNonNullComparable(obj, VALUE);
784 return lookupValue(obj) != null;
785 }
786
787 @Override
788 public Iterator<V> iterator() {
789 return new InverseViewMapIterator(orderType);
790 }
791
792 @Override
793 public boolean remove(final Object o) {
794 return doRemoveValue(o) != null;
795 }
796
797 }
798
799
800
801
802 final class ViewMapEntryIterator extends AbstractViewIterator implements OrderedIterator<Map.Entry<K, V>> {
803
804
805
806
807 ViewMapEntryIterator() {
808 super(KEY);
809 }
810
811 @Override
812 public Map.Entry<K, V> next() {
813 return navigateNext();
814 }
815
816 @Override
817 public Map.Entry<K, V> previous() {
818 return navigatePrevious();
819 }
820 }
821
822
823
824
825 final class ViewMapIterator extends AbstractViewIterator implements OrderedMapIterator<K, V> {
826
827
828
829
830 ViewMapIterator(final DataElement orderType) {
831 super(orderType);
832 }
833
834 @Override
835 public K getKey() {
836 if (lastReturnedNode == null) {
837 throw new IllegalStateException(
838 "Iterator getKey() can only be called after next() and before remove()");
839 }
840 return lastReturnedNode.getKey();
841 }
842
843 @Override
844 public V getValue() {
845 if (lastReturnedNode == null) {
846 throw new IllegalStateException(
847 "Iterator getValue() can only be called after next() and before remove()");
848 }
849 return lastReturnedNode.getValue();
850 }
851
852 @Override
853 public K next() {
854 return navigateNext().getKey();
855 }
856
857 @Override
858 public K previous() {
859 return navigatePrevious().getKey();
860 }
861
862 @Override
863 public V setValue(final V obj) {
864 throw new UnsupportedOperationException();
865 }
866 }
867
868 private static final long serialVersionUID = 721969328361807L;
869
870
871
872
873
874
875
876
877
878 private static void checkKey(final Object key) {
879 checkNonNullComparable(key, KEY);
880 }
881
882
883
884
885
886
887
888
889
890
891
892 private static void checkKeyAndValue(final Object key, final Object value) {
893 checkKey(key);
894 checkValue(value);
895 }
896
897
898
899
900
901
902
903
904
905
906
907
908 private static void checkNonNullComparable(final Object obj, final DataElement dataElement) {
909 Objects.requireNonNull(obj, Objects.toString(dataElement));
910 if (!(obj instanceof Comparable)) {
911 throw new ClassCastException(dataElement + " must be Comparable");
912 }
913 }
914
915
916
917
918
919
920
921
922
923 private static void checkValue(final Object value) {
924 checkNonNullComparable(value, VALUE);
925 }
926
927
928
929
930
931
932
933
934
935
936 private static <T extends Comparable<T>> int compare(final T o1, final T o2) {
937 return o1.compareTo(o2);
938 }
939
940
941
942
943
944
945
946
947
948 private static boolean isBlack(final Node<?, ?> node, final DataElement dataElement) {
949 return node == null || node.isBlack(dataElement);
950 }
951
952
953
954
955
956
957
958
959
960 private static boolean isRed(final Node<?, ?> node, final DataElement dataElement) {
961 return node != null && node.isRed(dataElement);
962 }
963
964
965
966
967
968
969
970
971 private static void makeBlack(final Node<?, ?> node, final DataElement dataElement) {
972 if (node != null) {
973 node.setBlack(dataElement);
974 }
975 }
976
977
978
979
980
981
982
983
984 private static void makeRed(final Node<?, ?> node, final DataElement dataElement) {
985 if (node != null) {
986 node.setRed(dataElement);
987 }
988 }
989
990 private transient Node<K, V>[] rootNode;
991
992 private transient int nodeCount;
993
994 private transient int modifications;
995
996 private transient Set<K> keySet;
997
998 private transient Set<V> valuesSet;
999
1000 private transient Set<Map.Entry<K, V>> entrySet;
1001
1002 private transient Inverse inverse;
1003
1004
1005
1006
1007 @SuppressWarnings("unchecked")
1008 public TreeBidiMap() {
1009 rootNode = new Node[2];
1010 }
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020 public TreeBidiMap(final Map<? extends K, ? extends V> map) {
1021 this();
1022 putAll(map);
1023 }
1024
1025
1026
1027
1028 @Override
1029 public void clear() {
1030 modify();
1031
1032 nodeCount = 0;
1033 rootNode[KEY.ordinal()] = null;
1034 rootNode[VALUE.ordinal()] = null;
1035 }
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047 @Override
1048 public boolean containsKey(final Object key) {
1049 checkKey(key);
1050 return lookupKey(key) != null;
1051 }
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063 @Override
1064 public boolean containsValue(final Object value) {
1065 checkValue(value);
1066 return lookupValue(value) != null;
1067 }
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078 private void copyColor(final Node<K, V> from, final Node<K, V> to, final DataElement dataElement) {
1079 if (to != null) {
1080 if (from == null) {
1081
1082 to.setBlack(dataElement);
1083 } else {
1084 to.copyColor(from, dataElement);
1085 }
1086 }
1087 }
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097 private boolean doEquals(final Object obj, final DataElement dataElement) {
1098 if (obj == this) {
1099 return true;
1100 }
1101 if (!(obj instanceof Map)) {
1102 return false;
1103 }
1104 final Map<?, ?> other = (Map<?, ?>) obj;
1105 if (other.size() != size()) {
1106 return false;
1107 }
1108
1109 if (nodeCount > 0) {
1110 try {
1111 for (final MapIterator<?, ?> it = getMapIterator(dataElement); it.hasNext(); ) {
1112 final Object key = it.next();
1113 final Object value = it.getValue();
1114 if (!value.equals(other.get(key))) {
1115 return false;
1116 }
1117 }
1118 } catch (final ClassCastException | NullPointerException ex) {
1119 return false;
1120 }
1121 }
1122 return true;
1123 }
1124
1125
1126
1127
1128
1129
1130
1131
1132 private int doHashCode(final DataElement dataElement) {
1133 int total = 0;
1134 if (nodeCount > 0) {
1135 for (final MapIterator<?, ?> it = getMapIterator(dataElement); it.hasNext(); ) {
1136 final Object key = it.next();
1137 final Object value = it.getValue();
1138 total += key.hashCode() ^ value.hashCode();
1139 }
1140 }
1141 return total;
1142 }
1143
1144
1145
1146
1147
1148
1149
1150 private void doPut(final K key, final V value) {
1151 checkKeyAndValue(key, value);
1152
1153
1154 doRemoveKey(key);
1155 doRemoveValue(value);
1156
1157 Node<K, V> node = rootNode[KEY.ordinal()];
1158 if (node == null) {
1159
1160 final Node<K, V> root = new Node<>(key, value);
1161 rootNode[KEY.ordinal()] = root;
1162 rootNode[VALUE.ordinal()] = root;
1163 grow();
1164
1165 } else {
1166
1167 while (true) {
1168 final int cmp = compare(key, node.getKey());
1169
1170 if (cmp == 0) {
1171
1172 throw new IllegalArgumentException("Cannot store a duplicate key (\"" + key + "\") in this Map");
1173 }
1174 if (cmp < 0) {
1175 if (node.getLeft(KEY) == null) {
1176 final Node<K, V> newNode = new Node<>(key, value);
1177
1178 insertValue(newNode);
1179 node.setLeft(newNode, KEY);
1180 newNode.setParent(node, KEY);
1181 doRedBlackInsert(newNode, KEY);
1182 grow();
1183
1184 break;
1185 }
1186 node = node.getLeft(KEY);
1187 } else {
1188 if (node.getRight(KEY) == null) {
1189 final Node<K, V> newNode = new Node<>(key, value);
1190
1191 insertValue(newNode);
1192 node.setRight(newNode, KEY);
1193 newNode.setParent(node, KEY);
1194 doRedBlackInsert(newNode, KEY);
1195 grow();
1196
1197 break;
1198 }
1199 node = node.getRight(KEY);
1200 }
1201 }
1202 }
1203 }
1204
1205
1206
1207
1208
1209
1210
1211 private void doRedBlackDelete(final Node<K, V> deletedNode) {
1212 for (final DataElement dataElement : DataElement.values()) {
1213
1214
1215 if (deletedNode.getLeft(dataElement) != null && deletedNode.getRight(dataElement) != null) {
1216 swapPosition(nextGreater(deletedNode, dataElement), deletedNode, dataElement);
1217 }
1218
1219 final Node<K, V> replacement = deletedNode.getLeft(dataElement) != null ?
1220 deletedNode.getLeft(dataElement) : deletedNode.getRight(dataElement);
1221
1222 if (replacement != null) {
1223 replacement.setParent(deletedNode.getParent(dataElement), dataElement);
1224
1225 if (deletedNode.getParent(dataElement) == null) {
1226 rootNode[dataElement.ordinal()] = replacement;
1227 } else if (deletedNode == deletedNode.getParent(dataElement).getLeft(dataElement)) {
1228 deletedNode.getParent(dataElement).setLeft(replacement, dataElement);
1229 } else {
1230 deletedNode.getParent(dataElement).setRight(replacement, dataElement);
1231 }
1232
1233 deletedNode.setLeft(null, dataElement);
1234 deletedNode.setRight(null, dataElement);
1235 deletedNode.setParent(null, dataElement);
1236
1237 if (isBlack(deletedNode, dataElement)) {
1238 doRedBlackDeleteFixup(replacement, dataElement);
1239 }
1240 } else {
1241
1242
1243 if (deletedNode.getParent(dataElement) == null) {
1244
1245
1246 rootNode[dataElement.ordinal()] = null;
1247 } else {
1248
1249
1250 if (isBlack(deletedNode, dataElement)) {
1251 doRedBlackDeleteFixup(deletedNode, dataElement);
1252 }
1253
1254 if (deletedNode.getParent(dataElement) != null) {
1255 if (deletedNode == deletedNode.getParent(dataElement).getLeft(dataElement)) {
1256 deletedNode.getParent(dataElement).setLeft(null, dataElement);
1257 } else {
1258 deletedNode.getParent(dataElement).setRight(null, dataElement);
1259 }
1260
1261 deletedNode.setParent(null, dataElement);
1262 }
1263 }
1264 }
1265 }
1266 shrink();
1267 }
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278 private void doRedBlackDeleteFixup(final Node<K, V> replacementNode, final DataElement dataElement) {
1279 Node<K, V> currentNode = replacementNode;
1280
1281 while (currentNode != rootNode[dataElement.ordinal()] && isBlack(currentNode, dataElement)) {
1282 if (currentNode.isLeftChild(dataElement)) {
1283 Node<K, V> siblingNode = getRightChild(getParent(currentNode, dataElement), dataElement);
1284
1285 if (isRed(siblingNode, dataElement)) {
1286 makeBlack(siblingNode, dataElement);
1287 makeRed(getParent(currentNode, dataElement), dataElement);
1288 rotateLeft(getParent(currentNode, dataElement), dataElement);
1289
1290 siblingNode = getRightChild(getParent(currentNode, dataElement), dataElement);
1291 }
1292
1293 if (isBlack(getLeftChild(siblingNode, dataElement), dataElement)
1294 && isBlack(getRightChild(siblingNode, dataElement), dataElement)) {
1295 makeRed(siblingNode, dataElement);
1296
1297 currentNode = getParent(currentNode, dataElement);
1298 } else {
1299 if (isBlack(getRightChild(siblingNode, dataElement), dataElement)) {
1300 makeBlack(getLeftChild(siblingNode, dataElement), dataElement);
1301 makeRed(siblingNode, dataElement);
1302 rotateRight(siblingNode, dataElement);
1303
1304 siblingNode = getRightChild(getParent(currentNode, dataElement), dataElement);
1305 }
1306
1307 copyColor(getParent(currentNode, dataElement), siblingNode, dataElement);
1308 makeBlack(getParent(currentNode, dataElement), dataElement);
1309 makeBlack(getRightChild(siblingNode, dataElement), dataElement);
1310 rotateLeft(getParent(currentNode, dataElement), dataElement);
1311
1312 currentNode = rootNode[dataElement.ordinal()];
1313 }
1314 } else {
1315 Node<K, V> siblingNode = getLeftChild(getParent(currentNode, dataElement), dataElement);
1316
1317 if (isRed(siblingNode, dataElement)) {
1318 makeBlack(siblingNode, dataElement);
1319 makeRed(getParent(currentNode, dataElement), dataElement);
1320 rotateRight(getParent(currentNode, dataElement), dataElement);
1321
1322 siblingNode = getLeftChild(getParent(currentNode, dataElement), dataElement);
1323 }
1324
1325 if (isBlack(getRightChild(siblingNode, dataElement), dataElement)
1326 && isBlack(getLeftChild(siblingNode, dataElement), dataElement)) {
1327 makeRed(siblingNode, dataElement);
1328
1329 currentNode = getParent(currentNode, dataElement);
1330 } else {
1331 if (isBlack(getLeftChild(siblingNode, dataElement), dataElement)) {
1332 makeBlack(getRightChild(siblingNode, dataElement), dataElement);
1333 makeRed(siblingNode, dataElement);
1334 rotateLeft(siblingNode, dataElement);
1335
1336 siblingNode = getLeftChild(getParent(currentNode, dataElement), dataElement);
1337 }
1338
1339 copyColor(getParent(currentNode, dataElement), siblingNode, dataElement);
1340 makeBlack(getParent(currentNode, dataElement), dataElement);
1341 makeBlack(getLeftChild(siblingNode, dataElement), dataElement);
1342 rotateRight(getParent(currentNode, dataElement), dataElement);
1343
1344 currentNode = rootNode[dataElement.ordinal()];
1345 }
1346 }
1347 }
1348
1349 makeBlack(currentNode, dataElement);
1350 }
1351
1352
1353
1354
1355
1356
1357
1358
1359 private void doRedBlackInsert(final Node<K, V> insertedNode, final DataElement dataElement) {
1360 Node<K, V> currentNode = insertedNode;
1361 makeRed(currentNode, dataElement);
1362
1363 while (currentNode != null
1364 && currentNode != rootNode[dataElement.ordinal()]
1365 && isRed(currentNode.getParent(dataElement), dataElement)) {
1366 if (currentNode.isLeftChild(dataElement)) {
1367 final Node<K, V> y = getRightChild(getGrandParent(currentNode, dataElement), dataElement);
1368
1369 if (isRed(y, dataElement)) {
1370 makeBlack(getParent(currentNode, dataElement), dataElement);
1371 makeBlack(y, dataElement);
1372 makeRed(getGrandParent(currentNode, dataElement), dataElement);
1373
1374 currentNode = getGrandParent(currentNode, dataElement);
1375 } else {
1376
1377 if (currentNode.isRightChild(dataElement)) {
1378 currentNode = getParent(currentNode, dataElement);
1379
1380 rotateLeft(currentNode, dataElement);
1381 }
1382
1383 makeBlack(getParent(currentNode, dataElement), dataElement);
1384 makeRed(getGrandParent(currentNode, dataElement), dataElement);
1385
1386 if (getGrandParent(currentNode, dataElement) != null) {
1387 rotateRight(getGrandParent(currentNode, dataElement), dataElement);
1388 }
1389 }
1390 } else {
1391
1392
1393 final Node<K, V> y = getLeftChild(getGrandParent(currentNode, dataElement), dataElement);
1394
1395 if (isRed(y, dataElement)) {
1396 makeBlack(getParent(currentNode, dataElement), dataElement);
1397 makeBlack(y, dataElement);
1398 makeRed(getGrandParent(currentNode, dataElement), dataElement);
1399
1400 currentNode = getGrandParent(currentNode, dataElement);
1401 } else {
1402
1403 if (currentNode.isLeftChild(dataElement)) {
1404 currentNode = getParent(currentNode, dataElement);
1405
1406 rotateRight(currentNode, dataElement);
1407 }
1408
1409 makeBlack(getParent(currentNode, dataElement), dataElement);
1410 makeRed(getGrandParent(currentNode, dataElement), dataElement);
1411
1412 if (getGrandParent(currentNode, dataElement) != null) {
1413 rotateLeft(getGrandParent(currentNode, dataElement), dataElement);
1414 }
1415 }
1416 }
1417 }
1418
1419 makeBlack(rootNode[dataElement.ordinal()], dataElement);
1420 }
1421
1422 private V doRemoveKey(final Object key) {
1423 final Node<K, V> node = lookupKey(key);
1424 if (node == null) {
1425 return null;
1426 }
1427 doRedBlackDelete(node);
1428 return node.getValue();
1429 }
1430
1431 private K doRemoveValue(final Object value) {
1432 final Node<K, V> node = lookupValue(value);
1433 if (node == null) {
1434 return null;
1435 }
1436 doRedBlackDelete(node);
1437 return node.getKey();
1438 }
1439
1440
1441
1442
1443
1444
1445
1446
1447 private String doToString(final DataElement dataElement) {
1448 if (nodeCount == 0) {
1449 return "{}";
1450 }
1451 final StringBuilder buf = new StringBuilder(nodeCount * 32);
1452 buf.append('{');
1453 final MapIterator<?, ?> it = getMapIterator(dataElement);
1454 boolean hasNext = it.hasNext();
1455 while (hasNext) {
1456 final Object key = it.next();
1457 final Object value = it.getValue();
1458 buf.append(key == this ? "(this Map)" : key)
1459 .append('=')
1460 .append(value == this ? "(this Map)" : value);
1461
1462 hasNext = it.hasNext();
1463 if (hasNext) {
1464 buf.append(", ");
1465 }
1466 }
1467
1468 buf.append('}');
1469 return buf.toString();
1470 }
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486 @Override
1487 public Set<Map.Entry<K, V>> entrySet() {
1488 if (entrySet == null) {
1489 entrySet = new EntryView();
1490 }
1491 return entrySet;
1492 }
1493
1494
1495
1496
1497
1498
1499
1500 @Override
1501 public boolean equals(final Object obj) {
1502 return this.doEquals(obj, KEY);
1503 }
1504
1505
1506
1507
1508
1509
1510
1511 @Override
1512 public K firstKey() {
1513 if (nodeCount == 0) {
1514 throw new NoSuchElementException("Map is empty");
1515 }
1516 return leastNode(rootNode[KEY.ordinal()], KEY).getKey();
1517 }
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531 @Override
1532 public V get(final Object key) {
1533 checkKey(key);
1534 final Node<K, V> node = lookupKey(key);
1535 return node == null ? null : node.getValue();
1536 }
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546 private Node<K, V> getGrandParent(final Node<K, V> node, final DataElement dataElement) {
1547 return getParent(getParent(node, dataElement), dataElement);
1548 }
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562 @Override
1563 public K getKey(final Object value) {
1564 checkValue(value);
1565 final Node<K, V> node = lookupValue(value);
1566 return node == null ? null : node.getKey();
1567 }
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577 private Node<K, V> getLeftChild(final Node<K, V> node, final DataElement dataElement) {
1578 return node == null ? null : node.getLeft(dataElement);
1579 }
1580
1581 private MapIterator<?, ?> getMapIterator(final DataElement dataElement) {
1582 switch (dataElement) {
1583 case KEY:
1584 return new ViewMapIterator(KEY);
1585 case VALUE:
1586 return new InverseViewMapIterator(VALUE);
1587 default:
1588 throw new IllegalArgumentException();
1589 }
1590 }
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600 private Node<K, V> getParent(final Node<K, V> node, final DataElement dataElement) {
1601 return node == null ? null : node.getParent(dataElement);
1602 }
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612 private Node<K, V> getRightChild(final Node<K, V> node, final DataElement dataElement) {
1613 return node == null ? null : node.getRight(dataElement);
1614 }
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624 private Node<K, V> greatestNode(final Node<K, V> node, final DataElement dataElement) {
1625 Node<K, V> rval = node;
1626 if (rval != null) {
1627 while (rval.getRight(dataElement) != null) {
1628 rval = rval.getRight(dataElement);
1629 }
1630 }
1631 return rval;
1632 }
1633
1634
1635
1636
1637 private void grow() {
1638 modify();
1639 nodeCount++;
1640 }
1641
1642
1643
1644
1645
1646
1647 @Override
1648 public int hashCode() {
1649 return this.doHashCode(KEY);
1650 }
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660 private void insertValue(final Node<K, V> newNode) throws IllegalArgumentException {
1661 Node<K, V> node = rootNode[VALUE.ordinal()];
1662
1663 while (true) {
1664 final int cmp = compare(newNode.getValue(), node.getValue());
1665
1666 if (cmp == 0) {
1667 throw new IllegalArgumentException(
1668 "Cannot store a duplicate value (\"" + newNode.getData(VALUE) + "\") in this Map");
1669 }
1670 if (cmp < 0) {
1671 if (node.getLeft(VALUE) == null) {
1672 node.setLeft(newNode, VALUE);
1673 newNode.setParent(node, VALUE);
1674 doRedBlackInsert(newNode, VALUE);
1675
1676 break;
1677 }
1678 node = node.getLeft(VALUE);
1679 } else {
1680 if (node.getRight(VALUE) == null) {
1681 node.setRight(newNode, VALUE);
1682 newNode.setParent(node, VALUE);
1683 doRedBlackInsert(newNode, VALUE);
1684
1685 break;
1686 }
1687 node = node.getRight(VALUE);
1688 }
1689 }
1690 }
1691
1692
1693
1694
1695
1696
1697 @Override
1698 public OrderedBidiMap<V, K> inverseBidiMap() {
1699 if (inverse == null) {
1700 inverse = new Inverse();
1701 }
1702 return inverse;
1703 }
1704
1705
1706
1707
1708
1709
1710 @Override
1711 public boolean isEmpty() {
1712 return nodeCount == 0;
1713 }
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727 @Override
1728 public Set<K> keySet() {
1729 if (keySet == null) {
1730 keySet = new KeyView(KEY);
1731 }
1732 return keySet;
1733 }
1734
1735
1736
1737
1738
1739
1740
1741 @Override
1742 public K lastKey() {
1743 if (nodeCount == 0) {
1744 throw new NoSuchElementException("Map is empty");
1745 }
1746 return greatestNode(rootNode[KEY.ordinal()], KEY).getKey();
1747 }
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758 private Node<K, V> leastNode(final Node<K, V> node, final DataElement dataElement) {
1759 Node<K, V> rval = node;
1760 if (rval != null) {
1761 while (rval.getLeft(dataElement) != null) {
1762 rval = rval.getLeft(dataElement);
1763 }
1764 }
1765 return rval;
1766 }
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777 @SuppressWarnings("unchecked")
1778 private <T extends Comparable<T>> Node<K, V> lookup(final Object data, final DataElement dataElement) {
1779 Node<K, V> rval = null;
1780 Node<K, V> node = rootNode[dataElement.ordinal()];
1781
1782 while (node != null) {
1783 final int cmp = compare((T) data, (T) node.getData(dataElement));
1784 if (cmp == 0) {
1785 rval = node;
1786 break;
1787 }
1788 node = cmp < 0 ? node.getLeft(dataElement) : node.getRight(dataElement);
1789 }
1790
1791 return rval;
1792 }
1793
1794 private Node<K, V> lookupKey(final Object key) {
1795 return this.<K>lookup(key, KEY);
1796 }
1797
1798 private Node<K, V> lookupValue(final Object value) {
1799 return this.<V>lookup(value, VALUE);
1800 }
1801
1802 @Override
1803 public OrderedMapIterator<K, V> mapIterator() {
1804 if (isEmpty()) {
1805 return EmptyOrderedMapIterator.<K, V>emptyOrderedMapIterator();
1806 }
1807 return new ViewMapIterator(KEY);
1808 }
1809
1810
1811
1812
1813
1814
1815 private void modify() {
1816 modifications++;
1817 }
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827 private Node<K, V> nextGreater(final Node<K, V> node, final DataElement dataElement) {
1828 final Node<K, V> rval;
1829 if (node == null) {
1830 rval = null;
1831 } else if (node.getRight(dataElement) != null) {
1832
1833
1834 rval = leastNode(node.getRight(dataElement), dataElement);
1835 } else {
1836
1837
1838
1839
1840
1841
1842 Node<K, V> parent = node.getParent(dataElement);
1843 Node<K, V> child = node;
1844
1845 while (parent != null && child == parent.getRight(dataElement)) {
1846 child = parent;
1847 parent = parent.getParent(dataElement);
1848 }
1849 rval = parent;
1850 }
1851 return rval;
1852 }
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862 @Override
1863 public K nextKey(final K key) {
1864 checkKey(key);
1865 final Node<K, V> node = nextGreater(lookupKey(key), KEY);
1866 return node == null ? null : node.getKey();
1867 }
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877 private Node<K, V> nextSmaller(final Node<K, V> node, final DataElement dataElement) {
1878 final Node<K, V> rval;
1879 if (node == null) {
1880 rval = null;
1881 } else if (node.getLeft(dataElement) != null) {
1882
1883
1884 rval = greatestNode(node.getLeft(dataElement), dataElement);
1885 } else {
1886
1887
1888
1889
1890
1891
1892 Node<K, V> parent = node.getParent(dataElement);
1893 Node<K, V> child = node;
1894
1895 while (parent != null && child == parent.getLeft(dataElement)) {
1896 child = parent;
1897 parent = parent.getParent(dataElement);
1898 }
1899 rval = parent;
1900 }
1901 return rval;
1902 }
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912 @Override
1913 public K previousKey(final K key) {
1914 checkKey(key);
1915 final Node<K, V> node = nextSmaller(lookupKey(key), KEY);
1916 return node == null ? null : node.getKey();
1917 }
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943 @Override
1944 public V put(final K key, final V value) {
1945 final V result = get(key);
1946 doPut(key, value);
1947 return result;
1948 }
1949
1950
1951
1952
1953
1954
1955
1956
1957 @Override
1958 public void putAll(final Map<? extends K, ? extends V> map) {
1959 for (final Map.Entry<? extends K, ? extends V> e : map.entrySet()) {
1960 put(e.getKey(), e.getValue());
1961 }
1962 }
1963
1964
1965
1966
1967
1968
1969
1970
1971 @SuppressWarnings("unchecked")
1972 private void readObject(final ObjectInputStream stream) throws IOException, ClassNotFoundException {
1973 stream.defaultReadObject();
1974 rootNode = new Node[2];
1975 final int size = stream.readInt();
1976 for (int i = 0; i < size; i++) {
1977 final K k = (K) stream.readObject();
1978 final V v = (V) stream.readObject();
1979 put(k, v);
1980 }
1981 }
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994 @Override
1995 public V remove(final Object key) {
1996 return doRemoveKey(key);
1997 }
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010 @Override
2011 public K removeValue(final Object value) {
2012 return doRemoveValue(value);
2013 }
2014
2015
2016
2017
2018
2019
2020
2021
2022 private void rotateLeft(final Node<K, V> node, final DataElement dataElement) {
2023 final Node<K, V> rightChild = node.getRight(dataElement);
2024 node.setRight(rightChild.getLeft(dataElement), dataElement);
2025
2026 if (rightChild.getLeft(dataElement) != null) {
2027 rightChild.getLeft(dataElement).setParent(node, dataElement);
2028 }
2029 rightChild.setParent(node.getParent(dataElement), dataElement);
2030
2031 if (node.getParent(dataElement) == null) {
2032
2033 rootNode[dataElement.ordinal()] = rightChild;
2034 } else if (node.getParent(dataElement).getLeft(dataElement) == node) {
2035 node.getParent(dataElement).setLeft(rightChild, dataElement);
2036 } else {
2037 node.getParent(dataElement).setRight(rightChild, dataElement);
2038 }
2039
2040 rightChild.setLeft(node, dataElement);
2041 node.setParent(rightChild, dataElement);
2042 }
2043
2044
2045
2046
2047
2048
2049
2050
2051 private void rotateRight(final Node<K, V> node, final DataElement dataElement) {
2052 final Node<K, V> leftChild = node.getLeft(dataElement);
2053 node.setLeft(leftChild.getRight(dataElement), dataElement);
2054 if (leftChild.getRight(dataElement) != null) {
2055 leftChild.getRight(dataElement).setParent(node, dataElement);
2056 }
2057 leftChild.setParent(node.getParent(dataElement), dataElement);
2058
2059 if (node.getParent(dataElement) == null) {
2060
2061 rootNode[dataElement.ordinal()] = leftChild;
2062 } else if (node.getParent(dataElement).getRight(dataElement) == node) {
2063 node.getParent(dataElement).setRight(leftChild, dataElement);
2064 } else {
2065 node.getParent(dataElement).setLeft(leftChild, dataElement);
2066 }
2067
2068 leftChild.setRight(node, dataElement);
2069 node.setParent(leftChild, dataElement);
2070 }
2071
2072
2073
2074
2075 private void shrink() {
2076 modify();
2077 nodeCount--;
2078 }
2079
2080
2081
2082
2083
2084
2085 @Override
2086 public int size() {
2087 return nodeCount;
2088 }
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099 private void swapPosition(final Node<K, V> x, final Node<K, V> y, final DataElement dataElement) {
2100
2101 final Node<K, V> xFormerParent = x.getParent(dataElement);
2102 final Node<K, V> xFormerLeftChild = x.getLeft(dataElement);
2103 final Node<K, V> xFormerRightChild = x.getRight(dataElement);
2104 final Node<K, V> yFormerParent = y.getParent(dataElement);
2105 final Node<K, V> yFormerLeftChild = y.getLeft(dataElement);
2106 final Node<K, V> yFormerRightChild = y.getRight(dataElement);
2107 final boolean xWasLeftChild =
2108 x.getParent(dataElement) != null && x == x.getParent(dataElement).getLeft(dataElement);
2109 final boolean yWasLeftChild =
2110 y.getParent(dataElement) != null && y == y.getParent(dataElement).getLeft(dataElement);
2111
2112
2113 if (x == yFormerParent) {
2114 x.setParent(y, dataElement);
2115
2116 if (yWasLeftChild) {
2117 y.setLeft(x, dataElement);
2118 y.setRight(xFormerRightChild, dataElement);
2119 } else {
2120 y.setRight(x, dataElement);
2121 y.setLeft(xFormerLeftChild, dataElement);
2122 }
2123 } else {
2124 x.setParent(yFormerParent, dataElement);
2125
2126 if (yFormerParent != null) {
2127 if (yWasLeftChild) {
2128 yFormerParent.setLeft(x, dataElement);
2129 } else {
2130 yFormerParent.setRight(x, dataElement);
2131 }
2132 }
2133
2134 y.setLeft(xFormerLeftChild, dataElement);
2135 y.setRight(xFormerRightChild, dataElement);
2136 }
2137
2138 if (y == xFormerParent) {
2139 y.setParent(x, dataElement);
2140
2141 if (xWasLeftChild) {
2142 x.setLeft(y, dataElement);
2143 x.setRight(yFormerRightChild, dataElement);
2144 } else {
2145 x.setRight(y, dataElement);
2146 x.setLeft(yFormerLeftChild, dataElement);
2147 }
2148 } else {
2149 y.setParent(xFormerParent, dataElement);
2150
2151 if (xFormerParent != null) {
2152 if (xWasLeftChild) {
2153 xFormerParent.setLeft(y, dataElement);
2154 } else {
2155 xFormerParent.setRight(y, dataElement);
2156 }
2157 }
2158
2159 x.setLeft(yFormerLeftChild, dataElement);
2160 x.setRight(yFormerRightChild, dataElement);
2161 }
2162
2163
2164 if (x.getLeft(dataElement) != null) {
2165 x.getLeft(dataElement).setParent(x, dataElement);
2166 }
2167
2168 if (x.getRight(dataElement) != null) {
2169 x.getRight(dataElement).setParent(x, dataElement);
2170 }
2171
2172 if (y.getLeft(dataElement) != null) {
2173 y.getLeft(dataElement).setParent(y, dataElement);
2174 }
2175
2176 if (y.getRight(dataElement) != null) {
2177 y.getRight(dataElement).setParent(y, dataElement);
2178 }
2179
2180 x.swapColors(y, dataElement);
2181
2182
2183 if (rootNode[dataElement.ordinal()] == x) {
2184 rootNode[dataElement.ordinal()] = y;
2185 } else if (rootNode[dataElement.ordinal()] == y) {
2186 rootNode[dataElement.ordinal()] = x;
2187 }
2188 }
2189
2190
2191
2192
2193
2194
2195 @Override
2196 public String toString() {
2197 return this.doToString(KEY);
2198 }
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213 @Override
2214 public Set<V> values() {
2215 if (valuesSet == null) {
2216 valuesSet = new ValueView(KEY);
2217 }
2218 return valuesSet;
2219 }
2220
2221
2222
2223
2224
2225
2226
2227 private void writeObject(final ObjectOutputStream stream) throws IOException {
2228 stream.defaultWriteObject();
2229 stream.writeInt(this.size());
2230 for (final Entry<K, V> entry : entrySet()) {
2231 stream.writeObject(entry.getKey());
2232 stream.writeObject(entry.getValue());
2233 }
2234 }
2235
2236 }