001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.commons.collections;
018
019 import java.util.AbstractCollection;
020 import java.util.AbstractMap;
021 import java.util.AbstractSet;
022 import java.util.Collection;
023 import java.util.ConcurrentModificationException;
024 import java.util.Iterator;
025 import java.util.Map;
026 import java.util.NoSuchElementException;
027 import java.util.Set;
028
029 /**
030 * Red-Black tree-based implementation of Map. This class guarantees
031 * that the map will be in both ascending key order and ascending
032 * value order, sorted according to the natural order for the key's
033 * and value's classes.
034 * <p>
035 * This Map is intended for applications that need to be able to look
036 * up a key-value pairing by either key or value, and need to do so
037 * with equal efficiency.
038 * <p>
039 * While that goal could be accomplished by taking a pair of TreeMaps
040 * and redirecting requests to the appropriate TreeMap (e.g.,
041 * containsKey would be directed to the TreeMap that maps values to
042 * keys, containsValue would be directed to the TreeMap that maps keys
043 * to values), there are problems with that implementation,
044 * particularly when trying to keep the two TreeMaps synchronized with
045 * each other. And if the data contained in the TreeMaps is large, the
046 * cost of redundant storage becomes significant. (See also the new
047 * {@link org.apache.commons.collections.bidimap.DualTreeBidiMap DualTreeBidiMap} and
048 * {@link org.apache.commons.collections.bidimap.DualHashBidiMap DualHashBidiMap}
049 * implementations.)
050 * <p>
051 * This solution keeps the data properly synchronized and minimizes
052 * the data storage. The red-black algorithm is based on TreeMap's,
053 * but has been modified to simultaneously map a tree node by key and
054 * by value. This doubles the cost of put operations (but so does
055 * using two TreeMaps), and nearly doubles the cost of remove
056 * operations (there is a savings in that the lookup of the node to be
057 * removed only has to be performed once). And since only one node
058 * contains the key and value, storage is significantly less than that
059 * required by two TreeMaps.
060 * <p>
061 * There are some limitations placed on data kept in this Map. The
062 * biggest one is this:
063 * <p>
064 * When performing a put operation, neither the key nor the value may
065 * already exist in the Map. In the java.util Map implementations
066 * (HashMap, TreeMap), you can perform a put with an already mapped
067 * key, and neither cares about duplicate values at all ... but this
068 * implementation's put method with throw an IllegalArgumentException
069 * if either the key or the value is already in the Map.
070 * <p>
071 * Obviously, that same restriction (and consequence of failing to
072 * heed that restriction) applies to the putAll method.
073 * <p>
074 * The Map.Entry instances returned by the appropriate methods will
075 * not allow setValue() and will throw an
076 * UnsupportedOperationException on attempts to call that method.
077 * <p>
078 * New methods are added to take advantage of the fact that values are
079 * kept sorted independently of their keys:
080 * <p>
081 * Object getKeyForValue(Object value) is the opposite of get; it
082 * takes a value and returns its key, if any.
083 * <p>
084 * Object removeValue(Object value) finds and removes the specified
085 * value and returns the now un-used key.
086 * <p>
087 * Set entrySetByValue() returns the Map.Entry's in a Set whose
088 * iterator will iterate over the Map.Entry's in ascending order by
089 * their corresponding values.
090 * <p>
091 * Set keySetByValue() returns the keys in a Set whose iterator will
092 * iterate over the keys in ascending order by their corresponding
093 * values.
094 * <p>
095 * Collection valuesByValue() returns the values in a Collection whose
096 * iterator will iterate over the values in ascending order.
097 *
098 * @deprecated Replaced by TreeBidiMap in bidimap subpackage. Due to be removed in v4.0.
099 * @see BidiMap
100 * @see org.apache.commons.collections.bidimap.DualTreeBidiMap
101 * @see org.apache.commons.collections.bidimap.DualHashBidiMap
102 * @since Commons Collections 2.0
103 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
104 *
105 * @author Marc Johnson
106 */
107 public final class DoubleOrderedMap extends AbstractMap {
108 // final for performance
109
110 private static final int KEY = 0;
111 private static final int VALUE = 1;
112 private static final int SUM_OF_INDICES = KEY + VALUE;
113 private static final int FIRST_INDEX = 0;
114 private static final int NUMBER_OF_INDICES = 2;
115 private static final String[] dataName = new String[] { "key", "value" };
116
117 private Node[] rootNode = new Node[] { null, null };
118 private int nodeCount = 0;
119 private int modifications = 0;
120 private Set[] setOfKeys = new Set[] { null, null };
121 private Set[] setOfEntries = new Set[] { null, null };
122 private Collection[] collectionOfValues = new Collection[] { null, null };
123
124 /**
125 * Construct a new DoubleOrderedMap
126 */
127 public DoubleOrderedMap() {
128 }
129
130 /**
131 * Constructs a new DoubleOrderedMap from an existing Map, with keys and
132 * values sorted
133 *
134 * @param map the map whose mappings are to be placed in this map.
135 *
136 * @throws ClassCastException if the keys in the map are not
137 * Comparable, or are not mutually
138 * comparable; also if the values in
139 * the map are not Comparable, or
140 * are not mutually Comparable
141 * @throws NullPointerException if any key or value in the map
142 * is null
143 * @throws IllegalArgumentException if there are duplicate keys
144 * or duplicate values in the
145 * map
146 */
147 public DoubleOrderedMap(final Map map)
148 throws ClassCastException, NullPointerException,
149 IllegalArgumentException {
150 putAll(map);
151 }
152
153 /**
154 * Returns the key to which this map maps the specified value.
155 * Returns null if the map contains no mapping for this value.
156 *
157 * @param value value whose associated key is to be returned.
158 *
159 * @return the key to which this map maps the specified value, or
160 * null if the map contains no mapping for this value.
161 *
162 * @throws ClassCastException if the value is of an
163 * inappropriate type for this map.
164 * @throws NullPointerException if the value is null
165 */
166 public Object getKeyForValue(final Object value)
167 throws ClassCastException, NullPointerException {
168 return doGet((Comparable) value, VALUE);
169 }
170
171 /**
172 * Removes the mapping for this value from this map if present
173 *
174 * @param value value whose mapping is to be removed from the map.
175 *
176 * @return previous key associated with specified value, or null
177 * if there was no mapping for value.
178 */
179 public Object removeValue(final Object value) {
180 return doRemove((Comparable) value, VALUE);
181 }
182
183 /**
184 * Returns a set view of the mappings contained in this map. Each
185 * element in the returned set is a Map.Entry. The set is backed
186 * by the map, so changes to the map are reflected in the set, and
187 * vice-versa. If the map is modified while an iteration over the
188 * set is in progress, the results of the iteration are
189 * undefined. The set supports element removal, which removes the
190 * corresponding mapping from the map, via the Iterator.remove,
191 * Set.remove, removeAll, retainAll and clear operations. It does
192 * not support the add or addAll operations.<p>
193 *
194 * The difference between this method and entrySet is that
195 * entrySet's iterator() method returns an iterator that iterates
196 * over the mappings in ascending order by key. This method's
197 * iterator method iterates over the mappings in ascending order
198 * by value.
199 *
200 * @return a set view of the mappings contained in this map.
201 */
202 public Set entrySetByValue() {
203
204 if (setOfEntries[VALUE] == null) {
205 setOfEntries[VALUE] = new AbstractSet() {
206
207 public Iterator iterator() {
208
209 return new DoubleOrderedMapIterator(VALUE) {
210
211 protected Object doGetNext() {
212 return lastReturnedNode;
213 }
214 };
215 }
216
217 public boolean contains(Object o) {
218
219 if (!(o instanceof Map.Entry)) {
220 return false;
221 }
222
223 Map.Entry entry = (Map.Entry) o;
224 Object key = entry.getKey();
225 Node node = lookup((Comparable) entry.getValue(),
226 VALUE);
227
228 return (node != null) && node.getData(KEY).equals(key);
229 }
230
231 public boolean remove(Object o) {
232
233 if (!(o instanceof Map.Entry)) {
234 return false;
235 }
236
237 Map.Entry entry = (Map.Entry) o;
238 Object key = entry.getKey();
239 Node node = lookup((Comparable) entry.getValue(),
240 VALUE);
241
242 if ((node != null) && node.getData(KEY).equals(key)) {
243 doRedBlackDelete(node);
244
245 return true;
246 }
247
248 return false;
249 }
250
251 public int size() {
252 return DoubleOrderedMap.this.size();
253 }
254
255 public void clear() {
256 DoubleOrderedMap.this.clear();
257 }
258 };
259 }
260
261 return setOfEntries[VALUE];
262 }
263
264 /**
265 * Returns a set view of the keys contained in this map. The set
266 * is backed by the map, so changes to the map are reflected in
267 * the set, and vice-versa. If the map is modified while an
268 * iteration over the set is in progress, the results of the
269 * iteration are undefined. The set supports element removal,
270 * which removes the corresponding mapping from the map, via the
271 * Iterator.remove, Set.remove, removeAll, retainAll, and clear
272 * operations. It does not support the add or addAll
273 * operations.<p>
274 *
275 * The difference between this method and keySet is that keySet's
276 * iterator() method returns an iterator that iterates over the
277 * keys in ascending order by key. This method's iterator method
278 * iterates over the keys in ascending order by value.
279 *
280 * @return a set view of the keys contained in this map.
281 */
282 public Set keySetByValue() {
283
284 if (setOfKeys[VALUE] == null) {
285 setOfKeys[VALUE] = new AbstractSet() {
286
287 public Iterator iterator() {
288
289 return new DoubleOrderedMapIterator(VALUE) {
290
291 protected Object doGetNext() {
292 return lastReturnedNode.getData(KEY);
293 }
294 };
295 }
296
297 public int size() {
298 return DoubleOrderedMap.this.size();
299 }
300
301 public boolean contains(Object o) {
302 return containsKey(o);
303 }
304
305 public boolean remove(Object o) {
306
307 int oldnodeCount = nodeCount;
308
309 DoubleOrderedMap.this.remove(o);
310
311 return nodeCount != oldnodeCount;
312 }
313
314 public void clear() {
315 DoubleOrderedMap.this.clear();
316 }
317 };
318 }
319
320 return setOfKeys[VALUE];
321 }
322
323 /**
324 * Returns a collection view of the values contained in this
325 * map. The collection is backed by the map, so changes to the map
326 * are reflected in the collection, and vice-versa. If the map is
327 * modified while an iteration over the collection is in progress,
328 * the results of the iteration are undefined. The collection
329 * supports element removal, which removes the corresponding
330 * mapping from the map, via the Iterator.remove,
331 * Collection.remove, removeAll, retainAll and clear operations.
332 * It does not support the add or addAll operations.<p>
333 *
334 * The difference between this method and values is that values's
335 * iterator() method returns an iterator that iterates over the
336 * values in ascending order by key. This method's iterator method
337 * iterates over the values in ascending order by key.
338 *
339 * @return a collection view of the values contained in this map.
340 */
341 public Collection valuesByValue() {
342
343 if (collectionOfValues[VALUE] == null) {
344 collectionOfValues[VALUE] = new AbstractCollection() {
345
346 public Iterator iterator() {
347
348 return new DoubleOrderedMapIterator(VALUE) {
349
350 protected Object doGetNext() {
351 return lastReturnedNode.getData(VALUE);
352 }
353 };
354 }
355
356 public int size() {
357 return DoubleOrderedMap.this.size();
358 }
359
360 public boolean contains(Object o) {
361 return containsValue(o);
362 }
363
364 public boolean remove(Object o) {
365
366 int oldnodeCount = nodeCount;
367
368 removeValue(o);
369
370 return nodeCount != oldnodeCount;
371 }
372
373 public boolean removeAll(Collection c) {
374
375 boolean modified = false;
376 Iterator iter = c.iterator();
377
378 while (iter.hasNext()) {
379 if (removeValue(iter.next()) != null) {
380 modified = true;
381 }
382 }
383
384 return modified;
385 }
386
387 public void clear() {
388 DoubleOrderedMap.this.clear();
389 }
390 };
391 }
392
393 return collectionOfValues[VALUE];
394 }
395
396 /**
397 * common remove logic (remove by key or remove by value)
398 *
399 * @param o the key, or value, that we're looking for
400 * @param index KEY or VALUE
401 *
402 * @return the key, if remove by value, or the value, if remove by
403 * key. null if the specified key or value could not be
404 * found
405 */
406 private Object doRemove(final Comparable o, final int index) {
407
408 Node node = lookup(o, index);
409 Object rval = null;
410
411 if (node != null) {
412 rval = node.getData(oppositeIndex(index));
413
414 doRedBlackDelete(node);
415 }
416
417 return rval;
418 }
419
420 /**
421 * common get logic, used to get by key or get by value
422 *
423 * @param o the key or value that we're looking for
424 * @param index KEY or VALUE
425 *
426 * @return the key (if the value was mapped) or the value (if the
427 * key was mapped); null if we couldn't find the specified
428 * object
429 */
430 private Object doGet(final Comparable o, final int index) {
431
432 checkNonNullComparable(o, index);
433
434 Node node = lookup(o, index);
435
436 return ((node == null)
437 ? null
438 : node.getData(oppositeIndex(index)));
439 }
440
441 /**
442 * Get the opposite index of the specified index
443 *
444 * @param index KEY or VALUE
445 *
446 * @return VALUE (if KEY was specified), else KEY
447 */
448 private int oppositeIndex(final int index) {
449
450 // old trick ... to find the opposite of a value, m or n,
451 // subtract the value from the sum of the two possible
452 // values. (m + n) - m = n; (m + n) - n = m
453 return SUM_OF_INDICES - index;
454 }
455
456 /**
457 * do the actual lookup of a piece of data
458 *
459 * @param data the key or value to be looked up
460 * @param index KEY or VALUE
461 *
462 * @return the desired Node, or null if there is no mapping of the
463 * specified data
464 */
465 private Node lookup(final Comparable data, final int index) {
466
467 Node rval = null;
468 Node node = rootNode[index];
469
470 while (node != null) {
471 int cmp = compare(data, node.getData(index));
472
473 if (cmp == 0) {
474 rval = node;
475
476 break;
477 } else {
478 node = (cmp < 0)
479 ? node.getLeft(index)
480 : node.getRight(index);
481 }
482 }
483
484 return rval;
485 }
486
487 /**
488 * Compare two objects
489 *
490 * @param o1 the first object
491 * @param o2 the second object
492 *
493 * @return negative value if o1 < o2; 0 if o1 == o2; positive
494 * value if o1 > o2
495 */
496 private static int compare(final Comparable o1, final Comparable o2) {
497 return o1.compareTo(o2);
498 }
499
500 /**
501 * find the least node from a given node. very useful for starting
502 * a sorting iterator ...
503 *
504 * @param node the node from which we will start searching
505 * @param index KEY or VALUE
506 *
507 * @return the smallest node, from the specified node, in the
508 * specified mapping
509 */
510 private static Node leastNode(final Node node, final int index) {
511
512 Node rval = node;
513
514 if (rval != null) {
515 while (rval.getLeft(index) != null) {
516 rval = rval.getLeft(index);
517 }
518 }
519
520 return rval;
521 }
522
523 /**
524 * get the next larger node from the specified node
525 *
526 * @param node the node to be searched from
527 * @param index KEY or VALUE
528 *
529 * @return the specified node
530 */
531 private Node nextGreater(final Node node, final int index) {
532
533 Node rval = null;
534
535 if (node == null) {
536 rval = null;
537 } else if (node.getRight(index) != null) {
538
539 // everything to the node's right is larger. The least of
540 // the right node's descendants is the next larger node
541 rval = leastNode(node.getRight(index), index);
542 } else {
543
544 // traverse up our ancestry until we find an ancestor that
545 // is null or one whose left child is our ancestor. If we
546 // find a null, then this node IS the largest node in the
547 // tree, and there is no greater node. Otherwise, we are
548 // the largest node in the subtree on that ancestor's left
549 // ... and that ancestor is the next greatest node
550 Node parent = node.getParent(index);
551 Node child = node;
552
553 while ((parent != null) && (child == parent.getRight(index))) {
554 child = parent;
555 parent = parent.getParent(index);
556 }
557
558 rval = parent;
559 }
560
561 return rval;
562 }
563
564 /**
565 * copy the color from one node to another, dealing with the fact
566 * that one or both nodes may, in fact, be null
567 *
568 * @param from the node whose color we're copying; may be null
569 * @param to the node whose color we're changing; may be null
570 * @param index KEY or VALUE
571 */
572 private static void copyColor(final Node from, final Node to,
573 final int index) {
574
575 if (to != null) {
576 if (from == null) {
577
578 // by default, make it black
579 to.setBlack(index);
580 } else {
581 to.copyColor(from, index);
582 }
583 }
584 }
585
586 /**
587 * is the specified node red? if the node does not exist, no, it's
588 * black, thank you
589 *
590 * @param node the node (may be null) in question
591 * @param index KEY or VALUE
592 */
593 private static boolean isRed(final Node node, final int index) {
594
595 return ((node == null)
596 ? false
597 : node.isRed(index));
598 }
599
600 /**
601 * is the specified black red? if the node does not exist, sure,
602 * it's black, thank you
603 *
604 * @param node the node (may be null) in question
605 * @param index KEY or VALUE
606 */
607 private static boolean isBlack(final Node node, final int index) {
608
609 return ((node == null)
610 ? true
611 : node.isBlack(index));
612 }
613
614 /**
615 * force a node (if it exists) red
616 *
617 * @param node the node (may be null) in question
618 * @param index KEY or VALUE
619 */
620 private static void makeRed(final Node node, final int index) {
621
622 if (node != null) {
623 node.setRed(index);
624 }
625 }
626
627 /**
628 * force a node (if it exists) black
629 *
630 * @param node the node (may be null) in question
631 * @param index KEY or VALUE
632 */
633 private static void makeBlack(final Node node, final int index) {
634
635 if (node != null) {
636 node.setBlack(index);
637 }
638 }
639
640 /**
641 * get a node's grandparent. mind you, the node, its parent, or
642 * its grandparent may not exist. no problem
643 *
644 * @param node the node (may be null) in question
645 * @param index KEY or VALUE
646 */
647 private static Node getGrandParent(final Node node, final int index) {
648 return getParent(getParent(node, index), index);
649 }
650
651 /**
652 * get a node's parent. mind you, the node, or its parent, may not
653 * exist. no problem
654 *
655 * @param node the node (may be null) in question
656 * @param index KEY or VALUE
657 */
658 private static Node getParent(final Node node, final int index) {
659
660 return ((node == null)
661 ? null
662 : node.getParent(index));
663 }
664
665 /**
666 * get a node's right child. mind you, the node may not exist. no
667 * problem
668 *
669 * @param node the node (may be null) in question
670 * @param index KEY or VALUE
671 */
672 private static Node getRightChild(final Node node, final int index) {
673
674 return (node == null)
675 ? null
676 : node.getRight(index);
677 }
678
679 /**
680 * get a node's left child. mind you, the node may not exist. no
681 * problem
682 *
683 * @param node the node (may be null) in question
684 * @param index KEY or VALUE
685 */
686 private static Node getLeftChild(final Node node, final int index) {
687
688 return (node == null)
689 ? null
690 : node.getLeft(index);
691 }
692
693 /**
694 * is this node its parent's left child? mind you, the node, or
695 * its parent, may not exist. no problem. if the node doesn't
696 * exist ... it's its non-existent parent's left child. If the
697 * node does exist but has no parent ... no, we're not the
698 * non-existent parent's left child. Otherwise (both the specified
699 * node AND its parent exist), check.
700 *
701 * @param node the node (may be null) in question
702 * @param index KEY or VALUE
703 */
704 private static boolean isLeftChild(final Node node, final int index) {
705
706 return (node == null)
707 ? true
708 : ((node.getParent(index) == null)
709 ? false
710 : (node == node.getParent(index).getLeft(index)));
711 }
712
713 /**
714 * is this node its parent's right child? mind you, the node, or
715 * its parent, may not exist. no problem. if the node doesn't
716 * exist ... it's its non-existent parent's right child. If the
717 * node does exist but has no parent ... no, we're not the
718 * non-existent parent's right child. Otherwise (both the
719 * specified node AND its parent exist), check.
720 *
721 * @param node the node (may be null) in question
722 * @param index KEY or VALUE
723 */
724 private static boolean isRightChild(final Node node, final int index) {
725
726 return (node == null)
727 ? true
728 : ((node.getParent(index) == null)
729 ? false
730 : (node == node.getParent(index).getRight(index)));
731 }
732
733 /**
734 * do a rotate left. standard fare in the world of balanced trees
735 *
736 * @param node the node to be rotated
737 * @param index KEY or VALUE
738 */
739 private void rotateLeft(final Node node, final int index) {
740
741 Node rightChild = node.getRight(index);
742
743 node.setRight(rightChild.getLeft(index), index);
744
745 if (rightChild.getLeft(index) != null) {
746 rightChild.getLeft(index).setParent(node, index);
747 }
748
749 rightChild.setParent(node.getParent(index), index);
750
751 if (node.getParent(index) == null) {
752
753 // node was the root ... now its right child is the root
754 rootNode[index] = rightChild;
755 } else if (node.getParent(index).getLeft(index) == node) {
756 node.getParent(index).setLeft(rightChild, index);
757 } else {
758 node.getParent(index).setRight(rightChild, index);
759 }
760
761 rightChild.setLeft(node, index);
762 node.setParent(rightChild, index);
763 }
764
765 /**
766 * do a rotate right. standard fare in the world of balanced trees
767 *
768 * @param node the node to be rotated
769 * @param index KEY or VALUE
770 */
771 private void rotateRight(final Node node, final int index) {
772
773 Node leftChild = node.getLeft(index);
774
775 node.setLeft(leftChild.getRight(index), index);
776
777 if (leftChild.getRight(index) != null) {
778 leftChild.getRight(index).setParent(node, index);
779 }
780
781 leftChild.setParent(node.getParent(index), index);
782
783 if (node.getParent(index) == null) {
784
785 // node was the root ... now its left child is the root
786 rootNode[index] = leftChild;
787 } else if (node.getParent(index).getRight(index) == node) {
788 node.getParent(index).setRight(leftChild, index);
789 } else {
790 node.getParent(index).setLeft(leftChild, index);
791 }
792
793 leftChild.setRight(node, index);
794 node.setParent(leftChild, index);
795 }
796
797 /**
798 * complicated red-black insert stuff. Based on Sun's TreeMap
799 * implementation, though it's barely recognizable any more
800 *
801 * @param insertedNode the node to be inserted
802 * @param index KEY or VALUE
803 */
804 private void doRedBlackInsert(final Node insertedNode, final int index) {
805
806 Node currentNode = insertedNode;
807
808 makeRed(currentNode, index);
809
810 while ((currentNode != null) && (currentNode != rootNode[index])
811 && (isRed(currentNode.getParent(index), index))) {
812 if (isLeftChild(getParent(currentNode, index), index)) {
813 Node y = getRightChild(getGrandParent(currentNode, index),
814 index);
815
816 if (isRed(y, index)) {
817 makeBlack(getParent(currentNode, index), index);
818 makeBlack(y, index);
819 makeRed(getGrandParent(currentNode, index), index);
820
821 currentNode = getGrandParent(currentNode, index);
822 } else {
823 if (isRightChild(currentNode, index)) {
824 currentNode = getParent(currentNode, index);
825
826 rotateLeft(currentNode, index);
827 }
828
829 makeBlack(getParent(currentNode, index), index);
830 makeRed(getGrandParent(currentNode, index), index);
831
832 if (getGrandParent(currentNode, index) != null) {
833 rotateRight(getGrandParent(currentNode, index),
834 index);
835 }
836 }
837 } else {
838
839 // just like clause above, except swap left for right
840 Node y = getLeftChild(getGrandParent(currentNode, index),
841 index);
842
843 if (isRed(y, index)) {
844 makeBlack(getParent(currentNode, index), index);
845 makeBlack(y, index);
846 makeRed(getGrandParent(currentNode, index), index);
847
848 currentNode = getGrandParent(currentNode, index);
849 } else {
850 if (isLeftChild(currentNode, index)) {
851 currentNode = getParent(currentNode, index);
852
853 rotateRight(currentNode, index);
854 }
855
856 makeBlack(getParent(currentNode, index), index);
857 makeRed(getGrandParent(currentNode, index), index);
858
859 if (getGrandParent(currentNode, index) != null) {
860 rotateLeft(getGrandParent(currentNode, index), index);
861 }
862 }
863 }
864 }
865
866 makeBlack(rootNode[index], index);
867 }
868
869 /**
870 * complicated red-black delete stuff. Based on Sun's TreeMap
871 * implementation, though it's barely recognizable any more
872 *
873 * @param deletedNode the node to be deleted
874 */
875 private void doRedBlackDelete(final Node deletedNode) {
876
877 for (int index = FIRST_INDEX; index < NUMBER_OF_INDICES; index++) {
878
879 // if deleted node has both left and children, swap with
880 // the next greater node
881 if ((deletedNode.getLeft(index) != null)
882 && (deletedNode.getRight(index) != null)) {
883 swapPosition(nextGreater(deletedNode, index), deletedNode,
884 index);
885 }
886
887 Node replacement = ((deletedNode.getLeft(index) != null)
888 ? deletedNode.getLeft(index)
889 : deletedNode.getRight(index));
890
891 if (replacement != null) {
892 replacement.setParent(deletedNode.getParent(index), index);
893
894 if (deletedNode.getParent(index) == null) {
895 rootNode[index] = replacement;
896 } else if (deletedNode
897 == deletedNode.getParent(index).getLeft(index)) {
898 deletedNode.getParent(index).setLeft(replacement, index);
899 } else {
900 deletedNode.getParent(index).setRight(replacement, index);
901 }
902
903 deletedNode.setLeft(null, index);
904 deletedNode.setRight(null, index);
905 deletedNode.setParent(null, index);
906
907 if (isBlack(deletedNode, index)) {
908 doRedBlackDeleteFixup(replacement, index);
909 }
910 } else {
911
912 // replacement is null
913 if (deletedNode.getParent(index) == null) {
914
915 // empty tree
916 rootNode[index] = null;
917 } else {
918
919 // deleted node had no children
920 if (isBlack(deletedNode, index)) {
921 doRedBlackDeleteFixup(deletedNode, index);
922 }
923
924 if (deletedNode.getParent(index) != null) {
925 if (deletedNode
926 == deletedNode.getParent(index)
927 .getLeft(index)) {
928 deletedNode.getParent(index).setLeft(null, index);
929 } else {
930 deletedNode.getParent(index).setRight(null,
931 index);
932 }
933
934 deletedNode.setParent(null, index);
935 }
936 }
937 }
938 }
939
940 shrink();
941 }
942
943 /**
944 * complicated red-black delete stuff. Based on Sun's TreeMap
945 * implementation, though it's barely recognizable any more. This
946 * rebalances the tree (somewhat, as red-black trees are not
947 * perfectly balanced -- perfect balancing takes longer)
948 *
949 * @param replacementNode the node being replaced
950 * @param index KEY or VALUE
951 */
952 private void doRedBlackDeleteFixup(final Node replacementNode,
953 final int index) {
954
955 Node currentNode = replacementNode;
956
957 while ((currentNode != rootNode[index])
958 && (isBlack(currentNode, index))) {
959 if (isLeftChild(currentNode, index)) {
960 Node siblingNode =
961 getRightChild(getParent(currentNode, index), index);
962
963 if (isRed(siblingNode, index)) {
964 makeBlack(siblingNode, index);
965 makeRed(getParent(currentNode, index), index);
966 rotateLeft(getParent(currentNode, index), index);
967
968 siblingNode = getRightChild(getParent(currentNode, index), index);
969 }
970
971 if (isBlack(getLeftChild(siblingNode, index), index)
972 && isBlack(getRightChild(siblingNode, index),
973 index)) {
974 makeRed(siblingNode, index);
975
976 currentNode = getParent(currentNode, index);
977 } else {
978 if (isBlack(getRightChild(siblingNode, index), index)) {
979 makeBlack(getLeftChild(siblingNode, index), index);
980 makeRed(siblingNode, index);
981 rotateRight(siblingNode, index);
982
983 siblingNode =
984 getRightChild(getParent(currentNode, index), index);
985 }
986
987 copyColor(getParent(currentNode, index), siblingNode,
988 index);
989 makeBlack(getParent(currentNode, index), index);
990 makeBlack(getRightChild(siblingNode, index), index);
991 rotateLeft(getParent(currentNode, index), index);
992
993 currentNode = rootNode[index];
994 }
995 } else {
996 Node siblingNode = getLeftChild(getParent(currentNode, index), index);
997
998 if (isRed(siblingNode, index)) {
999 makeBlack(siblingNode, index);
1000 makeRed(getParent(currentNode, index), index);
1001 rotateRight(getParent(currentNode, index), index);
1002
1003 siblingNode = getLeftChild(getParent(currentNode, index), index);
1004 }
1005
1006 if (isBlack(getRightChild(siblingNode, index), index)
1007 && isBlack(getLeftChild(siblingNode, index), index)) {
1008 makeRed(siblingNode, index);
1009
1010 currentNode = getParent(currentNode, index);
1011 } else {
1012 if (isBlack(getLeftChild(siblingNode, index), index)) {
1013 makeBlack(getRightChild(siblingNode, index), index);
1014 makeRed(siblingNode, index);
1015 rotateLeft(siblingNode, index);
1016
1017 siblingNode =
1018 getLeftChild(getParent(currentNode, index), index);
1019 }
1020
1021 copyColor(getParent(currentNode, index), siblingNode,
1022 index);
1023 makeBlack(getParent(currentNode, index), index);
1024 makeBlack(getLeftChild(siblingNode, index), index);
1025 rotateRight(getParent(currentNode, index), index);
1026
1027 currentNode = rootNode[index];
1028 }
1029 }
1030 }
1031
1032 makeBlack(currentNode, index);
1033 }
1034
1035 /**
1036 * swap two nodes (except for their content), taking care of
1037 * special cases where one is the other's parent ... hey, it
1038 * happens.
1039 *
1040 * @param x one node
1041 * @param y another node
1042 * @param index KEY or VALUE
1043 */
1044 private void swapPosition(final Node x, final Node y, final int index) {
1045
1046 // Save initial values.
1047 Node xFormerParent = x.getParent(index);
1048 Node xFormerLeftChild = x.getLeft(index);
1049 Node xFormerRightChild = x.getRight(index);
1050 Node yFormerParent = y.getParent(index);
1051 Node yFormerLeftChild = y.getLeft(index);
1052 Node yFormerRightChild = y.getRight(index);
1053 boolean xWasLeftChild =
1054 (x.getParent(index) != null)
1055 && (x == x.getParent(index).getLeft(index));
1056 boolean yWasLeftChild =
1057 (y.getParent(index) != null)
1058 && (y == y.getParent(index).getLeft(index));
1059
1060 // Swap, handling special cases of one being the other's parent.
1061 if (x == yFormerParent) { // x was y's parent
1062 x.setParent(y, index);
1063
1064 if (yWasLeftChild) {
1065 y.setLeft(x, index);
1066 y.setRight(xFormerRightChild, index);
1067 } else {
1068 y.setRight(x, index);
1069 y.setLeft(xFormerLeftChild, index);
1070 }
1071 } else {
1072 x.setParent(yFormerParent, index);
1073
1074 if (yFormerParent != null) {
1075 if (yWasLeftChild) {
1076 yFormerParent.setLeft(x, index);
1077 } else {
1078 yFormerParent.setRight(x, index);
1079 }
1080 }
1081
1082 y.setLeft(xFormerLeftChild, index);
1083 y.setRight(xFormerRightChild, index);
1084 }
1085
1086 if (y == xFormerParent) { // y was x's parent
1087 y.setParent(x, index);
1088
1089 if (xWasLeftChild) {
1090 x.setLeft(y, index);
1091 x.setRight(yFormerRightChild, index);
1092 } else {
1093 x.setRight(y, index);
1094 x.setLeft(yFormerLeftChild, index);
1095 }
1096 } else {
1097 y.setParent(xFormerParent, index);
1098
1099 if (xFormerParent != null) {
1100 if (xWasLeftChild) {
1101 xFormerParent.setLeft(y, index);
1102 } else {
1103 xFormerParent.setRight(y, index);
1104 }
1105 }
1106
1107 x.setLeft(yFormerLeftChild, index);
1108 x.setRight(yFormerRightChild, index);
1109 }
1110
1111 // Fix children's parent pointers
1112 if (x.getLeft(index) != null) {
1113 x.getLeft(index).setParent(x, index);
1114 }
1115
1116 if (x.getRight(index) != null) {
1117 x.getRight(index).setParent(x, index);
1118 }
1119
1120 if (y.getLeft(index) != null) {
1121 y.getLeft(index).setParent(y, index);
1122 }
1123
1124 if (y.getRight(index) != null) {
1125 y.getRight(index).setParent(y, index);
1126 }
1127
1128 x.swapColors(y, index);
1129
1130 // Check if root changed
1131 if (rootNode[index] == x) {
1132 rootNode[index] = y;
1133 } else if (rootNode[index] == y) {
1134 rootNode[index] = x;
1135 }
1136 }
1137
1138 /**
1139 * check if an object is fit to be proper input ... has to be
1140 * Comparable and non-null
1141 *
1142 * @param o the object being checked
1143 * @param index KEY or VALUE (used to put the right word in the
1144 * exception message)
1145 *
1146 * @throws NullPointerException if o is null
1147 * @throws ClassCastException if o is not Comparable
1148 */
1149 private static void checkNonNullComparable(final Object o,
1150 final int index) {
1151
1152 if (o == null) {
1153 throw new NullPointerException(dataName[index]
1154 + " cannot be null");
1155 }
1156
1157 if (!(o instanceof Comparable)) {
1158 throw new ClassCastException(dataName[index]
1159 + " must be Comparable");
1160 }
1161 }
1162
1163 /**
1164 * check a key for validity (non-null and implements Comparable)
1165 *
1166 * @param key the key to be checked
1167 *
1168 * @throws NullPointerException if key is null
1169 * @throws ClassCastException if key is not Comparable
1170 */
1171 private static void checkKey(final Object key) {
1172 checkNonNullComparable(key, KEY);
1173 }
1174
1175 /**
1176 * check a value for validity (non-null and implements Comparable)
1177 *
1178 * @param value the value to be checked
1179 *
1180 * @throws NullPointerException if value is null
1181 * @throws ClassCastException if value is not Comparable
1182 */
1183 private static void checkValue(final Object value) {
1184 checkNonNullComparable(value, VALUE);
1185 }
1186
1187 /**
1188 * check a key and a value for validity (non-null and implements
1189 * Comparable)
1190 *
1191 * @param key the key to be checked
1192 * @param value the value to be checked
1193 *
1194 * @throws NullPointerException if key or value is null
1195 * @throws ClassCastException if key or value is not Comparable
1196 */
1197 private static void checkKeyAndValue(final Object key,
1198 final Object value) {
1199 checkKey(key);
1200 checkValue(value);
1201 }
1202
1203 /**
1204 * increment the modification count -- used to check for
1205 * concurrent modification of the map through the map and through
1206 * an Iterator from one of its Set or Collection views
1207 */
1208 private void modify() {
1209 modifications++;
1210 }
1211
1212 /**
1213 * bump up the size and note that the map has changed
1214 */
1215 private void grow() {
1216
1217 modify();
1218
1219 nodeCount++;
1220 }
1221
1222 /**
1223 * decrement the size and note that the map has changed
1224 */
1225 private void shrink() {
1226
1227 modify();
1228
1229 nodeCount--;
1230 }
1231
1232 /**
1233 * insert a node by its value
1234 *
1235 * @param newNode the node to be inserted
1236 *
1237 * @throws IllegalArgumentException if the node already exists
1238 * in the value mapping
1239 */
1240 private void insertValue(final Node newNode)
1241 throws IllegalArgumentException {
1242
1243 Node node = rootNode[VALUE];
1244
1245 while (true) {
1246 int cmp = compare(newNode.getData(VALUE), node.getData(VALUE));
1247
1248 if (cmp == 0) {
1249 throw new IllegalArgumentException(
1250 "Cannot store a duplicate value (\""
1251 + newNode.getData(VALUE) + "\") in this Map");
1252 } else if (cmp < 0) {
1253 if (node.getLeft(VALUE) != null) {
1254 node = node.getLeft(VALUE);
1255 } else {
1256 node.setLeft(newNode, VALUE);
1257 newNode.setParent(node, VALUE);
1258 doRedBlackInsert(newNode, VALUE);
1259
1260 break;
1261 }
1262 } else { // cmp > 0
1263 if (node.getRight(VALUE) != null) {
1264 node = node.getRight(VALUE);
1265 } else {
1266 node.setRight(newNode, VALUE);
1267 newNode.setParent(node, VALUE);
1268 doRedBlackInsert(newNode, VALUE);
1269
1270 break;
1271 }
1272 }
1273 }
1274 }
1275
1276 /* ********** START implementation of Map ********** */
1277
1278 /**
1279 * Returns the number of key-value mappings in this map. If the
1280 * map contains more than Integer.MAXVALUE elements, returns
1281 * Integer.MAXVALUE.
1282 *
1283 * @return the number of key-value mappings in this map.
1284 */
1285 public int size() {
1286 return nodeCount;
1287 }
1288
1289 /**
1290 * Returns true if this map contains a mapping for the specified
1291 * key.
1292 *
1293 * @param key key whose presence in this map is to be tested.
1294 *
1295 * @return true if this map contains a mapping for the specified
1296 * key.
1297 *
1298 * @throws ClassCastException if the key is of an inappropriate
1299 * type for this map.
1300 * @throws NullPointerException if the key is null
1301 */
1302 public boolean containsKey(final Object key)
1303 throws ClassCastException, NullPointerException {
1304
1305 checkKey(key);
1306
1307 return lookup((Comparable) key, KEY) != null;
1308 }
1309
1310 /**
1311 * Returns true if this map maps one or more keys to the
1312 * specified value.
1313 *
1314 * @param value value whose presence in this map is to be tested.
1315 *
1316 * @return true if this map maps one or more keys to the specified
1317 * value.
1318 */
1319 public boolean containsValue(final Object value) {
1320
1321 checkValue(value);
1322
1323 return lookup((Comparable) value, VALUE) != null;
1324 }
1325
1326 /**
1327 * Returns the value to which this map maps the specified
1328 * key. Returns null if the map contains no mapping for this key.
1329 *
1330 * @param key key whose associated value is to be returned.
1331 *
1332 * @return the value to which this map maps the specified key, or
1333 * null if the map contains no mapping for this key.
1334 *
1335 * @throws ClassCastException if the key is of an inappropriate
1336 * type for this map.
1337 * @throws NullPointerException if the key is null
1338 */
1339 public Object get(final Object key)
1340 throws ClassCastException, NullPointerException {
1341 return doGet((Comparable) key, KEY);
1342 }
1343
1344 /**
1345 * Associates the specified value with the specified key in this
1346 * map.
1347 *
1348 * @param key key with which the specified value is to be
1349 * associated.
1350 * @param value value to be associated with the specified key.
1351 *
1352 * @return null
1353 *
1354 * @throws ClassCastException if the class of the specified key
1355 * or value prevents it from being
1356 * stored in this map.
1357 * @throws NullPointerException if the specified key or value
1358 * is null
1359 * @throws IllegalArgumentException if the key duplicates an
1360 * existing key, or if the
1361 * value duplicates an
1362 * existing value
1363 */
1364 public Object put(final Object key, final Object value)
1365 throws ClassCastException, NullPointerException,
1366 IllegalArgumentException {
1367
1368 checkKeyAndValue(key, value);
1369
1370 Node node = rootNode[KEY];
1371
1372 if (node == null) {
1373 Node root = new Node((Comparable) key, (Comparable) value);
1374
1375 rootNode[KEY] = root;
1376 rootNode[VALUE] = root;
1377
1378 grow();
1379 } else {
1380 while (true) {
1381 int cmp = compare((Comparable) key, node.getData(KEY));
1382
1383 if (cmp == 0) {
1384 throw new IllegalArgumentException(
1385 "Cannot store a duplicate key (\"" + key
1386 + "\") in this Map");
1387 } else if (cmp < 0) {
1388 if (node.getLeft(KEY) != null) {
1389 node = node.getLeft(KEY);
1390 } else {
1391 Node newNode = new Node((Comparable) key,
1392 (Comparable) value);
1393
1394 insertValue(newNode);
1395 node.setLeft(newNode, KEY);
1396 newNode.setParent(node, KEY);
1397 doRedBlackInsert(newNode, KEY);
1398 grow();
1399
1400 break;
1401 }
1402 } else { // cmp > 0
1403 if (node.getRight(KEY) != null) {
1404 node = node.getRight(KEY);
1405 } else {
1406 Node newNode = new Node((Comparable) key,
1407 (Comparable) value);
1408
1409 insertValue(newNode);
1410 node.setRight(newNode, KEY);
1411 newNode.setParent(node, KEY);
1412 doRedBlackInsert(newNode, KEY);
1413 grow();
1414
1415 break;
1416 }
1417 }
1418 }
1419 }
1420
1421 return null;
1422 }
1423
1424 /**
1425 * Removes the mapping for this key from this map if present
1426 *
1427 * @param key key whose mapping is to be removed from the map.
1428 *
1429 * @return previous value associated with specified key, or null
1430 * if there was no mapping for key.
1431 */
1432 public Object remove(final Object key) {
1433 return doRemove((Comparable) key, KEY);
1434 }
1435
1436 /**
1437 * Removes all mappings from this map
1438 */
1439 public void clear() {
1440
1441 modify();
1442
1443 nodeCount = 0;
1444 rootNode[KEY] = null;
1445 rootNode[VALUE] = null;
1446 }
1447
1448 /**
1449 * Returns a set view of the keys contained in this map. The set
1450 * is backed by the map, so changes to the map are reflected in
1451 * the set, and vice-versa. If the map is modified while an
1452 * iteration over the set is in progress, the results of the
1453 * iteration are undefined. The set supports element removal,
1454 * which removes the corresponding mapping from the map, via the
1455 * Iterator.remove, Set.remove, removeAll, retainAll, and clear
1456 * operations. It does not support the add or addAll operations.
1457 *
1458 * @return a set view of the keys contained in this map.
1459 */
1460 public Set keySet() {
1461
1462 if (setOfKeys[KEY] == null) {
1463 setOfKeys[KEY] = new AbstractSet() {
1464
1465 public Iterator iterator() {
1466
1467 return new DoubleOrderedMapIterator(KEY) {
1468
1469 protected Object doGetNext() {
1470 return lastReturnedNode.getData(KEY);
1471 }
1472 };
1473 }
1474
1475 public int size() {
1476 return DoubleOrderedMap.this.size();
1477 }
1478
1479 public boolean contains(Object o) {
1480 return containsKey(o);
1481 }
1482
1483 public boolean remove(Object o) {
1484
1485 int oldNodeCount = nodeCount;
1486
1487 DoubleOrderedMap.this.remove(o);
1488
1489 return nodeCount != oldNodeCount;
1490 }
1491
1492 public void clear() {
1493 DoubleOrderedMap.this.clear();
1494 }
1495 };
1496 }
1497
1498 return setOfKeys[KEY];
1499 }
1500
1501 /**
1502 * Returns a collection view of the values contained in this
1503 * map. The collection is backed by the map, so changes to the map
1504 * are reflected in the collection, and vice-versa. If the map is
1505 * modified while an iteration over the collection is in progress,
1506 * the results of the iteration are undefined. The collection
1507 * supports element removal, which removes the corresponding
1508 * mapping from the map, via the Iterator.remove,
1509 * Collection.remove, removeAll, retainAll and clear operations.
1510 * It does not support the add or addAll operations.
1511 *
1512 * @return a collection view of the values contained in this map.
1513 */
1514 public Collection values() {
1515
1516 if (collectionOfValues[KEY] == null) {
1517 collectionOfValues[KEY] = new AbstractCollection() {
1518
1519 public Iterator iterator() {
1520
1521 return new DoubleOrderedMapIterator(KEY) {
1522
1523 protected Object doGetNext() {
1524 return lastReturnedNode.getData(VALUE);
1525 }
1526 };
1527 }
1528
1529 public int size() {
1530 return DoubleOrderedMap.this.size();
1531 }
1532
1533 public boolean contains(Object o) {
1534 return containsValue(o);
1535 }
1536
1537 public boolean remove(Object o) {
1538
1539 int oldNodeCount = nodeCount;
1540
1541 removeValue(o);
1542
1543 return nodeCount != oldNodeCount;
1544 }
1545
1546 public boolean removeAll(Collection c) {
1547
1548 boolean modified = false;
1549 Iterator iter = c.iterator();
1550
1551 while (iter.hasNext()) {
1552 if (removeValue(iter.next()) != null) {
1553 modified = true;
1554 }
1555 }
1556
1557 return modified;
1558 }
1559
1560 public void clear() {
1561 DoubleOrderedMap.this.clear();
1562 }
1563 };
1564 }
1565
1566 return collectionOfValues[KEY];
1567 }
1568
1569 /**
1570 * Returns a set view of the mappings contained in this map. Each
1571 * element in the returned set is a Map.Entry. The set is backed
1572 * by the map, so changes to the map are reflected in the set, and
1573 * vice-versa. If the map is modified while an iteration over the
1574 * set is in progress, the results of the iteration are
1575 * undefined.
1576 * <p>
1577 * The set supports element removal, which removes the corresponding
1578 * mapping from the map, via the Iterator.remove, Set.remove, removeAll,
1579 * retainAll and clear operations.
1580 * It does not support the add or addAll operations.
1581 * The setValue method is not supported on the Map Entry.
1582 *
1583 * @return a set view of the mappings contained in this map.
1584 */
1585 public Set entrySet() {
1586
1587 if (setOfEntries[KEY] == null) {
1588 setOfEntries[KEY] = new AbstractSet() {
1589
1590 public Iterator iterator() {
1591
1592 return new DoubleOrderedMapIterator(KEY) {
1593
1594 protected Object doGetNext() {
1595 return lastReturnedNode;
1596 }
1597 };
1598 }
1599
1600 public boolean contains(Object o) {
1601
1602 if (!(o instanceof Map.Entry)) {
1603 return false;
1604 }
1605
1606 Map.Entry entry = (Map.Entry) o;
1607 Object value = entry.getValue();
1608 Node node = lookup((Comparable) entry.getKey(),
1609 KEY);
1610
1611 return (node != null)
1612 && node.getData(VALUE).equals(value);
1613 }
1614
1615 public boolean remove(Object o) {
1616
1617 if (!(o instanceof Map.Entry)) {
1618 return false;
1619 }
1620
1621 Map.Entry entry = (Map.Entry) o;
1622 Object value = entry.getValue();
1623 Node node = lookup((Comparable) entry.getKey(),
1624 KEY);
1625
1626 if ((node != null) && node.getData(VALUE).equals(value)) {
1627 doRedBlackDelete(node);
1628
1629 return true;
1630 }
1631
1632 return false;
1633 }
1634
1635 public int size() {
1636 return DoubleOrderedMap.this.size();
1637 }
1638
1639 public void clear() {
1640 DoubleOrderedMap.this.clear();
1641 }
1642 };
1643 }
1644
1645 return setOfEntries[KEY];
1646 }
1647
1648 /* ********** END implementation of Map ********** */
1649 private abstract class DoubleOrderedMapIterator implements Iterator {
1650
1651 private int expectedModifications;
1652 protected Node lastReturnedNode;
1653 private Node nextNode;
1654 private int iteratorType;
1655
1656 /**
1657 * Constructor
1658 *
1659 * @param type
1660 */
1661 DoubleOrderedMapIterator(final int type) {
1662
1663 iteratorType = type;
1664 expectedModifications = DoubleOrderedMap.this.modifications;
1665 lastReturnedNode = null;
1666 nextNode = leastNode(rootNode[iteratorType],
1667 iteratorType);
1668 }
1669
1670 /**
1671 * @return 'next', whatever that means for a given kind of
1672 * DoubleOrderedMapIterator
1673 */
1674 protected abstract Object doGetNext();
1675
1676 /* ********** START implementation of Iterator ********** */
1677
1678 /**
1679 * @return true if the iterator has more elements.
1680 */
1681 public final boolean hasNext() {
1682 return nextNode != null;
1683 }
1684
1685 /**
1686 * @return the next element in the iteration.
1687 *
1688 * @throws NoSuchElementException if iteration has no more
1689 * elements.
1690 * @throws ConcurrentModificationException if the
1691 * DoubleOrderedMap is
1692 * modified behind
1693 * the iterator's
1694 * back
1695 */
1696 public final Object next()
1697 throws NoSuchElementException,
1698 ConcurrentModificationException {
1699
1700 if (nextNode == null) {
1701 throw new NoSuchElementException();
1702 }
1703
1704 if (modifications != expectedModifications) {
1705 throw new ConcurrentModificationException();
1706 }
1707
1708 lastReturnedNode = nextNode;
1709 nextNode = nextGreater(nextNode, iteratorType);
1710
1711 return doGetNext();
1712 }
1713
1714 /**
1715 * Removes from the underlying collection the last element
1716 * returned by the iterator. This method can be called only
1717 * once per call to next. The behavior of an iterator is
1718 * unspecified if the underlying collection is modified while
1719 * the iteration is in progress in any way other than by
1720 * calling this method.
1721 *
1722 * @throws IllegalStateException if the next method has not
1723 * yet been called, or the
1724 * remove method has already
1725 * been called after the last
1726 * call to the next method.
1727 * @throws ConcurrentModificationException if the
1728 * DoubleOrderedMap is
1729 * modified behind
1730 * the iterator's
1731 * back
1732 */
1733 public final void remove()
1734 throws IllegalStateException,
1735 ConcurrentModificationException {
1736
1737 if (lastReturnedNode == null) {
1738 throw new IllegalStateException();
1739 }
1740
1741 if (modifications != expectedModifications) {
1742 throw new ConcurrentModificationException();
1743 }
1744
1745 doRedBlackDelete(lastReturnedNode);
1746
1747 expectedModifications++;
1748
1749 lastReturnedNode = null;
1750 }
1751
1752 /* ********** END implementation of Iterator ********** */
1753 } // end private abstract class DoubleOrderedMapIterator
1754
1755 // final for performance
1756 private static final class Node implements Map.Entry, KeyValue {
1757
1758 private Comparable[] data;
1759 private Node[] leftNode;
1760 private Node[] rightNode;
1761 private Node[] parentNode;
1762 private boolean[] blackColor;
1763 private int hashcodeValue;
1764 private boolean calculatedHashCode;
1765
1766 /**
1767 * Make a new cell with given key and value, and with null
1768 * links, and black (true) colors.
1769 *
1770 * @param key
1771 * @param value
1772 */
1773 Node(final Comparable key, final Comparable value) {
1774
1775 data = new Comparable[]{ key, value };
1776 leftNode = new Node[]{ null, null };
1777 rightNode = new Node[]{ null, null };
1778 parentNode = new Node[]{ null, null };
1779 blackColor = new boolean[]{ true, true };
1780 calculatedHashCode = false;
1781 }
1782
1783 /**
1784 * get the specified data
1785 *
1786 * @param index KEY or VALUE
1787 *
1788 * @return the key or value
1789 */
1790 private Comparable getData(final int index) {
1791 return data[index];
1792 }
1793
1794 /**
1795 * Set this node's left node
1796 *
1797 * @param node the new left node
1798 * @param index KEY or VALUE
1799 */
1800 private void setLeft(final Node node, final int index) {
1801 leftNode[index] = node;
1802 }
1803
1804 /**
1805 * get the left node
1806 *
1807 * @param index KEY or VALUE
1808 *
1809 * @return the left node -- may be null
1810 */
1811 private Node getLeft(final int index) {
1812 return leftNode[index];
1813 }
1814
1815 /**
1816 * Set this node's right node
1817 *
1818 * @param node the new right node
1819 * @param index KEY or VALUE
1820 */
1821 private void setRight(final Node node, final int index) {
1822 rightNode[index] = node;
1823 }
1824
1825 /**
1826 * get the right node
1827 *
1828 * @param index KEY or VALUE
1829 *
1830 * @return the right node -- may be null
1831 */
1832 private Node getRight(final int index) {
1833 return rightNode[index];
1834 }
1835
1836 /**
1837 * Set this node's parent node
1838 *
1839 * @param node the new parent node
1840 * @param index KEY or VALUE
1841 */
1842 private void setParent(final Node node, final int index) {
1843 parentNode[index] = node;
1844 }
1845
1846 /**
1847 * get the parent node
1848 *
1849 * @param index KEY or VALUE
1850 *
1851 * @return the parent node -- may be null
1852 */
1853 private Node getParent(final int index) {
1854 return parentNode[index];
1855 }
1856
1857 /**
1858 * exchange colors with another node
1859 *
1860 * @param node the node to swap with
1861 * @param index KEY or VALUE
1862 */
1863 private void swapColors(final Node node, final int index) {
1864
1865 // Swap colors -- old hacker's trick
1866 blackColor[index] ^= node.blackColor[index];
1867 node.blackColor[index] ^= blackColor[index];
1868 blackColor[index] ^= node.blackColor[index];
1869 }
1870
1871 /**
1872 * is this node black?
1873 *
1874 * @param index KEY or VALUE
1875 *
1876 * @return true if black (which is represented as a true boolean)
1877 */
1878 private boolean isBlack(final int index) {
1879 return blackColor[index];
1880 }
1881
1882 /**
1883 * is this node red?
1884 *
1885 * @param index KEY or VALUE
1886 *
1887 * @return true if non-black
1888 */
1889 private boolean isRed(final int index) {
1890 return !blackColor[index];
1891 }
1892
1893 /**
1894 * make this node black
1895 *
1896 * @param index KEY or VALUE
1897 */
1898 private void setBlack(final int index) {
1899 blackColor[index] = true;
1900 }
1901
1902 /**
1903 * make this node red
1904 *
1905 * @param index KEY or VALUE
1906 */
1907 private void setRed(final int index) {
1908 blackColor[index] = false;
1909 }
1910
1911 /**
1912 * make this node the same color as another
1913 *
1914 * @param node the node whose color we're adopting
1915 * @param index KEY or VALUE
1916 */
1917 private void copyColor(final Node node, final int index) {
1918 blackColor[index] = node.blackColor[index];
1919 }
1920
1921 /* ********** START implementation of Map.Entry ********** */
1922
1923 /**
1924 * @return the key corresponding to this entry.
1925 */
1926 public Object getKey() {
1927 return data[KEY];
1928 }
1929
1930 /**
1931 * @return the value corresponding to this entry.
1932 */
1933 public Object getValue() {
1934 return data[VALUE];
1935 }
1936
1937 /**
1938 * Optional operation that is not permitted in this
1939 * implementation
1940 *
1941 * @param ignored
1942 *
1943 * @return does not return
1944 *
1945 * @throws UnsupportedOperationException
1946 */
1947 public Object setValue(Object ignored)
1948 throws UnsupportedOperationException {
1949 throw new UnsupportedOperationException(
1950 "Map.Entry.setValue is not supported");
1951 }
1952
1953 /**
1954 * Compares the specified object with this entry for equality.
1955 * Returns true if the given object is also a map entry and
1956 * the two entries represent the same mapping.
1957 *
1958 * @param o object to be compared for equality with this map
1959 * entry.
1960 * @return true if the specified object is equal to this map
1961 * entry.
1962 */
1963 public boolean equals(Object o) {
1964
1965 if (this == o) {
1966 return true;
1967 }
1968
1969 if (!(o instanceof Map.Entry)) {
1970 return false;
1971 }
1972
1973 Map.Entry e = (Map.Entry) o;
1974
1975 return data[KEY].equals(e.getKey())
1976 && data[VALUE].equals(e.getValue());
1977 }
1978
1979 /**
1980 * @return the hash code value for this map entry.
1981 */
1982 public int hashCode() {
1983
1984 if (!calculatedHashCode) {
1985 hashcodeValue = data[KEY].hashCode()
1986 ^ data[VALUE].hashCode();
1987 calculatedHashCode = true;
1988 }
1989
1990 return hashcodeValue;
1991 }
1992
1993 /* ********** END implementation of Map.Entry ********** */
1994 }
1995 } // end public class DoubleOrderedMap