1/* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18package java.util; 19 20import java.io.IOException; 21import java.io.ObjectInputStream; 22import java.io.ObjectOutputStream; 23import java.io.Serializable; 24 25/** 26 * TreeMap is an implementation of SortedMap. All optional operations (adding 27 * and removing) are supported. The values can be any objects. The keys can be 28 * any objects which are comparable to each other either using their natural 29 * order or a specified Comparator. 30 * 31 * @since 1.2 32 */ 33public class TreeMap <K, V> extends AbstractMap<K, V> implements SortedMap<K, V>, 34 Cloneable, Serializable { 35 private static final long serialVersionUID = 919286545866124006L; 36 37 transient int size; 38 39 private Comparator<? super K> comparator; 40 41 transient int modCount; 42 43 transient Set<Map.Entry<K, V>> entrySet; 44 45 transient Node<K, V> root; 46 47class MapEntry implements Map.Entry<K, V>, Cloneable { 48 49 final int offset; 50 final Node<K, V> node; 51 final K key; 52 53 MapEntry(Node<K, V> node, int offset) { 54 this.node = node; 55 this.offset = offset; 56 key = node.keys[offset]; 57 } 58 59 @Override 60 public Object clone() { 61 try { 62 return super.clone(); 63 } catch (CloneNotSupportedException e) { 64 throw new AssertionError(e); // android-changed 65 } 66 } 67 68 @Override 69 public boolean equals(Object object) { 70 if (this == object) { 71 return true; 72 } 73 if (object instanceof Map.Entry) { 74 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object; 75 V value = getValue(); 76 return (key == null ? entry.getKey() == null : key.equals(entry 77 .getKey())) 78 && (value == null ? entry.getValue() == null : value 79 .equals(entry.getValue())); 80 } 81 return false; 82 } 83 84 public K getKey() { 85 return key; 86 } 87 88 public V getValue() { 89 if (node.keys[offset] == key) { 90 return node.values[offset]; 91 } 92 if (containsKey(key)) { 93 return get(key); 94 } 95 throw new IllegalStateException(); 96 } 97 98 @Override 99 public int hashCode() { 100 V value = getValue(); 101 return (key == null ? 0 : key.hashCode()) 102 ^ (value == null ? 0 : value.hashCode()); 103 } 104 105 public V setValue(V object) { 106 if (node.keys[offset] == key) { 107 V res = node.values[offset]; 108 node.values[offset] = object; 109 return res; 110 } 111 if (containsKey(key)) { 112 return put(key, object); 113 } 114 throw new IllegalStateException(); 115 } 116 117 @Override 118 public String toString() { 119 return key + "=" + getValue(); 120 } 121 } 122 123 static class Node <K,V> implements Cloneable { 124 static final int NODE_SIZE = 64; 125 Node<K, V> prev, next; 126 Node<K, V> parent, left, right; 127 V[] values; 128 K[] keys; 129 int left_idx = 0; 130 int right_idx = -1; 131 int size = 0; 132 boolean color; 133 134 public Node() { 135 keys = (K[]) new Object[NODE_SIZE]; 136 values = (V[]) new Object[NODE_SIZE]; 137 } 138 139 @SuppressWarnings("unchecked") 140 Node<K, V> clone(Node<K, V> parent) throws CloneNotSupportedException { 141 Node<K, V> clone = (Node<K, V>) super.clone(); 142 clone.keys = (K[]) new Object[NODE_SIZE]; 143 clone.values = (V[]) new Object[NODE_SIZE]; 144 System.arraycopy(keys, 0, clone.keys, 0, keys.length); 145 System.arraycopy(values, 0, clone.values, 0, values.length); 146 clone.left_idx = left_idx; 147 clone.right_idx = right_idx; 148 clone.parent = parent; 149 if (left != null) { 150 clone.left = left.clone(clone); 151 } 152 if (right != null) { 153 clone.right = right.clone(clone); 154 } 155 clone.prev = null; 156 clone.next = null; 157 return clone; 158 } 159 } 160 161 @SuppressWarnings("unchecked") 162 private static <T> Comparable<T> toComparable(T obj) { 163 if (obj == null) { 164 throw new NullPointerException(); 165 } 166 return (Comparable) obj; 167 } 168 169 static class AbstractMapIterator <K,V> { 170 TreeMap<K, V> backingMap; 171 int expectedModCount; 172 Node<K, V> node; 173 Node<K, V> lastNode; 174 int offset; 175 int lastOffset; 176 177 AbstractMapIterator(TreeMap<K, V> map, Node<K, V> startNode, int startOffset) { 178 backingMap = map; 179 expectedModCount = map.modCount; 180 node = startNode; 181 offset = startOffset; 182 } 183 184 AbstractMapIterator(TreeMap<K, V> map, Node<K, V> startNode) { 185 this(map, startNode, startNode != null ? 186 startNode.right_idx - startNode.left_idx : 0); 187 } 188 189 AbstractMapIterator(TreeMap<K, V> map) { 190 this(map, minimum(map.root)); 191 } 192 193 public boolean hasNext() { 194 return node != null; 195 } 196 197 final void makeNext() { 198 if (expectedModCount != backingMap.modCount) { 199 throw new ConcurrentModificationException(); 200 } else if (node == null) { 201 throw new NoSuchElementException(); 202 } 203 lastNode = node; 204 lastOffset = offset; 205 if (offset != 0) { 206 offset--; 207 } else { 208 node = node.next; 209 if (node != null) { 210 offset = node.right_idx - node.left_idx; 211 } 212 } 213 } 214 215 final public void remove() { 216 if (expectedModCount == backingMap.modCount) { 217 if (lastNode != null) { 218 int idx = lastNode.right_idx - lastOffset; 219 backingMap.removeFromIterator(lastNode, idx); 220 lastNode = null; 221 expectedModCount++; 222 } else { 223 throw new IllegalStateException(); 224 } 225 } else { 226 throw new ConcurrentModificationException(); 227 } 228 } 229 } 230 231 static class UnboundedEntryIterator <K, V> extends AbstractMapIterator<K, V> 232 implements Iterator<Map.Entry<K, V>> { 233 234 UnboundedEntryIterator(TreeMap<K, V> map, Node<K, V> startNode, int startOffset) { 235 super(map, startNode, startOffset); 236 } 237 238 UnboundedEntryIterator(TreeMap<K, V> map) { 239 super(map); 240 } 241 242 public Map.Entry<K, V> next() { 243 makeNext(); 244 int idx = lastNode.right_idx - lastOffset; 245 return backingMap.new MapEntry(lastNode, idx); 246 } 247 } 248 249 static class UnboundedKeyIterator <K, V> extends AbstractMapIterator<K, V> 250 implements Iterator<K> { 251 252 UnboundedKeyIterator(TreeMap<K, V> map, Node<K, V> startNode, int startOffset) { 253 super(map, startNode, startOffset); 254 } 255 256 UnboundedKeyIterator(TreeMap<K, V> map) { 257 super(map); 258 } 259 260 public K next() { 261 makeNext(); 262 return lastNode.keys[lastNode.right_idx - lastOffset]; 263 } 264 } 265 266 static class UnboundedValueIterator <K, V> extends AbstractMapIterator<K, V> 267 implements Iterator<V> { 268 269 UnboundedValueIterator(TreeMap<K, V> map, Node<K, V> startNode, int startOffset) { 270 super(map, startNode, startOffset); 271 } 272 273 UnboundedValueIterator(TreeMap<K, V> map) { 274 super(map); 275 } 276 277 public V next() { 278 makeNext(); 279 return lastNode.values[lastNode.right_idx - lastOffset]; 280 } 281 } 282 283 static class BoundedMapIterator <K, V> extends AbstractMapIterator<K, V> { 284 285 Node<K, V> finalNode; 286 int finalOffset; 287 288 BoundedMapIterator(Node<K, V> startNode, int startOffset, TreeMap<K, V> map, 289 Node<K, V> finalNode, int finalOffset) { 290 super(map, finalNode==null? null : startNode, startOffset); 291 this.finalNode = finalNode; 292 this.finalOffset = finalOffset; 293 } 294 295 BoundedMapIterator(Node<K, V> startNode, TreeMap<K, V> map, 296 Node<K, V> finalNode, int finalOffset) { 297 this(startNode, startNode != null ? 298 startNode.right_idx - startNode.left_idx : 0, 299 map, finalNode, finalOffset); 300 } 301 302 BoundedMapIterator(Node<K, V> startNode, int startOffset, 303 TreeMap<K, V> map, Node<K, V> finalNode) { 304 this(startNode, startOffset, map, finalNode, 305 finalNode.right_idx - finalNode.left_idx); 306 } 307 308 void makeBoundedNext() { 309 makeNext(); 310 if (lastNode == finalNode && lastOffset == finalOffset) { 311 node = null; 312 } 313 } 314 } 315 316 static class BoundedEntryIterator <K, V> extends BoundedMapIterator<K, V> 317 implements Iterator<Map.Entry<K, V>> { 318 319 public BoundedEntryIterator(Node<K, V> startNode, int startOffset, TreeMap<K, V> map, 320 Node<K, V> finalNode, int finalOffset) { 321 super(startNode, startOffset, map, finalNode, finalOffset); 322 } 323 324 public Map.Entry<K, V> next() { 325 makeBoundedNext(); 326 int idx = lastNode.right_idx - lastOffset; 327 return backingMap.new MapEntry(lastNode, idx); 328 } 329 } 330 331 static class BoundedKeyIterator <K, V> extends BoundedMapIterator<K, V> 332 implements Iterator<K> { 333 334 public BoundedKeyIterator(Node<K, V> startNode, int startOffset, TreeMap<K, V> map, 335 Node<K, V> finalNode, int finalOffset) { 336 super(startNode, startOffset, map, finalNode, finalOffset); 337 } 338 339 public K next() { 340 makeBoundedNext(); 341 return lastNode.keys[lastNode.right_idx - lastOffset]; 342 } 343 } 344 345 static class BoundedValueIterator <K, V> extends BoundedMapIterator<K, V> 346 implements Iterator<V> { 347 348 public BoundedValueIterator(Node<K, V> startNode, int startOffset, TreeMap<K, V> map, 349 Node<K, V> finalNode, int finalOffset) { 350 super(startNode, startOffset, map, finalNode, finalOffset); 351 } 352 353 public V next() { 354 makeBoundedNext(); 355 return lastNode.values[lastNode.right_idx - lastOffset]; 356 } 357 } 358 359 static final class SubMap <K,V> extends AbstractMap<K, V> 360 implements SortedMap<K, V>, Serializable { 361 private static final long serialVersionUID = -6520786458950516097L; 362 363 private TreeMap<K, V> backingMap; 364 365 boolean hasStart, hasEnd; 366 K startKey, endKey; 367 transient Set<Map.Entry<K, V>> entrySet = null; 368 transient int firstKeyModCount = -1; 369 transient int lastKeyModCount = -1; 370 transient Node<K, V> firstKeyNode; 371 transient int firstKeyIndex; 372 transient Node<K, V> lastKeyNode; 373 transient int lastKeyIndex; 374 375 SubMap(K start, TreeMap<K, V> map) { 376 backingMap = map; 377 hasStart = true; 378 startKey = start; 379 } 380 381 SubMap(K start, TreeMap<K, V> map, K end) { 382 backingMap = map; 383 hasStart = hasEnd = true; 384 startKey = start; 385 endKey = end; 386 } 387 388 SubMap(TreeMap<K, V> map, K end) { 389 backingMap = map; 390 hasEnd = true; 391 endKey = end; 392 } 393 394 private void checkRange(K key) { 395 Comparator<? super K> cmp = backingMap.comparator; 396 if (cmp == null) { 397 Comparable<K> object = toComparable(key); 398 if (hasStart && object.compareTo(startKey) < 0) { 399 throw new IllegalArgumentException(); 400 } 401 if (hasEnd && object.compareTo(endKey) > 0) { 402 throw new IllegalArgumentException(); 403 } 404 } else { 405 if (hasStart 406 && backingMap.comparator().compare(key, startKey) < 0) { 407 throw new IllegalArgumentException(); 408 } 409 if (hasEnd && backingMap.comparator().compare(key, endKey) > 0) { 410 throw new IllegalArgumentException(); 411 } 412 } 413 } 414 415 private boolean isInRange(K key) { 416 Comparator<? super K> cmp = backingMap.comparator; 417 if (cmp == null) { 418 Comparable<K> object = toComparable(key); 419 if (hasStart && object.compareTo(startKey) < 0) { 420 return false; 421 } 422 if (hasEnd && object.compareTo(endKey) >= 0) { 423 return false; 424 } 425 } else { 426 if (hasStart && cmp.compare(key, startKey) < 0) { 427 return false; 428 } 429 if (hasEnd && cmp.compare(key, endKey) >= 0) { 430 return false; 431 } 432 } 433 return true; 434 } 435 436 private boolean checkUpperBound(K key) { 437 if (hasEnd) { 438 Comparator<? super K> cmp = backingMap.comparator; 439 if (cmp == null) { 440 return (toComparable(key).compareTo(endKey) < 0); 441 } 442 return (cmp.compare(key, endKey) < 0); 443 } 444 return true; 445 } 446 447 private boolean checkLowerBound(K key) { 448 if (hasStart) { 449 Comparator<? super K> cmp = backingMap.comparator; 450 if (cmp == null) { 451 return (toComparable(key).compareTo(startKey) >= 0); 452 } 453 return (cmp.compare(key, startKey) >= 0); 454 } 455 return true; 456 } 457 458 public Comparator<? super K> comparator() { 459 return backingMap.comparator(); 460 } 461 462 @SuppressWarnings("unchecked") 463 @Override 464 public boolean containsKey(Object key) { 465 if (isInRange((K) key)) { 466 return backingMap.containsKey(key); 467 } 468 return false; 469 } 470 471 @Override 472 public void clear() { 473 keySet().clear(); 474 } 475 476 @Override 477 public boolean containsValue(Object value) { 478 Iterator<V> it = values().iterator(); 479 if (value != null) { 480 while (it.hasNext()) { 481 if (value.equals(it.next())) { 482 return true; 483 } 484 } 485 } else { 486 while (it.hasNext()) { 487 if (it.next() == null) { 488 return true; 489 } 490 } 491 } 492 return false; 493 } 494 495 @Override 496 public Set<Map.Entry<K, V>> entrySet() { 497 if (entrySet == null) { 498 entrySet = new SubMapEntrySet<K, V>(this); 499 } 500 return entrySet; 501 } 502 503 private void setFirstKey() { 504 if (firstKeyModCount == backingMap.modCount) { 505 return; 506 } 507 Comparable<K> object = backingMap.comparator == null ? 508 toComparable((K) startKey) : null; 509 K key = (K) startKey; 510 Node<K, V> node = backingMap.root; 511 Node<K, V> foundNode = null; 512 int foundIndex = -1; 513 TOP_LOOP: 514 while (node != null) { 515 K[] keys = node.keys; 516 int left_idx = node.left_idx; 517 int result = backingMap.cmp(object, key, keys[left_idx]); 518 if (result < 0) { 519 foundNode = node; 520 foundIndex = left_idx; 521 node = node.left; 522 } else if (result == 0) { 523 foundNode = node; 524 foundIndex = left_idx; 525 break; 526 } else { 527 int right_idx = node.right_idx; 528 if (left_idx != right_idx) { 529 result = backingMap.cmp(object, key, keys[right_idx]); 530 } 531 if (result > 0) { 532 node = node.right; 533 } else if (result == 0) { 534 foundNode = node; 535 foundIndex = right_idx; 536 break; 537 } else { /*search in node*/ 538 foundNode = node; 539 foundIndex = right_idx; 540 int low = left_idx + 1, mid = 0, high = right_idx - 1; 541 while (low <= high) { 542 mid = (low + high) >>> 1; 543 result = backingMap.cmp(object, key, keys[mid]); 544 if (result > 0) { 545 low = mid + 1; 546 } else if (result == 0) { 547 foundNode = node; 548 foundIndex = mid; 549 break TOP_LOOP; 550 } else { 551 foundNode = node; 552 foundIndex = mid; 553 high = mid - 1; 554 } 555 } 556 break TOP_LOOP; 557 } 558 } 559 } 560 if (foundNode != null && !checkUpperBound(foundNode.keys[foundIndex])) { 561 foundNode = null; 562 } 563 firstKeyNode = foundNode; 564 firstKeyIndex = foundIndex; 565 firstKeyModCount = backingMap.modCount; 566 } 567 568 public K firstKey() { 569 if (backingMap.size > 0) { 570 if (!hasStart) { 571 Node<K, V> node = minimum(backingMap.root); 572 if (node != null && checkUpperBound(node.keys[node.left_idx])) { 573 return node.keys[node.left_idx]; 574 } 575 } else { 576 setFirstKey(); 577 if (firstKeyNode != null) { 578 return firstKeyNode.keys[firstKeyIndex]; 579 } 580 } 581 } 582 throw new NoSuchElementException(); 583 } 584 585 586 @SuppressWarnings("unchecked") 587 @Override 588 public V get(Object key) { 589 if (isInRange((K) key)) { 590 return backingMap.get(key); 591 } 592 return null; 593 } 594 595 public SortedMap<K, V> headMap(K endKey) { 596 checkRange(endKey); 597 if (hasStart) { 598 return new SubMap<K, V>(startKey, backingMap, endKey); 599 } 600 return new SubMap<K, V>(backingMap, endKey); 601 } 602 603 @Override 604 public boolean isEmpty() { 605 if (hasStart) { 606 setFirstKey(); 607 return firstKeyNode == null; 608 } else { 609 setLastKey(); 610 return lastKeyNode == null; 611 } 612 } 613 614 @Override 615 public Set<K> keySet() { 616 if (keySet == null) { 617 keySet = new SubMapKeySet<K, V>(this); 618 } 619 return keySet; 620 } 621 622 private void setLastKey() { 623 if (lastKeyModCount == backingMap.modCount) { 624 return; 625 } 626 Comparable<K> object = backingMap.comparator == null ? 627 toComparable((K) endKey) : null; 628 K key = (K) endKey; 629 Node<K, V> node = backingMap.root; 630 Node<K, V> foundNode = null; 631 int foundIndex = -1; 632 TOP_LOOP: 633 while (node != null) { 634 K[] keys = node.keys; 635 int left_idx = node.left_idx; 636 int result = backingMap.cmp(object, key, keys[left_idx]); 637 if (result <= 0) { 638 node = node.left; 639 } else { 640 int right_idx = node.right_idx; 641 if (left_idx != right_idx) { 642 result = backingMap.cmp(object, key, keys[right_idx]); 643 } 644 if (result > 0) { 645 foundNode = node; 646 foundIndex = right_idx; 647 node = node.right; 648 } else if (result == 0) { 649 if (node.left_idx == node.right_idx) { 650 foundNode = node.prev; 651 if (foundNode != null) { 652 foundIndex = foundNode.right_idx - 1; 653 } 654 } else { 655 foundNode = node; 656 foundIndex = right_idx - 1; 657 } 658 break; 659 } else { /*search in node*/ 660 foundNode = node; 661 foundIndex = left_idx; 662 int low = left_idx + 1, mid = 0, high = right_idx - 1; 663 while (low <= high) { 664 mid = (low + high) >>> 1; 665 result = backingMap.cmp(object, key, keys[mid]); 666 if (result > 0) { 667 foundNode = node; 668 foundIndex = mid; 669 low = mid + 1; 670 } else if (result == 0) { 671 foundNode = node; 672 foundIndex = mid - 1; 673 break TOP_LOOP; 674 } else { 675 high = mid - 1; 676 } 677 } 678 break TOP_LOOP; 679 } 680 } 681 } 682 if (foundNode != null && !checkLowerBound(foundNode.keys[foundIndex])) { 683 foundNode = null; 684 } 685 lastKeyNode = foundNode; 686 lastKeyIndex = foundIndex; 687 lastKeyModCount = backingMap.modCount; 688 } 689 690 public K lastKey() { 691 if (backingMap.size > 0) { 692 if (!hasEnd) { 693 Node<K, V> node = maximum(backingMap.root); 694 if (node != null && checkLowerBound(node.keys[node.right_idx])) { 695 return node.keys[node.right_idx]; 696 } 697 } else { 698 setLastKey(); 699 if (lastKeyNode != null) { 700 return lastKeyNode.keys[lastKeyIndex]; 701 } 702 } 703 } 704 throw new NoSuchElementException(); 705 } 706 707 708 @Override 709 public V put(K key, V value) { 710 if (isInRange(key)) { 711 return backingMap.put(key, value); 712 } 713 throw new IllegalArgumentException(); 714 } 715 716 @SuppressWarnings("unchecked") 717 @Override 718 public V remove(Object key) { 719 if (isInRange((K) key)) { 720 return backingMap.remove(key); 721 } 722 return null; 723 } 724 725 public SortedMap<K, V> subMap(K startKey, K endKey) { 726 checkRange(startKey); 727 checkRange(endKey); 728 Comparator<? super K> c = backingMap.comparator(); 729 if (c == null) { 730 if (toComparable(startKey).compareTo(endKey) <= 0) { 731 return new SubMap<K, V>(startKey, backingMap, endKey); 732 } 733 } else { 734 if (c.compare(startKey, endKey) <= 0) { 735 return new SubMap<K, V>(startKey, backingMap, endKey); 736 } 737 } 738 throw new IllegalArgumentException(); 739 } 740 741 public SortedMap<K, V> tailMap(K startKey) { 742 checkRange(startKey); 743 if (hasEnd) { 744 return new SubMap<K, V>(startKey, backingMap, endKey); 745 } 746 return new SubMap<K, V>(startKey, backingMap); 747 } 748 749 @Override 750 public Collection<V> values() { 751 if (valuesCollection == null) { 752 valuesCollection = new SubMapValuesCollection<K, V>(this); 753 } 754 return valuesCollection; 755 } 756 757 public int size() { 758 Node<K, V> from, to; 759 int fromIndex, toIndex; 760 if (hasStart) { 761 setFirstKey(); 762 from = firstKeyNode; 763 fromIndex = firstKeyIndex; 764 } else { 765 from = minimum(backingMap.root); 766 fromIndex = from == null ? 0 : from.left_idx; 767 } 768 if (from == null) { 769 return 0; 770 } 771 if (hasEnd) { 772 setLastKey(); 773 to = lastKeyNode; 774 toIndex = lastKeyIndex; 775 } else { 776 to = maximum(backingMap.root); 777 toIndex = to == null ? 0 : to.right_idx; 778 } 779 if (to == null) { 780 return 0; 781 } 782 if (from == to) { 783 return toIndex - fromIndex + 1; 784 } 785 int sum = 0; 786 while (from != to) { 787 sum += (from.right_idx - fromIndex + 1); 788 from = from.next; 789 fromIndex = from.left_idx; 790 } 791 return sum + toIndex - fromIndex + 1; 792 } 793 794 private void readObject(ObjectInputStream stream) throws IOException, 795 ClassNotFoundException { 796 stream.defaultReadObject(); 797 firstKeyModCount = -1; 798 lastKeyModCount = -1; 799 } 800 } 801 802 static class SubMapEntrySet <K,V> extends AbstractSet<Map.Entry<K, V>> 803 implements Set<Map.Entry<K, V>> { 804 SubMap<K, V> subMap; 805 806 SubMapEntrySet(SubMap<K, V> map) { 807 subMap = map; 808 } 809 810 @Override 811 public boolean isEmpty() { 812 return subMap.isEmpty(); 813 } 814 815 public Iterator<Map.Entry<K, V>> iterator() { 816 Node<K, V> from; 817 int fromIndex; 818 if (subMap.hasStart) { 819 subMap.setFirstKey(); 820 from = subMap.firstKeyNode; 821 fromIndex = subMap.firstKeyIndex; 822 } else { 823 from = minimum(subMap.backingMap.root); 824 fromIndex = from != null ? from.left_idx : 0; 825 } 826 if (!subMap.hasEnd) { 827 return new UnboundedEntryIterator<K, V>(subMap.backingMap, from, from == null ? 0 : from.right_idx - fromIndex); 828 } 829 subMap.setLastKey(); 830 Node<K, V> to = subMap.lastKeyNode; 831 int toIndex = subMap.lastKeyIndex; 832 return new BoundedEntryIterator<K, V>(from, from == null ? 0 : from.right_idx - fromIndex, subMap.backingMap, to, to == null ? 0 : to.right_idx - toIndex); 833 } 834 835 @Override 836 public int size() { 837 return subMap.size(); 838 } 839 840 @SuppressWarnings("unchecked") 841 @Override 842 public boolean contains(Object object) { 843 if (object instanceof Map.Entry) { 844 Map.Entry<K, V> entry = (Map.Entry<K, V>) object; 845 K key = entry.getKey(); 846 if (subMap.isInRange(key)) { 847 V v1 = subMap.get(key), v2 = entry.getValue(); 848 return v1 == null ? ( v2 == null && subMap.containsKey(key) ) : v1.equals(v2); 849 } 850 } 851 return false; 852 } 853 854 @Override 855 public boolean remove(Object object) { 856 if (contains(object)) { 857 Map.Entry<K, V> entry = (Map.Entry<K, V>) object; 858 K key = entry.getKey(); 859 subMap.remove(key); 860 return true; 861 } 862 return false; 863 } 864 } 865 866 static class SubMapKeySet <K,V> extends AbstractSet<K> implements Set<K> { 867 SubMap<K, V> subMap; 868 869 SubMapKeySet(SubMap<K, V> map) { 870 subMap = map; 871 } 872 873 @Override 874 public boolean contains(Object object) { 875 return subMap.containsKey(object); 876 } 877 878 @Override 879 public boolean isEmpty() { 880 return subMap.isEmpty(); 881 } 882 883 @Override 884 public int size() { 885 return subMap.size(); 886 } 887 888 @Override 889 public boolean remove(Object object) { 890 if (subMap.containsKey(object)) { 891 subMap.remove(object); 892 return true; 893 } 894 return false; 895 } 896 897 public Iterator<K> iterator() { 898 Node<K, V> from; 899 int fromIndex; 900 if (subMap.hasStart) { 901 subMap.setFirstKey(); 902 from = subMap.firstKeyNode; 903 fromIndex = subMap.firstKeyIndex; 904 } else { 905 from = minimum(subMap.backingMap.root); 906 fromIndex = from != null ? from.left_idx : 0; 907 } 908 if (!subMap.hasEnd) { 909 return new UnboundedKeyIterator<K, V>(subMap.backingMap, from, 910 from == null ? 0 : from.right_idx - fromIndex); 911 } 912 subMap.setLastKey(); 913 Node<K, V> to = subMap.lastKeyNode; 914 int toIndex = subMap.lastKeyIndex; 915 return new BoundedKeyIterator<K, V>(from, 916 from == null ? 0 : from.right_idx - fromIndex, subMap.backingMap, to, 917 to == null ? 0 : to.right_idx - toIndex); 918 } 919 } 920 921 static class SubMapValuesCollection <K,V> extends AbstractCollection<V> { 922 SubMap<K, V> subMap; 923 924 public SubMapValuesCollection(SubMap<K, V> subMap) { 925 this.subMap = subMap; 926 } 927 928 @Override 929 public boolean isEmpty() { 930 return subMap.isEmpty(); 931 } 932 933 @Override 934 public Iterator<V> iterator() { 935 Node<K, V> from; 936 int fromIndex; 937 if (subMap.hasStart) { 938 subMap.setFirstKey(); 939 from = subMap.firstKeyNode; 940 fromIndex = subMap.firstKeyIndex; 941 } else { 942 from = minimum(subMap.backingMap.root); 943 fromIndex = from != null ? from.left_idx : 0; 944 } 945 if (!subMap.hasEnd) { 946 return new UnboundedValueIterator<K, V>(subMap.backingMap, from, 947 from == null ? 0 : from.right_idx - fromIndex); 948 } 949 subMap.setLastKey(); 950 Node<K, V> to = subMap.lastKeyNode; 951 int toIndex = subMap.lastKeyIndex; 952 return new BoundedValueIterator<K, V>(from, 953 from == null ? 0 : from.right_idx - fromIndex, subMap.backingMap, to, 954 to == null ? 0 : to.right_idx - toIndex); 955 } 956 957 @Override 958 public int size() { 959 return subMap.size(); 960 } 961 } 962 963 /** 964 * Constructs a new empty {@code TreeMap} instance. 965 */ 966 public TreeMap() { 967 } 968 969 /** 970 * Constructs a new empty {@code TreeMap} instance with the specified 971 * comparator. 972 * 973 * @param comparator 974 * the comparator to compare keys with. 975 */ 976 public TreeMap(Comparator<? super K> comparator) { 977 this.comparator = comparator; 978 } 979 980 /** 981 * Constructs a new {@code TreeMap} instance containing the mappings from 982 * the specified map and using natural ordering. 983 * 984 * @param map 985 * the mappings to add. 986 * @throws ClassCastException 987 * if a key in the specified map does not implement the 988 * Comparable interface, or if the keys in the map cannot be 989 * compared. 990 */ 991 public TreeMap(Map<? extends K, ? extends V> map) { 992 putAll(map); 993 } 994 995 /** 996 * Constructs a new {@code TreeMap} instance containing the mappings from 997 * the specified SortedMap and using the same comparator. 998 * 999 * @param map 1000 * the mappings to add. 1001 */ 1002 public TreeMap(SortedMap<K, ? extends V> map) { 1003 this(map.comparator()); 1004 Node<K, V> lastNode = null; 1005 Iterator<? extends Map.Entry<K, ? extends V>> it = map.entrySet().iterator(); 1006 while (it.hasNext()) { 1007 Map.Entry<K, ? extends V> entry = it.next(); 1008 lastNode = addToLast(lastNode, entry.getKey(), entry.getValue()); 1009 } 1010 } 1011 1012 Node<K, V> addToLast(Node<K, V> last, K key, V value) { 1013 if (last == null) { 1014 root = last = createNode(key, value); 1015 size = 1; 1016 } else if (last.size == Node.NODE_SIZE) { 1017 Node<K, V> newNode = createNode(key, value); 1018 attachToRight(last, newNode); 1019 balance(newNode); 1020 size++; 1021 last = newNode; 1022 } else { 1023 appendFromRight(last, key, value); 1024 size++; 1025 } 1026 return last; 1027 } 1028 1029 /** 1030 * Removes all mappings from this TreeMap, leaving it empty. 1031 * 1032 * @see Map#isEmpty() 1033 * @see #size() 1034 */ 1035 @Override 1036 public void clear() { 1037 root = null; 1038 size = 0; 1039 modCount++; 1040 } 1041 1042 /** 1043 * Returns a new {@code TreeMap} with the same mappings, size and comparator 1044 * as this instance. 1045 * 1046 * @return a shallow copy of this instance. 1047 * @see java.lang.Cloneable 1048 */ 1049 @SuppressWarnings("unchecked") 1050 @Override 1051 public Object clone() { 1052 try { 1053 TreeMap<K, V> clone = (TreeMap<K, V>) super.clone(); 1054 clone.entrySet = null; 1055 if (root != null) { 1056 clone.root = root.clone(null); 1057 // restore prev/next chain 1058 Node<K, V> node = minimum(clone.root); 1059 while (true) { 1060 Node<K, V> nxt = successor(node); 1061 if (nxt == null) { 1062 break; 1063 } 1064 nxt.prev = node; 1065 node.next = nxt; 1066 node = nxt; 1067 } 1068 } 1069 return clone; 1070 } catch (CloneNotSupportedException e) { 1071 throw new AssertionError(e); // android-changed 1072 } 1073 } 1074 1075 static private <K, V> Node<K, V> successor(Node<K, V> x) { 1076 if (x.right != null) { 1077 return minimum(x.right); 1078 } 1079 Node<K, V> y = x.parent; 1080 while (y != null && x == y.right) { 1081 x = y; 1082 y = y.parent; 1083 } 1084 return y; 1085 } 1086 1087 /** 1088 * Returns the comparator used to compare elements in this map. 1089 * 1090 * @return the comparator or {@code null} if the natural ordering is used. 1091 */ 1092 public Comparator<? super K> comparator() { 1093 return comparator; 1094 } 1095 1096 /** 1097 * Returns whether this map contains the specified key. 1098 * 1099 * @param key 1100 * the key to search for. 1101 * @return {@code true} if this map contains the specified key, 1102 * {@code false} otherwise. 1103 * @throws ClassCastException 1104 * if the specified key cannot be compared with the keys in this 1105 * map. 1106 * @throws NullPointerException 1107 * if the specified key is {@code null} and the comparator 1108 * cannot handle {@code null} keys. 1109 */ 1110 @Override 1111 public boolean containsKey(Object key) { 1112 Comparable<K> object = comparator == null ? toComparable((K) key) : null; 1113 K keyK = (K) key; 1114 Node<K, V> node = root; 1115 while (node != null) { 1116 K[] keys = node.keys; 1117 int left_idx = node.left_idx; 1118 int result = cmp(object, keyK, keys[left_idx]); 1119 if (result < 0) { 1120 node = node.left; 1121 } else if (result == 0) { 1122 return true; 1123 } else { 1124 int right_idx = node.right_idx; 1125 if (left_idx != right_idx) { 1126 result = cmp(object, keyK, keys[right_idx]); 1127 } 1128 if (result > 0) { 1129 node = node.right; 1130 } else if (result == 0) { 1131 return true; 1132 } else { /*search in node*/ 1133 int low = left_idx + 1, mid = 0, high = right_idx - 1; 1134 while (low <= high) { 1135 mid = (low + high) >>> 1; 1136 result = cmp(object, keyK, keys[mid]); 1137 if (result > 0) { 1138 low = mid + 1; 1139 } else if (result == 0) { 1140 return true; 1141 } else { 1142 high = mid - 1; 1143 } 1144 } 1145 return false; 1146 } 1147 } 1148 } 1149 return false; 1150 } 1151 1152 /** 1153 * Returns whether this map contains the specified value. 1154 * 1155 * @param value 1156 * the value to search for. 1157 * @return {@code true} if this map contains the specified value, 1158 * {@code false} otherwise. 1159 */ 1160 @Override 1161 public boolean containsValue(Object value) { 1162 if (root == null) { 1163 return false; 1164 } 1165 Node<K, V> node = minimum(root); 1166 if (value != null) { 1167 while (node != null) { 1168 int to = node.right_idx; 1169 V[] values = node.values; 1170 for (int i = node.left_idx; i <= to; i++) { 1171 if (value.equals(values[i])) { 1172 return true; 1173 } 1174 } 1175 node = node.next; 1176 } 1177 } else { 1178 while (node != null) { 1179 int to = node.right_idx; 1180 V[] values = node.values; 1181 for (int i = node.left_idx; i <= to; i++) { 1182 if (values[i] == null) { 1183 return true; 1184 } 1185 } 1186 node = node.next; 1187 } 1188 } 1189 return false; 1190 } 1191 1192 /** 1193 * Returns a set containing all of the mappings in this map. Each mapping is 1194 * an instance of {@link Map.Entry}. As the set is backed by this map, 1195 * changes in one will be reflected in the other. It does not support adding 1196 * operations. 1197 * 1198 * @return a set of the mappings. 1199 */ 1200 @Override 1201 public Set<Map.Entry<K, V>> entrySet() { 1202 if (entrySet == null) { 1203 entrySet = new AbstractSet<Map.Entry<K, V>>() { 1204 @Override 1205 public int size() { 1206 return size; 1207 } 1208 1209 @Override 1210 public void clear() { 1211 TreeMap.this.clear(); 1212 } 1213 1214 @SuppressWarnings("unchecked") 1215 @Override 1216 public boolean contains(Object object) { 1217 if (object instanceof Map.Entry) { 1218 Map.Entry<K, V> entry = (Map.Entry<K, V>) object; 1219 K key = entry.getKey(); 1220 Object v1 = TreeMap.this.get(key), v2 = entry.getValue(); 1221 return v1 == null ? ( v2 == null && TreeMap.this.containsKey(key) ) : v1.equals(v2); 1222 } 1223 return false; 1224 } 1225 1226 @Override 1227 public boolean remove(Object object) { 1228 if (contains(object)) { 1229 Map.Entry<K, V> entry = (Map.Entry<K, V>) object; 1230 K key = entry.getKey(); 1231 TreeMap.this.remove(key); 1232 return true; 1233 } 1234 return false; 1235 } 1236 1237 @Override 1238 public Iterator<Map.Entry<K, V>> iterator() { 1239 return new UnboundedEntryIterator<K, V>(TreeMap.this); 1240 } 1241 }; 1242 } 1243 return entrySet; 1244 } 1245 1246 /** 1247 * Returns the first key in this map. 1248 * 1249 * @return the first key in this map. 1250 * @throws NoSuchElementException 1251 * if this map is empty. 1252 */ 1253 public K firstKey() { 1254 if (root != null) { 1255 Node<K, V> node = minimum(root); 1256 return node.keys[node.left_idx]; 1257 } 1258 throw new NoSuchElementException(); 1259 } 1260 1261 1262 /** 1263 * Returns the value of the mapping with the specified key. 1264 * 1265 * @param key 1266 * the key. 1267 * @return the value of the mapping with the specified key. 1268 * @throws ClassCastException 1269 * if the key cannot be compared with the keys in this map. 1270 * @throws NullPointerException 1271 * if the key is {@code null} and the comparator cannot handle 1272 * {@code null}. 1273 */ 1274 @Override 1275 public V get(Object key) { 1276 Comparable<K> object = comparator == null ? toComparable((K) key) : null; 1277 K keyK = (K) key; 1278 Node<K, V> node = root; 1279 while (node != null) { 1280 K[] keys = node.keys; 1281 int left_idx = node.left_idx; 1282 int result = cmp(object, keyK, keys[left_idx]); 1283 if (result < 0) { 1284 node = node.left; 1285 } else if (result == 0) { 1286 return node.values[left_idx]; 1287 } else { 1288 int right_idx = node.right_idx; 1289 if (left_idx != right_idx) { 1290 result = cmp(object, keyK, keys[right_idx]); 1291 } 1292 if (result > 0) { 1293 node = node.right; 1294 } else if (result == 0) { 1295 return node.values[right_idx]; 1296 } else { /*search in node*/ 1297 int low = left_idx + 1, mid = 0, high = right_idx - 1; 1298 while (low <= high) { 1299 mid = (low + high) >>> 1; 1300 result = cmp(object, keyK, keys[mid]); 1301 if (result > 0) { 1302 low = mid + 1; 1303 } else if (result == 0) { 1304 return node.values[mid]; 1305 } else { 1306 high = mid - 1; 1307 } 1308 } 1309 return null; 1310 } 1311 } 1312 } 1313 return null; 1314 } 1315 1316 private int cmp(Comparable<K> object, K key1, K key2) { 1317 return object != null ? 1318 object.compareTo(key2) : comparator.compare(key1, key2); 1319 } 1320 1321 /** 1322 * Returns a sorted map over a range of this sorted map with all keys that 1323 * are less than the specified {@code endKey}. Changes to the returned 1324 * sorted map are reflected in this sorted map and vice versa. 1325 * <p> 1326 * Note: The returned map will not allow an insertion of a key outside the 1327 * specified range. 1328 * 1329 * @param endKey 1330 * the high boundary of the range specified. 1331 * @return a sorted map where the keys are less than {@code endKey}. 1332 * @throws ClassCastException 1333 * if the specified key cannot be compared with the keys in this 1334 * map. 1335 * @throws NullPointerException 1336 * if the specified key is {@code null} and the comparator 1337 * cannot handle {@code null} keys. 1338 * @throws IllegalArgumentException 1339 * if this map is itself a sorted map over a range of another 1340 * map and the specified key is outside of its range. 1341 */ 1342 public SortedMap<K, V> headMap(K endKey) { 1343 // Check for errors 1344 if (comparator == null) { 1345 toComparable(endKey).compareTo(endKey); 1346 } else { 1347 comparator.compare(endKey, endKey); 1348 } 1349 return new SubMap<K, V>(this, endKey); 1350 } 1351 1352 /** 1353 * Returns a set of the keys contained in this map. The set is backed by 1354 * this map so changes to one are reflected by the other. The set does not 1355 * support adding. 1356 * 1357 * @return a set of the keys. 1358 */ 1359 @Override 1360 public Set<K> keySet() { 1361 if (keySet == null) { 1362 keySet = new AbstractSet<K>() { 1363 @Override 1364 public boolean contains(Object object) { 1365 return TreeMap.this.containsKey(object); 1366 } 1367 1368 @Override 1369 public int size() { 1370 return TreeMap.this.size; 1371 } 1372 1373 @Override 1374 public void clear() { 1375 TreeMap.this.clear(); 1376 } 1377 1378 @Override 1379 public boolean remove(Object object) { 1380 if (contains(object)) { 1381 TreeMap.this.remove(object); 1382 return true; 1383 } 1384 return false; 1385 } 1386 1387 @Override 1388 public Iterator<K> iterator() { 1389 return new UnboundedKeyIterator<K, V>(TreeMap.this); 1390 } 1391 }; 1392 } 1393 return keySet; 1394 } 1395 1396 /** 1397 * Returns the last key in this map. 1398 * 1399 * @return the last key in this map. 1400 * @throws NoSuchElementException 1401 * if this map is empty. 1402 */ 1403 public K lastKey() { 1404 if (root != null) { 1405 Node<K, V> node = maximum(root); 1406 return node.keys[node.right_idx]; 1407 } 1408 throw new NoSuchElementException(); 1409 } 1410 1411 static <K,V> Node<K, V> minimum(Node<K, V> x) { 1412 if (x == null) { 1413 return null; 1414 } 1415 while (x.left != null) { 1416 x = x.left; 1417 } 1418 return x; 1419 } 1420 1421 static <K,V> Node<K, V> maximum(Node<K, V> x) { 1422 if (x == null) { 1423 return null; 1424 } 1425 while (x.right != null) { 1426 x = x.right; 1427 } 1428 return x; 1429 } 1430 1431 /** 1432 * Maps the specified key to the specified value. 1433 * 1434 * @param key 1435 * the key. 1436 * @param value 1437 * the value. 1438 * @return the value of any previous mapping with the specified key or 1439 * {@code null} if there was no mapping. 1440 * @throws ClassCastException 1441 * if the specified key cannot be compared with the keys in this 1442 * map. 1443 * @throws NullPointerException 1444 * if the specified key is {@code null} and the comparator 1445 * cannot handle {@code null} keys. 1446 */ 1447 @Override 1448 public V put(K key, V value) { 1449 if (root == null) { 1450 root = createNode(key, value); 1451 size = 1; 1452 modCount++; 1453 return null; 1454 } 1455 Comparable<K> object = comparator == null ? toComparable((K) key) : null; 1456 K keyK = (K) key; 1457 Node<K, V> node = root; 1458 Node<K, V> prevNode = null; 1459 int result = 0; 1460 while (node != null) { 1461 prevNode = node; 1462 K[] keys = node.keys; 1463 int left_idx = node.left_idx; 1464 result = cmp(object, keyK, keys[left_idx]); 1465 if (result < 0) { 1466 node = node.left; 1467 } else if (result == 0) { 1468 V res = node.values[left_idx]; 1469 node.values[left_idx] = value; 1470 return res; 1471 } else { 1472 int right_idx = node.right_idx; 1473 if (left_idx != right_idx) { 1474 result = cmp(object, keyK, keys[right_idx]); 1475 } 1476 if (result > 0) { 1477 node = node.right; 1478 } else if (result == 0) { 1479 V res = node.values[right_idx]; 1480 node.values[right_idx] = value; 1481 return res; 1482 } else { /*search in node*/ 1483 int low = left_idx + 1, mid = 0, high = right_idx - 1; 1484 while (low <= high) { 1485 mid = (low + high) >>> 1; 1486 result = cmp(object, keyK, keys[mid]); 1487 if (result > 0) { 1488 low = mid + 1; 1489 } else if (result == 0) { 1490 V res = node.values[mid]; 1491 node.values[mid] = value; 1492 return res; 1493 } else { 1494 high = mid - 1; 1495 } 1496 } 1497 result = low; 1498 break; 1499 } 1500 } 1501 } /* while */ 1502/* 1503 if(node == null) { 1504 if(prevNode==null) { 1505 - case of empty Tree 1506 } else { 1507 result < 0 - prevNode.left==null - attach here 1508 result > 0 - prevNode.right==null - attach here 1509 } 1510 } else { 1511 insert into node. 1512 result - index where it should be inserted. 1513 } 1514 */ 1515 size++; 1516 modCount++; 1517 if (node == null) { 1518 if (prevNode == null) { 1519 // case of empty Tree 1520 root = createNode(key, value); 1521 } else if (prevNode.size < Node.NODE_SIZE) { 1522 // there is a place for insert 1523 if (result < 0) { 1524 appendFromLeft(prevNode, key, value); 1525 } else { 1526 appendFromRight(prevNode, key, value); 1527 } 1528 } else { 1529 // create and link 1530 Node<K, V> newNode = createNode(key, value); 1531 if (result < 0) { 1532 attachToLeft(prevNode, newNode); 1533 } else { 1534 attachToRight(prevNode, newNode); 1535 } 1536 balance(newNode); 1537 } 1538 } else { 1539 // insert into node. 1540 // result - index where it should be inserted. 1541 if (node.size < Node.NODE_SIZE) { // insert and ok 1542 int left_idx = node.left_idx; 1543 int right_idx = node.right_idx; 1544 if (left_idx == 0 || ((right_idx != Node.NODE_SIZE - 1) && (right_idx - result <= result - left_idx))) { 1545 int right_idxPlus1 = right_idx + 1; 1546 System.arraycopy(node.keys, result, node.keys, result + 1, right_idxPlus1 - result); 1547 System.arraycopy(node.values, result, node.values, result + 1, right_idxPlus1 - result); 1548 node.right_idx = right_idxPlus1; 1549 node.keys[result] = key; 1550 node.values[result] = value; 1551 } else { 1552 int left_idxMinus1 = left_idx - 1; 1553 System.arraycopy(node.keys, left_idx, node.keys, left_idxMinus1, result - left_idx); 1554 System.arraycopy(node.values, left_idx, node.values, left_idxMinus1, result - left_idx); 1555 node.left_idx = left_idxMinus1; 1556 node.keys[result - 1] = key; 1557 node.values[result - 1] = value; 1558 } 1559 node.size++; 1560 } else { 1561 // there are no place here 1562 // insert and push old pair 1563 Node<K, V> previous = node.prev; 1564 Node<K, V> nextNode = node.next; 1565 boolean removeFromStart; 1566 boolean attachFromLeft = false; 1567 Node<K, V> attachHere = null; 1568 if (previous == null) { 1569 if (nextNode != null && nextNode.size < Node.NODE_SIZE) { 1570 // move last pair to next 1571 removeFromStart = false; 1572 } else { 1573 // next node doesn't exist or full 1574 // left==null 1575 // drop first pair to new node from left 1576 removeFromStart = true; 1577 attachFromLeft = true; 1578 attachHere = node; 1579 } 1580 } else if (nextNode == null) { 1581 if (previous.size < Node.NODE_SIZE) { 1582 // move first pair to prev 1583 removeFromStart = true; 1584 } else { 1585 // right == null; 1586 // drop last pair to new node from right 1587 removeFromStart = false; 1588 attachFromLeft = false; 1589 attachHere = node; 1590 } 1591 } else { 1592 if (previous.size < Node.NODE_SIZE) { 1593 if (nextNode.size < Node.NODE_SIZE) { 1594 // choose prev or next for moving 1595 removeFromStart = previous.size < nextNode.size; 1596 } else { 1597 // move first pair to prev 1598 removeFromStart = true; 1599 } 1600 } else { 1601 if (nextNode.size < Node.NODE_SIZE) { 1602 // move last pair to next 1603 removeFromStart = false; 1604 } else { 1605 // prev & next are full 1606 // if node.right!=null then node.next.left==null 1607 // if node.left!=null then node.prev.right==null 1608 if (node.right == null) { 1609 attachHere = node; 1610 attachFromLeft = false; 1611 removeFromStart = false; 1612 } else { 1613 attachHere = nextNode; 1614 attachFromLeft = true; 1615 removeFromStart = false; 1616 } 1617 } 1618 } 1619 } 1620 K movedKey; 1621 V movedValue; 1622 if (removeFromStart) { 1623 // node.left_idx == 0 1624 movedKey = node.keys[0]; 1625 movedValue = node.values[0]; 1626 int resMunus1 = result - 1; 1627 System.arraycopy(node.keys, 1, node.keys, 0, resMunus1); 1628 System.arraycopy(node.values, 1, node.values, 0, resMunus1); 1629 node.keys [resMunus1] = key; 1630 node.values[resMunus1] = value; 1631 } else { 1632 // node.right_idx == Node.NODE_SIZE - 1 1633 movedKey = node.keys[Node.NODE_SIZE - 1]; 1634 movedValue = node.values[Node.NODE_SIZE - 1]; 1635 System.arraycopy(node.keys, result, node.keys, result + 1, Node.NODE_SIZE - 1 - result); 1636 System.arraycopy(node.values, result, node.values, result + 1, Node.NODE_SIZE - 1 - result); 1637 node.keys[result] = key; 1638 node.values[result] = value; 1639 } 1640 if (attachHere == null) { 1641 if (removeFromStart) { 1642 appendFromRight(previous, movedKey, movedValue); 1643 } else { 1644 appendFromLeft(nextNode, movedKey, movedValue); 1645 } 1646 } else { 1647 Node<K, V> newNode = createNode(movedKey, movedValue); 1648 if (attachFromLeft) { 1649 attachToLeft(attachHere, newNode); 1650 } else { 1651 attachToRight(attachHere, newNode); 1652 } 1653 balance(newNode); 1654 } 1655 } 1656 } 1657 return null; 1658 } 1659 1660 private void appendFromLeft(Node<K, V> node, K keyObj, V value) { 1661 if (node.left_idx == 0) { 1662 int new_right = node.right_idx + 1; 1663 System.arraycopy(node.keys, 0, node.keys, 1, new_right); 1664 System.arraycopy(node.values, 0, node.values, 1, new_right); 1665 node.right_idx = new_right; 1666 } else { 1667 node.left_idx--; 1668 } 1669 node.size++; 1670 node.keys[node.left_idx] = keyObj; 1671 node.values[node.left_idx] = value; 1672 } 1673 1674 private void attachToLeft(Node<K, V> node, Node<K, V> newNode) { 1675 newNode.parent = node; 1676 // node.left==null - attach here 1677 node.left = newNode; 1678 Node<K, V> predecessor = node.prev; 1679 newNode.prev = predecessor; 1680 newNode.next = node; 1681 if (predecessor != null) { 1682 predecessor.next = newNode; 1683 } 1684 node.prev = newNode; 1685 } 1686 1687 /* add pair into node; existence free room in the node should be checked 1688 * before call 1689 */ 1690 private void appendFromRight(Node<K, V> node, K keyObj, V value) { 1691 if (node.right_idx == Node.NODE_SIZE - 1) { 1692 int left_idx = node.left_idx; 1693 int left_idxMinus1 = left_idx - 1; 1694 System.arraycopy(node.keys, left_idx, node.keys, left_idxMinus1, Node.NODE_SIZE - left_idx); 1695 System.arraycopy(node.values, left_idx, node.values, left_idxMinus1, Node.NODE_SIZE - left_idx); 1696 node.left_idx = left_idxMinus1; 1697 } else { 1698 node.right_idx++; 1699 } 1700 node.size++; 1701 node.keys[node.right_idx] = keyObj; 1702 node.values[node.right_idx] = value; 1703 } 1704 1705 private void attachToRight(Node<K, V> node, Node<K, V> newNode) { 1706 newNode.parent = node; 1707 // - node.right==null - attach here 1708 node.right = newNode; 1709 newNode.prev = node; 1710 Node<K, V> successor = node.next; 1711 newNode.next = successor; 1712 if (successor != null) { 1713 successor.prev = newNode; 1714 } 1715 node.next = newNode; 1716 } 1717 1718 private Node<K, V> createNode(K keyObj, V value) { 1719 Node<K, V> node = new Node<K, V>(); 1720 node.keys[0] = keyObj; 1721 node.values[0] = value; 1722 node.left_idx = 0; 1723 node.right_idx = 0; 1724 node.size = 1; 1725 return node; 1726 } 1727 1728 void balance(Node<K, V> x) { 1729 Node<K, V> y; 1730 x.color = true; 1731 while (x != root && x.parent.color) { 1732 if (x.parent == x.parent.parent.left) { 1733 y = x.parent.parent.right; 1734 if (y != null && y.color) { 1735 x.parent.color = false; 1736 y.color = false; 1737 x.parent.parent.color = true; 1738 x = x.parent.parent; 1739 } else { 1740 if (x == x.parent.right) { 1741 x = x.parent; 1742 leftRotate(x); 1743 } 1744 x.parent.color = false; 1745 x.parent.parent.color = true; 1746 rightRotate(x.parent.parent); 1747 } 1748 } else { 1749 y = x.parent.parent.left; 1750 if (y != null && y.color) { 1751 x.parent.color = false; 1752 y.color = false; 1753 x.parent.parent.color = true; 1754 x = x.parent.parent; 1755 } else { 1756 if (x == x.parent.left) { 1757 x = x.parent; 1758 rightRotate(x); 1759 } 1760 x.parent.color = false; 1761 x.parent.parent.color = true; 1762 leftRotate(x.parent.parent); 1763 } 1764 } 1765 } 1766 root.color = false; 1767 } 1768 1769 private void rightRotate(Node<K, V> x) { 1770 Node<K, V> y = x.left; 1771 x.left = y.right; 1772 if (y.right != null) { 1773 y.right.parent = x; 1774 } 1775 y.parent = x.parent; 1776 if (x.parent == null) { 1777 root = y; 1778 } else { 1779 if (x == x.parent.right) { 1780 x.parent.right = y; 1781 } else { 1782 x.parent.left = y; 1783 } 1784 } 1785 y.right = x; 1786 x.parent = y; 1787 } 1788 1789 1790 private void leftRotate(Node<K, V> x) { 1791 Node<K, V> y = x.right; 1792 x.right = y.left; 1793 if (y.left != null) { 1794 y.left.parent = x; 1795 } 1796 y.parent = x.parent; 1797 if (x.parent == null) { 1798 root = y; 1799 } else { 1800 if (x == x.parent.left) { 1801 x.parent.left = y; 1802 } else { 1803 x.parent.right = y; 1804 } 1805 } 1806 y.left = x; 1807 x.parent = y; 1808 } 1809 1810 1811 /** 1812 * Copies all the mappings in the given map to this map. These mappings will 1813 * replace all mappings that this map had for any of the keys currently in 1814 * the given map. 1815 * 1816 * @param map 1817 * the map to copy mappings from. 1818 * @throws ClassCastException 1819 * if a key in the specified map cannot be compared with the 1820 * keys in this map. 1821 * @throws NullPointerException 1822 * if a key in the specified map is {@code null} and the 1823 * comparator cannot handle {@code null} keys. 1824 */ 1825 @Override 1826 public void putAll(Map<? extends K, ? extends V> map) { 1827 super.putAll(map); 1828 } 1829 1830 /** 1831 * Removes the mapping with the specified key from this map. 1832 * 1833 * @param key 1834 * the key of the mapping to remove. 1835 * @return the value of the removed mapping or {@code null} if no mapping 1836 * for the specified key was found. 1837 * @throws ClassCastException 1838 * if the specified key cannot be compared with the keys in this 1839 * map. 1840 * @throws NullPointerException 1841 * if the specified key is {@code null} and the comparator 1842 * cannot handle {@code null} keys. 1843 */ 1844 @Override 1845 public V remove(Object key) { 1846 if (size == 0) { 1847 return null; 1848 } 1849 Comparable<K> object = comparator == null ? toComparable((K) key) : null; 1850 K keyK = (K) key; 1851 Node<K, V> node = root; 1852 while (node != null) { 1853 K[] keys = node.keys; 1854 int left_idx = node.left_idx; 1855 int result = cmp(object, keyK, keys[left_idx]); 1856 if (result < 0) { 1857 node = node.left; 1858 } else if (result == 0) { 1859 V value = node.values[left_idx]; 1860 removeLeftmost(node); 1861 return value; 1862 } else { 1863 int right_idx = node.right_idx; 1864 if (left_idx != right_idx) { 1865 result = cmp(object, keyK, keys[right_idx]); 1866 } 1867 if (result > 0) { 1868 node = node.right; 1869 } else if (result == 0) { 1870 V value = node.values[right_idx]; 1871 removeRightmost(node); 1872 return value; 1873 } else { /*search in node*/ 1874 int low = left_idx + 1, mid = 0, high = right_idx - 1; 1875 while (low <= high) { 1876 mid = (low + high) >>> 1; 1877 result = cmp(object, keyK, keys[mid]); 1878 if (result > 0) { 1879 low = mid + 1; 1880 } else if (result == 0) { 1881 V value = node.values[mid]; 1882 removeMiddleElement(node, mid); 1883 return value; 1884 } else { 1885 high = mid - 1; 1886 } 1887 } 1888 return null; 1889 } 1890 } 1891 } 1892 return null; 1893 } 1894 1895 void removeLeftmost(Node<K, V> node) { 1896 int index = node.left_idx; 1897 if (node.size == 1) { 1898 deleteNode(node); 1899 } else if (node.prev != null && (Node.NODE_SIZE - 1 - node.prev.right_idx) > node.size) { 1900 // move all to prev node and kill it 1901 Node<K, V> prev = node.prev; 1902 int size = node.right_idx - index; 1903 System.arraycopy(node.keys, index + 1, prev.keys, prev.right_idx + 1, size); 1904 System.arraycopy(node.values, index + 1, prev.values, prev.right_idx + 1, size); 1905 prev.right_idx += size; 1906 prev.size += size; 1907 deleteNode(node); 1908 } else if (node.next != null && (node.next.left_idx) > node.size) { 1909 // move all to next node and kill it 1910 Node<K, V> next = node.next; 1911 int size = node.right_idx - index; 1912 int next_new_left = next.left_idx - size; 1913 next.left_idx = next_new_left; 1914 System.arraycopy(node.keys, index + 1, next.keys, next_new_left, size); 1915 System.arraycopy(node.values, index + 1, next.values, next_new_left, size); 1916 next.size += size; 1917 deleteNode(node); 1918 } else { 1919 node.keys[index] = null; 1920 node.values[index] = null; 1921 node.left_idx++; 1922 node.size--; 1923 Node<K, V> prev = node.prev; 1924 if (prev != null && prev.size == 1) { 1925 node.size++; 1926 node.left_idx--; 1927 node.keys [node.left_idx] = prev.keys [prev.left_idx]; 1928 node.values[node.left_idx] = prev.values[prev.left_idx]; 1929 deleteNode(prev); 1930 } 1931 } 1932 modCount++; 1933 size--; 1934 } 1935 1936 void removeRightmost(Node<K, V> node) { 1937 int index = node.right_idx; 1938 if (node.size == 1) { 1939 deleteNode(node); 1940 } else if (node.prev != null && (Node.NODE_SIZE - 1 - node.prev.right_idx) > node.size) { 1941 // move all to prev node and kill it 1942 Node<K, V> prev = node.prev; 1943 int left_idx = node.left_idx; 1944 int size = index - left_idx; 1945 System.arraycopy(node.keys, left_idx, prev.keys, prev.right_idx + 1, size); 1946 System.arraycopy(node.values, left_idx, prev.values, prev.right_idx + 1, size); 1947 prev.right_idx += size; 1948 prev.size += size; 1949 deleteNode(node); 1950 } else if (node.next != null && (node.next.left_idx) > node.size) { 1951 // move all to next node and kill it 1952 Node<K, V> next = node.next; 1953 int left_idx = node.left_idx; 1954 int size = index - left_idx; 1955 int next_new_left = next.left_idx - size; 1956 next.left_idx = next_new_left; 1957 System.arraycopy(node.keys, left_idx, next.keys, next_new_left, size); 1958 System.arraycopy(node.values, left_idx, next.values, next_new_left, size); 1959 next.size += size; 1960 deleteNode(node); 1961 } else { 1962 node.keys[index] = null; 1963 node.values[index] = null; 1964 node.right_idx--; 1965 node.size--; 1966 Node<K, V> next = node.next; 1967 if (next != null && next.size == 1) { 1968 node.size++; 1969 node.right_idx++; 1970 node.keys[node.right_idx] = next.keys[next.left_idx]; 1971 node.values[node.right_idx] = next.values[next.left_idx]; 1972 deleteNode(next); 1973 } 1974 } 1975 modCount++; 1976 size--; 1977 } 1978 1979 void removeMiddleElement(Node<K, V> node, int index) { 1980 // this function is called iff index if some middle element; 1981 // so node.left_idx < index < node.right_idx 1982 // condition above assume that node.size > 1 1983 if (node.prev != null && (Node.NODE_SIZE - 1 - node.prev.right_idx) > node.size) { 1984 // move all to prev node and kill it 1985 Node<K, V> prev = node.prev; 1986 int left_idx = node.left_idx; 1987 int size = index - left_idx; 1988 System.arraycopy(node.keys, left_idx, prev.keys, prev.right_idx + 1, size); 1989 System.arraycopy(node.values, left_idx, prev.values, prev.right_idx + 1, size); 1990 prev.right_idx += size; 1991 size = node.right_idx - index; 1992 System.arraycopy(node.keys, index + 1, prev.keys, prev.right_idx + 1, size); 1993 System.arraycopy(node.values, index + 1, prev.values, prev.right_idx + 1, size); 1994 prev.right_idx += size; 1995 prev.size += (node.size - 1); 1996 deleteNode(node); 1997 } else if (node.next != null && (node.next.left_idx) > node.size) { 1998 // move all to next node and kill it 1999 Node<K, V> next = node.next; 2000 int left_idx = node.left_idx; 2001 int next_new_left = next.left_idx - node.size + 1; 2002 next.left_idx = next_new_left; 2003 int size = index - left_idx; 2004 System.arraycopy(node.keys, left_idx, next.keys, next_new_left, size); 2005 System.arraycopy(node.values, left_idx, next.values, next_new_left, size); 2006 next_new_left += size; 2007 size = node.right_idx - index; 2008 System.arraycopy(node.keys, index + 1, next.keys, next_new_left, size); 2009 System.arraycopy(node.values, index + 1, next.values, next_new_left, size); 2010 next.size += (node.size - 1); 2011 deleteNode(node); 2012 } else { 2013 int moveFromRight = node.right_idx - index; 2014 int left_idx = node.left_idx; 2015 int moveFromLeft = index - left_idx ; 2016 if (moveFromRight <= moveFromLeft) { 2017 System.arraycopy(node.keys, index + 1, node.keys, index, moveFromRight); 2018 System.arraycopy(node.values, index + 1, node.values, index, moveFromRight); 2019 Node<K, V> next = node.next; 2020 if (next != null && next.size == 1) { 2021 node.keys [node.right_idx] = next.keys [next.left_idx]; 2022 node.values[node.right_idx] = next.values[next.left_idx]; 2023 deleteNode(next); 2024 } else { 2025 node.keys [node.right_idx] = null; 2026 node.values[node.right_idx] = null; 2027 node.right_idx--; 2028 node.size--; 2029 } 2030 } else { 2031 System.arraycopy(node.keys, left_idx , node.keys, left_idx + 1, moveFromLeft); 2032 System.arraycopy(node.values, left_idx , node.values, left_idx + 1, moveFromLeft); 2033 Node<K, V> prev = node.prev; 2034 if (prev != null && prev.size == 1) { 2035 node.keys [left_idx ] = prev.keys [prev.left_idx]; 2036 node.values[left_idx ] = prev.values[prev.left_idx]; 2037 deleteNode(prev); 2038 } else { 2039 node.keys [left_idx ] = null; 2040 node.values[left_idx ] = null; 2041 node.left_idx++; 2042 node.size--; 2043 } 2044 } 2045 } 2046 modCount++; 2047 size--; 2048 } 2049 2050 void removeFromIterator(Node<K, V> node, int index) { 2051 if (node.size == 1) { 2052 // it is safe to delete the whole node here. 2053 // iterator already moved to the next node; 2054 deleteNode(node); 2055 } else { 2056 int left_idx = node.left_idx; 2057 if (index == left_idx) { 2058 Node<K, V> prev = node.prev; 2059 if (prev != null && prev.size == 1) { 2060 node.keys [left_idx] = prev.keys [prev.left_idx]; 2061 node.values[left_idx] = prev.values[prev.left_idx]; 2062 deleteNode(prev); 2063 } else { 2064 node.keys [left_idx] = null; 2065 node.values[left_idx] = null; 2066 node.left_idx++; 2067 node.size--; 2068 } 2069 } else if (index == node.right_idx) { 2070 node.keys [index] = null; 2071 node.values[index] = null; 2072 node.right_idx--; 2073 node.size--; 2074 } else { 2075 int moveFromRight = node.right_idx - index; 2076 int moveFromLeft = index - left_idx; 2077 if (moveFromRight <= moveFromLeft) { 2078 System.arraycopy(node.keys, index + 1, node.keys, index, moveFromRight ); 2079 System.arraycopy(node.values, index + 1, node.values, index, moveFromRight ); 2080 node.keys [node.right_idx] = null; 2081 node.values[node.right_idx] = null; 2082 node.right_idx--; 2083 node.size--; 2084 } else { 2085 System.arraycopy(node.keys, left_idx, node.keys, left_idx+ 1, moveFromLeft); 2086 System.arraycopy(node.values, left_idx, node.values, left_idx+ 1, moveFromLeft); 2087 node.keys [left_idx] = null; 2088 node.values[left_idx] = null; 2089 node.left_idx++; 2090 node.size--; 2091 } 2092 } 2093 } 2094 modCount++; 2095 size--; 2096 } 2097 2098 private void deleteNode(Node<K, V> node) { 2099 if (node.right == null) { 2100 if (node.left != null) { 2101 attachToParent(node, node.left); 2102 } else { 2103 attachNullToParent(node); 2104 } 2105 fixNextChain(node); 2106 } else if(node.left == null) { // node.right != null 2107 attachToParent(node, node.right); 2108 fixNextChain(node); 2109 } else { 2110 // Here node.left!=nul && node.right!=null 2111 // node.next should replace node in tree 2112 // node.next!=null by tree logic. 2113 // node.next.left==null by tree logic. 2114 // node.next.right may be null or non-null 2115 Node<K, V> toMoveUp = node.next; 2116 fixNextChain(node); 2117 if(toMoveUp.right==null){ 2118 attachNullToParent(toMoveUp); 2119 } else { 2120 attachToParent(toMoveUp, toMoveUp.right); 2121 } 2122 // Here toMoveUp is ready to replace node 2123 toMoveUp.left = node.left; 2124 if (node.left != null) { 2125 node.left.parent = toMoveUp; 2126 } 2127 toMoveUp.right = node.right; 2128 if (node.right != null) { 2129 node.right.parent = toMoveUp; 2130 } 2131 attachToParentNoFixup(node,toMoveUp); 2132 toMoveUp.color = node.color; 2133 } 2134 } 2135 2136 private void attachToParentNoFixup(Node<K, V> toDelete, Node<K, V> toConnect) { 2137 // assert toConnect!=null 2138 Node<K,V> parent = toDelete.parent; 2139 toConnect.parent = parent; 2140 if (parent == null) { 2141 root = toConnect; 2142 } else if (toDelete == parent.left) { 2143 parent.left = toConnect; 2144 } else { 2145 parent.right = toConnect; 2146 } 2147 } 2148 2149 private void attachToParent(Node<K, V> toDelete, Node<K, V> toConnect) { 2150 // assert toConnect!=null 2151 attachToParentNoFixup(toDelete,toConnect); 2152 if (!toDelete.color) { 2153 fixup(toConnect); 2154 } 2155 } 2156 2157 private void attachNullToParent(Node<K, V> toDelete) { 2158 Node<K, V> parent = toDelete.parent; 2159 if (parent == null) { 2160 root = null; 2161 } else { 2162 if (toDelete == parent.left) { 2163 parent.left = null; 2164 } else { 2165 parent.right = null; 2166 } 2167 if (!toDelete.color) { 2168 fixup(parent); 2169 } 2170 } 2171 } 2172 2173 private void fixNextChain(Node<K, V> node) { 2174 if (node.prev != null) { 2175 node.prev.next = node.next; 2176 } 2177 if (node.next != null) { 2178 node.next.prev = node.prev; 2179 } 2180 } 2181 2182 private void fixup(Node<K, V> x) { 2183 Node<K, V> w; 2184 while (x != root && !x.color) { 2185 if (x == x.parent.left) { 2186 w = x.parent.right; 2187 if (w == null) { 2188 x = x.parent; 2189 continue; 2190 } 2191 if (w.color) { 2192 w.color = false; 2193 x.parent.color = true; 2194 leftRotate(x.parent); 2195 w = x.parent.right; 2196 if (w == null) { 2197 x = x.parent; 2198 continue; 2199 } 2200 } 2201 if ((w.left == null || !w.left.color) 2202 && (w.right == null || !w.right.color)) { 2203 w.color = true; 2204 x = x.parent; 2205 } else { 2206 if (w.right == null || !w.right.color) { 2207 w.left.color = false; 2208 w.color = true; 2209 rightRotate(w); 2210 w = x.parent.right; 2211 } 2212 w.color = x.parent.color; 2213 x.parent.color = false; 2214 w.right.color = false; 2215 leftRotate(x.parent); 2216 x = root; 2217 } 2218 } else { 2219 w = x.parent.left; 2220 if (w == null) { 2221 x = x.parent; 2222 continue; 2223 } 2224 if (w.color) { 2225 w.color = false; 2226 x.parent.color = true; 2227 rightRotate(x.parent); 2228 w = x.parent.left; 2229 if (w == null) { 2230 x = x.parent; 2231 continue; 2232 } 2233 } 2234 if ((w.left == null || !w.left.color) 2235 && (w.right == null || !w.right.color)) { 2236 w.color = true; 2237 x = x.parent; 2238 } else { 2239 if (w.left == null || !w.left.color) { 2240 w.right.color = false; 2241 w.color = true; 2242 leftRotate(w); 2243 w = x.parent.left; 2244 } 2245 w.color = x.parent.color; 2246 x.parent.color = false; 2247 w.left.color = false; 2248 rightRotate(x.parent); 2249 x = root; 2250 } 2251 } 2252 } 2253 x.color = false; 2254 } 2255 2256 2257 /** 2258 * Returns the number of mappings in this map. 2259 * 2260 * @return the number of mappings in this map. 2261 */ 2262 @Override 2263 public int size() { 2264 return size; 2265 } 2266 2267 /** 2268 * Returns a sorted map over a range of this sorted map with all keys 2269 * greater than or equal to the specified {@code startKey} and less than the 2270 * specified {@code endKey}. Changes to the returned sorted map are 2271 * reflected in this sorted map and vice versa. 2272 * <p> 2273 * Note: The returned map will not allow an insertion of a key outside the 2274 * specified range. 2275 * 2276 * @param startKey 2277 * the low boundary of the range (inclusive). 2278 * @param endKey 2279 * the high boundary of the range (exclusive), 2280 * @return a sorted map with the key from the specified range. 2281 * @throws ClassCastException 2282 * if the start or end key cannot be compared with the keys in 2283 * this map. 2284 * @throws NullPointerException 2285 * if the start or end key is {@code null} and the comparator 2286 * cannot handle {@code null} keys. 2287 * @throws IllegalArgumentException 2288 * if the start key is greater than the end key, or if this map 2289 * is itself a sorted map over a range of another sorted map and 2290 * the specified range is outside of its range. 2291 */ 2292 public SortedMap<K, V> subMap(K startKey, K endKey) { 2293 if (comparator == null) { 2294 if (toComparable(startKey).compareTo(endKey) <= 0) { 2295 return new SubMap<K, V>(startKey, this, endKey); 2296 } 2297 } else { 2298 if (comparator.compare(startKey, endKey) <= 0) { 2299 return new SubMap<K, V>(startKey, this, endKey); 2300 } 2301 } 2302 throw new IllegalArgumentException(); 2303 } 2304 2305 /** 2306 * Returns a sorted map over a range of this sorted map with all keys that 2307 * are greater than or equal to the specified {@code startKey}. Changes to 2308 * the returned sorted map are reflected in this sorted map and vice versa. 2309 * <p> 2310 * Note: The returned map will not allow an insertion of a key outside the 2311 * specified range. 2312 * 2313 * @param startKey 2314 * the low boundary of the range specified. 2315 * @return a sorted map where the keys are greater or equal to 2316 * {@code startKey}. 2317 * @throws ClassCastException 2318 * if the specified key cannot be compared with the keys in this 2319 * map. 2320 * @throws NullPointerException 2321 * if the specified key is {@code null} and the comparator 2322 * cannot handle {@code null} keys. 2323 * @throws IllegalArgumentException 2324 * if this map itself a sorted map over a range of another map 2325 * and the specified key is outside of its range. 2326 */ 2327 public SortedMap<K, V> tailMap(K startKey) { 2328 // Check for errors 2329 if (comparator == null) { 2330 toComparable(startKey).compareTo(startKey); 2331 } else { 2332 comparator.compare(startKey, startKey); 2333 } 2334 return new SubMap<K, V>(startKey, this); 2335 } 2336 2337 /** 2338 * Returns a collection of the values contained in this map. The collection 2339 * is backed by this map so changes to one are reflected by the other. The 2340 * collection supports remove, removeAll, retainAll and clear operations, 2341 * and it does not support add or addAll operations. 2342 * <p> 2343 * This method returns a collection which is the subclass of 2344 * AbstractCollection. The iterator method of this subclass returns a 2345 * "wrapper object" over the iterator of map's entrySet(). The {@code size} 2346 * method wraps the map's size method and the {@code contains} method wraps 2347 * the map's containsValue method. 2348 * <p> 2349 * The collection is created when this method is called for the first time 2350 * and returned in response to all subsequent calls. This method may return 2351 * different collections when multiple concurrent calls occur, since no 2352 * synchronization is performed. 2353 * 2354 * @return a collection of the values contained in this map. 2355 */ 2356 @Override 2357 public Collection<V> values() { 2358 if (valuesCollection == null) { 2359 valuesCollection = new AbstractCollection<V>() { 2360 @Override 2361 public boolean contains(Object object) { 2362 return containsValue(object); 2363 } 2364 2365 @Override 2366 public int size() { 2367 return size; 2368 } 2369 2370 @Override 2371 public void clear() { 2372 TreeMap.this.clear(); 2373 } 2374 2375 @Override 2376 public Iterator<V> iterator() { 2377 return new UnboundedValueIterator<K, V>(TreeMap.this); 2378 } 2379 }; 2380 } 2381 return valuesCollection; 2382 } 2383 2384 private void writeObject(ObjectOutputStream stream) throws IOException { 2385 stream.defaultWriteObject(); 2386 stream.writeInt(size); 2387 if (size > 0) { 2388 Node<K, V> node = minimum(root); 2389 while (node != null) { 2390 int to = node.right_idx; 2391 for (int i = node.left_idx; i <= to; i++) { 2392 stream.writeObject(node.keys[i]); 2393 stream.writeObject(node.values[i]); 2394 } 2395 node = node.next; 2396 } 2397 } 2398 } 2399 2400 @SuppressWarnings("unchecked") 2401 private void readObject(ObjectInputStream stream) throws IOException, 2402 ClassNotFoundException { 2403 stream.defaultReadObject(); 2404 int size = stream.readInt(); 2405 Node<K, V> lastNode = null; 2406 for (int i = 0; i < size; i++) { 2407 lastNode = addToLast(lastNode, (K) stream.readObject(), (V) stream.readObject()); 2408 } 2409 } 2410} 2411