1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.collections.bidimap;
18
19 import java.util.AbstractSet;
20 import java.util.Collection;
21 import java.util.ConcurrentModificationException;
22 import java.util.Iterator;
23 import java.util.Map;
24 import java.util.NoSuchElementException;
25 import java.util.Set;
26
27 import org.apache.commons.collections.BidiMap;
28 import org.apache.commons.collections.KeyValue;
29 import org.apache.commons.collections.MapIterator;
30 import org.apache.commons.collections.OrderedBidiMap;
31 import org.apache.commons.collections.OrderedIterator;
32 import org.apache.commons.collections.OrderedMapIterator;
33 import org.apache.commons.collections.iterators.EmptyOrderedMapIterator;
34 import org.apache.commons.collections.keyvalue.UnmodifiableMapEntry;
35
36 /**
37 * Red-Black tree-based implementation of BidiMap where all objects added
38 * implement the <code>Comparable</code> interface.
39 * <p>
40 * This class guarantees that the map will be in both ascending key order
41 * and ascending value order, sorted according to the natural order for
42 * the key's and value's classes.
43 * <p>
44 * This Map is intended for applications that need to be able to look
45 * up a key-value pairing by either key or value, and need to do so
46 * with equal efficiency.
47 * <p>
48 * While that goal could be accomplished by taking a pair of TreeMaps
49 * and redirecting requests to the appropriate TreeMap (e.g.,
50 * containsKey would be directed to the TreeMap that maps values to
51 * keys, containsValue would be directed to the TreeMap that maps keys
52 * to values), there are problems with that implementation.
53 * If the data contained in the TreeMaps is large, the cost of redundant
54 * storage becomes significant. The {@link DualTreeBidiMap} and
55 * {@link DualHashBidiMap} implementations use this approach.
56 * <p>
57 * This solution keeps minimizes the data storage by holding data only once.
58 * The red-black algorithm is based on java util TreeMap, but has been modified
59 * to simultaneously map a tree node by key and by value. This doubles the
60 * cost of put operations (but so does using two TreeMaps), and nearly doubles
61 * the cost of remove operations (there is a savings in that the lookup of the
62 * node to be removed only has to be performed once). And since only one node
63 * contains the key and value, storage is significantly less than that
64 * required by two TreeMaps.
65 * <p>
66 * The Map.Entry instances returned by the appropriate methods will
67 * not allow setValue() and will throw an
68 * UnsupportedOperationException on attempts to call that method.
69 *
70 * @since Commons Collections 3.0 (previously DoubleOrderedMap v2.0)
71 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
72 *
73 * @author Marc Johnson
74 * @author Stephen Colebourne
75 */
76 public class TreeBidiMap implements OrderedBidiMap {
77
78 private static final int KEY = 0;
79 private static final int VALUE = 1;
80 private static final int MAPENTRY = 2;
81 private static final int INVERSEMAPENTRY = 3;
82 private static final int SUM_OF_INDICES = KEY + VALUE;
83 private static final int FIRST_INDEX = 0;
84 private static final int NUMBER_OF_INDICES = 2;
85 private static final String[] dataName = new String[] { "key", "value" };
86
87 private Node[] rootNode = new Node[2];
88 private int nodeCount = 0;
89 private int modifications = 0;
90 private Set keySet;
91 private Set valuesSet;
92 private Set entrySet;
93 private TreeBidiMap.Inverse inverse = null;
94
95 //-----------------------------------------------------------------------
96 /**
97 * Constructs a new empty TreeBidiMap.
98 */
99 public TreeBidiMap() {
100 super();
101 }
102
103 /**
104 * Constructs a new TreeBidiMap by copying an existing Map.
105 *
106 * @param map the map to copy
107 * @throws ClassCastException if the keys/values in the map are
108 * not Comparable or are not mutually comparable
109 * @throws NullPointerException if any key or value in the map is null
110 */
111 public TreeBidiMap(final Map map) {
112 super();
113 putAll(map);
114 }
115
116 //-----------------------------------------------------------------------
117 /**
118 * Returns the number of key-value mappings in this map.
119 *
120 * @return the number of key-value mappings in this map
121 */
122 public int size() {
123 return nodeCount;
124 }
125
126 /**
127 * Checks whether the map is empty or not.
128 *
129 * @return true if the map is empty
130 */
131 public boolean isEmpty() {
132 return (nodeCount == 0);
133 }
134
135 /**
136 * Checks whether this map contains the a mapping for the specified key.
137 * <p>
138 * The key must implement <code>Comparable</code>.
139 *
140 * @param key key whose presence in this map is to be tested
141 * @return true if this map contains a mapping for the specified key
142 * @throws ClassCastException if the key is of an inappropriate type
143 * @throws NullPointerException if the key is null
144 */
145 public boolean containsKey(final Object key) {
146 checkKey(key);
147 return (lookup((Comparable) key, KEY) != null);
148 }
149
150 /**
151 * Checks whether this map contains the a mapping for the specified value.
152 * <p>
153 * The value must implement <code>Comparable</code>.
154 *
155 * @param value value whose presence in this map is to be tested
156 * @return true if this map contains a mapping for the specified value
157 * @throws ClassCastException if the value is of an inappropriate type
158 * @throws NullPointerException if the value is null
159 */
160 public boolean containsValue(final Object value) {
161 checkValue(value);
162 return (lookup((Comparable) value, VALUE) != null);
163 }
164
165 /**
166 * Gets the value to which this map maps the specified key.
167 * Returns null if the map contains no mapping for this key.
168 * <p>
169 * The key must implement <code>Comparable</code>.
170 *
171 * @param key key whose associated value is to be returned
172 * @return the value to which this map maps the specified key,
173 * or null if the map contains no mapping for this key
174 * @throws ClassCastException if the key is of an inappropriate type
175 * @throws NullPointerException if the key is null
176 */
177 public Object get(final Object key) {
178 return doGet((Comparable) key, KEY);
179 }
180
181 /**
182 * Puts the key-value pair into the map, replacing any previous pair.
183 * <p>
184 * When adding a key-value pair, the value may already exist in the map
185 * against a different key. That mapping is removed, to ensure that the
186 * value only occurs once in the inverse map.
187 * <pre>
188 * BidiMap map1 = new TreeBidiMap();
189 * map.put("A","B"); // contains A mapped to B, as per Map
190 * map.put("A","C"); // contains A mapped to C, as per Map
191 *
192 * BidiMap map2 = new TreeBidiMap();
193 * map.put("A","B"); // contains A mapped to B, as per Map
194 * map.put("C","B"); // contains C mapped to B, key A is removed
195 * </pre>
196 * <p>
197 * Both key and value must implement <code>Comparable</code>.
198 *
199 * @param key key with which the specified value is to be associated
200 * @param value value to be associated with the specified key
201 * @return the previous value for the key
202 * @throws ClassCastException if the key is of an inappropriate type
203 * @throws NullPointerException if the key is null
204 */
205 public Object put(final Object key, final Object value) {
206 return doPut((Comparable) key, (Comparable) value, KEY);
207 }
208
209 /**
210 * Puts all the mappings from the specified map into this map.
211 * <p>
212 * All keys and values must implement <code>Comparable</code>.
213 *
214 * @param map the map to copy from
215 */
216 public void putAll(Map map) {
217 Iterator it = map.entrySet().iterator();
218 while (it.hasNext()) {
219 Map.Entry entry = (Map.Entry) it.next();
220 put(entry.getKey(), entry.getValue());
221 }
222 }
223
224 /**
225 * Removes the mapping for this key from this map if present.
226 * <p>
227 * The key must implement <code>Comparable</code>.
228 *
229 * @param key key whose mapping is to be removed from the map.
230 * @return previous value associated with specified key,
231 * or null if there was no mapping for key.
232 * @throws ClassCastException if the key is of an inappropriate type
233 * @throws NullPointerException if the key is null
234 */
235 public Object remove(final Object key) {
236 return doRemove((Comparable) key, KEY);
237 }
238
239 /**
240 * Removes all mappings from this map.
241 */
242 public void clear() {
243 modify();
244
245 nodeCount = 0;
246 rootNode[KEY] = null;
247 rootNode[VALUE] = null;
248 }
249
250 //-----------------------------------------------------------------------
251 /**
252 * Returns the key to which this map maps the specified value.
253 * Returns null if the map contains no mapping for this value.
254 * <p>
255 * The value must implement <code>Comparable</code>.
256 *
257 * @param value value whose associated key is to be returned.
258 * @return the key to which this map maps the specified value,
259 * or null if the map contains no mapping for this value.
260 * @throws ClassCastException if the value is of an inappropriate type
261 * @throws NullPointerException if the value is null
262 */
263 public Object getKey(final Object value) {
264 return doGet((Comparable) value, VALUE);
265 }
266
267 /**
268 * Removes the mapping for this value from this map if present.
269 * <p>
270 * The value must implement <code>Comparable</code>.
271 *
272 * @param value value whose mapping is to be removed from the map
273 * @return previous key associated with specified value,
274 * or null if there was no mapping for value.
275 * @throws ClassCastException if the value is of an inappropriate type
276 * @throws NullPointerException if the value is null
277 */
278 public Object removeValue(final Object value) {
279 return doRemove((Comparable) value, VALUE);
280 }
281
282 //-----------------------------------------------------------------------
283 /**
284 * Gets the first (lowest) key currently in this map.
285 *
286 * @return the first (lowest) key currently in this sorted map
287 * @throws NoSuchElementException if this map is empty
288 */
289 public Object firstKey() {
290 if (nodeCount == 0) {
291 throw new NoSuchElementException("Map is empty");
292 }
293 return leastNode(rootNode[KEY], KEY).getKey();
294 }
295
296 /**
297 * Gets the last (highest) key currently in this map.
298 *
299 * @return the last (highest) key currently in this sorted map
300 * @throws NoSuchElementException if this map is empty
301 */
302 public Object lastKey() {
303 if (nodeCount == 0) {
304 throw new NoSuchElementException("Map is empty");
305 }
306 return greatestNode(rootNode[KEY], KEY).getKey();
307 }
308
309 /**
310 * Gets the next key after the one specified.
311 * <p>
312 * The key must implement <code>Comparable</code>.
313 *
314 * @param key the key to search for next from
315 * @return the next key, null if no match or at end
316 */
317 public Object nextKey(Object key) {
318 checkKey(key);
319 Node node = nextGreater(lookup((Comparable) key, KEY), KEY);
320 return (node == null ? null : node.getKey());
321 }
322
323 /**
324 * Gets the previous key before the one specified.
325 * <p>
326 * The key must implement <code>Comparable</code>.
327 *
328 * @param key the key to search for previous from
329 * @return the previous key, null if no match or at start
330 */
331 public Object previousKey(Object key) {
332 checkKey(key);
333 Node node = nextSmaller(lookup((Comparable) key, KEY), KEY);
334 return (node == null ? null : node.getKey());
335 }
336
337 //-----------------------------------------------------------------------
338 /**
339 * Returns a set view of the keys contained in this map in key order.
340 * <p>
341 * The set is backed by the map, so changes to the map are reflected in
342 * the set, and vice-versa. If the map is modified while an iteration over
343 * the set is in progress, the results of the iteration are undefined.
344 * <p>
345 * The set supports element removal, which removes the corresponding mapping
346 * from the map. It does not support the add or addAll operations.
347 *
348 * @return a set view of the keys contained in this map.
349 */
350 public Set keySet() {
351 if (keySet == null) {
352 keySet = new View(this, KEY, KEY);
353 }
354 return keySet;
355 }
356
357 //-----------------------------------------------------------------------
358 /**
359 * Returns a set view of the values contained in this map in key order.
360 * The returned object can be cast to a Set.
361 * <p>
362 * The set is backed by the map, so changes to the map are reflected in
363 * the set, and vice-versa. If the map is modified while an iteration over
364 * the set is in progress, the results of the iteration are undefined.
365 * <p>
366 * The set supports element removal, which removes the corresponding mapping
367 * from the map. It does not support the add or addAll operations.
368 *
369 * @return a set view of the values contained in this map.
370 */
371 public Collection values() {
372 if (valuesSet == null) {
373 valuesSet = new View(this, KEY, VALUE);
374 }
375 return valuesSet;
376 }
377
378 //-----------------------------------------------------------------------
379 /**
380 * Returns a set view of the entries contained in this map in key order.
381 * For simple iteration through the map, the MapIterator is quicker.
382 * <p>
383 * The set is backed by the map, so changes to the map are reflected in
384 * the set, and vice-versa. If the map is modified while an iteration over
385 * the set is in progress, the results of the iteration are undefined.
386 * <p>
387 * The set supports element removal, which removes the corresponding mapping
388 * from the map. It does not support the add or addAll operations.
389 * The returned MapEntry objects do not support setValue.
390 *
391 * @return a set view of the values contained in this map.
392 */
393 public Set entrySet() {
394 if (entrySet == null) {
395 return new EntryView(this, KEY, MAPENTRY);
396 }
397 return entrySet;
398 }
399
400 //-----------------------------------------------------------------------
401 /**
402 * Gets an iterator over the map entries.
403 * <p>
404 * For this map, this iterator is the fastest way to iterate over the entries.
405 *
406 * @return an iterator
407 */
408 public MapIterator mapIterator() {
409 if (isEmpty()) {
410 return EmptyOrderedMapIterator.INSTANCE;
411 }
412 return new ViewMapIterator(this, KEY);
413 }
414
415 /**
416 * Gets an ordered iterator over the map entries.
417 * <p>
418 * This iterator allows both forward and reverse iteration over the entries.
419 *
420 * @return an iterator
421 */
422 public OrderedMapIterator orderedMapIterator() {
423 if (isEmpty()) {
424 return EmptyOrderedMapIterator.INSTANCE;
425 }
426 return new ViewMapIterator(this, KEY);
427 }
428
429 //-----------------------------------------------------------------------
430 /**
431 * Gets the inverse map for comparison.
432 *
433 * @return the inverse map
434 */
435 public BidiMap inverseBidiMap() {
436 return inverseOrderedBidiMap();
437 }
438
439 /**
440 * Gets the inverse map for comparison.
441 *
442 * @return the inverse map
443 */
444 public OrderedBidiMap inverseOrderedBidiMap() {
445 if (inverse == null) {
446 inverse = new Inverse(this);
447 }
448 return inverse;
449 }
450
451 //-----------------------------------------------------------------------
452 /**
453 * Compares for equals as per the API.
454 *
455 * @param obj the object to compare to
456 * @return true if equal
457 */
458 public boolean equals(Object obj) {
459 return this.doEquals(obj, KEY);
460 }
461
462 /**
463 * Gets the hash code value for this map as per the API.
464 *
465 * @return the hash code value for this map
466 */
467 public int hashCode() {
468 return this.doHashCode(KEY);
469 }
470
471 /**
472 * Returns a string version of this Map in standard format.
473 *
474 * @return a standard format string version of the map
475 */
476 public String toString() {
477 return this.doToString(KEY);
478 }
479
480 //-----------------------------------------------------------------------
481 /**
482 * Common get logic, used to get by key or get by value
483 *
484 * @param obj the key or value that we're looking for
485 * @param index the KEY or VALUE int
486 * @return the key (if the value was mapped) or the value (if the
487 * key was mapped); null if we couldn't find the specified
488 * object
489 */
490 private Object doGet(final Comparable obj, final int index) {
491 checkNonNullComparable(obj, index);
492 Node node = lookup(obj, index);
493 return ((node == null) ? null : node.getData(oppositeIndex(index)));
494 }
495
496 /**
497 * Common put logic, differing only in the return value.
498 *
499 * @param key the key, always the main map key
500 * @param value the value, always the main map value
501 * @param index the KEY or VALUE int, for the return value only
502 * @return the previously mapped value
503 */
504 private Object doPut(final Comparable key, final Comparable value, final int index) {
505 checkKeyAndValue(key, value);
506
507 // store previous and remove previous mappings
508 Object prev = (index == KEY ? doGet(key, KEY) : doGet(value, VALUE));
509 doRemove(key, KEY);
510 doRemove(value, VALUE);
511
512 Node node = rootNode[KEY];
513 if (node == null) {
514 // map is empty
515 Node root = new Node(key, value);
516 rootNode[KEY] = root;
517 rootNode[VALUE] = root;
518 grow();
519
520 } else {
521 // add new mapping
522 while (true) {
523 int cmp = compare(key, node.getData(KEY));
524
525 if (cmp == 0) {
526 // shouldn't happen
527 throw new IllegalArgumentException("Cannot store a duplicate key (\"" + key + "\") in this Map");
528 } else if (cmp < 0) {
529 if (node.getLeft(KEY) != null) {
530 node = node.getLeft(KEY);
531 } else {
532 Node newNode = new Node(key, value);
533
534 insertValue(newNode);
535 node.setLeft(newNode, KEY);
536 newNode.setParent(node, KEY);
537 doRedBlackInsert(newNode, KEY);
538 grow();
539
540 break;
541 }
542 } else { // cmp > 0
543 if (node.getRight(KEY) != null) {
544 node = node.getRight(KEY);
545 } else {
546 Node newNode = new Node(key, value);
547
548 insertValue(newNode);
549 node.setRight(newNode, KEY);
550 newNode.setParent(node, KEY);
551 doRedBlackInsert(newNode, KEY);
552 grow();
553
554 break;
555 }
556 }
557 }
558 }
559 return prev;
560 }
561
562 /**
563 * Remove by object (remove by key or remove by value)
564 *
565 * @param o the key, or value, that we're looking for
566 * @param index the KEY or VALUE int
567 *
568 * @return the key, if remove by value, or the value, if remove by
569 * key. null if the specified key or value could not be
570 * found
571 */
572 private Object doRemove(final Comparable o, final int index) {
573 Node node = lookup(o, index);
574 Object rval = null;
575 if (node != null) {
576 rval = node.getData(oppositeIndex(index));
577 doRedBlackDelete(node);
578 }
579 return rval;
580 }
581
582 /**
583 * do the actual lookup of a piece of data
584 *
585 * @param data the key or value to be looked up
586 * @param index the KEY or VALUE int
587 * @return the desired Node, or null if there is no mapping of the
588 * specified data
589 */
590 private Node lookup(final Comparable data, final int index) {
591 Node rval = null;
592 Node node = rootNode[index];
593
594 while (node != null) {
595 int cmp = compare(data, node.getData(index));
596 if (cmp == 0) {
597 rval = node;
598 break;
599 } else {
600 node = (cmp < 0) ? node.getLeft(index) : node.getRight(index);
601 }
602 }
603
604 return rval;
605 }
606
607 /**
608 * get the next larger node from the specified node
609 *
610 * @param node the node to be searched from
611 * @param index the KEY or VALUE int
612 * @return the specified node
613 */
614 private Node nextGreater(final Node node, final int index) {
615 Node rval = null;
616 if (node == null) {
617 rval = null;
618 } else if (node.getRight(index) != null) {
619 // everything to the node's right is larger. The least of
620 // the right node's descendants is the next larger node
621 rval = leastNode(node.getRight(index), index);
622 } else {
623 // traverse up our ancestry until we find an ancestor that
624 // is null or one whose left child is our ancestor. If we
625 // find a null, then this node IS the largest node in the
626 // tree, and there is no greater node. Otherwise, we are
627 // the largest node in the subtree on that ancestor's left
628 // ... and that ancestor is the next greatest node
629 Node parent = node.getParent(index);
630 Node child = node;
631
632 while ((parent != null) && (child == parent.getRight(index))) {
633 child = parent;
634 parent = parent.getParent(index);
635 }
636 rval = parent;
637 }
638 return rval;
639 }
640
641 /**
642 * get the next larger node from the specified node
643 *
644 * @param node the node to be searched from
645 * @param index the KEY or VALUE int
646 * @return the specified node
647 */
648 private Node nextSmaller(final Node node, final int index) {
649 Node rval = null;
650 if (node == null) {
651 rval = null;
652 } else if (node.getLeft(index) != null) {
653 // everything to the node's left is smaller. The greatest of
654 // the left node's descendants is the next smaller node
655 rval = greatestNode(node.getLeft(index), index);
656 } else {
657 // traverse up our ancestry until we find an ancestor that
658 // is null or one whose right child is our ancestor. If we
659 // find a null, then this node IS the largest node in the
660 // tree, and there is no greater node. Otherwise, we are
661 // the largest node in the subtree on that ancestor's right
662 // ... and that ancestor is the next greatest node
663 Node parent = node.getParent(index);
664 Node child = node;
665
666 while ((parent != null) && (child == parent.getLeft(index))) {
667 child = parent;
668 parent = parent.getParent(index);
669 }
670 rval = parent;
671 }
672 return rval;
673 }
674
675 //-----------------------------------------------------------------------
676 /**
677 * Get the opposite index of the specified index
678 *
679 * @param index the KEY or VALUE int
680 * @return VALUE (if KEY was specified), else KEY
681 */
682 private static int oppositeIndex(final int index) {
683 // old trick ... to find the opposite of a value, m or n,
684 // subtract the value from the sum of the two possible
685 // values. (m + n) - m = n; (m + n) - n = m
686 return SUM_OF_INDICES - index;
687 }
688
689 /**
690 * Compare two objects
691 *
692 * @param o1 the first object
693 * @param o2 the second object
694 *
695 * @return negative value if o1 < o2; 0 if o1 == o2; positive
696 * value if o1 > o2
697 */
698 private static int compare(final Comparable o1, final Comparable o2) {
699 return o1.compareTo(o2);
700 }
701
702 /**
703 * Find the least node from a given node.
704 *
705 * @param node the node from which we will start searching
706 * @param index the KEY or VALUE int
707 * @return the smallest node, from the specified node, in the
708 * specified mapping
709 */
710 private static Node leastNode(final Node node, final int index) {
711 Node rval = node;
712 if (rval != null) {
713 while (rval.getLeft(index) != null) {
714 rval = rval.getLeft(index);
715 }
716 }
717 return rval;
718 }
719
720 /**
721 * Find the greatest node from a given node.
722 *
723 * @param node the node from which we will start searching
724 * @param index the KEY or VALUE int
725 * @return the greatest node, from the specified node
726 */
727 private static Node greatestNode(final Node node, final int index) {
728 Node rval = node;
729 if (rval != null) {
730 while (rval.getRight(index) != null) {
731 rval = rval.getRight(index);
732 }
733 }
734 return rval;
735 }
736
737 /**
738 * copy the color from one node to another, dealing with the fact
739 * that one or both nodes may, in fact, be null
740 *
741 * @param from the node whose color we're copying; may be null
742 * @param to the node whose color we're changing; may be null
743 * @param index the KEY or VALUE int
744 */
745 private static void copyColor(final Node from, final Node to, final int index) {
746 if (to != null) {
747 if (from == null) {
748 // by default, make it black
749 to.setBlack(index);
750 } else {
751 to.copyColor(from, index);
752 }
753 }
754 }
755
756 /**
757 * is the specified node red? if the node does not exist, no, it's
758 * black, thank you
759 *
760 * @param node the node (may be null) in question
761 * @param index the KEY or VALUE int
762 */
763 private static boolean isRed(final Node node, final int index) {
764 return ((node == null) ? false : node.isRed(index));
765 }
766
767 /**
768 * is the specified black red? if the node does not exist, sure,
769 * it's black, thank you
770 *
771 * @param node the node (may be null) in question
772 * @param index the KEY or VALUE int
773 */
774 private static boolean isBlack(final Node node, final int index) {
775 return ((node == null) ? true : node.isBlack(index));
776 }
777
778 /**
779 * force a node (if it exists) red
780 *
781 * @param node the node (may be null) in question
782 * @param index the KEY or VALUE int
783 */
784 private static void makeRed(final Node node, final int index) {
785 if (node != null) {
786 node.setRed(index);
787 }
788 }
789
790 /**
791 * force a node (if it exists) black
792 *
793 * @param node the node (may be null) in question
794 * @param index the KEY or VALUE int
795 */
796 private static void makeBlack(final Node node, final int index) {
797 if (node != null) {
798 node.setBlack(index);
799 }
800 }
801
802 /**
803 * get a node's grandparent. mind you, the node, its parent, or
804 * its grandparent may not exist. no problem
805 *
806 * @param node the node (may be null) in question
807 * @param index the KEY or VALUE int
808 */
809 private static Node getGrandParent(final Node node, final int index) {
810 return getParent(getParent(node, index), index);
811 }
812
813 /**
814 * get a node's parent. mind you, the node, or its parent, may not
815 * exist. no problem
816 *
817 * @param node the node (may be null) in question
818 * @param index the KEY or VALUE int
819 */
820 private static Node getParent(final Node node, final int index) {
821 return ((node == null) ? null : node.getParent(index));
822 }
823
824 /**
825 * get a node's right child. mind you, the node may not exist. no
826 * problem
827 *
828 * @param node the node (may be null) in question
829 * @param index the KEY or VALUE int
830 */
831 private static Node getRightChild(final Node node, final int index) {
832 return (node == null) ? null : node.getRight(index);
833 }
834
835 /**
836 * get a node's left child. mind you, the node may not exist. no
837 * problem
838 *
839 * @param node the node (may be null) in question
840 * @param index the KEY or VALUE int
841 */
842 private static Node getLeftChild(final Node node, final int index) {
843 return (node == null) ? null : node.getLeft(index);
844 }
845
846 /**
847 * is this node its parent's left child? mind you, the node, or
848 * its parent, may not exist. no problem. if the node doesn't
849 * exist ... it's its non-existent parent's left child. If the
850 * node does exist but has no parent ... no, we're not the
851 * non-existent parent's left child. Otherwise (both the specified
852 * node AND its parent exist), check.
853 *
854 * @param node the node (may be null) in question
855 * @param index the KEY or VALUE int
856 */
857 private static boolean isLeftChild(final Node node, final int index) {
858 return (node == null)
859 ? true
860 : ((node.getParent(index) == null) ?
861 false : (node == node.getParent(index).getLeft(index)));
862 }
863
864 /**
865 * is this node its parent's right child? mind you, the node, or
866 * its parent, may not exist. no problem. if the node doesn't
867 * exist ... it's its non-existent parent's right child. If the
868 * node does exist but has no parent ... no, we're not the
869 * non-existent parent's right child. Otherwise (both the
870 * specified node AND its parent exist), check.
871 *
872 * @param node the node (may be null) in question
873 * @param index the KEY or VALUE int
874 */
875 private static boolean isRightChild(final Node node, final int index) {
876 return (node == null)
877 ? true
878 : ((node.getParent(index) == null) ?
879 false : (node == node.getParent(index).getRight(index)));
880 }
881
882 /**
883 * do a rotate left. standard fare in the world of balanced trees
884 *
885 * @param node the node to be rotated
886 * @param index the KEY or VALUE int
887 */
888 private void rotateLeft(final Node node, final int index) {
889 Node rightChild = node.getRight(index);
890 node.setRight(rightChild.getLeft(index), index);
891
892 if (rightChild.getLeft(index) != null) {
893 rightChild.getLeft(index).setParent(node, index);
894 }
895 rightChild.setParent(node.getParent(index), index);
896
897 if (node.getParent(index) == null) {
898 // node was the root ... now its right child is the root
899 rootNode[index] = rightChild;
900 } else if (node.getParent(index).getLeft(index) == node) {
901 node.getParent(index).setLeft(rightChild, index);
902 } else {
903 node.getParent(index).setRight(rightChild, index);
904 }
905
906 rightChild.setLeft(node, index);
907 node.setParent(rightChild, index);
908 }
909
910 /**
911 * do a rotate right. standard fare in the world of balanced trees
912 *
913 * @param node the node to be rotated
914 * @param index the KEY or VALUE int
915 */
916 private void rotateRight(final Node node, final int index) {
917 Node leftChild = node.getLeft(index);
918 node.setLeft(leftChild.getRight(index), index);
919 if (leftChild.getRight(index) != null) {
920 leftChild.getRight(index).setParent(node, index);
921 }
922 leftChild.setParent(node.getParent(index), index);
923
924 if (node.getParent(index) == null) {
925 // node was the root ... now its left child is the root
926 rootNode[index] = leftChild;
927 } else if (node.getParent(index).getRight(index) == node) {
928 node.getParent(index).setRight(leftChild, index);
929 } else {
930 node.getParent(index).setLeft(leftChild, index);
931 }
932
933 leftChild.setRight(node, index);
934 node.setParent(leftChild, index);
935 }
936
937 /**
938 * complicated red-black insert stuff. Based on Sun's TreeMap
939 * implementation, though it's barely recognizable any more
940 *
941 * @param insertedNode the node to be inserted
942 * @param index the KEY or VALUE int
943 */
944 private void doRedBlackInsert(final Node insertedNode, final int index) {
945 Node currentNode = insertedNode;
946 makeRed(currentNode, index);
947
948 while ((currentNode != null)
949 && (currentNode != rootNode[index])
950 && (isRed(currentNode.getParent(index), index))) {
951 if (isLeftChild(getParent(currentNode, index), index)) {
952 Node y = getRightChild(getGrandParent(currentNode, index), index);
953
954 if (isRed(y, index)) {
955 makeBlack(getParent(currentNode, index), index);
956 makeBlack(y, index);
957 makeRed(getGrandParent(currentNode, index), index);
958
959 currentNode = getGrandParent(currentNode, index);
960 } else {
961 if (isRightChild(currentNode, index)) {
962 currentNode = getParent(currentNode, index);
963
964 rotateLeft(currentNode, index);
965 }
966
967 makeBlack(getParent(currentNode, index), index);
968 makeRed(getGrandParent(currentNode, index), index);
969
970 if (getGrandParent(currentNode, index) != null) {
971 rotateRight(getGrandParent(currentNode, index), index);
972 }
973 }
974 } else {
975
976 // just like clause above, except swap left for right
977 Node y = getLeftChild(getGrandParent(currentNode, index), index);
978
979 if (isRed(y, index)) {
980 makeBlack(getParent(currentNode, index), index);
981 makeBlack(y, index);
982 makeRed(getGrandParent(currentNode, index), index);
983
984 currentNode = getGrandParent(currentNode, index);
985 } else {
986 if (isLeftChild(currentNode, index)) {
987 currentNode = getParent(currentNode, index);
988
989 rotateRight(currentNode, index);
990 }
991
992 makeBlack(getParent(currentNode, index), index);
993 makeRed(getGrandParent(currentNode, index), index);
994
995 if (getGrandParent(currentNode, index) != null) {
996 rotateLeft(getGrandParent(currentNode, index), index);
997 }
998 }
999 }
1000 }
1001
1002 makeBlack(rootNode[index], index);
1003 }
1004
1005 /**
1006 * complicated red-black delete stuff. Based on Sun's TreeMap
1007 * implementation, though it's barely recognizable any more
1008 *
1009 * @param deletedNode the node to be deleted
1010 */
1011 private void doRedBlackDelete(final Node deletedNode) {
1012 for (int index = FIRST_INDEX; index < NUMBER_OF_INDICES; index++) {
1013 // if deleted node has both left and children, swap with
1014 // the next greater node
1015 if ((deletedNode.getLeft(index) != null) && (deletedNode.getRight(index) != null)) {
1016 swapPosition(nextGreater(deletedNode, index), deletedNode, index);
1017 }
1018
1019 Node replacement =
1020 ((deletedNode.getLeft(index) != null) ? deletedNode.getLeft(index) : deletedNode.getRight(index));
1021
1022 if (replacement != null) {
1023 replacement.setParent(deletedNode.getParent(index), index);
1024
1025 if (deletedNode.getParent(index) == null) {
1026 rootNode[index] = replacement;
1027 } else if (deletedNode == deletedNode.getParent(index).getLeft(index)) {
1028 deletedNode.getParent(index).setLeft(replacement, index);
1029 } else {
1030 deletedNode.getParent(index).setRight(replacement, index);
1031 }
1032
1033 deletedNode.setLeft(null, index);
1034 deletedNode.setRight(null, index);
1035 deletedNode.setParent(null, index);
1036
1037 if (isBlack(deletedNode, index)) {
1038 doRedBlackDeleteFixup(replacement, index);
1039 }
1040 } else {
1041
1042 // replacement is null
1043 if (deletedNode.getParent(index) == null) {
1044
1045 // empty tree
1046 rootNode[index] = null;
1047 } else {
1048
1049 // deleted node had no children
1050 if (isBlack(deletedNode, index)) {
1051 doRedBlackDeleteFixup(deletedNode, index);
1052 }
1053
1054 if (deletedNode.getParent(index) != null) {
1055 if (deletedNode == deletedNode.getParent(index).getLeft(index)) {
1056 deletedNode.getParent(index).setLeft(null, index);
1057 } else {
1058 deletedNode.getParent(index).setRight(null, index);
1059 }
1060
1061 deletedNode.setParent(null, index);
1062 }
1063 }
1064 }
1065 }
1066 shrink();
1067 }
1068
1069 /**
1070 * complicated red-black delete stuff. Based on Sun's TreeMap
1071 * implementation, though it's barely recognizable any more. This
1072 * rebalances the tree (somewhat, as red-black trees are not
1073 * perfectly balanced -- perfect balancing takes longer)
1074 *
1075 * @param replacementNode the node being replaced
1076 * @param index the KEY or VALUE int
1077 */
1078 private void doRedBlackDeleteFixup(final Node replacementNode, final int index) {
1079 Node currentNode = replacementNode;
1080
1081 while ((currentNode != rootNode[index]) && (isBlack(currentNode, index))) {
1082 if (isLeftChild(currentNode, index)) {
1083 Node siblingNode = getRightChild(getParent(currentNode, index), index);
1084
1085 if (isRed(siblingNode, index)) {
1086 makeBlack(siblingNode, index);
1087 makeRed(getParent(currentNode, index), index);
1088 rotateLeft(getParent(currentNode, index), index);
1089
1090 siblingNode = getRightChild(getParent(currentNode, index), index);
1091 }
1092
1093 if (isBlack(getLeftChild(siblingNode, index), index)
1094 && isBlack(getRightChild(siblingNode, index), index)) {
1095 makeRed(siblingNode, index);
1096
1097 currentNode = getParent(currentNode, index);
1098 } else {
1099 if (isBlack(getRightChild(siblingNode, index), index)) {
1100 makeBlack(getLeftChild(siblingNode, index), index);
1101 makeRed(siblingNode, index);
1102 rotateRight(siblingNode, index);
1103
1104 siblingNode = getRightChild(getParent(currentNode, index), index);
1105 }
1106
1107 copyColor(getParent(currentNode, index), siblingNode, index);
1108 makeBlack(getParent(currentNode, index), index);
1109 makeBlack(getRightChild(siblingNode, index), index);
1110 rotateLeft(getParent(currentNode, index), index);
1111
1112 currentNode = rootNode[index];
1113 }
1114 } else {
1115 Node siblingNode = getLeftChild(getParent(currentNode, index), index);
1116
1117 if (isRed(siblingNode, index)) {
1118 makeBlack(siblingNode, index);
1119 makeRed(getParent(currentNode, index), index);
1120 rotateRight(getParent(currentNode, index), index);
1121
1122 siblingNode = getLeftChild(getParent(currentNode, index), index);
1123 }
1124
1125 if (isBlack(getRightChild(siblingNode, index), index)
1126 && isBlack(getLeftChild(siblingNode, index), index)) {
1127 makeRed(siblingNode, index);
1128
1129 currentNode = getParent(currentNode, index);
1130 } else {
1131 if (isBlack(getLeftChild(siblingNode, index), index)) {
1132 makeBlack(getRightChild(siblingNode, index), index);
1133 makeRed(siblingNode, index);
1134 rotateLeft(siblingNode, index);
1135
1136 siblingNode = getLeftChild(getParent(currentNode, index), index);
1137 }
1138
1139 copyColor(getParent(currentNode, index), siblingNode, index);
1140 makeBlack(getParent(currentNode, index), index);
1141 makeBlack(getLeftChild(siblingNode, index), index);
1142 rotateRight(getParent(currentNode, index), index);
1143
1144 currentNode = rootNode[index];
1145 }
1146 }
1147 }
1148
1149 makeBlack(currentNode, index);
1150 }
1151
1152 /**
1153 * swap two nodes (except for their content), taking care of
1154 * special cases where one is the other's parent ... hey, it
1155 * happens.
1156 *
1157 * @param x one node
1158 * @param y another node
1159 * @param index the KEY or VALUE int
1160 */
1161 private void swapPosition(final Node x, final Node y, final int index) {
1162 // Save initial values.
1163 Node xFormerParent = x.getParent(index);
1164 Node xFormerLeftChild = x.getLeft(index);
1165 Node xFormerRightChild = x.getRight(index);
1166 Node yFormerParent = y.getParent(index);
1167 Node yFormerLeftChild = y.getLeft(index);
1168 Node yFormerRightChild = y.getRight(index);
1169 boolean xWasLeftChild = (x.getParent(index) != null) && (x == x.getParent(index).getLeft(index));
1170 boolean yWasLeftChild = (y.getParent(index) != null) && (y == y.getParent(index).getLeft(index));
1171
1172 // Swap, handling special cases of one being the other's parent.
1173 if (x == yFormerParent) { // x was y's parent
1174 x.setParent(y, index);
1175
1176 if (yWasLeftChild) {
1177 y.setLeft(x, index);
1178 y.setRight(xFormerRightChild, index);
1179 } else {
1180 y.setRight(x, index);
1181 y.setLeft(xFormerLeftChild, index);
1182 }
1183 } else {
1184 x.setParent(yFormerParent, index);
1185
1186 if (yFormerParent != null) {
1187 if (yWasLeftChild) {
1188 yFormerParent.setLeft(x, index);
1189 } else {
1190 yFormerParent.setRight(x, index);
1191 }
1192 }