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