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