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 }