001 /** 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 package org.fusesource.hawtdb.util; 018 019 import java.io.Serializable; 020 import java.util.AbstractCollection; 021 import java.util.AbstractSet; 022 import java.util.Collection; 023 import java.util.Comparator; 024 import java.util.Iterator; 025 import java.util.Map; 026 import java.util.Set; 027 import java.util.Map.Entry; 028 029 /** 030 * A TreeMap that is lighter weight than the Sun implementation with 031 * implementations for upper/lower/floor/ceiling accessors. 032 * 033 * @author <a href="http://hiramchirino.com">Hiram Chirino</a> 034 */ 035 public class TreeMap<K, V> implements Serializable { 036 037 private static final long serialVersionUID = 6107175734705142096L; 038 039 private static final boolean RED = false; 040 private static final boolean BLACK = true; 041 042 private int count; 043 private TreeEntry<K, V> root; 044 private final Comparator<? super K> comparator; 045 046 public TreeMap() { 047 this.comparator = null; 048 } 049 050 @SuppressWarnings("unchecked") 051 private int compare(K k1, K k2) { 052 if (comparator != null) { 053 return comparator.compare(k1, k2); 054 } else { 055 return ((Comparable<K>) k1).compareTo(k2); 056 } 057 } 058 059 public TreeMap(Comparator<? super K> comparator) { 060 this.comparator = comparator; 061 } 062 063 public Comparator<? super K> comparator() { 064 return comparator; 065 } 066 067 /** 068 * 069 * @return The first key in the map. 070 */ 071 public K firstKey() { 072 TreeEntry<K, V> first = firstEntry(); 073 if (first != null) { 074 return first.key; 075 } 076 return null; 077 } 078 079 /** 080 * @return The last key in the map. 081 */ 082 public K lastKey() { 083 TreeEntry<K, V> last = lastEntry(); 084 if (last != null) { 085 return last.key; 086 } 087 return null; 088 } 089 090 /** 091 * Clears all elements in this map. 092 */ 093 public void clear() { 094 //TODO possible assist gc here by scanning and removing refs? 095 //Will almost certain want to do this if we switch this over 096 //to allowing additions to be the entries themselves. 097 root = null; 098 count = 0; 099 } 100 101 /* 102 * (non-Javadoc) 103 * 104 * @see java.util.Map#containsKey(java.lang.Object) 105 */ 106 public boolean containsKey(K key) { 107 return getEntry(key, root) != null; 108 } 109 110 /* 111 * (non-Javadoc) 112 * 113 * @see java.util.Map#containsValue(java.lang.Object) 114 */ 115 public boolean containsValue(Object value) { 116 for (Map.Entry<K, V> entry : entrySet()) { 117 if (entry.getValue() == value) { 118 return true; 119 } else if (value != null && value.equals(entry)) { 120 return true; 121 } 122 } 123 return false; 124 } 125 126 /* 127 * (non-Javadoc) 128 * 129 * @see java.util.Map#entrySet() 130 */ 131 public Set<Map.Entry<K, V>> entrySet() { 132 return new AbstractSet<Map.Entry<K, V>>() { 133 134 @Override 135 public Iterator<Entry<K, V>> iterator() { 136 return new EntryIterator(); 137 } 138 139 @SuppressWarnings("unchecked") 140 @Override 141 public boolean contains(Object o) { 142 try { 143 Map.Entry<K, V> entry = (Map.Entry<K, V>) o; 144 TreeEntry<K, V> ours = getEntry(entry.getKey(), root); 145 if (ours != null) { 146 return ours.value == null ? entry.getValue() == null : ours.value.equals(entry.getValue()); 147 } else { 148 return false; 149 } 150 } catch (ClassCastException cce) { 151 return false; 152 } 153 } 154 155 @SuppressWarnings("unchecked") 156 @Override 157 public boolean remove(Object o) { 158 return TreeMap.this.removeEntry((TreeEntry<K, V>) o) != null; 159 } 160 161 @Override 162 public int size() { 163 return count; 164 } 165 166 @Override 167 public void clear() { 168 TreeMap.this.clear(); 169 } 170 }; 171 } 172 173 /* 174 * (non-Javadoc) 175 * 176 * @see java.util.Map#get(java.lang.Object) 177 */ 178 public V get(K key) { 179 TreeEntry<K, V> node = getEntry(key, root); 180 if (node != null) { 181 return node.value; 182 } 183 return null; 184 } 185 186 public final TreeEntry<K, V> getEntry(K key) { 187 return getEntry(key, root); 188 } 189 190 private final TreeEntry<K, V> getEntry(K key, TreeEntry<K, V> r) { 191 while (r != null) { 192 int c = compare(key, r.key); 193 if (c == 0) { 194 return r; 195 } else if (c > 0) { 196 r = r.right; 197 } else { 198 r = r.left; 199 } 200 } 201 return null; 202 } 203 204 /** 205 * Returns a key-value mapping associated with the least key in this map, or 206 * null if the map is empty. 207 * 208 * @return The lowest key in the map 209 */ 210 public TreeEntry<K, V> firstEntry() { 211 TreeEntry<K, V> r = root; 212 while (r != null) { 213 if (r.left == null) { 214 break; 215 } 216 r = r.left; 217 } 218 219 return r; 220 } 221 222 /** 223 * Returns a key-value mapping associated with the greatest key in this map, 224 * or null if the map is empty. 225 * 226 * @return The entry associated with the greates key in the map. 227 */ 228 public TreeEntry<K, V> lastEntry() { 229 TreeEntry<K, V> r = root; 230 while (r != null) { 231 if (r.right == null) { 232 break; 233 } 234 r = r.right; 235 } 236 237 return r; 238 } 239 240 /** 241 * Returns a key-value mapping associated with the greatest key strictly 242 * less than the given key, or null if there is no such key 243 * 244 * @param key 245 * the key. 246 * @return 247 */ 248 public TreeEntry<K, V> lowerEntry(K key) { 249 TreeEntry<K, V> n = root; 250 TreeEntry<K, V> l = null; 251 while (n != null) { 252 int c = compare(key, n.key); 253 if (c <= 0) { 254 n = n.left; 255 } else { 256 //Update the low node: 257 if (l == null || compare(n.key, l.key) > 0) { 258 l = n; 259 } 260 //Now need to scan the right tree to see if there is 261 //a higher low value to consider: 262 if (n.right == null) { 263 break; 264 } 265 n = n.right; 266 } 267 } 268 return l; 269 } 270 271 /** 272 * Returns a key-value mapping associated with the greatest key less than or 273 * equal to the given key, or null if there is no such key. 274 * 275 * @param key 276 * The key for which to search. 277 * @return a key-value mapping associated with the greatest key less than or 278 * equal to the given key, or null if there is no such key. 279 */ 280 public TreeEntry<K, V> floorEntry(K key) { 281 TreeEntry<K, V> n = root; 282 TreeEntry<K, V> l = null; 283 while (n != null) { 284 int c = compare(key, n.key); 285 if (c == 0) { 286 return n; 287 } 288 289 if (c < 0) { 290 n = n.left; 291 } else { 292 //Update the low node: 293 if (l == null || compare(n.key, l.key) > 0) { 294 l = n; 295 } 296 //Now need to scan the right tree to see if there is 297 //a higher low value to consider: 298 if (n.right == null) { 299 break; 300 } 301 n = n.right; 302 } 303 } 304 return l; 305 } 306 307 /** 308 * Returns a key-value mapping associated with the lowest key strictly 309 * greater than the given key, or null if there is no such key 310 * 311 * @param key 312 * The key 313 * @return a key-value mapping associated with the lowest key strictly 314 * greater than the given key 315 */ 316 public TreeEntry<K, V> upperEntry(K key) { 317 TreeEntry<K, V> n = root; 318 TreeEntry<K, V> h = null; 319 while (n != null) { 320 int c = compare(key, n.key); 321 if (c >= 0) { 322 n = n.right; 323 } else { 324 //Update the high node: 325 if (h == null || compare(n.key, h.key) < 0) { 326 h = n; 327 } 328 //Now need to scan the left tree to see if there is 329 //a lower high value to consider: 330 if (n.left == null) { 331 break; 332 } 333 n = n.left; 334 } 335 } 336 return h; 337 } 338 339 /** 340 * Returns a key-value mapping associated with the least key greater than or 341 * equal to the given key, or null if there is no such key. 342 * 343 * @param key 344 * @return 345 */ 346 public TreeEntry<K, V> ceilingEntry(K key) { 347 TreeEntry<K, V> n = root; 348 TreeEntry<K, V> h = null; 349 while (n != null) { 350 int c = compare(key, n.key); 351 if (c == 0) { 352 return n; 353 } 354 355 if (c > 0) { 356 n = n.right; 357 } else { 358 //Update the high node: 359 if (h == null || compare(n.key, h.key) < 0) { 360 h = n; 361 } 362 //Now need to scan the left tree to see if there is 363 //a lower high value to consider: 364 if (n.left == null) { 365 break; 366 } 367 n = n.left; 368 } 369 } 370 return h; 371 } 372 373 static private final <K,V> TreeEntry<K, V> next(TreeEntry<K, V> n) { 374 if (n == null) 375 return null; 376 else if (n.right != null) { 377 TreeEntry<K, V> p = n.right; 378 while (p.left != null) { 379 p = p.left; 380 } 381 return p; 382 } else { 383 TreeEntry<K, V> p = n.parent; 384 TreeEntry<K, V> ch = n; 385 while (p != null && ch == p.right) { 386 ch = p; 387 p = p.parent; 388 } 389 return p; 390 } 391 } 392 393 static private final <K,V> TreeEntry<K, V> previous(TreeEntry<K, V> n) { 394 if (n == null) 395 return null; 396 else if (n.left != null) { 397 TreeEntry<K, V> p = n.left; 398 while (p.right != null) { 399 p = p.right; 400 } 401 return p; 402 } else { 403 TreeEntry<K, V> p = n.parent; 404 TreeEntry<K, V> ch = n; 405 while (p != null && ch == p.left) { 406 ch = p; 407 p = p.parent; 408 } 409 return p; 410 } 411 } 412 413 /* 414 * (non-Javadoc) 415 * 416 * @see java.util.Map#isEmpty() 417 */ 418 public boolean isEmpty() { 419 return count == 0; 420 } 421 422 /* 423 * (non-Javadoc) 424 * 425 * @see java.util.Map#keySet() 426 */ 427 public Set<K> keySet() { 428 return new AbstractSet<K>() { 429 430 @Override 431 public void clear() { 432 TreeMap.this.clear(); 433 } 434 435 @SuppressWarnings("unchecked") 436 @Override 437 public boolean remove(Object o) { 438 return TreeMap.this.remove((K) o) != null; 439 } 440 441 @Override 442 public Iterator<K> iterator() { 443 return new KeyIterator(); 444 } 445 446 @Override 447 public int size() { 448 return count; 449 } 450 }; 451 452 } 453 454 /* 455 * (non-Javadoc) 456 * 457 * @see java.util.Map#putAll(java.util.Map) 458 */ 459 public void putAll(Map<? extends K, ? extends V> t) { 460 for (Map.Entry<? extends K, ? extends V> entry : t.entrySet()) { 461 put(entry.getKey(), entry.getValue()); 462 } 463 } 464 465 /* 466 * (non-Javadoc) 467 * 468 * @see java.util.Map#remove(java.lang.Object) 469 */ 470 public V remove(K key) { 471 return removeEntry(getEntry(key, root)); 472 } 473 474 /* 475 * (non-Javadoc) 476 * 477 * @see java.util.Map#put(java.lang.Object, java.lang.Object) 478 */ 479 public V put(final K key, final V value) { 480 481 if (root == null) { 482 // map is empty 483 root = new TreeEntry<K, V>(key, value, null, this); 484 count++; 485 return null; 486 } 487 TreeEntry<K, V> n = root; 488 489 // add new mapping 490 while (true) { 491 int c = compare(key, n.key); 492 493 if (c == 0) { 494 V old = n.value; 495 n.value = value; 496 return old; 497 } else if (c < 0) { 498 if (n.left != null) { 499 n = n.left; 500 } else { 501 n.left = new TreeEntry<K, V>(key, value, n, this); 502 count++; 503 doRedBlackInsert(n.left); 504 return null; 505 } 506 } else { // c > 0 507 if (n.right != null) { 508 n = n.right; 509 } else { 510 n.right = new TreeEntry<K, V>(key, value, n, this); 511 count++; 512 doRedBlackInsert(n.right); 513 return null; 514 } 515 } 516 } 517 } 518 519 /** 520 * complicated red-black insert stuff. Based on apache commons BidiMap 521 * method: 522 * 523 * @param n 524 * the newly inserted node 525 */ 526 private void doRedBlackInsert(final TreeEntry<K, V> n) { 527 TreeEntry<K, V> currentNode = n; 528 color(currentNode, RED); 529 530 while (currentNode != null && currentNode != root && isRed(currentNode.parent)) { 531 if (isLeftChild(parent(currentNode))) { 532 TreeEntry<K, V> y = getRight(getGrandParent(currentNode)); 533 534 if (isRed(y)) { 535 color(parent(currentNode), BLACK); 536 color(y, BLACK); 537 color(getGrandParent(currentNode), RED); 538 539 currentNode = getGrandParent(currentNode); 540 } else { 541 if (isRightChild(currentNode)) { 542 currentNode = parent(currentNode); 543 544 rotateLeft(currentNode); 545 } 546 547 color(parent(currentNode), BLACK); 548 color(getGrandParent(currentNode), RED); 549 550 if (getGrandParent(currentNode) != null) { 551 rotateRight(getGrandParent(currentNode)); 552 } 553 } 554 } else { 555 556 // just like clause above, except swap left for right 557 TreeEntry<K, V> y = getLeft(getGrandParent(currentNode)); 558 559 if (isRed(y)) { 560 color(parent(currentNode), BLACK); 561 color(y, BLACK); 562 color(getGrandParent(currentNode), RED); 563 564 currentNode = getGrandParent(currentNode); 565 } else { 566 if (isLeftChild(currentNode)) { 567 currentNode = parent(currentNode); 568 569 rotateRight(currentNode); 570 } 571 572 color(parent(currentNode), BLACK); 573 color(getGrandParent(currentNode), RED); 574 575 if (getGrandParent(currentNode) != null) { 576 rotateLeft(getGrandParent(currentNode)); 577 } 578 } 579 } 580 } 581 582 color(root, BLACK); 583 } 584 585 //Based on Apache common's TreeBidiMap 586 private void rotateLeft(TreeEntry<K, V> n) { 587 TreeEntry<K, V> r = n.right; 588 n.right = r.left; 589 if (r.left != null) { 590 r.left.parent = n; 591 } 592 r.parent = n.parent; 593 if (n.parent == null) { 594 root = r; 595 } else if (n.parent.left == n) { 596 n.parent.left = r; 597 } else { 598 n.parent.right = r; 599 } 600 601 r.left = n; 602 n.parent = r; 603 } 604 605 //Based on Apache common's TreeBidiMap 606 private void rotateRight(TreeEntry<K, V> n) { 607 TreeEntry<K, V> l = n.left; 608 n.left = l.right; 609 if (l.right != null) { 610 l.right.parent = n; 611 } 612 l.parent = n.parent; 613 if (n.parent == null) { 614 root = l; 615 } else if (n.parent.right == n) { 616 n.parent.right = l; 617 } else { 618 n.parent.left = l; 619 } 620 l.right = n; 621 n.parent = l; 622 } 623 624 /** 625 * complicated red-black delete stuff. Based on Apache Common's TreeBidiMap 626 * 627 * @param n 628 * the node to be deleted 629 */ 630 public final V removeEntry(TreeEntry<K, V> n) { 631 if (n == null) { 632 return null; 633 } 634 635 if (n.map != this) { 636 throw new IllegalStateException("Node not in list"); 637 } 638 639 V old = n.value; 640 641 count--; 642 643 //if deleted node has both left and children, swap with 644 // the next greater node 645 if (n.left != null && n.right != null) { 646 TreeEntry<K, V> next = next(n); 647 n.key = next.key; 648 n.value = next.value; 649 n = next; 650 } 651 652 TreeEntry<K, V> replacement = n.left != null ? n.left : n.right; 653 654 if (replacement != null) { 655 replacement.parent = n.parent; 656 657 if (n.parent == null) { 658 root = replacement; 659 } else if (n == n.parent.left) { 660 n.parent.left = replacement; 661 } else { 662 n.parent.right = replacement; 663 } 664 665 n.left = null; 666 n.right = null; 667 n.parent = null; 668 669 if (isBlack(n)) { 670 doRedBlackDeleteFixup(replacement); 671 } 672 } else { 673 674 // replacement is null 675 if (n.parent == null) { 676 // empty tree 677 root = null; 678 } else { 679 680 // deleted node had no children 681 if (isBlack(n)) { 682 doRedBlackDeleteFixup(n); 683 } 684 685 if (n.parent != null) { 686 if (n == n.parent.left) { 687 n.parent.left = null; 688 } else { 689 n.parent.right = null; 690 } 691 692 n.parent = null; 693 } 694 } 695 } 696 return old; 697 } 698 699 /** 700 * complicated red-black delete stuff. Based on Apache Commons TreeBidiMap. 701 * 702 * @param replacementNode 703 * the node being replaced 704 */ 705 private void doRedBlackDeleteFixup(final TreeEntry<K, V> replacementNode) { 706 TreeEntry<K, V> currentNode = replacementNode; 707 708 while (currentNode != root && isBlack(currentNode)) { 709 if (isLeftChild(currentNode)) { 710 TreeEntry<K, V> siblingNode = getRight(parent(currentNode)); 711 712 if (isRed(siblingNode)) { 713 color(siblingNode, BLACK); 714 color(parent(currentNode), RED); 715 rotateLeft(parent(currentNode)); 716 717 siblingNode = getRight(parent(currentNode)); 718 } 719 720 if (isBlack(getLeft(siblingNode)) && isBlack(getRight(siblingNode))) { 721 color(siblingNode, RED); 722 723 currentNode = parent(currentNode); 724 } else { 725 if (isBlack(getRight(siblingNode))) { 726 color(getLeft(siblingNode), BLACK); 727 color(siblingNode, RED); 728 rotateRight(siblingNode); 729 730 siblingNode = getRight(parent(currentNode)); 731 } 732 733 color(siblingNode, getColor(parent(currentNode))); 734 color(parent(currentNode), BLACK); 735 color(getRight(siblingNode), BLACK); 736 rotateLeft(parent(currentNode)); 737 738 currentNode = root; 739 } 740 } else { 741 TreeEntry<K, V> siblingNode = getLeft(parent(currentNode)); 742 743 if (isRed(siblingNode)) { 744 color(siblingNode, BLACK); 745 color(parent(currentNode), RED); 746 rotateRight(parent(currentNode)); 747 748 siblingNode = getLeft(parent(currentNode)); 749 } 750 751 if (isBlack(getRight(siblingNode)) && isBlack(getLeft(siblingNode))) { 752 color(siblingNode, RED); 753 754 currentNode = parent(currentNode); 755 } else { 756 if (isBlack(getLeft(siblingNode))) { 757 color(getRight(siblingNode), BLACK); 758 color(siblingNode, RED); 759 rotateLeft(siblingNode); 760 761 siblingNode = getLeft(parent(currentNode)); 762 } 763 764 color(siblingNode, getColor(parent(currentNode))); 765 color(parent(currentNode), BLACK); 766 color(getLeft(siblingNode), BLACK); 767 rotateRight(parent(currentNode)); 768 769 currentNode = root; 770 } 771 } 772 } 773 774 color(currentNode, BLACK); 775 } 776 777 778 /* 779 * (non-Javadoc) 780 * 781 * @see java.util.Map#size() 782 */ 783 public int size() { 784 return count; 785 } 786 787 /* 788 * (non-Javadoc) 789 * 790 * @see java.util.Map#values() 791 */ 792 public Collection<V> values() { 793 return new AbstractCollection<V>() { 794 795 @Override 796 public Iterator<V> iterator() { 797 return new ValueIterator(); 798 } 799 800 @Override 801 public int size() { 802 return count; 803 } 804 }; 805 } 806 807 private static <K, V> TreeEntry<K, V> parent(TreeEntry<K, V> n) { 808 return (n == null ? null : n.parent); 809 } 810 811 private static <K, V> void color(TreeEntry<K, V> n, boolean c) { 812 if (n != null) 813 n.color = c; 814 } 815 816 private static <K, V> boolean getColor(TreeEntry<K, V> n) { 817 return (n == null ? BLACK : n.color); 818 } 819 820 /** 821 * get a node's left child. mind you, the node may not exist. no problem 822 * 823 * @param node 824 * the node (may be null) in question 825 */ 826 private static <K, V> TreeEntry<K, V> getLeft(TreeEntry<K, V> n) { 827 return (n == null) ? null : n.left; 828 } 829 830 /** 831 * get a node's right child. mind you, the node may not exist. no problem 832 * 833 * @param node 834 * the node (may be null) in question 835 */ 836 private static <K, V> TreeEntry<K, V> getRight(TreeEntry<K, V> n) { 837 return (n == null) ? null : n.right; 838 } 839 840 /** 841 * is the specified node red? if the node does not exist, no, it's black, 842 * thank you 843 * 844 * @param node 845 * the node (may be null) in question 846 */ 847 private static <K, V> boolean isRed(TreeEntry<K, V> n) { 848 return n == null ? false : n.color == RED; 849 } 850 851 /** 852 * is the specified black red? if the node does not exist, sure, it's black, 853 * thank you 854 * 855 * @param node 856 * the node (may be null) in question 857 */ 858 private static <K, V> boolean isBlack(final TreeEntry<K, V> n) { 859 return n == null ? true : n.color == BLACK; 860 } 861 862 /** 863 * is this node its parent's left child? mind you, the node, or its parent, 864 * may not exist. no problem. if the node doesn't exist ... it's its 865 * non-existent parent's left child. If the node does exist but has no 866 * parent ... no, we're not the non-existent parent's left child. Otherwise 867 * (both the specified node AND its parent exist), check. 868 * 869 * @param node 870 * the node (may be null) in question 871 */ 872 private static <K, V> boolean isLeftChild(final TreeEntry<K, V> node) { 873 874 return node == null ? true : (node.parent == null ? false : (node == node.parent.left)); 875 } 876 877 /** 878 * is this node its parent's right child? mind you, the node, or its parent, 879 * may not exist. no problem. if the node doesn't exist ... it's its 880 * non-existent parent's right child. If the node does exist but has no 881 * parent ... no, we're not the non-existent parent's right child. Otherwise 882 * (both the specified node AND its parent exist), check. 883 * 884 * @param node 885 * the node (may be null) in question 886 * @param index 887 * the KEY or VALUE int 888 */ 889 private static <K, V> boolean isRightChild(final TreeEntry<K, V> node) { 890 return node == null ? true : (node.parent == null ? false : (node == node.parent.right)); 891 892 } 893 894 /** 895 * get a node's grandparent. mind you, the node, its parent, or its 896 * grandparent may not exist. no problem 897 * 898 * @param node 899 * the node (may be null) in question 900 */ 901 private static <K, V> TreeEntry<K, V> getGrandParent(final TreeEntry<K, V> node) { 902 return parent(parent(node)); 903 } 904 905 public static class TreeEntry<K, V> implements Map.Entry<K, V>, Serializable { 906 907 private static final long serialVersionUID = 8490652911043012737L; 908 909 TreeMap<K, V> map; 910 V value; 911 K key; 912 boolean color = BLACK; 913 914 TreeEntry<K, V> parent; 915 TreeEntry<K, V> left; 916 TreeEntry<K, V> right; 917 918 TreeEntry(K key, V val, TreeEntry<K, V> parent, TreeMap<K, V> map) { 919 this.key = key; 920 this.parent = parent; 921 this.value = val; 922 this.map = map; 923 } 924 925 /* 926 * (non-Javadoc) 927 * 928 * @see java.util.Map.Entry#getKey() 929 */ 930 public K getKey() { 931 return key; 932 } 933 934 /* 935 * (non-Javadoc) 936 * 937 * @see java.util.Map.Entry#getValue() 938 */ 939 public V getValue() { 940 return value; 941 } 942 943 /* 944 * (non-Javadoc) 945 * 946 * @see java.util.Map.Entry#setValue(java.lang.Object) 947 */ 948 public V setValue(V val) { 949 V old = this.value; 950 this.value = val; 951 return old; 952 } 953 954 @SuppressWarnings("unchecked") 955 public boolean equals(Object o) { 956 if (!(o instanceof Map.Entry)) 957 return false; 958 Map.Entry e = (Map.Entry) o; 959 960 return (key == null ? e.getKey() == null : key.equals(e.getKey())) && (value == null ? e.getValue() == null : value.equals(e.getValue())); 961 } 962 963 public int hashCode() { 964 int keyHash = (key == null ? 0 : key.hashCode()); 965 int valueHash = (value == null ? 0 : value.hashCode()); 966 return keyHash ^ valueHash; 967 } 968 969 public TreeEntry<K, V> next() { 970 return TreeMap.next(this); 971 } 972 973 public TreeEntry<K, V> previous() { 974 return TreeMap.previous(this); 975 } 976 977 @Override 978 public String toString() { 979 return "{ key: " +key+", value: "+value+" }"; 980 } 981 } 982 983 private class ValueIterator extends AbstractEntryIterator<V> { 984 985 /* 986 * (non-Javadoc) 987 * 988 * @see java.util.Iterator#next() 989 */ 990 public V next() { 991 getNext(); 992 if (last == null) { 993 return null; 994 } else { 995 return last.value; 996 } 997 } 998 } 999 1000 private class KeyIterator extends AbstractEntryIterator<K> { 1001 1002 /* 1003 * (non-Javadoc) 1004 * 1005 * @see java.util.Iterator#next() 1006 */ 1007 public K next() { 1008 getNext(); 1009 if (last == null) { 1010 return null; 1011 } else { 1012 return last.key; 1013 } 1014 } 1015 } 1016 1017 private class EntryIterator extends AbstractEntryIterator<Map.Entry<K, V>> { 1018 /* 1019 * (non-Javadoc) 1020 * 1021 * @see java.util.Iterator#next() 1022 */ 1023 public Entry<K, V> next() { 1024 getNext(); 1025 if (last == null) { 1026 return null; 1027 } else { 1028 return last; 1029 } 1030 } 1031 1032 } 1033 1034 private abstract class AbstractEntryIterator<T> implements Iterator<T> { 1035 1036 TreeEntry<K, V> last = null; 1037 TreeEntry<K, V> next = firstEntry(); 1038 1039 /* 1040 * (non-Javadoc) 1041 * 1042 * @see java.util.Iterator#hasNext() 1043 */ 1044 public boolean hasNext() { 1045 return next != null; 1046 } 1047 1048 /* 1049 * (non-Javadoc) 1050 * 1051 * @see java.util.Iterator#next() 1052 */ 1053 protected TreeEntry<K, V> getNext() { 1054 last = next; 1055 next = TreeMap.next(next); 1056 return last; 1057 } 1058 1059 /* 1060 * (non-Javadoc) 1061 * 1062 * @see java.util.Iterator#remove() 1063 */ 1064 public void remove() { 1065 TreeMap.this.removeEntry(last); 1066 last = null; 1067 } 1068 1069 } 1070 }