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.bidimap;
018
019 import java.util.AbstractSet;
020 import java.util.Collection;
021 import java.util.ConcurrentModificationException;
022 import java.util.Iterator;
023 import java.util.Map;
024 import java.util.NoSuchElementException;
025 import java.util.Set;
026
027 import org.apache.commons.collections.BidiMap;
028 import org.apache.commons.collections.KeyValue;
029 import org.apache.commons.collections.MapIterator;
030 import org.apache.commons.collections.OrderedBidiMap;
031 import org.apache.commons.collections.OrderedIterator;
032 import org.apache.commons.collections.OrderedMapIterator;
033 import org.apache.commons.collections.iterators.EmptyOrderedMapIterator;
034 import org.apache.commons.collections.keyvalue.UnmodifiableMapEntry;
035
036 /**
037 * Red-Black tree-based implementation of BidiMap where all objects added
038 * implement the <code>Comparable</code> interface.
039 * <p>
040 * This class guarantees that the map will be in both ascending key order
041 * and ascending value order, sorted according to the natural order for
042 * the key's and value's classes.
043 * <p>
044 * This Map is intended for applications that need to be able to look
045 * up a key-value pairing by either key or value, and need to do so
046 * with equal efficiency.
047 * <p>
048 * While that goal could be accomplished by taking a pair of TreeMaps
049 * and redirecting requests to the appropriate TreeMap (e.g.,
050 * containsKey would be directed to the TreeMap that maps values to
051 * keys, containsValue would be directed to the TreeMap that maps keys
052 * to values), there are problems with that implementation.
053 * If the data contained in the TreeMaps is large, the cost of redundant
054 * storage becomes significant. The {@link DualTreeBidiMap} and
055 * {@link DualHashBidiMap} implementations use this approach.
056 * <p>
057 * This solution keeps minimizes the data storage by holding data only once.
058 * The red-black algorithm is based on java util TreeMap, but has been modified
059 * to simultaneously map a tree node by key and by value. This doubles the
060 * cost of put operations (but so does using two TreeMaps), and nearly doubles
061 * the cost of remove operations (there is a savings in that the lookup of the
062 * node to be removed only has to be performed once). And since only one node
063 * contains the key and value, storage is significantly less than that
064 * required by two TreeMaps.
065 * <p>
066 * The Map.Entry instances returned by the appropriate methods will
067 * not allow setValue() and will throw an
068 * UnsupportedOperationException on attempts to call that method.
069 *
070 * @since Commons Collections 3.0 (previously DoubleOrderedMap v2.0)
071 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
072 *
073 * @author Marc Johnson
074 * @author Stephen Colebourne
075 */
076 public class TreeBidiMap implements OrderedBidiMap {
077
078 private static final int KEY = 0;
079 private static final int VALUE = 1;
080 private static final int MAPENTRY = 2;
081 private static final int INVERSEMAPENTRY = 3;
082 private static final int SUM_OF_INDICES = KEY + VALUE;
083 private static final int FIRST_INDEX = 0;
084 private static final int NUMBER_OF_INDICES = 2;
085 private static final String[] dataName = new String[] { "key", "value" };
086
087 private Node[] rootNode = new Node[2];
088 private int nodeCount = 0;
089 private int modifications = 0;
090 private Set keySet;
091 private Set valuesSet;
092 private Set entrySet;
093 private TreeBidiMap.Inverse inverse = null;
094
095 //-----------------------------------------------------------------------
096 /**
097 * Constructs a new empty TreeBidiMap.
098 */
099 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 }
1193
1194 y.setLeft(xFormerLeftChild, index);
1195 y.setRight(xFormerRightChild, index);
1196 }
1197
1198 if (y == xFormerParent) { // y was x's parent
1199 y.setParent(x, index);
1200
1201 if (xWasLeftChild) {
1202 x.setLeft(y, index);
1203 x.setRight(yFormerRightChild, index);
1204 } else {
1205 x.setRight(y, index);
1206 x.setLeft(yFormerLeftChild, index);
1207 }
1208 } else {
1209 y.setParent(xFormerParent, index);
1210
1211 if (xFormerParent != null) {
1212 if (xWasLeftChild) {
1213 xFormerParent.setLeft(y, index);
1214 } else {
1215 xFormerParent.setRight(y, index);
1216 }
1217 }
1218
1219 x.setLeft(yFormerLeftChild, index);
1220 x.setRight(yFormerRightChild, index);
1221 }
1222
1223 // Fix children's parent pointers
1224 if (x.getLeft(index) != null) {
1225 x.getLeft(index).setParent(x, index);
1226 }
1227
1228 if (x.getRight(index) != null) {
1229 x.getRight(index).setParent(x, index);
1230 }
1231
1232 if (y.getLeft(index) != null) {
1233 y.getLeft(index).setParent(y, index);
1234 }
1235
1236 if (y.getRight(index) != null) {
1237 y.getRight(index).setParent(y, index);
1238 }
1239
1240 x.swapColors(y, index);
1241
1242 // Check if root changed
1243 if (rootNode[index] == x) {
1244 rootNode[index] = y;
1245 } else if (rootNode[index] == y) {
1246 rootNode[index] = x;
1247 }
1248 }
1249
1250 /**
1251 * check if an object is fit to be proper input ... has to be
1252 * Comparable and non-null
1253 *
1254 * @param o the object being checked
1255 * @param index the KEY or VALUE int (used to put the right word in the
1256 * exception message)
1257 *
1258 * @throws NullPointerException if o is null
1259 * @throws ClassCastException if o is not Comparable
1260 */
1261 private static void checkNonNullComparable(final Object o, final int index) {
1262 if (o == null) {
1263 throw new NullPointerException(dataName[index] + " cannot be null");
1264 }
1265 if (!(o instanceof Comparable)) {
1266 throw new ClassCastException(dataName[index] + " must be Comparable");
1267 }
1268 }
1269
1270 /**
1271 * check a key for validity (non-null and implements Comparable)
1272 *
1273 * @param key the key to be checked
1274 *
1275 * @throws NullPointerException if key is null
1276 * @throws ClassCastException if key is not Comparable
1277 */
1278 private static void checkKey(final Object key) {
1279 checkNonNullComparable(key, KEY);
1280 }
1281
1282 /**
1283 * check a value for validity (non-null and implements Comparable)
1284 *
1285 * @param value the value to be checked
1286 *
1287 * @throws NullPointerException if value is null
1288 * @throws ClassCastException if value is not Comparable
1289 */
1290 private static void checkValue(final Object value) {
1291 checkNonNullComparable(value, VALUE);
1292 }
1293
1294 /**
1295 * check a key and a value for validity (non-null and implements
1296 * Comparable)
1297 *
1298 * @param key the key to be checked
1299 * @param value the value to be checked
1300 *
1301 * @throws NullPointerException if key or value is null
1302 * @throws ClassCastException if key or value is not Comparable
1303 */
1304 private static void checkKeyAndValue(final Object key, final Object value) {
1305 checkKey(key);
1306 checkValue(value);
1307 }
1308
1309 /**
1310 * increment the modification count -- used to check for
1311 * concurrent modification of the map through the map and through
1312 * an Iterator from one of its Set or Collection views
1313 */
1314 private void modify() {
1315 modifications++;
1316 }
1317
1318 /**
1319 * bump up the size and note that the map has changed
1320 */
1321 private void grow() {
1322 modify();
1323 nodeCount++;
1324 }
1325
1326 /**
1327 * decrement the size and note that the map has changed
1328 */
1329 private void shrink() {
1330 modify();
1331 nodeCount--;
1332 }
1333
1334 /**
1335 * insert a node by its value
1336 *
1337 * @param newNode the node to be inserted
1338 *
1339 * @throws IllegalArgumentException if the node already exists
1340 * in the value mapping
1341 */
1342 private void insertValue(final Node newNode) throws IllegalArgumentException {
1343 Node node = rootNode[VALUE];
1344
1345 while (true) {
1346 int cmp = compare(newNode.getData(VALUE), node.getData(VALUE));
1347
1348 if (cmp == 0) {
1349 throw new IllegalArgumentException(
1350 "Cannot store a duplicate value (\"" + newNode.getData(VALUE) + "\") in this Map");
1351 } else if (cmp < 0) {
1352 if (node.getLeft(VALUE) != null) {
1353 node = node.getLeft(VALUE);
1354 } else {
1355 node.setLeft(newNode, VALUE);
1356 newNode.setParent(node, VALUE);
1357 doRedBlackInsert(newNode, VALUE);
1358
1359 break;
1360 }
1361 } else { // cmp > 0
1362 if (node.getRight(VALUE) != null) {
1363 node = node.getRight(VALUE);
1364 } else {
1365 node.setRight(newNode, VALUE);
1366 newNode.setParent(node, VALUE);
1367 doRedBlackInsert(newNode, VALUE);
1368
1369 break;
1370 }
1371 }
1372 }
1373 }
1374
1375 //-----------------------------------------------------------------------
1376 /**
1377 * Compares for equals as per the API.
1378 *
1379 * @param obj the object to compare to
1380 * @param type the KEY or VALUE int
1381 * @return true if equal
1382 */
1383 private boolean doEquals(Object obj, final int type) {
1384 if (obj == this) {
1385 return true;
1386 }
1387 if (obj instanceof Map == false) {
1388 return false;
1389 }
1390 Map other = (Map) obj;
1391 if (other.size() != size()) {
1392 return false;
1393 }
1394
1395 if (nodeCount > 0) {
1396 try {
1397 for (MapIterator it = new ViewMapIterator(this, type); it.hasNext(); ) {
1398 Object key = it.next();
1399 Object value = it.getValue();
1400 if (value.equals(other.get(key)) == false) {
1401 return false;
1402 }
1403 }
1404 } catch (ClassCastException ex) {
1405 return false;
1406 } catch (NullPointerException ex) {
1407 return false;
1408 }
1409 }
1410 return true;
1411 }
1412
1413 /**
1414 * Gets the hash code value for this map as per the API.
1415 *
1416 * @param type the KEY or VALUE int
1417 * @return the hash code value for this map
1418 */
1419 private int doHashCode(final int type) {
1420 int total = 0;
1421 if (nodeCount > 0) {
1422 for (MapIterator it = new ViewMapIterator(this, type); it.hasNext(); ) {
1423 Object key = it.next();
1424 Object value = it.getValue();
1425 total += (key.hashCode() ^ value.hashCode());
1426 }
1427 }
1428 return total;
1429 }
1430
1431 /**
1432 * Gets the string form of this map as per AbstractMap.
1433 *
1434 * @param type the KEY or VALUE int
1435 * @return the string form of this map
1436 */
1437 private String doToString(final int type) {
1438 if (nodeCount == 0) {
1439 return "{}";
1440 }
1441 StringBuffer buf = new StringBuffer(nodeCount * 32);
1442 buf.append('{');
1443 MapIterator it = new ViewMapIterator(this, type);
1444 boolean hasNext = it.hasNext();
1445 while (hasNext) {
1446 Object key = it.next();
1447 Object value = it.getValue();
1448 buf.append(key == this ? "(this Map)" : key)
1449 .append('=')
1450 .append(value == this ? "(this Map)" : value);
1451
1452 hasNext = it.hasNext();
1453 if (hasNext) {
1454 buf.append(", ");
1455 }
1456 }
1457
1458 buf.append('}');
1459 return buf.toString();
1460 }
1461
1462 //-----------------------------------------------------------------------
1463 /**
1464 * A view of this map.
1465 */
1466 static class View extends AbstractSet {
1467
1468 /** The parent map. */
1469 protected final TreeBidiMap main;
1470 /** Whether to return KEY or VALUE order. */
1471 protected final int orderType;
1472 /** Whether to return KEY, VALUE, MAPENTRY or INVERSEMAPENTRY data. */
1473 protected final int dataType;
1474
1475 /**
1476 * Constructor.
1477 *
1478 * @param main the main map
1479 * @param orderType the KEY or VALUE int for the order
1480 * @param dataType the KEY, VALUE, MAPENTRY or INVERSEMAPENTRY int
1481 */
1482 View(final TreeBidiMap main, final int orderType, final int dataType) {
1483 super();
1484 this.main = main;
1485 this.orderType = orderType;
1486 this.dataType = dataType;
1487 }
1488
1489 public Iterator iterator() {
1490 return new ViewIterator(main, orderType, dataType);
1491 }
1492
1493 public int size() {
1494 return main.size();
1495 }
1496
1497 public boolean contains(final Object obj) {
1498 checkNonNullComparable(obj, dataType);
1499 return (main.lookup((Comparable) obj, dataType) != null);
1500 }
1501
1502 public boolean remove(final Object obj) {
1503 return (main.doRemove((Comparable) obj, dataType) != null);
1504 }
1505
1506 public void clear() {
1507 main.clear();
1508 }
1509 }
1510
1511 //-----------------------------------------------------------------------
1512 /**
1513 * An iterator over the map.
1514 */
1515 static class ViewIterator implements OrderedIterator {
1516
1517 /** The parent map. */
1518 protected final TreeBidiMap main;
1519 /** Whether to return KEY or VALUE order. */
1520 protected final int orderType;
1521 /** Whether to return KEY, VALUE, MAPENTRY or INVERSEMAPENTRY data. */
1522 protected final int dataType;
1523 /** The last node returned by the iterator. */
1524 protected Node lastReturnedNode;
1525 /** The next node to be returned by the iterator. */
1526 protected Node nextNode;
1527 /** The previous node in the sequence returned by the iterator. */
1528 protected Node previousNode;
1529 /** The modification count. */
1530 private int expectedModifications;
1531
1532 /**
1533 * Constructor.
1534 *
1535 * @param main the main map
1536 * @param orderType the KEY or VALUE int for the order
1537 * @param dataType the KEY, VALUE, MAPENTRY or INVERSEMAPENTRY int
1538 */
1539 ViewIterator(final TreeBidiMap main, final int orderType, final int dataType) {
1540 super();
1541 this.main = main;
1542 this.orderType = orderType;
1543 this.dataType = dataType;
1544 expectedModifications = main.modifications;
1545 nextNode = leastNode(main.rootNode[orderType], orderType);
1546 lastReturnedNode = null;
1547 previousNode = null;
1548 }
1549
1550 public final boolean hasNext() {
1551 return (nextNode != null);
1552 }
1553
1554 public final Object next() {
1555 if (nextNode == null) {
1556 throw new NoSuchElementException();
1557 }
1558 if (main.modifications != expectedModifications) {
1559 throw new ConcurrentModificationException();
1560 }
1561 lastReturnedNode = nextNode;
1562 previousNode = nextNode;
1563 nextNode = main.nextGreater(nextNode, orderType);
1564 return doGetData();
1565 }
1566
1567 public boolean hasPrevious() {
1568 return (previousNode != null);
1569 }
1570
1571 public Object previous() {
1572 if (previousNode == null) {
1573 throw new NoSuchElementException();
1574 }
1575 if (main.modifications != expectedModifications) {
1576 throw new ConcurrentModificationException();
1577 }
1578 nextNode = lastReturnedNode;
1579 if (nextNode == null) {
1580 nextNode = main.nextGreater(previousNode, orderType);
1581 }
1582 lastReturnedNode = previousNode;
1583 previousNode = main.nextSmaller(previousNode, orderType);
1584 return doGetData();
1585 }
1586
1587 /**
1588 * Gets the data value for the lastReturnedNode field.
1589 * @return the data value
1590 */
1591 protected Object doGetData() {
1592 switch (dataType) {
1593 case KEY:
1594 return lastReturnedNode.getKey();
1595 case VALUE:
1596 return lastReturnedNode.getValue();
1597 case MAPENTRY:
1598 return lastReturnedNode;
1599 case INVERSEMAPENTRY:
1600 return new UnmodifiableMapEntry(lastReturnedNode.getValue(), lastReturnedNode.getKey());
1601 }
1602 return null;
1603 }
1604
1605 public final void remove() {
1606 if (lastReturnedNode == null) {
1607 throw new IllegalStateException();
1608 }
1609 if (main.modifications != expectedModifications) {
1610 throw new ConcurrentModificationException();
1611 }
1612 main.doRedBlackDelete(lastReturnedNode);
1613 expectedModifications++;
1614 lastReturnedNode = null;
1615 if (nextNode == null) {
1616 previousNode = TreeBidiMap.greatestNode(main.rootNode[orderType], orderType);
1617 } else {
1618 previousNode = main.nextSmaller(nextNode, orderType);
1619 }
1620 }
1621 }
1622
1623 //-----------------------------------------------------------------------
1624 /**
1625 * An iterator over the map.
1626 */
1627 static class ViewMapIterator extends ViewIterator implements OrderedMapIterator {
1628
1629 private final int oppositeType;
1630
1631 /**
1632 * Constructor.
1633 *
1634 * @param main the main map
1635 * @param orderType the KEY or VALUE int for the order
1636 */
1637 ViewMapIterator(final TreeBidiMap main, final int orderType) {
1638 super(main, orderType, orderType);
1639 this.oppositeType = oppositeIndex(dataType);
1640 }
1641
1642 public Object getKey() {
1643 if (lastReturnedNode == null) {
1644 throw new IllegalStateException("Iterator getKey() can only be called after next() and before remove()");
1645 }
1646 return lastReturnedNode.getData(dataType);
1647 }
1648
1649 public Object getValue() {
1650 if (lastReturnedNode == null) {
1651 throw new IllegalStateException("Iterator getValue() can only be called after next() and before remove()");
1652 }
1653 return lastReturnedNode.getData(oppositeType);
1654 }
1655
1656 public Object setValue(final Object obj) {
1657 throw new UnsupportedOperationException();
1658 }
1659 }
1660
1661 //-----------------------------------------------------------------------
1662 /**
1663 * A view of this map.
1664 */
1665 static class EntryView extends View {
1666
1667 private final int oppositeType;
1668
1669 /**
1670 * Constructor.
1671 *
1672 * @param main the main map
1673 * @param orderType the KEY or VALUE int for the order
1674 * @param dataType the MAPENTRY or INVERSEMAPENTRY int for the returned data
1675 */
1676 EntryView(final TreeBidiMap main, final int orderType, final int dataType) {
1677 super(main, orderType, dataType);
1678 this.oppositeType = TreeBidiMap.oppositeIndex(orderType);
1679 }
1680
1681 public boolean contains(Object obj) {
1682 if (obj instanceof Map.Entry == false) {
1683 return false;
1684 }
1685 Map.Entry entry = (Map.Entry) obj;
1686 Object value = entry.getValue();
1687 Node node = main.lookup((Comparable) entry.getKey(), orderType);
1688 return (node != null && node.getData(oppositeType).equals(value));
1689 }
1690
1691 public boolean remove(Object obj) {
1692 if (obj instanceof Map.Entry == false) {
1693 return false;
1694 }
1695 Map.Entry entry = (Map.Entry) obj;
1696 Object value = entry.getValue();
1697 Node node = main.lookup((Comparable) entry.getKey(), orderType);
1698 if (node != null && node.getData(oppositeType).equals(value)) {
1699 main.doRedBlackDelete(node);
1700 return true;
1701 }
1702 return false;
1703 }
1704 }
1705
1706 //-----------------------------------------------------------------------
1707 /**
1708 * A node used to store the data.
1709 */
1710 static class Node implements Map.Entry, KeyValue {
1711
1712 private Comparable[] data;
1713 private Node[] leftNode;
1714 private Node[] rightNode;
1715 private Node[] parentNode;
1716 private boolean[] blackColor;
1717 private int hashcodeValue;
1718 private boolean calculatedHashCode;
1719
1720 /**
1721 * Make a new cell with given key and value, and with null
1722 * links, and black (true) colors.
1723 *
1724 * @param key
1725 * @param value
1726 */
1727 Node(final Comparable key, final Comparable value) {
1728 super();
1729 data = new Comparable[] { key, value };
1730 leftNode = new Node[2];
1731 rightNode = new Node[2];
1732 parentNode = new Node[2];
1733 blackColor = new boolean[] { true, true };
1734 calculatedHashCode = false;
1735 }
1736
1737 /**
1738 * Get the specified data.
1739 *
1740 * @param index the KEY or VALUE int
1741 * @return the key or value
1742 */
1743 private Comparable getData(final int index) {
1744 return data[index];
1745 }
1746
1747 /**
1748 * Set this node's left node.
1749 *
1750 * @param node the new left node
1751 * @param index the KEY or VALUE int
1752 */
1753 private void setLeft(final Node node, final int index) {
1754 leftNode[index] = node;
1755 }
1756
1757 /**
1758 * Get the left node.
1759 *
1760 * @param index the KEY or VALUE int
1761 * @return the left node, may be null
1762 */
1763 private Node getLeft(final int index) {
1764 return leftNode[index];
1765 }
1766
1767 /**
1768 * Set this node's right node.
1769 *
1770 * @param node the new right node
1771 * @param index the KEY or VALUE int
1772 */
1773 private void setRight(final Node node, final int index) {
1774 rightNode[index] = node;
1775 }
1776
1777 /**
1778 * Get the right node.
1779 *
1780 * @param index the KEY or VALUE int
1781 * @return the right node, may be null
1782 */
1783 private Node getRight(final int index) {
1784 return rightNode[index];
1785 }
1786
1787 /**
1788 * Set this node's parent node.
1789 *
1790 * @param node the new parent node
1791 * @param index the KEY or VALUE int
1792 */
1793 private void setParent(final Node node, final int index) {
1794 parentNode[index] = node;
1795 }
1796
1797 /**
1798 * Get the parent node.
1799 *
1800 * @param index the KEY or VALUE int
1801 * @return the parent node, may be null
1802 */
1803 private Node getParent(final int index) {
1804 return parentNode[index];
1805 }
1806
1807 /**
1808 * Exchange colors with another node.
1809 *
1810 * @param node the node to swap with
1811 * @param index the KEY or VALUE int
1812 */
1813 private void swapColors(final Node node, final int index) {
1814 // Swap colors -- old hacker's trick
1815 blackColor[index] ^= node.blackColor[index];
1816 node.blackColor[index] ^= blackColor[index];
1817 blackColor[index] ^= node.blackColor[index];
1818 }
1819
1820 /**
1821 * Is this node black?
1822 *
1823 * @param index the KEY or VALUE int
1824 * @return true if black (which is represented as a true boolean)
1825 */
1826 private boolean isBlack(final int index) {
1827 return blackColor[index];
1828 }
1829
1830 /**
1831 * Is this node red?
1832 *
1833 * @param index the KEY or VALUE int
1834 * @return true if non-black
1835 */
1836 private boolean isRed(final int index) {
1837 return !blackColor[index];
1838 }
1839
1840 /**
1841 * Make this node black.
1842 *
1843 * @param index the KEY or VALUE int
1844 */
1845 private void setBlack(final int index) {
1846 blackColor[index] = true;
1847 }
1848
1849 /**
1850 * Make this node red.
1851 *
1852 * @param index the KEY or VALUE int
1853 */
1854 private void setRed(final int index) {
1855 blackColor[index] = false;
1856 }
1857
1858 /**
1859 * Make this node the same color as another
1860 *
1861 * @param node the node whose color we're adopting
1862 * @param index the KEY or VALUE int
1863 */
1864 private void copyColor(final Node node, final int index) {
1865 blackColor[index] = node.blackColor[index];
1866 }
1867
1868 //-------------------------------------------------------------------
1869 /**
1870 * Gets the key.
1871 *
1872 * @return the key corresponding to this entry.
1873 */
1874 public Object getKey() {
1875 return data[KEY];
1876 }
1877
1878 /**
1879 * Gets the value.
1880 *
1881 * @return the value corresponding to this entry.
1882 */
1883 public Object getValue() {
1884 return data[VALUE];
1885 }
1886
1887 /**
1888 * Optional operation that is not permitted in this implementation
1889 *
1890 * @param ignored
1891 * @return does not return
1892 * @throws UnsupportedOperationException always
1893 */
1894 public Object setValue(final Object ignored)
1895 throws UnsupportedOperationException {
1896 throw new UnsupportedOperationException(
1897 "Map.Entry.setValue is not supported");
1898 }
1899
1900 /**
1901 * Compares the specified object with this entry for equality.
1902 * Returns true if the given object is also a map entry and
1903 * the two entries represent the same mapping.
1904 *
1905 * @param obj the object to be compared for equality with this entry.
1906 * @return true if the specified object is equal to this entry.
1907 */
1908 public boolean equals(final Object obj) {
1909 if (obj == this) {
1910 return true;
1911 }
1912 if (!(obj instanceof Map.Entry)) {
1913 return false;
1914 }
1915 Map.Entry e = (Map.Entry) obj;
1916 return data[KEY].equals(e.getKey()) && data[VALUE].equals(e.getValue());
1917 }
1918
1919 /**
1920 * @return the hash code value for this map entry.
1921 */
1922 public int hashCode() {
1923 if (!calculatedHashCode) {
1924 hashcodeValue = data[KEY].hashCode() ^ data[VALUE].hashCode();
1925 calculatedHashCode = true;
1926 }
1927 return hashcodeValue;
1928 }
1929 }
1930
1931 //-----------------------------------------------------------------------
1932 /**
1933 * A node used to store the data.
1934 */
1935 static class Inverse implements OrderedBidiMap {
1936
1937 /** The parent map. */
1938 private final TreeBidiMap main;
1939 /** Store the keySet once created. */
1940 private Set keySet;
1941 /** Store the valuesSet once created. */
1942 private Set valuesSet;
1943 /** Store the entrySet once created. */
1944 private Set entrySet;
1945
1946 /**
1947 * Constructor.
1948 * @param main the main map
1949 */
1950 Inverse(final TreeBidiMap main) {
1951 super();
1952 this.main = main;
1953 }
1954
1955 public int size() {
1956 return main.size();
1957 }
1958
1959 public boolean isEmpty() {
1960 return main.isEmpty();
1961 }
1962
1963 public Object get(final Object key) {
1964 return main.getKey(key);
1965 }
1966
1967 public Object getKey(final Object value) {
1968 return main.get(value);
1969 }
1970
1971 public boolean containsKey(final Object key) {
1972 return main.containsValue(key);
1973 }
1974
1975 public boolean containsValue(final Object value) {
1976 return main.containsKey(value);
1977 }
1978
1979 public Object firstKey() {
1980 if (main.nodeCount == 0) {
1981 throw new NoSuchElementException("Map is empty");
1982 }
1983 return TreeBidiMap.leastNode(main.rootNode[VALUE], VALUE).getValue();
1984 }
1985
1986 public Object lastKey() {
1987 if (main.nodeCount == 0) {
1988 throw new NoSuchElementException("Map is empty");
1989 }
1990 return TreeBidiMap.greatestNode(main.rootNode[VALUE], VALUE).getValue();
1991 }
1992
1993 public Object nextKey(Object key) {
1994 checkKey(key);
1995 Node node = main.nextGreater(main.lookup((Comparable) key, VALUE), VALUE);
1996 return (node == null ? null : node.getValue());
1997 }
1998
1999 public Object previousKey(Object key) {
2000 checkKey(key);
2001 Node node = main.nextSmaller(main.lookup((Comparable) key, VALUE), VALUE);
2002 return (node == null ? null : node.getValue());
2003 }
2004
2005 public Object put(final Object key, final Object value) {
2006 return main.doPut((Comparable) value, (Comparable) key, VALUE);
2007 }
2008
2009 public void putAll(Map map) {
2010 Iterator it = map.entrySet().iterator();
2011 while (it.hasNext()) {
2012 Map.Entry entry = (Map.Entry) it.next();
2013 put(entry.getKey(), entry.getValue());
2014 }
2015 }
2016
2017 public Object remove(final Object key) {
2018 return main.removeValue(key);
2019 }
2020
2021 public Object removeValue(final Object value) {
2022 return main.remove(value);
2023 }
2024
2025 public void clear() {
2026 main.clear();
2027 }
2028
2029 public Set keySet() {
2030 if (keySet == null) {
2031 keySet = new View(main, VALUE, VALUE);
2032 }
2033 return keySet;
2034 }
2035
2036 public Collection values() {
2037 if (valuesSet == null) {
2038 valuesSet = new View(main, VALUE, KEY);
2039 }
2040 return valuesSet;
2041 }
2042
2043 public Set entrySet() {
2044 if (entrySet == null) {
2045 return new EntryView(main, VALUE, INVERSEMAPENTRY);
2046 }
2047 return entrySet;
2048 }
2049
2050 public MapIterator mapIterator() {
2051 if (isEmpty()) {
2052 return EmptyOrderedMapIterator.INSTANCE;
2053 }
2054 return new ViewMapIterator(main, VALUE);
2055 }
2056
2057 public OrderedMapIterator orderedMapIterator() {
2058 if (isEmpty()) {
2059 return EmptyOrderedMapIterator.INSTANCE;
2060 }
2061 return new ViewMapIterator(main, VALUE);
2062 }
2063
2064 public BidiMap inverseBidiMap() {
2065 return main;
2066 }
2067
2068 public OrderedBidiMap inverseOrderedBidiMap() {
2069 return main;
2070 }
2071
2072 public boolean equals(Object obj) {
2073 return main.doEquals(obj, VALUE);
2074 }
2075
2076 public int hashCode() {
2077 return main.doHashCode(VALUE);
2078 }
2079
2080 public String toString() {
2081 return main.doToString(VALUE);
2082 }
2083 }
2084
2085 }