1/* 2 * Copyright (C) 2010 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package java.util; 18 19import java.io.IOException; 20import java.io.ObjectInputStream; 21import java.io.ObjectInputStream.GetField; 22import java.io.ObjectOutputStream; 23import java.io.ObjectStreamException; 24import java.io.Serializable; 25import static java.util.TreeMap.Bound.*; 26import static java.util.TreeMap.Relation.*; 27import libcore.util.Objects; 28 29/** 30 * A map whose entries are sorted by their keys. All optional operations such as 31 * {@link #put} and {@link #remove} are supported. 32 * 33 * <p>This map sorts keys using either a user-supplied comparator or the key's 34 * natural order: 35 * <ul> 36 * <li>User supplied comparators must be able to compare any pair of keys in 37 * this map. If a user-supplied comparator is in use, it will be returned 38 * by {@link #comparator}. 39 * <li>If no user-supplied comparator is supplied, keys will be sorted by 40 * their natural order. Keys must be <i>mutually comparable</i>: they must 41 * implement {@link Comparable} and {@link Comparable#compareTo 42 * compareTo()} must be able to compare each key with any other key in 43 * this map. In this case {@link #comparator} will return null. 44 * </ul> 45 * With either a comparator or a natural ordering, comparisons should be 46 * <i>consistent with equals</i>. An ordering is consistent with equals if for 47 * every pair of keys {@code a} and {@code b}, {@code a.equals(b)} if and only 48 * if {@code compare(a, b) == 0}. 49 * 50 * <p>When the ordering is not consistent with equals the behavior of this 51 * class is well defined but does not honor the contract specified by {@link 52 * Map}. Consider a tree map of case-insensitive strings, an ordering that is 53 * not consistent with equals: <pre> {@code 54 * TreeMap<String, String> map = new TreeMap<String, String>(String.CASE_INSENSITIVE_ORDER); 55 * map.put("a", "android"); 56 * 57 * // The Map API specifies that the next line should print "null" because 58 * // "a".equals("A") is false and there is no mapping for upper case "A". 59 * // But the case insensitive ordering says compare("a", "A") == 0. TreeMap 60 * // uses only comparators/comparable on keys and so this prints "android". 61 * System.out.println(map.get("A")); 62 * }</pre> 63 * 64 * @since 1.2 65 */ 66public class TreeMap<K, V> extends AbstractMap<K, V> 67 implements SortedMap<K, V>, NavigableMap<K, V>, Cloneable, Serializable { 68 69 @SuppressWarnings("unchecked") // to avoid Comparable<Comparable<Comparable<...>>> 70 private static final Comparator<Comparable> NATURAL_ORDER = new Comparator<Comparable>() { 71 public int compare(Comparable a, Comparable b) { 72 return a.compareTo(b); 73 } 74 }; 75 76 Comparator<? super K> comparator; 77 Node<K, V> root; 78 int size = 0; 79 int modCount = 0; 80 81 /** 82 * Create a natural order, empty tree map whose keys must be mutually 83 * comparable and non-null. 84 */ 85 @SuppressWarnings("unchecked") // unsafe! this assumes K is comparable 86 public TreeMap() { 87 this.comparator = (Comparator<? super K>) NATURAL_ORDER; 88 } 89 90 /** 91 * Create a natural order tree map populated with the key/value pairs of 92 * {@code copyFrom}. This map's keys must be mutually comparable and 93 * non-null. 94 * 95 * <p>Even if {@code copyFrom} is a {@code SortedMap}, the constructed map 96 * <strong>will not</strong> use {@code copyFrom}'s ordering. This 97 * constructor always creates a naturally-ordered map. Because the {@code 98 * TreeMap} constructor overloads are ambiguous, prefer to construct a map 99 * and populate it in two steps: <pre> {@code 100 * TreeMap<String, Integer> customOrderedMap 101 * = new TreeMap<String, Integer>(copyFrom.comparator()); 102 * customOrderedMap.putAll(copyFrom); 103 * }</pre> 104 */ 105 public TreeMap(Map<? extends K, ? extends V> copyFrom) { 106 this(); 107 for (Map.Entry<? extends K, ? extends V> entry : copyFrom.entrySet()) { 108 putInternal(entry.getKey(), entry.getValue()); 109 } 110 } 111 112 /** 113 * Create a tree map ordered by {@code comparator}. This map's keys may only 114 * be null if {@code comparator} permits. 115 * 116 * @param comparator the comparator to order elements with, or {@code null} to use the natural 117 * ordering. 118 */ 119 @SuppressWarnings("unchecked") // unsafe! if comparator is null, this assumes K is comparable 120 public TreeMap(Comparator<? super K> comparator) { 121 if (comparator != null) { 122 this.comparator = comparator; 123 } else { 124 this.comparator = (Comparator<? super K>) NATURAL_ORDER; 125 } 126 } 127 128 /** 129 * Create a tree map with the ordering and key/value pairs of {@code 130 * copyFrom}. This map's keys may only be null if the {@code copyFrom}'s 131 * ordering permits. 132 * 133 * <p>The constructed map <strong>will always use</strong> {@code 134 * copyFrom}'s ordering. Because the {@code TreeMap} constructor overloads 135 * are ambiguous, prefer to construct a map and populate it in two steps: 136 * <pre> {@code 137 * TreeMap<String, Integer> customOrderedMap 138 * = new TreeMap<String, Integer>(copyFrom.comparator()); 139 * customOrderedMap.putAll(copyFrom); 140 * }</pre> 141 */ 142 @SuppressWarnings("unchecked") // if copyFrom's keys are comparable this map's keys must be also 143 public TreeMap(SortedMap<K, ? extends V> copyFrom) { 144 Comparator<? super K> sourceComparator = copyFrom.comparator(); 145 if (sourceComparator != null) { 146 this.comparator = sourceComparator; 147 } else { 148 this.comparator = (Comparator<? super K>) NATURAL_ORDER; 149 } 150 for (Map.Entry<K, ? extends V> entry : copyFrom.entrySet()) { 151 putInternal(entry.getKey(), entry.getValue()); 152 } 153 } 154 155 @Override public Object clone() { 156 try { 157 @SuppressWarnings("unchecked") // super.clone() must return the same type 158 TreeMap<K, V> map = (TreeMap<K, V>) super.clone(); 159 map.root = root != null ? root.copy(null) : null; 160 map.entrySet = null; 161 map.keySet = null; 162 return map; 163 } catch (CloneNotSupportedException e) { 164 throw new AssertionError(); 165 } 166 } 167 168 @Override public int size() { 169 return size; 170 } 171 172 @Override public boolean isEmpty() { 173 return size == 0; 174 } 175 176 @Override public V get(Object key) { 177 Entry<K, V> entry = findByObject(key); 178 return entry != null ? entry.getValue() : null; 179 } 180 181 @Override public boolean containsKey(Object key) { 182 return findByObject(key) != null; 183 } 184 185 @Override public V put(K key, V value) { 186 return putInternal(key, value); 187 } 188 189 @Override public void clear() { 190 root = null; 191 size = 0; 192 modCount++; 193 } 194 195 @Override public V remove(Object key) { 196 Node<K, V> node = removeInternalByKey(key); 197 return node != null ? node.value : null; 198 } 199 200 /* 201 * AVL methods 202 */ 203 204 enum Relation { 205 LOWER, 206 FLOOR, 207 EQUAL, 208 CREATE, 209 CEILING, 210 HIGHER; 211 212 /** 213 * Returns a possibly-flipped relation for use in descending views. 214 * 215 * @param ascending false to flip; true to return this. 216 */ 217 Relation forOrder(boolean ascending) { 218 if (ascending) { 219 return this; 220 } 221 222 switch (this) { 223 case LOWER: 224 return HIGHER; 225 case FLOOR: 226 return CEILING; 227 case EQUAL: 228 return EQUAL; 229 case CEILING: 230 return FLOOR; 231 case HIGHER: 232 return LOWER; 233 default: 234 throw new IllegalStateException(); 235 } 236 } 237 } 238 239 V putInternal(K key, V value) { 240 Node<K, V> created = find(key, Relation.CREATE); 241 V result = created.value; 242 created.value = value; 243 return result; 244 } 245 246 /** 247 * Returns the node at or adjacent to the given key, creating it if requested. 248 * 249 * @throws ClassCastException if {@code key} and the tree's keys aren't mutually comparable. 250 */ 251 Node<K, V> find(K key, Relation relation) { 252 if (root == null) { 253 if (comparator == NATURAL_ORDER && !(key instanceof Comparable)) { 254 throw new ClassCastException(key.getClass().getName() + " is not Comparable"); // NullPointerException ok 255 } 256 if (relation == Relation.CREATE) { 257 root = new Node<K, V>(null, key); 258 size = 1; 259 modCount++; 260 return root; 261 } else { 262 return null; 263 } 264 } 265 266 /* 267 * Micro-optimization: avoid polymorphic calls to Comparator.compare(). 268 * This is 10% faster for naturally ordered trees. 269 */ 270 @SuppressWarnings("unchecked") // will throw a ClassCastException below if there's trouble 271 Comparable<Object> comparableKey = (comparator == NATURAL_ORDER) 272 ? (Comparable<Object>) key 273 : null; 274 275 Node<K, V> nearest = root; 276 while (true) { 277 int comparison = (comparableKey != null) 278 ? comparableKey.compareTo(nearest.key) 279 : comparator.compare(key, nearest.key); 280 281 /* 282 * We found the requested key. 283 */ 284 if (comparison == 0) { 285 switch (relation) { 286 case LOWER: 287 return nearest.prev(); 288 case FLOOR: 289 case EQUAL: 290 case CREATE: 291 case CEILING: 292 return nearest; 293 case HIGHER: 294 return nearest.next(); 295 } 296 } 297 298 Node<K, V> child = (comparison < 0) ? nearest.left : nearest.right; 299 if (child != null) { 300 nearest = child; 301 continue; 302 } 303 304 /* 305 * We found a nearest node. Every key not in the tree has up to two 306 * nearest nodes, one lower and one higher. 307 */ 308 309 if (comparison < 0) { // nearest.key is higher 310 switch (relation) { 311 case LOWER: 312 case FLOOR: 313 return nearest.prev(); 314 case CEILING: 315 case HIGHER: 316 return nearest; 317 case EQUAL: 318 return null; 319 case CREATE: 320 Node<K, V> created = new Node<K, V>(nearest, key); 321 nearest.left = created; 322 size++; 323 modCount++; 324 rebalance(nearest, true); 325 return created; 326 } 327 } else { // comparison > 0, nearest.key is lower 328 switch (relation) { 329 case LOWER: 330 case FLOOR: 331 return nearest; 332 case CEILING: 333 case HIGHER: 334 return nearest.next(); 335 case EQUAL: 336 return null; 337 case CREATE: 338 Node<K, V> created = new Node<K, V>(nearest, key); 339 nearest.right = created; 340 size++; 341 modCount++; 342 rebalance(nearest, true); 343 return created; 344 } 345 } 346 } 347 } 348 349 @SuppressWarnings("unchecked") // this method throws ClassCastExceptions! 350 Node<K, V> findByObject(Object key) { 351 return find((K) key, EQUAL); 352 } 353 354 /** 355 * Returns this map's entry that has the same key and value as {@code 356 * entry}, or null if this map has no such entry. 357 * 358 * <p>This method uses the comparator for key equality rather than {@code 359 * equals}. If this map's comparator isn't consistent with equals (such as 360 * {@code String.CASE_INSENSITIVE_ORDER}), then {@code remove()} and {@code 361 * contains()} will violate the collections API. 362 */ 363 Node<K, V> findByEntry(Entry<?, ?> entry) { 364 Node<K, V> mine = findByObject(entry.getKey()); 365 boolean valuesEqual = mine != null && Objects.equal(mine.value, entry.getValue()); 366 return valuesEqual ? mine : null; 367 } 368 369 /** 370 * Removes {@code node} from this tree, rearranging the tree's structure as 371 * necessary. 372 */ 373 void removeInternal(Node<K, V> node) { 374 Node<K, V> left = node.left; 375 Node<K, V> right = node.right; 376 Node<K, V> originalParent = node.parent; 377 if (left != null && right != null) { 378 379 /* 380 * To remove a node with both left and right subtrees, move an 381 * adjacent node from one of those subtrees into this node's place. 382 * 383 * Removing the adjacent node may change this node's subtrees. This 384 * node may no longer have two subtrees once the adjacent node is 385 * gone! 386 */ 387 388 Node<K, V> adjacent = (left.height > right.height) ? left.last() : right.first(); 389 removeInternal(adjacent); // takes care of rebalance and size-- 390 391 int leftHeight = 0; 392 left = node.left; 393 if (left != null) { 394 leftHeight = left.height; 395 adjacent.left = left; 396 left.parent = adjacent; 397 node.left = null; 398 } 399 int rightHeight = 0; 400 right = node.right; 401 if (right != null) { 402 rightHeight = right.height; 403 adjacent.right = right; 404 right.parent = adjacent; 405 node.right = null; 406 } 407 adjacent.height = Math.max(leftHeight, rightHeight) + 1; 408 replaceInParent(node, adjacent); 409 return; 410 } else if (left != null) { 411 replaceInParent(node, left); 412 node.left = null; 413 } else if (right != null) { 414 replaceInParent(node, right); 415 node.right = null; 416 } else { 417 replaceInParent(node, null); 418 } 419 420 rebalance(originalParent, false); 421 size--; 422 modCount++; 423 } 424 425 Node<K, V> removeInternalByKey(Object key) { 426 Node<K, V> node = findByObject(key); 427 if (node != null) { 428 removeInternal(node); 429 } 430 return node; 431 } 432 433 private void replaceInParent(Node<K, V> node, Node<K, V> replacement) { 434 Node<K, V> parent = node.parent; 435 node.parent = null; 436 if (replacement != null) { 437 replacement.parent = parent; 438 } 439 440 if (parent != null) { 441 if (parent.left == node) { 442 parent.left = replacement; 443 } else { 444 // assert (parent.right == node); 445 parent.right = replacement; 446 } 447 } else { 448 root = replacement; 449 } 450 } 451 452 /** 453 * Rebalances the tree by making any AVL rotations necessary between the 454 * newly-unbalanced node and the tree's root. 455 * 456 * @param insert true if the node was unbalanced by an insert; false if it 457 * was by a removal. 458 */ 459 private void rebalance(Node<K, V> unbalanced, boolean insert) { 460 for (Node<K, V> node = unbalanced; node != null; node = node.parent) { 461 Node<K, V> left = node.left; 462 Node<K, V> right = node.right; 463 int leftHeight = left != null ? left.height : 0; 464 int rightHeight = right != null ? right.height : 0; 465 466 int delta = leftHeight - rightHeight; 467 if (delta == -2) { 468 Node<K, V> rightLeft = right.left; 469 Node<K, V> rightRight = right.right; 470 int rightRightHeight = rightRight != null ? rightRight.height : 0; 471 int rightLeftHeight = rightLeft != null ? rightLeft.height : 0; 472 473 int rightDelta = rightLeftHeight - rightRightHeight; 474 if (rightDelta == -1 || (rightDelta == 0 && !insert)) { 475 rotateLeft(node); // AVL right right 476 } else { 477 // assert (rightDelta == 1); 478 rotateRight(right); // AVL right left 479 rotateLeft(node); 480 } 481 if (insert) { 482 break; // no further rotations will be necessary 483 } 484 485 } else if (delta == 2) { 486 Node<K, V> leftLeft = left.left; 487 Node<K, V> leftRight = left.right; 488 int leftRightHeight = leftRight != null ? leftRight.height : 0; 489 int leftLeftHeight = leftLeft != null ? leftLeft.height : 0; 490 491 int leftDelta = leftLeftHeight - leftRightHeight; 492 if (leftDelta == 1 || (leftDelta == 0 && !insert)) { 493 rotateRight(node); // AVL left left 494 } else { 495 // assert (leftDelta == -1); 496 rotateLeft(left); // AVL left right 497 rotateRight(node); 498 } 499 if (insert) { 500 break; // no further rotations will be necessary 501 } 502 503 } else if (delta == 0) { 504 node.height = leftHeight + 1; // leftHeight == rightHeight 505 if (insert) { 506 break; // the insert caused balance, so rebalancing is done! 507 } 508 509 } else { 510 // assert (delta == -1 || delta == 1); 511 node.height = Math.max(leftHeight, rightHeight) + 1; 512 if (!insert) { 513 break; // the height hasn't changed, so rebalancing is done! 514 } 515 } 516 } 517 } 518 519 /** 520 * Rotates the subtree so that its root's right child is the new root. 521 */ 522 private void rotateLeft(Node<K, V> root) { 523 Node<K, V> left = root.left; 524 Node<K, V> pivot = root.right; 525 Node<K, V> pivotLeft = pivot.left; 526 Node<K, V> pivotRight = pivot.right; 527 528 // move the pivot's left child to the root's right 529 root.right = pivotLeft; 530 if (pivotLeft != null) { 531 pivotLeft.parent = root; 532 } 533 534 replaceInParent(root, pivot); 535 536 // move the root to the pivot's left 537 pivot.left = root; 538 root.parent = pivot; 539 540 // fix heights 541 root.height = Math.max(left != null ? left.height : 0, 542 pivotLeft != null ? pivotLeft.height : 0) + 1; 543 pivot.height = Math.max(root.height, 544 pivotRight != null ? pivotRight.height : 0) + 1; 545 } 546 547 /** 548 * Rotates the subtree so that its root's left child is the new root. 549 */ 550 private void rotateRight(Node<K, V> root) { 551 Node<K, V> pivot = root.left; 552 Node<K, V> right = root.right; 553 Node<K, V> pivotLeft = pivot.left; 554 Node<K, V> pivotRight = pivot.right; 555 556 // move the pivot's right child to the root's left 557 root.left = pivotRight; 558 if (pivotRight != null) { 559 pivotRight.parent = root; 560 } 561 562 replaceInParent(root, pivot); 563 564 // move the root to the pivot's right 565 pivot.right = root; 566 root.parent = pivot; 567 568 // fixup heights 569 root.height = Math.max(right != null ? right.height : 0, 570 pivotRight != null ? pivotRight.height : 0) + 1; 571 pivot.height = Math.max(root.height, 572 pivotLeft != null ? pivotLeft.height : 0) + 1; 573 } 574 575 /* 576 * Navigable methods. 577 */ 578 579 /** 580 * Returns an immutable version of {@param entry}. Need this because we allow entry to be null, 581 * in which case we return a null SimpleImmutableEntry. 582 */ 583 private SimpleImmutableEntry<K, V> immutableCopy(Entry<K, V> entry) { 584 return entry == null ? null : new SimpleImmutableEntry<K, V>(entry); 585 } 586 587 public Entry<K, V> firstEntry() { 588 return immutableCopy(root == null ? null : root.first()); 589 } 590 591 private Entry<K, V> internalPollFirstEntry() { 592 if (root == null) { 593 return null; 594 } 595 Node<K, V> result = root.first(); 596 removeInternal(result); 597 return result; 598 } 599 600 public Entry<K, V> pollFirstEntry() { 601 return immutableCopy(internalPollFirstEntry()); 602 } 603 604 public K firstKey() { 605 if (root == null) { 606 throw new NoSuchElementException(); 607 } 608 return root.first().getKey(); 609 } 610 611 public Entry<K, V> lastEntry() { 612 return immutableCopy(root == null ? null : root.last()); 613 } 614 615 private Entry<K, V> internalPollLastEntry() { 616 if (root == null) { 617 return null; 618 } 619 Node<K, V> result = root.last(); 620 removeInternal(result); 621 return result; 622 } 623 624 public Entry<K, V> pollLastEntry() { 625 return immutableCopy(internalPollLastEntry()); 626 } 627 628 public K lastKey() { 629 if (root == null) { 630 throw new NoSuchElementException(); 631 } 632 return root.last().getKey(); 633 } 634 635 public Entry<K, V> lowerEntry(K key) { 636 return immutableCopy(find(key, LOWER)); 637 } 638 639 public K lowerKey(K key) { 640 Entry<K, V> entry = find(key, LOWER); 641 return entry != null ? entry.getKey() : null; 642 } 643 644 public Entry<K, V> floorEntry(K key) { 645 return immutableCopy(find(key, FLOOR)); 646 } 647 648 public K floorKey(K key) { 649 Entry<K, V> entry = find(key, FLOOR); 650 return entry != null ? entry.getKey() : null; 651 } 652 653 public Entry<K, V> ceilingEntry(K key) { 654 return immutableCopy(find(key, CEILING)); 655 } 656 657 public K ceilingKey(K key) { 658 Entry<K, V> entry = find(key, CEILING); 659 return entry != null ? entry.getKey() : null; 660 } 661 662 public Entry<K, V> higherEntry(K key) { 663 return immutableCopy(find(key, HIGHER)); 664 } 665 666 public K higherKey(K key) { 667 Entry<K, V> entry = find(key, HIGHER); 668 return entry != null ? entry.getKey() : null; 669 } 670 671 public Comparator<? super K> comparator() { 672 return comparator != NATURAL_ORDER ? comparator : null; 673 } 674 675 /* 676 * View factory methods. 677 */ 678 679 private EntrySet entrySet; 680 private KeySet keySet; 681 682 @Override public Set<Entry<K, V>> entrySet() { 683 EntrySet result = entrySet; 684 return result != null ? result : (entrySet = new EntrySet()); 685 } 686 687 @Override public Set<K> keySet() { 688 KeySet result = keySet; 689 return result != null ? result : (keySet = new KeySet()); 690 } 691 692 public NavigableSet<K> navigableKeySet() { 693 KeySet result = keySet; 694 return result != null ? result : (keySet = new KeySet()); 695 } 696 697 public NavigableMap<K, V> subMap(K from, boolean fromInclusive, K to, boolean toInclusive) { 698 Bound fromBound = fromInclusive ? INCLUSIVE : EXCLUSIVE; 699 Bound toBound = toInclusive ? INCLUSIVE : EXCLUSIVE; 700 return new BoundedMap(true, from, fromBound, to, toBound); 701 } 702 703 public SortedMap<K, V> subMap(K fromInclusive, K toExclusive) { 704 return new BoundedMap(true, fromInclusive, INCLUSIVE, toExclusive, EXCLUSIVE); 705 } 706 707 public NavigableMap<K, V> headMap(K to, boolean inclusive) { 708 Bound toBound = inclusive ? INCLUSIVE : EXCLUSIVE; 709 return new BoundedMap(true, null, NO_BOUND, to, toBound); 710 } 711 712 public SortedMap<K, V> headMap(K toExclusive) { 713 return new BoundedMap(true, null, NO_BOUND, toExclusive, EXCLUSIVE); 714 } 715 716 public NavigableMap<K, V> tailMap(K from, boolean inclusive) { 717 Bound fromBound = inclusive ? INCLUSIVE : EXCLUSIVE; 718 return new BoundedMap(true, from, fromBound, null, NO_BOUND); 719 } 720 721 public SortedMap<K, V> tailMap(K fromInclusive) { 722 return new BoundedMap(true, fromInclusive, INCLUSIVE, null, NO_BOUND); 723 } 724 725 public NavigableMap<K, V> descendingMap() { 726 return new BoundedMap(false, null, NO_BOUND, null, NO_BOUND); 727 } 728 729 public NavigableSet<K> descendingKeySet() { 730 return new BoundedMap(false, null, NO_BOUND, null, NO_BOUND).navigableKeySet(); 731 } 732 733 static class Node<K, V> implements Map.Entry<K, V> { 734 Node<K, V> parent; 735 Node<K, V> left; 736 Node<K, V> right; 737 final K key; 738 V value; 739 int height; 740 741 Node(Node<K, V> parent, K key) { 742 this.parent = parent; 743 this.key = key; 744 this.height = 1; 745 } 746 747 Node<K, V> copy(Node<K, V> parent) { 748 Node<K, V> result = new Node<K, V>(parent, key); 749 if (left != null) { 750 result.left = left.copy(result); 751 } 752 if (right != null) { 753 result.right = right.copy(result); 754 } 755 result.value = value; 756 result.height = height; 757 return result; 758 } 759 760 public K getKey() { 761 return key; 762 } 763 764 public V getValue() { 765 return value; 766 } 767 768 public V setValue(V value) { 769 V oldValue = this.value; 770 this.value = value; 771 return oldValue; 772 } 773 774 @Override public boolean equals(Object o) { 775 if (o instanceof Map.Entry) { 776 Map.Entry other = (Map.Entry) o; 777 return (key == null ? other.getKey() == null : key.equals(other.getKey())) 778 && (value == null ? other.getValue() == null : value.equals(other.getValue())); 779 } 780 return false; 781 } 782 783 @Override public int hashCode() { 784 return (key == null ? 0 : key.hashCode()) 785 ^ (value == null ? 0 : value.hashCode()); 786 } 787 788 @Override public String toString() { 789 return key + "=" + value; 790 } 791 792 /** 793 * Returns the next node in an inorder traversal, or null if this is the 794 * last node in the tree. 795 */ 796 Node<K, V> next() { 797 if (right != null) { 798 return right.first(); 799 } 800 801 Node<K, V> node = this; 802 Node<K, V> parent = node.parent; 803 while (parent != null) { 804 if (parent.left == node) { 805 return parent; 806 } 807 node = parent; 808 parent = node.parent; 809 } 810 return null; 811 } 812 813 /** 814 * Returns the previous node in an inorder traversal, or null if this is 815 * the first node in the tree. 816 */ 817 public Node<K, V> prev() { 818 if (left != null) { 819 return left.last(); 820 } 821 822 Node<K, V> node = this; 823 Node<K, V> parent = node.parent; 824 while (parent != null) { 825 if (parent.right == node) { 826 return parent; 827 } 828 node = parent; 829 parent = node.parent; 830 } 831 return null; 832 } 833 834 /** 835 * Returns the first node in this subtree. 836 */ 837 public Node<K, V> first() { 838 Node<K, V> node = this; 839 Node<K, V> child = node.left; 840 while (child != null) { 841 node = child; 842 child = node.left; 843 } 844 return node; 845 } 846 847 /** 848 * Returns the last node in this subtree. 849 */ 850 public Node<K, V> last() { 851 Node<K, V> node = this; 852 Node<K, V> child = node.right; 853 while (child != null) { 854 node = child; 855 child = node.right; 856 } 857 return node; 858 } 859 } 860 861 /** 862 * Walk the nodes of the tree left-to-right or right-to-left. Note that in 863 * descending iterations, {@code next} will return the previous node. 864 */ 865 abstract class MapIterator<T> implements Iterator<T> { 866 protected Node<K, V> next; 867 protected Node<K, V> last; 868 protected int expectedModCount = modCount; 869 870 MapIterator(Node<K, V> next) { 871 this.next = next; 872 } 873 874 public boolean hasNext() { 875 return next != null; 876 } 877 878 protected Node<K, V> stepForward() { 879 if (next == null) { 880 throw new NoSuchElementException(); 881 } 882 if (modCount != expectedModCount) { 883 throw new ConcurrentModificationException(); 884 } 885 last = next; 886 next = next.next(); 887 return last; 888 } 889 890 protected Node<K, V> stepBackward() { 891 if (next == null) { 892 throw new NoSuchElementException(); 893 } 894 if (modCount != expectedModCount) { 895 throw new ConcurrentModificationException(); 896 } 897 last = next; 898 next = next.prev(); 899 return last; 900 } 901 902 public void remove() { 903 if (last == null) { 904 throw new IllegalStateException(); 905 } 906 removeInternal(last); 907 expectedModCount = modCount; 908 last = null; 909 } 910 } 911 912 /* 913 * View implementations. 914 */ 915 916 class EntrySet extends AbstractSet<Map.Entry<K, V>> { 917 @Override public int size() { 918 return size; 919 } 920 921 @Override public Iterator<Entry<K, V>> iterator() { 922 return new MapIterator<Entry<K, V>>(root == null ? null : root.first()) { 923 public Entry<K, V> next() { 924 return stepForward(); 925 } 926 }; 927 } 928 929 @Override public boolean contains(Object o) { 930 return o instanceof Entry && findByEntry((Entry<?, ?>) o) != null; 931 } 932 933 @Override public boolean remove(Object o) { 934 if (!(o instanceof Entry)) { 935 return false; 936 } 937 938 Node<K, V> node = findByEntry((Entry<?, ?>) o); 939 if (node == null) { 940 return false; 941 } 942 removeInternal(node); 943 return true; 944 } 945 946 @Override public void clear() { 947 TreeMap.this.clear(); 948 } 949 } 950 951 class KeySet extends AbstractSet<K> implements NavigableSet<K> { 952 @Override public int size() { 953 return size; 954 } 955 956 @Override public Iterator<K> iterator() { 957 return new MapIterator<K>(root == null ? null : root.first()) { 958 public K next() { 959 return stepForward().key; 960 } 961 }; 962 } 963 964 public Iterator<K> descendingIterator() { 965 return new MapIterator<K>(root == null ? null : root.last()) { 966 public K next() { 967 return stepBackward().key; 968 } 969 }; 970 } 971 972 @Override public boolean contains(Object o) { 973 return containsKey(o); 974 } 975 976 @Override public boolean remove(Object key) { 977 return removeInternalByKey(key) != null; 978 } 979 980 @Override public void clear() { 981 TreeMap.this.clear(); 982 } 983 984 public Comparator<? super K> comparator() { 985 return TreeMap.this.comparator(); 986 } 987 988 /* 989 * Navigable methods. 990 */ 991 992 public K first() { 993 return firstKey(); 994 } 995 996 public K last() { 997 return lastKey(); 998 } 999 1000 public K lower(K key) { 1001 return lowerKey(key); 1002 } 1003 1004 public K floor(K key) { 1005 return floorKey(key); 1006 } 1007 1008 public K ceiling(K key) { 1009 return ceilingKey(key); 1010 } 1011 1012 public K higher(K key) { 1013 return higherKey(key); 1014 } 1015 1016 public K pollFirst() { 1017 Entry<K, V> entry = internalPollFirstEntry(); 1018 return entry != null ? entry.getKey() : null; 1019 } 1020 1021 public K pollLast() { 1022 Entry<K, V> entry = internalPollLastEntry(); 1023 return entry != null ? entry.getKey() : null; 1024 } 1025 1026 /* 1027 * View factory methods. 1028 */ 1029 1030 public NavigableSet<K> subSet(K from, boolean fromInclusive, K to, boolean toInclusive) { 1031 return TreeMap.this.subMap(from, fromInclusive, to, toInclusive).navigableKeySet(); 1032 } 1033 1034 public SortedSet<K> subSet(K fromInclusive, K toExclusive) { 1035 return TreeMap.this.subMap(fromInclusive, true, toExclusive, false).navigableKeySet(); 1036 } 1037 1038 public NavigableSet<K> headSet(K to, boolean inclusive) { 1039 return TreeMap.this.headMap(to, inclusive).navigableKeySet(); 1040 } 1041 1042 public SortedSet<K> headSet(K toExclusive) { 1043 return TreeMap.this.headMap(toExclusive, false).navigableKeySet(); 1044 } 1045 1046 public NavigableSet<K> tailSet(K from, boolean inclusive) { 1047 return TreeMap.this.tailMap(from, inclusive).navigableKeySet(); 1048 } 1049 1050 public SortedSet<K> tailSet(K fromInclusive) { 1051 return TreeMap.this.tailMap(fromInclusive, true).navigableKeySet(); 1052 } 1053 1054 public NavigableSet<K> descendingSet() { 1055 return new BoundedMap(false, null, NO_BOUND, null, NO_BOUND).navigableKeySet(); 1056 } 1057 } 1058 1059 /* 1060 * Bounded views implementations. 1061 */ 1062 1063 enum Bound { 1064 INCLUSIVE { 1065 @Override public String leftCap(Object from) { 1066 return "[" + from; 1067 } 1068 @Override public String rightCap(Object to) { 1069 return to + "]"; 1070 } 1071 }, 1072 EXCLUSIVE { 1073 @Override public String leftCap(Object from) { 1074 return "(" + from; 1075 } 1076 @Override public String rightCap(Object to) { 1077 return to + ")"; 1078 } 1079 }, 1080 NO_BOUND { 1081 @Override public String leftCap(Object from) { 1082 return "."; 1083 } 1084 @Override public String rightCap(Object to) { 1085 return "."; 1086 } 1087 }; 1088 1089 public abstract String leftCap(Object from); 1090 public abstract String rightCap(Object to); 1091 } 1092 1093 /** 1094 * A map with optional limits on its range. 1095 */ 1096 final class BoundedMap extends AbstractMap<K, V> implements NavigableMap<K, V>, Serializable { 1097 private final transient boolean ascending; 1098 private final transient K from; 1099 private final transient Bound fromBound; 1100 private final transient K to; 1101 private final transient Bound toBound; 1102 1103 BoundedMap(boolean ascending, K from, Bound fromBound, K to, Bound toBound) { 1104 /* 1105 * Validate the bounds. In addition to checking that from <= to, we 1106 * verify that the comparator supports our bound objects. 1107 */ 1108 if (fromBound != NO_BOUND && toBound != NO_BOUND) { 1109 if (comparator.compare(from, to) > 0) { 1110 throw new IllegalArgumentException(from + " > " + to); 1111 } 1112 } else if (fromBound != NO_BOUND) { 1113 comparator.compare(from, from); 1114 } else if (toBound != NO_BOUND) { 1115 comparator.compare(to, to); 1116 } 1117 1118 this.ascending = ascending; 1119 this.from = from; 1120 this.fromBound = fromBound; 1121 this.to = to; 1122 this.toBound = toBound; 1123 } 1124 1125 @Override public int size() { 1126 return count(entrySet().iterator()); 1127 } 1128 1129 @Override public boolean isEmpty() { 1130 return endpoint(true) == null; 1131 } 1132 1133 @Override public V get(Object key) { 1134 return isInBounds(key) ? TreeMap.this.get(key) : null; 1135 } 1136 1137 @Override public boolean containsKey(Object key) { 1138 return isInBounds(key) && TreeMap.this.containsKey(key); 1139 } 1140 1141 @Override public V put(K key, V value) { 1142 if (!isInBounds(key)) { 1143 throw outOfBounds(key, fromBound, toBound); 1144 } 1145 return putInternal(key, value); 1146 } 1147 1148 @Override public V remove(Object key) { 1149 return isInBounds(key) ? TreeMap.this.remove(key) : null; 1150 } 1151 1152 /** 1153 * Returns true if the key is in bounds. 1154 */ 1155 @SuppressWarnings("unchecked") // this method throws ClassCastExceptions! 1156 private boolean isInBounds(Object key) { 1157 return isInBounds((K) key, fromBound, toBound); 1158 } 1159 1160 /** 1161 * Returns true if the key is in bounds. Use this overload with 1162 * NO_BOUND to skip bounds checking on either end. 1163 */ 1164 private boolean isInBounds(K key, Bound fromBound, Bound toBound) { 1165 if (fromBound == INCLUSIVE) { 1166 if (comparator.compare(key, from) < 0) { 1167 return false; // less than from 1168 } 1169 } else if (fromBound == EXCLUSIVE) { 1170 if (comparator.compare(key, from) <= 0) { 1171 return false; // less than or equal to from 1172 } 1173 } 1174 1175 if (toBound == INCLUSIVE) { 1176 if (comparator.compare(key, to) > 0) { 1177 return false; // greater than 'to' 1178 } 1179 } else if (toBound == EXCLUSIVE) { 1180 if (comparator.compare(key, to) >= 0) { 1181 return false; // greater than or equal to 'to' 1182 } 1183 } 1184 1185 return true; 1186 } 1187 1188 /** 1189 * Returns the entry if it is in bounds, or null if it is out of bounds. 1190 */ 1191 private Node<K, V> bound(Node<K, V> node, Bound fromBound, Bound toBound) { 1192 return node != null && isInBounds(node.getKey(), fromBound, toBound) ? node : null; 1193 } 1194 1195 /* 1196 * Navigable methods. 1197 */ 1198 1199 public Entry<K, V> firstEntry() { 1200 return immutableCopy(endpoint(true)); 1201 } 1202 1203 public Entry<K, V> pollFirstEntry() { 1204 Node<K, V> result = endpoint(true); 1205 if (result != null) { 1206 removeInternal(result); 1207 } 1208 return immutableCopy(result); 1209 } 1210 1211 public K firstKey() { 1212 Entry<K, V> entry = endpoint(true); 1213 if (entry == null) { 1214 throw new NoSuchElementException(); 1215 } 1216 return entry.getKey(); 1217 } 1218 1219 public Entry<K, V> lastEntry() { 1220 return immutableCopy(endpoint(false)); 1221 } 1222 1223 public Entry<K, V> pollLastEntry() { 1224 Node<K, V> result = endpoint(false); 1225 if (result != null) { 1226 removeInternal(result); 1227 } 1228 return immutableCopy(result); 1229 } 1230 1231 public K lastKey() { 1232 Entry<K, V> entry = endpoint(false); 1233 if (entry == null) { 1234 throw new NoSuchElementException(); 1235 } 1236 return entry.getKey(); 1237 } 1238 1239 /** 1240 * @param first true for the first element, false for the last. 1241 */ 1242 private Node<K, V> endpoint(boolean first) { 1243 Node<K, V> node; 1244 if (ascending == first) { 1245 switch (fromBound) { 1246 case NO_BOUND: 1247 node = root == null ? null : root.first(); 1248 break; 1249 case INCLUSIVE: 1250 node = find(from, CEILING); 1251 break; 1252 case EXCLUSIVE: 1253 node = find(from, HIGHER); 1254 break; 1255 default: 1256 throw new AssertionError(); 1257 } 1258 return bound(node, NO_BOUND, toBound); 1259 } else { 1260 switch (toBound) { 1261 case NO_BOUND: 1262 node = root == null ? null : root.last(); 1263 break; 1264 case INCLUSIVE: 1265 node = find(to, FLOOR); 1266 break; 1267 case EXCLUSIVE: 1268 node = find(to, LOWER); 1269 break; 1270 default: 1271 throw new AssertionError(); 1272 } 1273 return bound(node, fromBound, NO_BOUND); 1274 } 1275 } 1276 1277 /** 1278 * Performs a find on the underlying tree after constraining it to the 1279 * bounds of this view. Examples: 1280 * 1281 * bound is (A..C) 1282 * findBounded(B, FLOOR) stays source.find(B, FLOOR) 1283 * 1284 * bound is (A..C) 1285 * findBounded(C, FLOOR) becomes source.find(C, LOWER) 1286 * 1287 * bound is (A..C) 1288 * findBounded(D, LOWER) becomes source.find(C, LOWER) 1289 * 1290 * bound is (A..C] 1291 * findBounded(D, FLOOR) becomes source.find(C, FLOOR) 1292 * 1293 * bound is (A..C] 1294 * findBounded(D, LOWER) becomes source.find(C, FLOOR) 1295 */ 1296 private Entry<K, V> findBounded(K key, Relation relation) { 1297 relation = relation.forOrder(ascending); 1298 Bound fromBoundForCheck = fromBound; 1299 Bound toBoundForCheck = toBound; 1300 1301 if (toBound != NO_BOUND && (relation == LOWER || relation == FLOOR)) { 1302 int comparison = comparator.compare(to, key); 1303 if (comparison <= 0) { 1304 key = to; 1305 if (toBound == EXCLUSIVE) { 1306 relation = LOWER; // 'to' is too high 1307 } else if (comparison < 0) { 1308 relation = FLOOR; // we already went lower 1309 } 1310 } 1311 toBoundForCheck = NO_BOUND; // we've already checked the upper bound 1312 } 1313 1314 if (fromBound != NO_BOUND && (relation == CEILING || relation == HIGHER)) { 1315 int comparison = comparator.compare(from, key); 1316 if (comparison >= 0) { 1317 key = from; 1318 if (fromBound == EXCLUSIVE) { 1319 relation = HIGHER; // 'from' is too low 1320 } else if (comparison > 0) { 1321 relation = CEILING; // we already went higher 1322 } 1323 } 1324 fromBoundForCheck = NO_BOUND; // we've already checked the lower bound 1325 } 1326 1327 return bound(find(key, relation), fromBoundForCheck, toBoundForCheck); 1328 } 1329 1330 public Entry<K, V> lowerEntry(K key) { 1331 return immutableCopy(findBounded(key, LOWER)); 1332 } 1333 1334 public K lowerKey(K key) { 1335 Entry<K, V> entry = findBounded(key, LOWER); 1336 return entry != null ? entry.getKey() : null; 1337 } 1338 1339 public Entry<K, V> floorEntry(K key) { 1340 return immutableCopy(findBounded(key, FLOOR)); 1341 } 1342 1343 public K floorKey(K key) { 1344 Entry<K, V> entry = findBounded(key, FLOOR); 1345 return entry != null ? entry.getKey() : null; 1346 } 1347 1348 public Entry<K, V> ceilingEntry(K key) { 1349 return immutableCopy(findBounded(key, CEILING)); 1350 } 1351 1352 public K ceilingKey(K key) { 1353 Entry<K, V> entry = findBounded(key, CEILING); 1354 return entry != null ? entry.getKey() : null; 1355 } 1356 1357 public Entry<K, V> higherEntry(K key) { 1358 return immutableCopy(findBounded(key, HIGHER)); 1359 } 1360 1361 public K higherKey(K key) { 1362 Entry<K, V> entry = findBounded(key, HIGHER); 1363 return entry != null ? entry.getKey() : null; 1364 } 1365 1366 public Comparator<? super K> comparator() { 1367 Comparator<? super K> forward = TreeMap.this.comparator(); 1368 if (ascending) { 1369 return forward; 1370 } else { 1371 return Collections.reverseOrder(forward); 1372 } 1373 } 1374 1375 /* 1376 * View factory methods. 1377 */ 1378 1379 private transient BoundedEntrySet entrySet; 1380 private transient BoundedKeySet keySet; 1381 1382 @Override public Set<Entry<K, V>> entrySet() { 1383 BoundedEntrySet result = entrySet; 1384 return result != null ? result : (entrySet = new BoundedEntrySet()); 1385 } 1386 1387 @Override public Set<K> keySet() { 1388 return navigableKeySet(); 1389 } 1390 1391 public NavigableSet<K> navigableKeySet() { 1392 BoundedKeySet result = keySet; 1393 return result != null ? result : (keySet = new BoundedKeySet()); 1394 } 1395 1396 public NavigableMap<K, V> descendingMap() { 1397 return new BoundedMap(!ascending, from, fromBound, to, toBound); 1398 } 1399 1400 public NavigableSet<K> descendingKeySet() { 1401 return new BoundedMap(!ascending, from, fromBound, to, toBound).navigableKeySet(); 1402 } 1403 1404 public NavigableMap<K, V> subMap(K from, boolean fromInclusive, K to, boolean toInclusive) { 1405 Bound fromBound = fromInclusive ? INCLUSIVE : EXCLUSIVE; 1406 Bound toBound = toInclusive ? INCLUSIVE : EXCLUSIVE; 1407 return subMap(from, fromBound, to, toBound); 1408 } 1409 1410 public NavigableMap<K, V> subMap(K fromInclusive, K toExclusive) { 1411 return subMap(fromInclusive, INCLUSIVE, toExclusive, EXCLUSIVE); 1412 } 1413 1414 public NavigableMap<K, V> headMap(K to, boolean inclusive) { 1415 Bound toBound = inclusive ? INCLUSIVE : EXCLUSIVE; 1416 return subMap(null, NO_BOUND, to, toBound); 1417 } 1418 1419 public NavigableMap<K, V> headMap(K toExclusive) { 1420 return subMap(null, NO_BOUND, toExclusive, EXCLUSIVE); 1421 } 1422 1423 public NavigableMap<K, V> tailMap(K from, boolean inclusive) { 1424 Bound fromBound = inclusive ? INCLUSIVE : EXCLUSIVE; 1425 return subMap(from, fromBound, null, NO_BOUND); 1426 } 1427 1428 public NavigableMap<K, V> tailMap(K fromInclusive) { 1429 return subMap(fromInclusive, INCLUSIVE, null, NO_BOUND); 1430 } 1431 1432 private NavigableMap<K, V> subMap(K from, Bound fromBound, K to, Bound toBound) { 1433 if (!ascending) { 1434 K fromTmp = from; 1435 Bound fromBoundTmp = fromBound; 1436 from = to; 1437 fromBound = toBound; 1438 to = fromTmp; 1439 toBound = fromBoundTmp; 1440 } 1441 1442 /* 1443 * If both the current and requested bounds are exclusive, the isInBounds check must be 1444 * inclusive. For example, to create (C..F) from (A..F), the bound 'F' is in bounds. 1445 */ 1446 1447 if (fromBound == NO_BOUND) { 1448 from = this.from; 1449 fromBound = this.fromBound; 1450 } else { 1451 Bound fromBoundToCheck = fromBound == this.fromBound ? INCLUSIVE : this.fromBound; 1452 if (!isInBounds(from, fromBoundToCheck, this.toBound)) { 1453 throw outOfBounds(to, fromBoundToCheck, this.toBound); 1454 } 1455 } 1456 1457 if (toBound == NO_BOUND) { 1458 to = this.to; 1459 toBound = this.toBound; 1460 } else { 1461 Bound toBoundToCheck = toBound == this.toBound ? INCLUSIVE : this.toBound; 1462 if (!isInBounds(to, this.fromBound, toBoundToCheck)) { 1463 throw outOfBounds(to, this.fromBound, toBoundToCheck); 1464 } 1465 } 1466 1467 return new BoundedMap(ascending, from, fromBound, to, toBound); 1468 } 1469 1470 private IllegalArgumentException outOfBounds(Object value, Bound fromBound, Bound toBound) { 1471 return new IllegalArgumentException(value + " not in range " 1472 + fromBound.leftCap(from) + ".." + toBound.rightCap(to)); 1473 } 1474 1475 /* 1476 * Bounded view implementations. 1477 */ 1478 1479 abstract class BoundedIterator<T> extends MapIterator<T> { 1480 protected BoundedIterator(Node<K, V> next) { 1481 super(next); 1482 } 1483 1484 @Override protected Node<K, V> stepForward() { 1485 Node<K, V> result = super.stepForward(); 1486 if (next != null && !isInBounds(next.key, NO_BOUND, toBound)) { 1487 next = null; 1488 } 1489 return result; 1490 } 1491 1492 @Override protected Node<K, V> stepBackward() { 1493 Node<K, V> result = super.stepBackward(); 1494 if (next != null && !isInBounds(next.key, fromBound, NO_BOUND)) { 1495 next = null; 1496 } 1497 return result; 1498 } 1499 } 1500 1501 final class BoundedEntrySet extends AbstractSet<Entry<K, V>> { 1502 @Override public int size() { 1503 return BoundedMap.this.size(); 1504 } 1505 1506 @Override public boolean isEmpty() { 1507 return BoundedMap.this.isEmpty(); 1508 } 1509 1510 @Override public Iterator<Entry<K, V>> iterator() { 1511 return new BoundedIterator<Entry<K, V>>(endpoint(true)) { 1512 public Entry<K, V> next() { 1513 return ascending ? stepForward() : stepBackward(); 1514 } 1515 }; 1516 } 1517 1518 @Override public boolean contains(Object o) { 1519 if (!(o instanceof Entry)) { 1520 return false; 1521 } 1522 Entry<?, ?> entry = (Entry<?, ?>) o; 1523 return isInBounds(entry.getKey()) && findByEntry(entry) != null; 1524 } 1525 1526 @Override public boolean remove(Object o) { 1527 if (!(o instanceof Entry)) { 1528 return false; 1529 } 1530 Entry<?, ?> entry = (Entry<?, ?>) o; 1531 return isInBounds(entry.getKey()) && TreeMap.this.entrySet().remove(entry); 1532 } 1533 } 1534 1535 final class BoundedKeySet extends AbstractSet<K> implements NavigableSet<K> { 1536 @Override public int size() { 1537 return BoundedMap.this.size(); 1538 } 1539 1540 @Override public boolean isEmpty() { 1541 return BoundedMap.this.isEmpty(); 1542 } 1543 1544 @Override public Iterator<K> iterator() { 1545 return new BoundedIterator<K>(endpoint(true)) { 1546 public K next() { 1547 return (ascending ? stepForward() : stepBackward()).key; 1548 } 1549 }; 1550 } 1551 1552 public Iterator<K> descendingIterator() { 1553 return new BoundedIterator<K>(endpoint(false)) { 1554 public K next() { 1555 return (ascending ? stepBackward() : stepForward()).key; 1556 } 1557 }; 1558 } 1559 1560 @Override public boolean contains(Object key) { 1561 return isInBounds(key) && findByObject(key) != null; 1562 } 1563 1564 @Override public boolean remove(Object key) { 1565 return isInBounds(key) && removeInternalByKey(key) != null; 1566 } 1567 1568 /* 1569 * Navigable methods. 1570 */ 1571 1572 public K first() { 1573 return firstKey(); 1574 } 1575 1576 public K pollFirst() { 1577 Entry<K, ?> entry = pollFirstEntry(); 1578 return entry != null ? entry.getKey() : null; 1579 } 1580 1581 public K last() { 1582 return lastKey(); 1583 } 1584 1585 public K pollLast() { 1586 Entry<K, ?> entry = pollLastEntry(); 1587 return entry != null ? entry.getKey() : null; 1588 } 1589 1590 public K lower(K key) { 1591 return lowerKey(key); 1592 } 1593 1594 public K floor(K key) { 1595 return floorKey(key); 1596 } 1597 1598 public K ceiling(K key) { 1599 return ceilingKey(key); 1600 } 1601 1602 public K higher(K key) { 1603 return higherKey(key); 1604 } 1605 1606 public Comparator<? super K> comparator() { 1607 return BoundedMap.this.comparator(); 1608 } 1609 1610 /* 1611 * View factory methods. 1612 */ 1613 1614 public NavigableSet<K> subSet(K from, boolean fromInclusive, K to, boolean toInclusive) { 1615 return subMap(from, fromInclusive, to, toInclusive).navigableKeySet(); 1616 } 1617 1618 public SortedSet<K> subSet(K fromInclusive, K toExclusive) { 1619 return subMap(fromInclusive, toExclusive).navigableKeySet(); 1620 } 1621 1622 public NavigableSet<K> headSet(K to, boolean inclusive) { 1623 return headMap(to, inclusive).navigableKeySet(); 1624 } 1625 1626 public SortedSet<K> headSet(K toExclusive) { 1627 return headMap(toExclusive).navigableKeySet(); 1628 } 1629 1630 public NavigableSet<K> tailSet(K from, boolean inclusive) { 1631 return tailMap(from, inclusive).navigableKeySet(); 1632 } 1633 1634 public SortedSet<K> tailSet(K fromInclusive) { 1635 return tailMap(fromInclusive).navigableKeySet(); 1636 } 1637 1638 public NavigableSet<K> descendingSet() { 1639 return new BoundedMap(!ascending, from, fromBound, to, toBound).navigableKeySet(); 1640 } 1641 } 1642 1643 Object writeReplace() throws ObjectStreamException { 1644 return ascending 1645 ? new AscendingSubMap<K, V>(TreeMap.this, from, fromBound, to, toBound) 1646 : new DescendingSubMap<K, V>(TreeMap.this, from, fromBound, to, toBound); 1647 } 1648 } 1649 1650 /** 1651 * Returns the number of elements in the iteration. 1652 */ 1653 static int count(Iterator<?> iterator) { 1654 int count = 0; 1655 while (iterator.hasNext()) { 1656 iterator.next(); 1657 count++; 1658 } 1659 return count; 1660 } 1661 1662 /* 1663 * Serialization 1664 */ 1665 1666 private static final long serialVersionUID = 919286545866124006L; 1667 1668 private void writeObject(ObjectOutputStream stream) throws IOException { 1669 stream.putFields().put("comparator", comparator()); 1670 stream.writeFields(); 1671 stream.writeInt(size); 1672 for (Map.Entry<K, V> entry : entrySet()) { 1673 stream.writeObject(entry.getKey()); 1674 stream.writeObject(entry.getValue()); 1675 } 1676 } 1677 1678 @SuppressWarnings("unchecked") // we have to trust that keys are Ks and values are Vs 1679 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { 1680 GetField fields = stream.readFields(); 1681 comparator = (Comparator<? super K>) fields.get("comparator", null); 1682 if (comparator == null) { 1683 comparator = (Comparator<? super K>) NATURAL_ORDER; 1684 } 1685 int size = stream.readInt(); 1686 for (int i = 0; i < size; i++) { 1687 putInternal((K) stream.readObject(), (V) stream.readObject()); 1688 } 1689 } 1690 1691 static abstract class NavigableSubMap<K, V> extends AbstractMap<K, V> implements Serializable { 1692 private static final long serialVersionUID = -2102997345730753016L; 1693 TreeMap<K, V> m; 1694 Object lo; 1695 Object hi; 1696 boolean fromStart; 1697 boolean toEnd; 1698 boolean loInclusive; 1699 boolean hiInclusive; 1700 1701 NavigableSubMap(TreeMap<K, V> delegate, K from, Bound fromBound, K to, Bound toBound) { 1702 this.m = delegate; 1703 this.lo = from; 1704 this.hi = to; 1705 this.fromStart = fromBound == NO_BOUND; 1706 this.toEnd = toBound == NO_BOUND; 1707 this.loInclusive = fromBound == INCLUSIVE; 1708 this.hiInclusive = toBound == INCLUSIVE; 1709 } 1710 1711 @Override public Set<Entry<K, V>> entrySet() { 1712 throw new UnsupportedOperationException(); 1713 } 1714 1715 @SuppressWarnings("unchecked") // we have to trust that the bounds are Ks 1716 protected Object readResolve() throws ObjectStreamException { 1717 Bound fromBound = fromStart ? NO_BOUND : (loInclusive ? INCLUSIVE : EXCLUSIVE); 1718 Bound toBound = toEnd ? NO_BOUND : (hiInclusive ? INCLUSIVE : EXCLUSIVE); 1719 boolean ascending = !(this instanceof DescendingSubMap); 1720 return m.new BoundedMap(ascending, (K) lo, fromBound, (K) hi, toBound); 1721 } 1722 } 1723 1724 static class DescendingSubMap<K, V> extends NavigableSubMap<K, V> { 1725 private static final long serialVersionUID = 912986545866120460L; 1726 Comparator<K> reverseComparator; 1727 DescendingSubMap(TreeMap<K, V> delegate, K from, Bound fromBound, K to, Bound toBound) { 1728 super(delegate, from, fromBound, to, toBound); 1729 } 1730 } 1731 1732 static class AscendingSubMap<K, V> extends NavigableSubMap<K, V> { 1733 private static final long serialVersionUID = 912986545866124060L; 1734 AscendingSubMap(TreeMap<K, V> delegate, K from, Bound fromBound, K to, Bound toBound) { 1735 super(delegate, from, fromBound, to, toBound); 1736 } 1737 } 1738 1739 class SubMap extends AbstractMap<K, V> implements Serializable { 1740 private static final long serialVersionUID = -6520786458950516097L; 1741 Object fromKey; 1742 Object toKey; 1743 boolean fromStart; 1744 boolean toEnd; 1745 1746 @Override public Set<Entry<K, V>> entrySet() { 1747 throw new UnsupportedOperationException(); 1748 } 1749 1750 @SuppressWarnings("unchecked") // we have to trust that the bounds are Ks 1751 protected Object readResolve() throws ObjectStreamException { 1752 Bound fromBound = fromStart ? NO_BOUND : INCLUSIVE; 1753 Bound toBound = toEnd ? NO_BOUND : EXCLUSIVE; 1754 return new BoundedMap(true, (K) fromKey, fromBound, (K) toKey, toBound); 1755 } 1756 } 1757} 1758