Java API By Example, From Geeks To Geeks.

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

A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame Popular Tags