1 /
55
56 package org.apache.poi.util;
57
58 import java.util.*;
59
60
128 public final class BinaryTree
129
130 extends AbstractMap
131 {
132 private Node[] _root = new Node[]
133 {
134 null, null
135 };
136 private int _size = 0;
137 private int _modifications = 0;
138 private Set[] _key_set = new Set[]
139 {
140 null, null
141 };
142 private Set[] _entry_set = new Set[]
143 {
144 null, null
145 };
146 private Collection[] _value_collection = new Collection[]
147 {
148 null, null
149 };
150 private static final int _KEY = 0;
151 private static final int _VALUE = 1;
152 private static final int _INDEX_SUM = _KEY + _VALUE;
153 private static final int _MINIMUM_INDEX = 0;
154 private static final int _INDEX_COUNT = 2;
155 private static final String[] _data_name = new String[]
156 {
157 "key", "value"
158 };
159
160
163
164 public BinaryTree()
165 {
166 }
167
168
185
186 public BinaryTree(final Map map)
187 throws ClassCastException, NullPointerException,
188 IllegalArgumentException
189 {
190 putAll(map);
191 }
192
193
206
207 public Object getKeyForValue(final Object value)
208 throws ClassCastException, NullPointerException
209 {
210 return doGet(( Comparable ) value, _VALUE);
211 }
212
213
221
222 public Object removeValue(final Object value)
223 {
224 return doRemove(( Comparable ) value, _VALUE);
225 }
226
227
246
247 public Set entrySetByValue()
248 {
249 if (_entry_set[ _VALUE ] == null)
250 {
251 _entry_set[ _VALUE ] = new AbstractSet()
252 {
253 public Iterator iterator()
254 {
255 return new BinaryTreeIterator(_VALUE)
256 {
257 protected Object doGetNext()
258 {
259 return _last_returned_node;
260 }
261 };
262 }
263
264 public boolean contains(Object o)
265 {
266 if (!(o instanceof Map.Entry))
267 {
268 return false;
269 }
270 Map.Entry entry = ( Map.Entry ) o;
271 Object key = entry.getKey();
272 Node node = lookup(( Comparable ) entry.getValue(),
273 _VALUE);
274
275 return (node != null) && node.getData(_KEY).equals(key);
276 }
277
278 public boolean remove(Object o)
279 {
280 if (!(o instanceof Map.Entry))
281 {
282 return false;
283 }
284 Map.Entry entry = ( Map.Entry ) o;
285 Object key = entry.getKey();
286 Node node = lookup(( Comparable ) entry.getValue(),
287 _VALUE);
288
289 if ((node != null) && node.getData(_KEY).equals(key))
290 {
291 doRedBlackDelete(node);
292 return true;
293 }
294 return false;
295 }
296
297 public int size()
298 {
299 return BinaryTree.this.size();
300 }
301
302 public void clear()
303 {
304 BinaryTree.this.clear();
305 }
306 };
307 }
308 return _entry_set[ _VALUE ];
309 }
310
311
329
330 public Set keySetByValue()
331 {
332 if (_key_set[ _VALUE ] == null)
333 {
334 _key_set[ _VALUE ] = new AbstractSet()
335 {
336 public Iterator iterator()
337 {
338 return new BinaryTreeIterator(_VALUE)
339 {
340 protected Object doGetNext()
341 {
342 return _last_returned_node.getData(_KEY);
343 }
344 };
345 }
346
347 public int size()
348 {
349 return BinaryTree.this.size();
350 }
351
352 public boolean contains(Object o)
353 {
354 return containsKey(o);
355 }
356
357 public boolean remove(Object o)
358 {
359 int old_size = _size;
360
361 BinaryTree.this.remove(o);
362 return _size != old_size;
363 }
364
365 public void clear()
366 {
367 BinaryTree.this.clear();
368 }
369 };
370 }
371 return _key_set[ _VALUE ];
372 }
373
374
392
393 public Collection valuesByValue()
394 {
395 if (_value_collection[ _VALUE ] == null)
396 {
397 _value_collection[ _VALUE ] = new AbstractCollection()
398 {
399 public Iterator iterator()
400 {
401 return new BinaryTreeIterator(_VALUE)
402 {
403 protected Object doGetNext()
404 {
405 return _last_returned_node.getData(_VALUE);
406 }
407 };
408 }
409
410 public int size()
411 {
412 return BinaryTree.this.size();
413 }
414
415 public boolean contains(Object o)
416 {
417 return containsValue(o);
418 }
419
420 public boolean remove(Object o)
421 {
422 int old_size = _size;
423
424 removeValue(o);
425 return _size != old_size;
426 }
427
428 public boolean removeAll(Collection c)
429 {
430 boolean modified = false;
431 Iterator iter = c.iterator();
432
433 while (iter.hasNext())
434 {
435 if (removeValue(iter.next()) != null)
436 {
437 modified = true;
438 }
439 }
440 return modified;
441 }
442
443 public void clear()
444 {
445 BinaryTree.this.clear();
446 }
447 };
448 }
449 return _value_collection[ _VALUE ];
450 }
451
452
462
463 private Object doRemove(final Comparable o, final int index)
464 {
465 Node node = lookup(o, index);
466 Object rval = null;
467
468 if (node != null)
469 {
470 rval = node.getData(oppositeIndex(index));
471 doRedBlackDelete(node);
472 }
473 return rval;
474 }
475
476
486
487 private Object doGet(final Comparable o, final int index)
488 {
489 checkNonNullComparable(o, index);
490 Node node = lookup(o, index);
491
492 return ((node == null) ? null
493 : node.getData(oppositeIndex(index)));
494 }
495
496
503
504 private int oppositeIndex(final int index)
505 {
506
507
508
509
510 return _INDEX_SUM - index;
511 }
512
513
522
523 private Node lookup(final Comparable data, final int index)
524 {
525 Node rval = null;
526 Node node = _root[ index ];
527
528 while (node != null)
529 {
530 int cmp = compare(data, node.getData(index));
531
532 if (cmp == 0)
533 {
534 rval = node;
535 break;
536 }
537 else
538 {
539 node = (cmp < 0) ? node.getLeft(index)
540 : node.getRight(index);
541 }
542 }
543 return rval;
544 }
545
546
555
556 private static int compare(final Comparable o1, final Comparable o2)
557 {
558 return (( Comparable ) o1).compareTo(o2);
559 }
560
561
571
572 private static Node leastNode(final Node node, final int index)
573 {
574 Node rval = node;
575
576 if (rval != null)
577 {
578 while (rval.getLeft(index) != null)
579 {
580 rval = rval.getLeft(index);
581 }
582 }
583 return rval;
584 }
585
586
594
595 private Node nextGreater(final Node node, final int index)
596 {
597 Node rval = null;
598
599 if (node == null)
600 {
601 rval = null;
602 }
603 else if (node.getRight(index) != null)
604 {
605
606
607
608 rval = leastNode(node.getRight(index), index);
609 }
610 else
611 {
612
613
614
615
616
617
618
619 Node parent = node.getParent(index);
620 Node child = node;
621
622 while ((parent != null) && (child == parent.getRight(index)))
623 {
624 child = parent;
625 parent = parent.getParent(index);
626 }
627 rval = parent;
628 }
629 return rval;
630 }
631
632
640
641 private static void copyColor(final Node from, final Node to,
642 final int index)
643 {
644 if (to != null)
645 {
646 if (from == null)
647 {
648
649
650 to.setBlack(index);
651 }
652 else
653 {
654 to.copyColor(from, index);
655 }
656 }
657 }
658
659
666
667 private static boolean isRed(final Node node, final int index)
668 {
669 return ((node == null) ? false
670 : node.isRed(index));
671 }
672
673
680
681 private static boolean isBlack(final Node node, final int index)
682 {
683 return ((node == null) ? true
684 : node.isBlack(index));
685 }
686
687
693
694 private static void makeRed(final Node node, final int index)
695 {
696 if (node != null)
697 {
698 node.setRed(index);
699 }
700 }
701
702
708
709 private static void makeBlack(final Node node, final int index)
710 {
711 if (node != null)
712 {
713 node.setBlack(index);
714 }
715 }
716
717
724
725 private static Node getGrandParent(final Node node, final int index)
726 {
727 return getParent(getParent(node, index), index);
728 }
729
730
737
738 private static Node getParent(final Node node, final int index)
739 {
740 return ((node == null) ? null
741 : node.getParent(index));
742 }
743
744
751
752 private static Node getRightChild(final Node node, final int index)
753 {
754 return (node == null) ? null
755 : node.getRight(index);
756 }
757
758
765
766 private static Node getLeftChild(final Node node, final int index)
767 {
768 return (node == null) ? null
769 : node.getLeft(index);
770 }
771
772
783
784 private static boolean isLeftChild(final Node node, final int index)
785 {
786 return (node == null) ? true
787 : ((node.getParent(index) == null) ? false
788 : (node
789 == node.getParentgetLeft index).getLeft(
790 index)));
791 }
792
793
804
805 private static boolean isRightChild(final Node node, final int index)
806 {
807 return (node == null) ? true
808 : ((node.getParent(index) == null) ? false
809 : (node
810 == node.getParentgetRight index).getRight(
811 index)));
812 }
813
814
820
821 private void rotateLeft(final Node node, final int index)
822 {
823 Node right_child = node.getRight(index);
824
825 node.setRight(right_child.getLeft(index), index);
826 if (right_child.getLeft(index) != null)
827 {
828 right_child.getLeft(index).setParent(node, index);
829 }
830 right_child.setParent(node.getParent(index), index);
831 if (node.getParent(index) == null)
832 {
833
834
835 _root[ index ] = right_child;
836 }
837 else if (node.getParent(index).getLeft(index) == node)
838 {
839 node.getParent(index).setLeft(right_child, index);
840 }
841 else
842 {
843 node.getParent(index).setRight(right_child, index);
844 }
845 right_child.setLeft(node, index);
846 node.setParent(right_child, index);
847 }
848
849
855
856 private void rotateRight(final Node node, final int index)
857 {
858 Node left_child = node.getLeft(index);
859
860 node.setLeft(left_child.getRight(index), index);
861 if (left_child.getRight(index) != null)
862 {
863 left_child.getRight(index).setParent(node, index);
864 }
865 left_child.setParent(node.getParent(index), index);
866 if (node.getParent(index) == null)
867 {
868
869
870 _root[ index ] = left_child;
871 }
872 else if (node.getParent(index).getRight(index) == node)
873 {
874 node.getParent(index).setRight(left_child, index);
875 }
876 else
877 {
878 node.getParent(index).setLeft(left_child, index);
879 }
880 left_child.setRight(node, index);
881 node.setParent(left_child, index);
882 }
883
884
891
892 private void doRedBlackInsert(final Node inserted_node, final int index)
893 {
894 Node current_node = inserted_node;
895
896 makeRed(current_node, index);
897 while ((current_node != null) && (current_node != _root[ index ])
898 && (isRed(current_node.getParent(index), index)))
899 {
900 if (isLeftChild(getParent(current_node, index), index))
901 {
902 Node y = getRightChild(getGrandParent(current_node, index),
903 index);
904
905 if (isRed(y, index))
906 {
907 makeBlack(getParent(current_node, index), index);
908 makeBlack(y, index);
909 makeRed(getGrandParent(current_node, index), index);
910 current_node = getGrandParent(current_node, index);
911 }
912 else
913 {
914 if (isRightChild(current_node, index))
915 {
916 current_node = getParent(current_node, index);
917 rotateLeft(current_node, index);
918 }
919 makeBlack(getParent(current_node, index), index);
920 makeRed(getGrandParent(current_node, index), index);
921 if (getGrandParent(current_node, index) != null)
922 {
923 rotateRight(getGrandParent(current_node, index),
924 index);
925 }
926 }
927 }
928 else
929 {
930
931
932 Node y = getLeftChild(getGrandParent(current_node, index),
933 index);
934
935 if (isRed(y, index))
936 {
937 makeBlack(getParent(current_node, index), index);
938 makeBlack(y, index);
939 makeRed(getGrandParent(current_node, index), index);
940 current_node = getGrandParent(current_node, index);
941 }
942 else
943 {
944 if (isLeftChild(current_node, index))
945 {
946 current_node = getParent(current_node, index);
947 rotateRight(current_node, index);
948 }
949 makeBlack(getParent(current_node, index), index);
950 makeRed(getGrandParent(current_node, index), index);
951 if (getGrandParent(current_node, index) != null)
952 {
953 rotateLeft(getGrandParent(current_node, index),
954 index);
955 }
956 }
957 }
958 }
959 makeBlack(_root[ index ], index);
960 }
961
962
968
969 private void doRedBlackDelete(final Node deleted_node)
970 {
971 for (int index = _MINIMUM_INDEX; index < _INDEX_COUNT; index++)
972 {
973
974
975
976 if ((deleted_node.getLeft(index) != null)
977 && (deleted_node.getRight(index) != null))
978 {
979 swapPosition(nextGreater(deleted_node, index), deleted_node,
980 index);
981 }
982 Node replacement = ((deleted_node.getLeft(index) != null)
983 ? deleted_node.getLeft(index)
984 : deleted_node.getRight(index));
985
986 if (replacement != null)
987 {
988 replacement.setParent(deleted_node.getParent(index), index);
989 if (deleted_node.getParent(index) == null)
990 {
991 _root[ index ] = replacement;
992 }
993 else if (deleted_node
994 == deleted_node.getParent(index).getLeft(index))
995 {
996 deleted_node.getParent(index).setLeft(replacement, index);
997 }
998 else
999 {
1000 deleted_node.getParent(index).setRight(replacement,
1001 index);
1002 }
1003 deleted_node.setLeft(null, index);
1004 deleted_node.setRight(null, index);
1005 deleted_node.setParent(null, index);
1006 if (isBlack(deleted_node, index))
1007 {
1008 doRedBlackDeleteFixup(replacement, index);
1009 }
1010 }
1011 else
1012 {
1013
1014
1015 if (deleted_node.getParent(index) == null)
1016 {
1017
1018
1019 _root[ index ] = null;
1020 }
1021 else
1022 {
1023
1024
1025 if (isBlack(deleted_node, index))
1026 {
1027 doRedBlackDeleteFixup(deleted_node, index);
1028 }
1029 if (deleted_node.getParent(index) != null)
1030 {
1031 if (deleted_node
1032 == deleted_nodegetLeftgetParentindex .getLeft(index))
1033 {
1034 deleted_node.getParent(index).setLeft(null,
1035 index);
1036 }
1037 else
1038 {
1039 deleted_node.getParent(index).setRight(null,
1040 index);
1041 }
1042 deleted_node.setParent(null, index);
1043 }
1044 }
1045 }
1046 }
1047 shrink();
1048 }
1049
1050
1059
1060 private void doRedBlackDeleteFixup(final Node replacement_node,
1061 final int index)
1062 {
1063 Node current_node = replacement_node;
1064
1065 while ((current_node != _root[ index ])
1066 && (isBlack(current_node, index)))
1067 {
1068 if (isLeftChild(current_node, index))
1069 {
1070 Node sibling_node =
1071 getRightChild(getParent(current_node, index), index);
1072
1073 if (isRed(sibling_node, index))
1074 {
1075 makeBlack(sibling_node, index);
1076 makeRed(getParent(current_node, index), index);
1077 rotateLeft(getParent(current_node, index), index);
1078 sibling_node =
1079 getRightChild(getParent(current_node, index), index);
1080 }
1081 if (isBlack(getLeftChild(sibling_node, index), index)
1082 && isBlack(getRightChild(sibling_node, index), index))
1083 {
1084 makeRed(sibling_node, index);
1085 current_node = getParent(current_node, index);
1086 }
1087 else
1088 {
1089 if (isBlack(getRightChild(sibling_node, index), index))
1090 {
1091 makeBlack(getLeftChild(sibling_node, index), index);
1092 makeRed(sibling_node, index);
1093 rotateRight(sibling_node, index);
1094 sibling_node =
1095 getRightChild(getParent(current_node, index),
1096 index);
1097 }
1098 copyColor(getParent(current_node, index), sibling_node,
1099 index);
1100 makeBlack(getParent(current_node, index), index);
1101 makeBlack(getRightChild(sibling_node, index), index);
1102 rotateLeft(getParent(current_node, index), index);
1103 current_node = _root[ index ];
1104 }
1105 }
1106 else
1107 {
1108 Node sibling_node =
1109 getLeftChild(getParent(current_node, index), index);
1110
1111 if (isRed(sibling_node, index))
1112 {
1113 makeBlack(sibling_node, index);
1114 makeRed(getParent(current_node, index), index);
1115 rotateRight(getParent(current_node, index), index);
1116 sibling_node =
1117 getLeftChild(getParent(current_node, index), index);
1118 }
1119 if (isBlack(getRightChild(sibling_node, index), index)
1120 && isBlack(getLeftChild(sibling_node, index), index))
1121 {
1122 makeRed(sibling_node, index);
1123 current_node = getParent(current_node, index);
1124 }
1125 else
1126 {
1127 if (isBlack(getLeftChild(sibling_node, index), index))
1128 {
1129 makeBlack(getRightChild(sibling_node, index), index);
1130 makeRed(sibling_node, index);
1131 rotateLeft(sibling_node, index);
1132 sibling_node =
1133 getLeftChild(getParent(current_node, index),
1134 index);
1135 }
1136 copyColor(getParent(current_node, index), sibling_node,
1137 index);
1138 makeBlack(getParent(current_node, index), index);
1139 makeBlack(getLeftChild(sibling_node, index), index);
1140 rotateRight(getParent(current_node, index), index);
1141 current_node = _root[ index ];
1142 }
1143 }
1144 }
1145 makeBlack(current_node, index);
1146 }
1147
1148
1157
1158 private void swapPosition(final Node x, final Node y, final int index)
1159 {
1160
1161
1162 Node x_old_parent = x.getParent(index);
1163 Node x_old_left_child = x.getLeft(index);
1164 Node x_old_right_child = x.getRight(index);
1165 Node y_old_parent = y.getParent(index);
1166 Node y_old_left_child = y.getLeft(index);
1167 Node y_old_right_child = y.getRight(index);
1168 boolean x_was_left_child =
1169 (x.getParent(index) != null)
1170 && (x == x.getParent(index).getLeft(index));
1171 boolean y_was_left_child =
1172 (y.getParent(index) != null)
1173 && (y == y.getParent(index).getLeft(index));
1174
1175
1176 if (x == y_old_parent)
1177 {
1178 x.setParent(y, index);
1179 if (y_was_left_child)
1180 {
1181 y.setLeft(x, index);
1182 y.setRight(x_old_right_child, index);
1183 }
1184 else
1185 {
1186 y.setRight(x, index);
1187 y.setLeft(x_old_left_child, index);
1188 }
1189 }
1190 else
1191 {
1192 x.setParent(y_old_parent, index);
1193 if (y_old_parent != null)
1194 {
1195 if (y_was_left_child)
1196 {
1197 y_old_parent.setLeft(x, index);
1198 }
1199 else
1200 {
1201 y_old_parent.setRight(x, index);
1202 }
1203 }
1204 y.setLeft(x_old_left_child, index);
1205 y.setRight(x_old_right_child, index);
1206 }
1207 if (y == x_old_parent)
1208 {
1209 y.setParent(x, index);
1210 if (x_was_left_child)
1211 {
1212 x.setLeft(y, index);
1213 x.setRight(y_old_right_child, index);
1214 }
1215 else
1216 {
1217 x.setRight(y, index);
1218 x.setLeft(y_old_left_child, index);
1219 }
1220 }
1221 else
1222 {
1223 y.setParent(x_old_parent, index);
1224 if (x_old_parent != null)
1225 {
1226 if (x_was_left_child)
1227 {
1228 x_old_parent.setLeft(y, index);
1229 }
1230 else
1231 {
1232 x_old_parent.setRight(y, index);
1233 }
1234 }
1235 x.setLeft(y_old_left_child, index);
1236 x.setRight(y_old_right_child, index);
1237 }
1238
1239
1240 if (x.getLeft(index) != null)
1241 {
1242 x.getLeft(index).setParent(x, index);
1243 }
1244 if (x.getRight(index) != null)
1245 {
1246 x.getRight(index).setParent(x, index);
1247 }
1248 if (y.getLeft(index) != null)
1249 {
1250 y.getLeft(index).setParent(y, index);
1251 }
1252 if (y.getRight(index) != null)
1253 {
1254 y.getRight(index).setParent(y, index);
1255 }
1256 x.swapColors(y, index);
1257
1258
1259 if (_root[ index ] == x)
1260 {
1261 _root[ index ] = y;
1262 }
1263 else if (_root[ index ] == y)
1264 {
1265 _root[ index ] = x;
1266 }
1267 }
1268
1269
1280
1281 private static void checkNonNullComparable(final Object o,
1282 final int index)
1283 {
1284 if (o == null)
1285 {
1286 throw new NullPointerException(_data_name[ index ]
1287 + " cannot be null");
1288 }
1289 if (!(o instanceof Comparable))
1290 {
1291 throw new ClassCastException(_data_name[ index ]
1292 + " must be Comparable");
1293 }
1294 }
1295
1296
1304
1305 private static void checkKey(final Object key)
1306 {
1307 checkNonNullComparable(key, _KEY);
1308 }
1309
1310
1318
1319 private static void checkValue(final Object value)
1320 {
1321 checkNonNullComparable(value, _VALUE);
1322 }
1323
1324
1334
1335 private static void checkKeyAndValue(final Object key, final Object value)
1336 {
1337 checkKey(key);
1338 checkValue(value);
1339 }
1340
1341
1346
1347 private void modify()
1348 {
1349 _modifications++;
1350 }
1351
1352
1355
1356 private void grow()
1357 {
1358 modify();
1359 _size++;
1360 }
1361
1362
1365
1366 private void shrink()
1367 {
1368 modify();
1369 _size--;
1370 }
1371
1372
1380
1381 private void insertValue(final Node newNode)
1382 throws IllegalArgumentException
1383 {
1384 Node node = _root[ _VALUE ];
1385
1386 while (true)
1387 {
1388 int cmp = compare(newNode.getData(_VALUE), node.getData(_VALUE));
1389
1390 if (cmp == 0)
1391 {
1392 throw new IllegalArgumentException(
1393 "Cannot store a duplicate value (\""
1394 + newNode.getData(_VALUE) + "\") in this Map");
1395 }
1396 else if (cmp < 0)
1397 {
1398 if (node.getLeft(_VALUE) != null)
1399 {
1400 node = node.getLeft(_VALUE);
1401 }
1402 else
1403 {
1404 node.setLeft(newNode, _VALUE);
1405 newNode.setParent(node, _VALUE);
1406 doRedBlackInsert(newNode, _VALUE);
1407 break;
1408 }
1409 }
1410 else
1411 {
1412 if (node.getRight(_VALUE) != null)
1413 {
1414 node = node.getRight(_VALUE);
1415 }
1416 else
1417 {
1418 node.setRight(newNode, _VALUE);
1419 newNode.setParent(node, _VALUE);
1420 doRedBlackInsert(newNode, _VALUE);
1421 break;
1422 }
1423 }
1424 }
1425 }
1426
1427
1428
1429
1436
1437 public int size()
1438 {
1439 return _size;
1440 }
1441
1442
1455
1456 public boolean containsKey(final Object key)
1457 throws ClassCastException, NullPointerException
1458 {
1459 checkKey(key);
1460 return lookup(( Comparable ) key, _KEY) != null;
1461 }
1462
1463
1472
1473 public boolean containsValue(final Object value)
1474 {
1475 checkValue(value);
1476 return lookup(( Comparable ) value, _VALUE) != null;
1477 }
1478
1479
1492
1493 public Object get(final Object key)
1494 throws ClassCastException, NullPointerException
1495 {
1496 return doGet(( Comparable ) key, _KEY);
1497 }
1498
1499
1519
1520 public Object put(final Object key, final Object value)
1521 throws ClassCastException, NullPointerException,
1522 IllegalArgumentException
1523 {
1524 checkKeyAndValue(key, value);
1525 Node node = _root[ _KEY ];
1526
1527 if (node == null)
1528 {
1529 Node root = new Node(( Comparable ) key, ( Comparable ) value);
1530
1531 _root[ _KEY ] = root;
1532 _root[ _VALUE ] = root;
1533 grow();
1534 }
1535 else
1536 {
1537 while (true)
1538 {
1539 int cmp = compare(( Comparable ) key, node.getData(_KEY));
1540
1541 if (cmp == 0)
1542 {
1543 throw new IllegalArgumentException(
1544 "Cannot store a duplicate key (\"" + key
1545 + "\") in this Map");
1546 }
1547 else if (cmp < 0)
1548 {
1549 if (node.getLeft(_KEY) != null)
1550 {
1551 node = node.getLeft(_KEY);
1552 }
1553 else
1554 {
1555 Node newNode = new Node(( Comparable ) key,
1556 ( Comparable ) value);
1557
1558 insertValue(newNode);
1559 node.setLeft(newNode, _KEY);
1560 newNode.setParent(node, _KEY);
1561 doRedBlackInsert(newNode, _KEY);
1562 grow();
1563 break;
1564 }
1565 }
1566 else
1567 {
1568 if (node.getRight(_KEY) != null)
1569 {
1570 node = node.getRight(_KEY);
1571 }
1572 else
1573 {
1574 Node newNode = new Node(( Comparable ) key,
1575 ( Comparable ) value);
1576
1577 insertValue(newNode);
1578 node.setRight(newNode, _KEY);
1579 newNode.setParent(node, _KEY);
1580 doRedBlackInsert(newNode, _KEY);
1581 grow();
1582 break;
1583 }
1584 }
1585 }
1586 }
1587 return null;
1588 }
1589
1590
1598
1599 public Object remove(final Object key)
1600 {
1601 return doRemove(( Comparable ) key, _KEY);
1602 }
1603
1604
1607
1608 public void clear()
1609 {
1610 modify();
1611 _size = 0;
1612 _root[ _KEY ] = null;
1613 _root[ _VALUE ] = null;
1614 }
1615
1616
1628
1629 public Set keySet()
1630 {
1631 if (_key_set[ _KEY ] == null)
1632 {
1633 _key_set[ _KEY ] = new AbstractSet()
1634 {
1635 public Iterator iterator()
1636 {
1637 return new BinaryTreeIterator(_KEY)
1638 {
1639 protected Object doGetNext()
1640 {
1641 return _last_returned_node.getData(_KEY);
1642 }
1643 };
1644 }
1645
1646 public int size()
1647 {
1648 return BinaryTree.this.size();
1649 }
1650
1651 public boolean contains(Object o)
1652 {
1653 return containsKey(o);
1654 }
1655
1656 public boolean remove(Object o)
1657 {
1658 int old_size = _size;
1659
1660 BinaryTree.this.remove(o);
1661 return _size != old_size;
1662 }
1663
1664 public void clear()
1665 {
1666 BinaryTree.this.clear();
1667 }
1668 };
1669 }
1670 return _key_set[ _KEY ];
1671 }
1672
1673
1686
1687 public Collection values()
1688 {
1689 if (_value_collection[ _KEY ] == null)
1690 {
1691 _value_collection[ _KEY ] = new AbstractCollection()
1692 {
1693 public Iterator iterator()
1694 {
1695 return new BinaryTreeIterator(_KEY)
1696 {
1697 protected Object doGetNext()
1698 {
1699 return _last_returned_node.getData(_VALUE);
1700 }
1701 };
1702 }
1703
1704 public int size()
1705 {
1706 return BinaryTree.this.size();
1707 }
1708
1709 public boolean contains(Object o)
1710 {
1711 return containsValue(o);
1712 }
1713
1714 public boolean remove(Object o)
1715 {
1716 int old_size = _size;
1717
1718 removeValue(o);
1719 return _size != old_size;
1720 }
1721
1722 public boolean removeAll(Collection c)
1723 {
1724 boolean modified = false;
1725 Iterator iter = c.iterator();
1726
1727 while (iter.hasNext())
1728 {
1729 if (removeValue(iter.next()) != null)
1730 {
1731 modified = true;
1732 }
1733 }
1734 return modified;
1735 }
1736
1737 public void clear()
1738 {
1739 BinaryTree.this.clear();
1740 }
1741 };
1742 }
1743 return _value_collection[ _KEY ];
1744 }
1745
1746
1759
1760 public Set entrySet()
1761 {
1762 if (_entry_set[ _KEY ] == null)
1763 {
1764 _entry_set[ _KEY ] = new AbstractSet()
1765 {
1766 public Iterator iterator()
1767 {
1768 return new BinaryTreeIterator(_KEY)
1769 {
1770 protected Object doGetNext()
1771 {
1772 return _last_returned_node;
1773 }
1774 };
1775 }
1776
1777 public boolean contains(Object o)
1778 {
1779 if (!(o instanceof Map.Entry))
1780 {
1781 return false;
1782 }
1783 Map.Entry entry = ( Map.Entry ) o;
1784 Object value = entry.getValue();
1785 Node node = lookup(( Comparable ) entry.getKey(),
1786 _KEY);
1787
1788 return (node != null)
1789 && node.getData(_VALUE).equals(value);
1790 }
1791
1792 public boolean remove(Object o)
1793 {
1794 if (!(o instanceof Map.Entry))
1795 {
1796 return false;
1797 }
1798 Map.Entry entry = ( Map.Entry ) o;
1799 Object value = entry.getValue();
1800 Node node = lookup(( Comparable ) entry.getKey(),
1801 _KEY);
1802
1803 if ((node != null) && node.getData(_VALUE).equals(value))
1804 {
1805 doRedBlackDelete(node);
1806 return true;
1807 }
1808 return false;
1809 }
1810
1811 public int size()
1812 {
1813 return BinaryTree.this.size();
1814 }
1815
1816 public void clear()
1817 {
1818 BinaryTree.this.clear();
1819 }
1820 };
1821 }
1822 return _entry_set[ _KEY ];
1823 }
1824
1825
1826 private abstract class BinaryTreeIterator
1827 implements Iterator
1828 {
1829 private int _expected_modifications;
1830 protected Node _last_returned_node;
1831 private Node _next_node;
1832 private int _type;
1833
1834
1839
1840 BinaryTreeIterator(final int type)
1841 {
1842 _type = type;
1843 _expected_modifications = BinaryTree.this._modifications;
1844 _last_returned_node = null;
1845 _next_node = leastNode(_root[ _type ], _type);
1846 }
1847
1848
1852
1853 protected abstract Object doGetNext();
1854
1855
1856
1857
1860
1861 public final boolean hasNext()
1862 {
1863 return _next_node != null;
1864 }
1865
1866
1877
1878 public final Object next()
1879 throws NoSuchElementException, ConcurrentModificationException
1880 {
1881 if (_next_node == null)
1882 {
1883 throw new NoSuchElementException();
1884 }
1885 if (_modifications != _expected_modifications)
1886 {
1887 throw new ConcurrentModificationException();
1888 }
1889 _last_returned_node = _next_node;
1890 _next_node = nextGreater(_next_node, _type);
1891 return doGetNext();
1892 }
1893
1894
1913
1914 public final void remove()
1915 throws IllegalStateException, ConcurrentModificationException
1916 {
1917 if (_last_returned_node == null)
1918 {
1919 throw new IllegalStateException();
1920 }
1921 if (_modifications != _expected_modifications)
1922 {
1923 throw new ConcurrentModificationException();
1924 }
1925 doRedBlackDelete(_last_returned_node);
1926 _expected_modifications++;
1927 _last_returned_node = null;
1928 }
1929
1930
1931 }
1932
1933
1934 private static final class Node
1935 implements Map.Entry
1936 {
1937 private Comparable[] _data;
1938 private Node[] _left;
1939 private Node[] _right;
1940 private Node[] _parent;
1941 private boolean[] _black;
1942 private int _hashcode;
1943 private boolean _calculated_hashcode;
1944
1945
1952
1953 Node(final Comparable key, final Comparable value)
1954 {
1955 _data = new Comparable[]
1956 {
1957 key, value
1958 };
1959 _left = new Node[]
1960 {
1961 null, null
1962 };
1963 _right = new Node[]
1964 {
1965 null, null
1966 };
1967 _parent = new Node[]
1968 {
1969 null, null
1970 };
1971 _black = new boolean[]
1972 {
1973 true, true
1974 };
1975 _calculated_hashcode = false;
1976 }
1977
1978
1985
1986 private Comparable getData(final int index)
1987 {
1988 return _data[ index ];
1989 }
1990
1991
1997
1998 private void setLeft(final Node node, final int index)
1999 {
2000 _left[ index ] = node;
2001 }
2002
2003
2010
2011 private Node getLeft(final int index)
2012 {
2013 return _left[ index ];
2014 }
2015
2016
2022
2023 private void setRight(final Node node, final int index)
2024 {
2025 _right[ index ] = node;
2026 }
2027
2028
2035
2036 private Node getRight(final int index)
2037 {
2038 return _right[ index ];
2039 }
2040
2041
2047
2048 private void setParent(final Node node, final int index)
2049 {
2050 _parent[ index ] = node;
2051 }
2052
2053
2060
2061 private Node getParent(final int index)
2062 {
2063 return _parent[ index ];
2064 }
2065
2066
2072
2073 private void swapColors(final Node node, final int index)
2074 {
2075
2076
2077 _black[ index ] ^= node._black[ index ];
2078 node._black[ index ] ^= _black[ index ];
2079 _black[ index ] ^= node._black[ index ];
2080 }
2081
2082
2089
2090 private boolean isBlack(final int index)
2091 {
2092 return _black[ index ];
2093 }
2094
2095
2102
2103 private boolean isRed(final int index)
2104 {
2105 return !_black[ index ];
2106 }
2107
2108
2113
2114 private void setBlack(final int index)
2115 {
2116 _black[ index ] = true;
2117 }
2118
2119
2124
2125 private void setRed(final int index)
2126 {
2127 _black[ index ] = false;
2128 }
2129
2130
2136
2137 private void copyColor(final Node node, final int index)
2138 {
2139 _black[ index ] = node._black[ index ];
2140 }
2141
2142
2143
2144
2147
2148 public Object getKey()
2149 {
2150 return _data[ _KEY ];
2151 }
2152
2153
2156
2157 public Object getValue()
2158 {
2159 return _data[ _VALUE ];
2160 }
2161
2162
2172
2173 public Object setValue(Object ignored)
2174 throws UnsupportedOperationException
2175 {
2176 throw new UnsupportedOperationException(
2177 "Map.Entry.setValue is not supported");
2178 }
2179
2180
2190
2191 public boolean equals(Object o)
2192 {
2193 if (this == o)
2194 {
2195 return true;
2196 }
2197 if (!(o instanceof Map.Entry))
2198 {
2199 return false;
2200 }
2201 Map.Entry e = ( Map.Entry ) o;
2202
2203 return _data[ _KEY ].equals(e.getKey())
2204 && _data[ _VALUE ].equals(e.getValue());
2205 }
2206
2207
2210
2211 public int hashCode()
2212 {
2213 if (!_calculated_hashcode)
2214 {
2215 _hashcode = _data[ _KEY ].hashCode()
2216 ^ _data[ _VALUE ].hashCode();
2217 _calculated_hashcode = true;
2218 }
2219 return _hashcode;
2220 }
2221
2222
2223 }
2224 }
2225
2226