TreeMap.java 50.6 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
/* TreeMap.java -- a class providing a basic Red-Black Tree data structure,
   mapping Object --> Object
   Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.

This file is part of GNU Classpath.

GNU Classpath is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING.  If not, write to the
Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA.

As a special exception, if you link this library with other files to
produce an executable, this library does not by itself cause the
resulting executable to be covered by the GNU General Public License.
This exception does not however invalidate any other reasons why the
executable file might be covered by the GNU General Public License. */


package java.util;

import java.io.Serializable;
import java.io.ObjectOutputStream;
import java.io.ObjectInputStream;
import java.io.IOException;

/**
 * This class provides a red-black tree implementation of the SortedMap
 * interface.  Elements in the Map will be sorted by either a user-provided
 * Comparator object, or by the natural ordering of the keys.
 *
41 42 43 44 45 46 47
 * The algorithms are adopted from Corman, Leiserson, and Rivest's
 * <i>Introduction to Algorithms.</i>  TreeMap guarantees O(log n)
 * insertion and deletion of elements.  That being said, there is a large
 * enough constant coefficient in front of that "log n" (overhead involved
 * in keeping the tree balanced), that TreeMap may not be the best choice
 * for small collections. If something is already sorted, you may want to
 * just use a LinkedHashMap to maintain the order while providing O(1) access.
48 49
 *
 * TreeMap is a part of the JDK1.2 Collections API.  Null keys are allowed
50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
 * only if a Comparator is used which can deal with them; natural ordering
 * cannot cope with null.  Null values are always allowed. Note that the
 * ordering must be <i>consistent with equals</i> to correctly implement
 * the Map interface. If this condition is violated, the map is still
 * well-behaved, but you may have suprising results when comparing it to
 * other maps.<p>
 *
 * This implementation is not synchronized. If you need to share this between
 * multiple threads, do something like:<br>
 * <code>SortedMap m
 *       = Collections.synchronizedSortedMap(new TreeMap(...));</code><p>
 *
 * The iterators are <i>fail-fast</i>, meaning that any structural
 * modification, except for <code>remove()</code> called on the iterator
 * itself, cause the iterator to throw a
 * <code>ConcurrentModificationException</code> rather than exhibit
 * non-deterministic behavior.
67
 *
68 69 70 71 72 73 74 75 76 77 78 79 80
 * @author Jon Zeppieri
 * @author Bryce McKinlay
 * @author Eric Blake <ebb9@email.byu.edu>
 * @see Map
 * @see HashMap
 * @see Hashtable
 * @see LinkedHashMap
 * @see Comparable
 * @see Comparator
 * @see Collection
 * @see Collections#synchronizedSortedMap(SortedMap)
 * @since 1.2
 * @status updated to 1.4
81 82 83 84
 */
public class TreeMap extends AbstractMap
  implements SortedMap, Cloneable, Serializable
{
85 86 87 88 89 90
  // Implementation note:
  // A red-black tree is a binary search tree with the additional properties
  // that all paths to a leaf node visit the same number of black nodes,
  // and no red node has red children. To avoid some null-pointer checks,
  // we use the special node nil which is always black, has no relatives,
  // and has key and value of null (but is not equal to a mapping of null).
91

92 93 94 95
  /**
   * Compatible with JDK 1.2.
   */
  private static final long serialVersionUID = 919286545866124006L;
96

97 98 99 100 101
  /**
   * Color status of a node. Package visible for use by nested classes.
   */
  static final int RED = -1,
                   BLACK = 1;
102

103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
  /**
   * Sentinal node, used to avoid null checks for corner cases and make the
   * delete rebalance code simpler. The rebalance code must never assign
   * the parent, left, or right of nil, but may safely reassign the color
   * to be black. This object must never be used as a key in a TreeMap, or
   * it will break bounds checking of a SubMap.
   */
  static final Node nil = new Node(null, null, BLACK);
  static
    {
      // Nil is self-referential, so we must initialize it after creation.
      nil.parent = nil;
      nil.left = nil;
      nil.right = nil;
    }
118

119 120 121 122 123 124 125 126 127
  /**
   * The root node of this TreeMap.
   */
  private transient Node root = nil;

  /**
   * The size of this TreeMap. Package visible for use by nested classes.
   */
  transient int size;
128

129 130 131 132
  /**
   * The cache for {@link #entrySet()}.
   */
  private transient Set entries;
133

134 135 136 137 138 139 140 141 142 143 144 145 146
  /**
   * Counts the number of modifications this TreeMap has undergone, used
   * by Iterators to know when to throw ConcurrentModificationExceptions.
   * Package visible for use by nested classes.
   */
  transient int modCount;

  /**
   * This TreeMap's comparator, or null for natural ordering.
   * Package visible for use by nested classes.
   * @serial the comparator ordering this tree, or null
   */
  final Comparator comparator;
147

148 149 150 151 152 153 154
  /**
   * Class to represent an entry in the tree. Holds a single key-value pair,
   * plus pointers to parent and child nodes.
   *
   * @author Eric Blake <ebb9@email.byu.edu>
   */
  private static final class Node extends BasicMapEntry
155
  {
156 157
    // All fields package visible for use by nested classes.
    /** The color of this node. */
158 159
    int color;

160 161 162 163 164 165 166 167 168 169 170 171 172
    /** The left child node. */
    Node left = nil;
    /** The right child node. */
    Node right = nil;
    /** The parent node. */
    Node parent = nil;

    /**
     * Simple constructor.
     * @param key the key
     * @param value the value
     */
    Node(Object key, Object value, int color)
173 174
    {
      super(key, value);
175
      this.color = color;
176 177 178 179
    }
  }

  /**
180 181 182 183 184
   * Instantiate a new TreeMap with no elements, using the keys' natural
   * ordering to sort. All entries in the map must have a key which implements
   * Comparable, and which are <i>mutually comparable</i>, otherwise map
   * operations may throw a {@link ClassCastException}. Attempts to use
   * a null key will throw a {@link NullPointerException}.
185
   *
186
   * @see Comparable
187 188 189
   */
  public TreeMap()
  {
190
    this((Comparator) null);
191 192 193
  }

  /**
194 195 196 197
   * Instantiate a new TreeMap with no elements, using the provided comparator
   * to sort. All entries in the map must have keys which are mutually
   * comparable by the Comparator, otherwise map operations may throw a
   * {@link ClassCastException}.
198
   *
199 200
   * @param comparator the sort order for the keys of this map, or null
   *        for the natural order
201 202 203 204 205 206 207
   */
  public TreeMap(Comparator c)
  {
    comparator = c;
  }

  /**
208 209 210 211 212 213
   * Instantiate a new TreeMap, initializing it with all of the elements in
   * the provided Map.  The elements will be sorted using the natural
   * ordering of the keys. This algorithm runs in n*log(n) time. All entries
   * in the map must have keys which implement Comparable and are mutually
   * comparable, otherwise map operations may throw a
   * {@link ClassCastException}.
214
   *
215 216 217 218 219
   * @param map a Map, whose entries will be put into this TreeMap
   * @throws ClassCastException if the keys in the provided Map are not
   *         comparable
   * @throws NullPointerException if map is null
   * @see Comparable
220 221 222
   */
  public TreeMap(Map map)
  {
223
    this((Comparator) null);
224 225 226
    putAll(map);
  }

227 228 229 230 231 232 233
  /**
   * Instantiate a new TreeMap, initializing it with all of the elements in
   * the provided SortedMap.  The elements will be sorted using the same
   * comparator as in the provided SortedMap. This runs in linear time.
   *
   * @param sm a SortedMap, whose entries will be put into this TreeMap
   * @throws NullPointerException if sm is null
234 235 236 237
   */
  public TreeMap(SortedMap sm)
  {
    this(sm.comparator());
238
    int pos = sm.size();
239 240
    Iterator itr = sm.entrySet().iterator();

241
    fabricateTree(pos);
242
    Node node = firstNode();
243 244

    while (--pos >= 0)
245
      {
246 247 248 249
        Map.Entry me = (Map.Entry) itr.next();
        node.key = me.getKey();
        node.value = me.getValue();
        node = successor(node);
250 251 252
      }
  }

253 254 255
  /**
   * Clears the Map so it has no keys. This is O(1).
   */
256 257
  public void clear()
  {
258 259 260 261 262 263
    if (size > 0)
      {
        modCount++;
        root = nil;
        size = 0;
      }
264 265
  }

266 267 268 269 270 271
  /**
   * Returns a shallow clone of this TreeMap. The Map itself is cloned,
   * but its contents are not.
   *
   * @return the clone
   */
272 273
  public Object clone()
  {
274 275 276 277 278 279 280 281
    TreeMap copy = null;
    try
      {
        copy = (TreeMap) super.clone();
      }
    catch (CloneNotSupportedException x)
      {
      }
282
    copy.entries = null;
283 284 285 286
    copy.fabricateTree(size);

    Node node = firstNode();
    Node cnode = copy.firstNode();
287

288 289 290
    while (node != nil)
      {
        cnode.key = node.key;
291 292 293
        cnode.value = node.value;
        node = successor(node);
        cnode = copy.successor(cnode);
294 295 296
      }
    return copy;
  }
297 298 299 300 301 302 303

  /**
   * Return the comparator used to sort this map, or null if it is by
   * natural order.
   *
   * @return the map's comparator
   */
304 305 306 307 308
  public Comparator comparator()
  {
    return comparator;
  }

309 310 311 312 313 314 315 316 317
  /**
   * Returns true if the map contains a mapping for the given key.
   *
   * @param key the key to look for
   * @return true if the key has a mapping
   * @throws ClassCastException if key is not comparable to map elements
   * @throws NullPointerException if key is null and the comparator is not
   *         tolerant of nulls
   */
318 319 320 321 322
  public boolean containsKey(Object key)
  {
    return getNode(key) != nil;
  }

323 324 325 326 327 328 329
  /**
   * Returns true if the map contains at least one mapping to the given value.
   * This requires linear time.
   *
   * @param value the value to look for
   * @return true if the value appears in a mapping
   */
330 331 332 333 334
  public boolean containsValue(Object value)
  {
    Node node = firstNode();
    while (node != nil)
      {
335 336 337
        if (equals(value, node.value))
          return true;
        node = successor(node);
338 339 340 341
      }
    return false;
  }

342 343 344 345 346 347 348 349 350 351 352 353 354
  /**
   * Returns a "set view" of this TreeMap's entries. The set is backed by
   * the TreeMap, so changes in one show up in the other.  The set supports
   * element removal, but not element addition.<p>
   *
   * Note that the iterators for all three views, from keySet(), entrySet(),
   * and values(), traverse the TreeMap in sorted sequence.
   *
   * @return a set view of the entries
   * @see #keySet()
   * @see #values()
   * @see Map.Entry
   */
355 356
  public Set entrySet()
  {
357 358 359 360
    if (entries == null)
      // Create an AbstractSet with custom implementations of those methods
      // that can be overriden easily and efficiently.
      entries = new AbstractSet()
361
      {
362 363 364 365
        public int size()
        {
          return size;
        }
366

367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383
        public Iterator iterator()
        {
          return new TreeIterator(ENTRIES);
        }

        public void clear()
        {
          TreeMap.this.clear();
        }

        public boolean contains(Object o)
        {
          if (! (o instanceof Map.Entry))
            return false;
          Map.Entry me = (Map.Entry) o;
          Node n = getNode(me.getKey());
          return n != nil && AbstractSet.equals(me.getValue(), n.value);
384
      }
385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400

        public boolean remove(Object o)
        {
          if (! (o instanceof Map.Entry))
            return false;
          Map.Entry me = (Map.Entry) o;
          Node n = getNode(me.getKey());
          if (n != nil && AbstractSet.equals(me.getValue(), n.value))
            {
              removeNode(n);
              return true;
            }
          return false;
        }
      };
    return entries;
401 402
  }

403 404 405 406 407 408
  /**
   * Returns the first (lowest) key in the map.
   *
   * @return the first key
   * @throws NoSuchElementException if the map is empty
   */
409 410 411
  public Object firstKey()
  {
    if (root == nil)
412 413
      throw new NoSuchElementException();
    return firstNode().key;
414 415
  }

416 417 418 419 420 421 422 423 424 425 426 427 428 429
  /**
   * Return the value in this TreeMap associated with the supplied key,
   * or <code>null</code> if the key maps to nothing.  NOTE: Since the value
   * could also be null, you must use containsKey to see if this key
   * actually maps to something.
   *
   * @param key the key for which to fetch an associated value
   * @return what the key maps to, if present
   * @throws ClassCastException if key is not comparable to elements in the map
   * @throws NullPointerException if key is null but the comparator does not
   *         tolerate nulls
   * @see #put(Object, Object)
   * @see #containsKey(Object)
   */
430 431
  public Object get(Object key)
  {
432
    // Exploit fact that nil.value == null.
433 434 435
    return getNode(key).value;
  }

436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453
  /**
   * Returns a view of this Map including all entries with keys less than
   * <code>toKey</code>. The returned map is backed by the original, so changes
   * in one appear in the other. The submap will throw an
   * {@link IllegalArgumentException} for any attempt to access or add an
   * element beyond the specified cutoff. The returned map does not include
   * the endpoint; if you want inclusion, pass the successor element.
   *
   * @param toKey the (exclusive) cutoff point
   * @return a view of the map less than the cutoff
   * @throws ClassCastException if <code>toKey</code> is not compatible with
   *         the comparator (or is not Comparable, for natural ordering)
   * @throws NullPointerException if toKey is null, but the comparator does not
   *         tolerate null elements
   */
  public SortedMap headMap(Object toKey)
  {
    return new SubMap(nil, toKey);
454 455
  }

456 457 458 459 460 461 462 463 464
  /**
   * Returns a "set view" of this TreeMap's keys. The set is backed by the
   * TreeMap, so changes in one show up in the other.  The set supports
   * element removal, but not element addition.
   *
   * @return a set view of the keys
   * @see #values()
   * @see #entrySet()
   */
465 466
  public Set keySet()
  {
467 468 469 470
    if (keys == null)
      // Create an AbstractSet with custom implementations of those methods
      // that can be overriden easily and efficiently.
      keys = new AbstractSet()
471
      {
472 473 474 475
        public int size()
        {
          return size;
        }
476

477 478 479 480
        public Iterator iterator()
        {
          return new TreeIterator(KEYS);
        }
481

482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514
        public void clear()
        {
          TreeMap.this.clear();
        }

        public boolean contains(Object o)
        {
          return containsKey(o);
        }

        public boolean remove(Object key)
        {
          Node n = getNode(key);
          if (n == nil)
            return false;
          removeNode(n);
          return true;
        }
      };
    return keys;
  }

  /**
   * Returns the last (highest) key in the map.
   *
   * @return the last key
   * @throws NoSuchElementException if the map is empty
   */
  public Object lastKey()
  {
    if (root == nil)
      throw new NoSuchElementException("empty");
    return lastNode().key;
515 516
  }

517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532
  /**
   * Puts the supplied value into the Map, mapped by the supplied key.
   * The value may be retrieved by any object which <code>equals()</code>
   * this key. NOTE: Since the prior value could also be null, you must
   * first use containsKey if you want to see if you are replacing the
   * key's mapping.
   *
   * @param key the key used to locate the value
   * @param value the value to be stored in the HashMap
   * @return the prior mapping of the key, or null if there was none
   * @throws ClassCastException if key is not comparable to current map keys
   * @throws NullPointerException if key is null, but the comparator does
   *         not tolerate nulls
   * @see #get(Object)
   * @see Object#equals(Object)
   */
533 534 535 536 537
  public Object put(Object key, Object value)
  {
    Node current = root;
    Node parent = nil;
    int comparison = 0;
538

539 540 541
    // Find new node's parent.
    while (current != nil)
      {
542 543 544 545 546 547 548 549
        parent = current;
        comparison = compare(key, current.key);
        if (comparison > 0)
          current = current.right;
        else if (comparison < 0)
          current = current.left;
        else // Key already in tree.
          return current.setValue(value);
550
      }
551

552
    // Set up new node.
553
    Node n = new Node(key, value, RED);
554
    n.parent = parent;
555

556
    // Insert node in tree.
557
    modCount++;
558 559 560
    size++;
    if (parent == nil)
      {
561 562 563
        // Special case inserting into an empty tree.
        root = n;
        return null;
564
      }
565
    if (comparison > 0)
566 567
      parent.right = n;
    else
568 569
      parent.left = n;

570 571 572 573 574
    // Rebalance after insert.
    insertFixup(n);
    return null;
  }

575 576 577 578 579 580 581 582 583 584 585
  /**
   * Copies all elements of the given map into this hashtable.  If this table
   * already has a mapping for a key, the new mapping replaces the current
   * one.
   *
   * @param m the map to be hashed into this
   * @throws ClassCastException if a key in m is not comparable with keys
   *         in the map
   * @throws NullPointerException if a key in m is null, and the comparator
   *         does not tolerate nulls
   */
586 587 588
  public void putAll(Map m)
  {
    Iterator itr = m.entrySet().iterator();
589 590
    int pos = m.size();
    while (--pos >= 0)
591
      {
592 593
        Map.Entry e = (Map.Entry) itr.next();
        put(e.getKey(), e.getValue());
594 595 596
      }
  }

597 598 599 600 601 602 603 604 605 606 607 608 609
  /**
   * Removes from the TreeMap and returns the value which is mapped by the
   * supplied key. If the key maps to nothing, then the TreeMap remains
   * unchanged, and <code>null</code> is returned. NOTE: Since the value
   * could also be null, you must use containsKey to see if you are
   * actually removing a mapping.
   *
   * @param key the key used to locate the value to remove
   * @return whatever the key mapped to, if present
   * @throws ClassCastException if key is not comparable to current map keys
   * @throws NullPointerException if key is null, but the comparator does
   *         not tolerate nulls
   */
610 611 612
  public Object remove(Object key)
  {
    Node n = getNode(key);
613 614 615 616
    if (n == nil)
      return null;
    removeNode(n);
    return n.value;
617
  }
618 619 620 621 622 623 624

  /**
   * Returns the number of key-value mappings currently in this Map.
   *
   * @return the size
   */
  public int size()
625
  {
626 627
    return size;
  }
628

629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651
  /**
   * Returns a view of this Map including all entries with keys greater or
   * equal to <code>fromKey</code> and less than <code>toKey</code> (a
   * half-open interval). The returned map is backed by the original, so
   * changes in one appear in the other. The submap will throw an
   * {@link IllegalArgumentException} for any attempt to access or add an
   * element beyond the specified cutoffs. The returned map includes the low
   * endpoint but not the high; if you want to reverse this behavior on
   * either end, pass in the successor element.
   *
   * @param fromKey the (inclusive) low cutoff point
   * @param toKey the (exclusive) high cutoff point
   * @return a view of the map between the cutoffs
   * @throws ClassCastException if either cutoff is not compatible with
   *         the comparator (or is not Comparable, for natural ordering)
   * @throws NullPointerException if fromKey or toKey is null, but the
   *         comparator does not tolerate null elements
   * @throws IllegalArgumentException if fromKey is greater than toKey
   */
  public SortedMap subMap(Object fromKey, Object toKey)
  {
    return new SubMap(fromKey, toKey);
  }
652

653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688
  /**
   * Returns a view of this Map including all entries with keys greater or
   * equal to <code>fromKey</code>. The returned map is backed by the
   * original, so changes in one appear in the other. The submap will throw an
   * {@link IllegalArgumentException} for any attempt to access or add an
   * element beyond the specified cutoff. The returned map includes the
   * endpoint; if you want to exclude it, pass in the successor element.
   *
   * @param fromKey the (inclusive) low cutoff point
   * @return a view of the map above the cutoff
   * @throws ClassCastException if <code>fromKey</code> is not compatible with
   *         the comparator (or is not Comparable, for natural ordering)
   * @throws NullPointerException if fromKey is null, but the comparator
   *         does not tolerate null elements
   */
  public SortedMap tailMap(Object fromKey)
  {
    return new SubMap(fromKey, nil);
  }

  /**
   * Returns a "collection view" (or "bag view") of this TreeMap's values.
   * The collection is backed by the TreeMap, so changes in one show up
   * in the other.  The collection supports element removal, but not element
   * addition.
   *
   * @return a bag view of the values
   * @see #keySet()
   * @see #entrySet()
   */
  public Collection values()
  {
    if (values == null)
      // We don't bother overriding many of the optional methods, as doing so
      // wouldn't provide any significant performance advantage.
      values = new AbstractCollection()
689
      {
690 691 692 693
        public int size()
        {
          return size;
        }
694

695 696 697 698
        public Iterator iterator()
        {
          return new TreeIterator(VALUES);
        }
699

700 701 702 703 704 705 706
        public void clear()
        {
          TreeMap.this.clear();
        }
      };
    return values;
  }
707

708 709 710 711 712 713 714 715 716 717 718 719 720 721 722
  /**
   * Compares two elements by the set comparator, or by natural ordering.
   * Package visible for use by nested classes.
   *
   * @param o1 the first object
   * @param o2 the second object
   * @throws ClassCastException if o1 and o2 are not mutually comparable,
   *         or are not Comparable with natural ordering
   * @throws NullPointerException if o1 or o2 is null with natural ordering
   */
  final int compare(Object o1, Object o2)
  {
    return (comparator == null
            ? ((Comparable) o1).compareTo(o2)
            : comparator.compare(o1, o2));
723 724
  }

725 726 727 728 729 730 731
  /**
   * Maintain red-black balance after deleting a node.
   *
   * @param node the child of the node just deleted, possibly nil
   * @param parent the parent of the node just deleted, never nil
   */
  private void deleteFixup(Node node, Node parent)
732
  {
733 734 735
    // if (parent == nil)
    //   throw new InternalError();
    // If a black node has been removed, we need to rebalance to avoid
736
    // violating the "same number of black nodes on any path" rule. If
737
    // node is red, we can simply recolor it black and all is well.
738 739
    while (node != root && node.color == BLACK)
      {
740 741 742 743 744 745 746 747 748 749
        if (node == parent.left)
          {
            // Rebalance left side.
            Node sibling = parent.right;
            // if (sibling == nil)
            //   throw new InternalError();
            if (sibling.color == RED)
              {
                // Case 1: Sibling is red.
                // Recolor sibling and parent, and rotate parent left.
750
                sibling.color = BLACK;
751 752 753 754
                parent.color = RED;
                rotateLeft(parent);
                sibling = parent.right;
              }
755

756
            if (sibling.left.color == BLACK && sibling.right.color == BLACK)
757
              {
758 759 760 761 762
                // Case 2: Sibling has no red children.
                // Recolor sibling, and move to parent.
                sibling.color = RED;
                node = parent;
                parent = parent.parent;
763
              }
764 765 766 767 768 769 770 771
            else
              {
                if (sibling.right.color == BLACK)
                  {
                    // Case 3: Sibling has red left child.
                    // Recolor sibling and left child, rotate sibling right.
                    sibling.left.color = BLACK;
                    sibling.color = RED;
772
                    rotateRight(sibling);
773 774 775 776 777 778 779 780
                    sibling = parent.right;
                  }
                // Case 4: Sibling has red right child. Recolor sibling,
                // right child, and parent, and rotate parent left.
                sibling.color = parent.color;
                parent.color = BLACK;
                sibling.right.color = BLACK;
                rotateLeft(parent);
781
                node = root; // Finished.
782 783 784 785 786 787 788 789 790 791 792 793
              }
          }
        else
          {
            // Symmetric "mirror" of left-side case.
            Node sibling = parent.left;
            // if (sibling == nil)
            //   throw new InternalError();
            if (sibling.color == RED)
              {
                // Case 1: Sibling is red.
                // Recolor sibling and parent, and rotate parent right.
794
                sibling.color = BLACK;
795 796 797 798
                parent.color = RED;
                rotateRight(parent);
                sibling = parent.left;
              }
799

800
            if (sibling.right.color == BLACK && sibling.left.color == BLACK)
801
              {
802 803 804 805 806
                // Case 2: Sibling has no red children.
                // Recolor sibling, and move to parent.
                sibling.color = RED;
                node = parent;
                parent = parent.parent;
807
              }
808 809 810 811 812 813 814 815
            else
              {
                if (sibling.left.color == BLACK)
                  {
                    // Case 3: Sibling has red right child.
                    // Recolor sibling and right child, rotate sibling left.
                    sibling.right.color = BLACK;
                    sibling.color = RED;
816
                    rotateLeft(sibling);
817 818 819 820 821 822 823 824 825 826 827
                    sibling = parent.left;
                  }
                // Case 4: Sibling has red left child. Recolor sibling,
                // left child, and parent, and rotate parent right.
                sibling.color = parent.color;
                parent.color = BLACK;
                sibling.left.color = BLACK;
                rotateRight(parent);
                node = root; // Finished.
              }
          }
828 829 830 831
      }
    node.color = BLACK;
  }

832 833 834 835 836 837 838
  /**
   * Construct a perfectly balanced tree consisting of n "blank" nodes. This
   * permits a tree to be generated from pre-sorted input in linear time.
   *
   * @param count the number of blank nodes, non-negative
   */
  private void fabricateTree(final int count)
839
  {
840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907
    if (count == 0)
      return;

    // We color every row of nodes black, except for the overflow nodes.
    // I believe that this is the optimal arrangement. We construct the tree
    // in place by temporarily linking each node to the next node in the row,
    // then updating those links to the children when working on the next row.

    // Make the root node.
    root = new Node(null, null, BLACK);
    size = count;
    Node row = root;
    int rowsize;

    // Fill each row that is completely full of nodes.
    for (rowsize = 2; rowsize + rowsize < count; rowsize <<= 1)
      {
        Node parent = row;
        Node last = null;
        for (int i = 0; i < rowsize; i += 2)
          {
            Node left = new Node(null, null, BLACK);
            Node right = new Node(null, null, BLACK);
            left.parent = parent;
            left.right = right;
            right.parent = parent;
            parent.left = left;
            Node next = parent.right;
            parent.right = right;
            parent = next;
            if (last != null)
              last.right = left;
            last = right;
          }
        row = row.left;
      }

    // Now do the partial final row in red.
    int overflow = count - rowsize;
    Node parent = row;
    int i;
    for (i = 0; i < overflow; i += 2)
      {
        Node left = new Node(null, null, RED);
        Node right = new Node(null, null, RED);
        left.parent = parent;
        right.parent = parent;
        parent.left = left;
        Node next = parent.right;
        parent.right = right;
        parent = next;
      }
    // Add a lone left node if necessary.
    if (i - overflow == 0)
      {
        Node left = new Node(null, null, RED);
        left.parent = parent;
        parent.left = left;
        parent = parent.right;
        left.parent.right = nil;
      }
    // Unlink the remaining nodes of the previous row.
    while (parent != nil)
      {
        Node next = parent.right;
        parent.right = nil;
        parent = next;
      }
908 909
  }

910 911 912 913 914 915 916
  /**
   * Returns the first sorted node in the map, or nil if empty. Package
   * visible for use by nested classes.
   *
   * @return the first node
   */
  final Node firstNode()
917
  {
918 919 920 921 922
    // Exploit fact that nil.left == nil.
    Node node = root;
    while (node.left != nil)
      node = node.left;
    return node;
923 924
  }

925 926 927 928 929 930 931 932
  /**
   * Return the TreeMap.Node associated with key, or the nil node if no such
   * node exists in the tree. Package visible for use by nested classes.
   *
   * @param key the key to search for
   * @return the node where the key is found, or nil
   */
  final Node getNode(Object key)
933
  {
934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050
    Node current = root;
    while (current != nil)
      {
        int comparison = compare(key, current.key);
        if (comparison > 0)
          current = current.right;
        else if (comparison < 0)
          current = current.left;
        else
          return current;
      }
    return current;
  }

  /**
   * Find the "highest" node which is &lt; key. If key is nil, return last
   * node. Package visible for use by nested classes.
   *
   * @param key the upper bound, exclusive
   * @return the previous node
   */
  final Node highestLessThan(Object key)
  {
    if (key == nil)
      return lastNode();

    Node last = nil;
    Node current = root;
    int comparison = 0;

    while (current != nil)
      {
        last = current;
        comparison = compare(key, current.key);
        if (comparison > 0)
          current = current.right;
        else if (comparison < 0)
          current = current.left;
        else // Exact match.
          return predecessor(last);
      }
    return comparison <= 0 ? predecessor(last) : last;
  }

  /**
   * Maintain red-black balance after inserting a new node.
   *
   * @param n the newly inserted node
   */
  private void insertFixup(Node n)
  {
    // Only need to rebalance when parent is a RED node, and while at least
    // 2 levels deep into the tree (ie: node has a grandparent). Remember
    // that nil.color == BLACK.
    while (n.parent.color == RED && n.parent.parent != nil)
      {
        if (n.parent == n.parent.parent.left)
          {
            Node uncle = n.parent.parent.right;
            // Uncle may be nil, in which case it is BLACK.
            if (uncle.color == RED)
              {
                // Case 1. Uncle is RED: Change colors of parent, uncle,
                // and grandparent, and move n to grandparent.
                n.parent.color = BLACK;
                uncle.color = BLACK;
                uncle.parent.color = RED;
                n = uncle.parent;
              }
            else
              {
                if (n == n.parent.right)
                  {
                    // Case 2. Uncle is BLACK and x is right child.
                    // Move n to parent, and rotate n left.
                    n = n.parent;
                    rotateLeft(n);
                  }
                // Case 3. Uncle is BLACK and x is left child.
                // Recolor parent, grandparent, and rotate grandparent right.
                n.parent.color = BLACK;
                n.parent.parent.color = RED;
                rotateRight(n.parent.parent);
              }
          }
        else
          {
            // Mirror image of above code.
            Node uncle = n.parent.parent.left;
            // Uncle may be nil, in which case it is BLACK.
            if (uncle.color == RED)
              {
                // Case 1. Uncle is RED: Change colors of parent, uncle,
                // and grandparent, and move n to grandparent.
                n.parent.color = BLACK;
                uncle.color = BLACK;
                uncle.parent.color = RED;
                n = uncle.parent;
              }
            else
              {
                if (n == n.parent.left)
                {
                    // Case 2. Uncle is BLACK and x is left child.
                    // Move n to parent, and rotate n right.
                    n = n.parent;
                    rotateRight(n);
                  }
                // Case 3. Uncle is BLACK and x is right child.
                // Recolor parent, grandparent, and rotate grandparent left.
                n.parent.color = BLACK;
                n.parent.parent.color = RED;
                rotateLeft(n.parent.parent);
              }
          }
      }
    root.color = BLACK;
1051 1052
  }

1053 1054 1055 1056 1057 1058
  /**
   * Returns the last sorted node in the map, or nil if empty.
   *
   * @return the last node
   */
  private Node lastNode()
1059
  {
1060 1061 1062 1063 1064
    // Exploit fact that nil.right == nil.
    Node node = root;
    while (node.right != nil)
      node = node.right;
    return node;
1065 1066
  }

1067 1068 1069 1070 1071 1072 1073 1074 1075 1076
  /**
   * Find the "lowest" node which is &gt;= key. If key is nil, return either
   * nil or the first node, depending on the parameter first.
   * Package visible for use by nested classes.
   *
   * @param key the lower bound, inclusive
   * @param first true to return the first element instead of nil for nil key
   * @return the next node
   */
  final Node lowestGreaterThan(Object key, boolean first)
1077 1078
  {
    if (key == nil)
1079 1080
      return first ? firstNode() : nil;

1081 1082 1083 1084 1085 1086 1087 1088
    Node last = nil;
    Node current = root;
    int comparison = 0;

    while (current != nil)
      {
        last = current;
        comparison = compare(key, current.key);
1089 1090 1091 1092 1093 1094
        if (comparison > 0)
          current = current.right;
        else if (comparison < 0)
          current = current.left;
        else
          return current;
1095
      }
1096
    return comparison > 0 ? successor(last) : last;
1097 1098
  }

1099 1100 1101 1102 1103 1104 1105
  /**
   * Return the node preceding the given one, or nil if there isn't one.
   *
   * @param node the current node, not nil
   * @return the prior node in sorted order
   */
  private Node predecessor(Node node)
1106
  {
1107 1108 1109 1110 1111 1112 1113
    if (node.left != nil)
      {
        node = node.left;
        while (node.right != nil)
          node = node.right;
        return node;
      }
1114

1115 1116 1117
    Node parent = node.parent;
    // Exploit fact that nil.left == nil and node is non-nil.
    while (node == parent.left)
1118
      {
1119 1120
        node = parent;
        parent = node.parent;
1121
      }
1122 1123
    return parent;
  }
1124

1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139
  /**
   * Construct a tree from sorted keys in linear time. Package visible for
   * use by TreeSet.
   *
   * @param s the stream to read from
   * @param count the number of keys to read
   * @param readValue true to read values, false to insert "" as the value
   * @throws ClassNotFoundException if the underlying stream fails
   * @throws IOException if the underlying stream fails
   * @see #readObject(ObjectInputStream)
   * @see TreeSet#readObject(ObjectInputStream)
   */
  final void putFromObjStream(ObjectInputStream s, int count,
                              boolean readValues)
    throws IOException, ClassNotFoundException
1140
  {
1141
    fabricateTree(count);
1142
    Node node = firstNode();
1143 1144

    while (--count >= 0)
1145
      {
1146 1147 1148
        node.key = s.readObject();
        node.value = readValues ? s.readObject() : "";
        node = successor(node);
1149 1150 1151
      }
  }

1152 1153 1154 1155 1156 1157 1158 1159 1160
  /**
   * Construct a tree from sorted keys in linear time, with values of "".
   * Package visible for use by TreeSet.
   *
   * @param keys the iterator over the sorted keys
   * @param count the number of nodes to insert
   * @see TreeSet#TreeSet(SortedSet)
   */
  final void putKeysLinear(Iterator keys, int count)
1161
  {
1162 1163 1164 1165 1166 1167 1168 1169 1170
    fabricateTree(count);
    Node node = firstNode();

    while (--count >= 0)
      {
        node.key = keys.next();
        node.value = "";
        node = successor(node);
      }
1171 1172
  }

1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183
  /**
   * Deserializes this object from the given stream.
   *
   * @param s the stream to read from
   * @throws ClassNotFoundException if the underlying stream fails
   * @throws IOException if the underlying stream fails
   * @serialData the <i>size</i> (int), followed by key (Object) and value
   *             (Object) pairs in sorted order
   */
  private void readObject(ObjectInputStream s)
    throws IOException, ClassNotFoundException
1184
  {
1185 1186 1187
    s.defaultReadObject();
    int size = s.readInt();
    putFromObjStream(s, size, true);
1188 1189
  }

1190 1191 1192 1193 1194 1195 1196
  /**
   * Remove node from tree. This will increment modCount and decrement size.
   * Node must exist in the tree. Package visible for use by nested classes.
   *
   * @param node the node to remove
   */
  final void removeNode(Node node)
1197
  {
1198 1199 1200 1201 1202 1203 1204 1205
    Node splice;
    Node child;

    modCount++;
    size--;

    // Find splice, the node at the position to actually remove from the tree.
    if (node.left == nil)
1206
      {
1207 1208 1209
        // Node to be deleted has 0 or 1 children.
        splice = node;
        child = node.right;
1210
      }
1211
    else if (node.right == nil)
1212
      {
1213 1214 1215
        // Node to be deleted has 1 child.
        splice = node;
        child = node.left;
1216
      }
1217
    else
1218
      {
1219 1220 1221 1222 1223 1224 1225 1226
        // Node has 2 children. Splice is node's predecessor, and we swap
        // its contents into node.
        splice = node.left;
        while (splice.right != nil)
          splice = splice.right;
        child = splice.left;
        node.key = splice.key;
        node.value = splice.value;
1227
      }
1228 1229 1230 1231 1232 1233

    // Unlink splice from the tree.
    Node parent = splice.parent;
    if (child != nil)
      child.parent = parent;
    if (parent == nil)
1234
      {
1235 1236 1237
        // Special case for 0 or 1 node remaining.
        root = child;
        return;
1238
      }
1239 1240 1241 1242 1243 1244 1245
    if (splice == parent.left)
      parent.left = child;
    else
      parent.right = child;

    if (splice.color == BLACK)
      deleteFixup(child, parent);
1246 1247
  }

1248 1249 1250 1251 1252
  /**
   * Rotate node n to the left.
   *
   * @param node the node to rotate
   */
1253 1254 1255
  private void rotateLeft(Node node)
  {
    Node child = node.right;
1256 1257 1258
    // if (node == nil || child == nil)
    //   throw new InternalError();

1259 1260 1261 1262 1263 1264 1265 1266 1267 1268
    // Establish node.right link.
    node.right = child.left;
    if (child.left != nil)
      child.left.parent = node;

    // Establish child->parent link.
    child.parent = node.parent;
    if (node.parent != nil)
      {
        if (node == node.parent.left)
1269 1270 1271
          node.parent.left = child;
        else
          node.parent.right = child;
1272 1273 1274 1275 1276 1277
      }
    else
      root = child;

    // Link n and child.
    child.left = node;
1278
    node.parent = child;
1279 1280
  }

1281 1282 1283 1284 1285
  /**
   * Rotate node n to the right.
   *
   * @param node the node to rotate
   */
1286 1287 1288
  private void rotateRight(Node node)
  {
    Node child = node.left;
1289 1290 1291
    // if (node == nil || child == nil)
    //   throw new InternalError();

1292 1293 1294 1295
    // Establish node.left link.
    node.left = child.right;
    if (child.right != nil)
      child.right.parent = node;
1296

1297 1298 1299 1300 1301
    // Establish child->parent link.
    child.parent = node.parent;
    if (node.parent != nil)
      {
        if (node == node.parent.right)
1302 1303 1304
          node.parent.right = child;
        else
          node.parent.left = child;
1305 1306 1307
      }
    else
      root = child;
1308

1309 1310
    // Link n and child.
    child.right = node;
1311
    node.parent = child;
1312 1313
  }

1314 1315 1316 1317 1318 1319 1320 1321
  /**
   * Return the node following the given one, or nil if there isn't one.
   * Package visible for use by nested classes.
   *
   * @param node the current node, not nil
   * @return the next node in sorted order
   */
  final Node successor(Node node)
1322
  {
1323
    if (node.right != nil)
1324
      {
1325 1326 1327 1328
        node = node.right;
        while (node.left != nil)
          node = node.left;
        return node;
1329 1330
      }

1331 1332 1333
    Node parent = node.parent;
    // Exploit fact that nil.right == nil and node is non-nil.
    while (node == parent.right)
1334
      {
1335 1336
        node = parent;
        parent = parent.parent;
1337
      }
1338
    return parent;
1339
  }
1340 1341 1342 1343 1344 1345 1346 1347 1348 1349

  /**
   * Serializes this object to the given stream.
   *
   * @param s the stream to write to
   * @throws IOException if the underlying stream fails
   * @serialData the <i>size</i> (int), followed by key (Object) and value
   *             (Object) pairs in sorted order
   */
  private void writeObject(ObjectOutputStream s) throws IOException
1350
  {
1351 1352 1353 1354 1355
    s.defaultWriteObject();

    Node node = firstNode();
    s.writeInt(size);
    while (node != nil)
1356
      {
1357 1358 1359
        s.writeObject(node.key);
        s.writeObject(node.value);
        node = successor(node);
1360 1361 1362 1363
      }
  }

  /**
1364 1365 1366 1367 1368 1369
   * Iterate over HashMap's entries. This implementation is parameterized
   * to give a sequential view of keys, values, or entries.
   *
   * @author Eric Blake <ebb9@email.byu.edu>
   */
  private final class TreeIterator implements Iterator
1370
  {
1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391
    /**
     * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
     * or {@link #ENTRIES}.
     */
    private final int type;
    /** The number of modifications to the backing Map that we know about. */
    private int knownMod = modCount;
    /** The last Entry returned by a next() call. */
    private Node last;
    /** The next entry that should be returned by next(). */
    private Node next;
    /**
     * The last node visible to this iterator. This is used when iterating
     * on a SubMap.
     */
    private final Node max;

    /**
     * Construct a new TreeIterator with the supplied type.
     * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
     */
1392 1393
    TreeIterator(int type)
    {
1394 1395
      // FIXME gcj cannot handle this. Bug java/4695
      // this(type, firstNode(), nil);
1396 1397
      this.type = type;
      this.next = firstNode();
1398
      this.max = nil;
1399
    }
1400 1401 1402 1403 1404 1405 1406 1407 1408

    /**
     * Construct a new TreeIterator with the supplied type. Iteration will
     * be from "first" (inclusive) to "max" (exclusive).
     *
     * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
     * @param first where to start iteration, nil for empty iterator
     * @param max the cutoff for iteration, nil for all remaining nodes
     */
1409 1410 1411 1412 1413 1414 1415
    TreeIterator(int type, Node first, Node max)
    {
      this.type = type;
      this.next = first;
      this.max = max;
    }

1416 1417 1418 1419 1420
    /**
     * Returns true if the Iterator has more elements.
     * @return true if there are more elements
     * @throws ConcurrentModificationException if the TreeMap was modified
     */
1421 1422
    public boolean hasNext()
    {
1423 1424 1425
      if (knownMod != modCount)
        throw new ConcurrentModificationException();
      return next != max;
1426 1427
    }

1428 1429 1430 1431 1432 1433
    /**
     * Returns the next element in the Iterator's sequential view.
     * @return the next element
     * @throws ConcurrentModificationException if the TreeMap was modified
     * @throws NoSuchElementException if there is none
     */
1434 1435
    public Object next()
    {
1436 1437 1438 1439 1440 1441 1442
      if (knownMod != modCount)
        throw new ConcurrentModificationException();
      if (next == max)
        throw new NoSuchElementException();
      last = next;
      next = successor(last);

1443
      if (type == VALUES)
1444
        return last.value;
1445
      else if (type == KEYS)
1446 1447
        return last.key;
      return last;
1448 1449
    }

1450 1451 1452 1453 1454 1455
    /**
     * Removes from the backing TreeMap the last element which was fetched
     * with the <code>next()</code> method.
     * @throws ConcurrentModificationException if the TreeMap was modified
     * @throws IllegalStateException if called when there is no last element
     */
1456 1457
    public void remove()
    {
1458 1459
      if (knownMod != modCount)
        throw new ConcurrentModificationException();
1460
      if (last == null)
1461 1462 1463
        throw new IllegalStateException();

      removeNode(last);
1464
      last = null;
1465
      knownMod++;
1466
    }
1467
  } // class TreeIterator
1468

1469 1470 1471 1472 1473 1474 1475 1476 1477
  /**
   * Implementation of {@link #subMap(Object, Object)} and other map
   * ranges. This class provides a view of a portion of the original backing
   * map, and throws {@link IllegalArgumentException} for attempts to
   * access beyond that range.
   *
   * @author Eric Blake <ebb9@email.byu.edu>
   */
  private final class SubMap extends AbstractMap implements SortedMap
1478
  {
1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504
    /**
     * The lower range of this view, inclusive, or nil for unbounded.
     * Package visible for use by nested classes.
     */
    final Object minKey;

    /**
     * The upper range of this view, exclusive, or nil for unbounded.
     * Package visible for use by nested classes.
     */
    final Object maxKey;

    /**
     * The cache for {@link #entrySet()}.
     */
    private Set entries;

    /**
     * Create a SubMap representing the elements between minKey (inclusive)
     * and maxKey (exclusive). If minKey is nil, SubMap has no lower bound
     * (headMap). If maxKey is nil, the SubMap has no upper bound (tailMap).
     *
     * @param minKey the lower bound
     * @param maxKey the upper bound
     * @throws IllegalArgumentException if minKey &gt; maxKey
     */
1505 1506
    SubMap(Object minKey, Object maxKey)
    {
1507 1508
      if (minKey != nil && maxKey != nil && compare(minKey, maxKey) > 0)
        throw new IllegalArgumentException("fromKey > toKey");
1509 1510 1511 1512
      this.minKey = minKey;
      this.maxKey = maxKey;
    }

1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526
    /**
     * Check if "key" is in within the range bounds for this SubMap. The
     * lower ("from") SubMap range is inclusive, and the upper ("to") bound
     * is exclusive. Package visible for use by nested classes.
     *
     * @param key the key to check
     * @return true if the key is in range
     */
    final boolean keyInRange(Object key)
    {
      return ((minKey == nil || compare(key, minKey) >= 0)
              && (maxKey == nil || compare(key, maxKey) < 0));
    }

1527 1528
    public void clear()
    {
1529 1530 1531
      Node next = lowestGreaterThan(minKey, true);
      Node max = lowestGreaterThan(maxKey, false);
      while (next != max)
1532
        {
1533 1534 1535 1536
          Node current = next;
          next = successor(current);
          removeNode(current);
        }
1537
    }
1538 1539

    public Comparator comparator()
1540
    {
1541
      return comparator;
1542 1543 1544 1545
    }

    public boolean containsKey(Object key)
    {
1546
      return keyInRange(key) && TreeMap.this.containsKey(key);
1547 1548 1549 1550
    }

    public boolean containsValue(Object value)
    {
1551 1552 1553 1554 1555 1556 1557 1558 1559
      Node node = lowestGreaterThan(minKey, true);
      Node max = lowestGreaterThan(maxKey, false);
      while (node != max)
        {
          if (equals(value, node.getValue()))
            return true;
          node = successor(node);
        }
      return false;
1560 1561
    }

1562
    public Set entrySet()
1563
    {
1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615
      if (entries == null)
        // Create an AbstractSet with custom implementations of those methods
        // that can be overriden easily and efficiently.
        entries = new AbstractSet()
        {
          public int size()
          {
            return SubMap.this.size();
          }

          public Iterator iterator()
          {
            Node first = lowestGreaterThan(minKey, true);
            Node max = lowestGreaterThan(maxKey, false);
            return new TreeIterator(ENTRIES, first, max);
          }

          public void clear()
          {
            SubMap.this.clear();
          }

          public boolean contains(Object o)
          {
            if (! (o instanceof Map.Entry))
              return false;
            Map.Entry me = (Map.Entry) o;
            Object key = me.getKey();
            if (! keyInRange(key))
              return false;
            Node n = getNode(key);
            return n != nil && AbstractSet.equals(me.getValue(), n.value);
          }

          public boolean remove(Object o)
          {
            if (! (o instanceof Map.Entry))
              return false;
            Map.Entry me = (Map.Entry) o;
            Object key = me.getKey();
            if (! keyInRange(key))
              return false;
            Node n = getNode(key);
            if (n != nil && AbstractSet.equals(me.getValue(), n.value))
              {
                removeNode(n);
                return true;
              }
            return false;
          }
        };
      return entries;
1616 1617
    }

1618
    public Object firstKey()
1619
    {
1620 1621 1622 1623
      Node node = lowestGreaterThan(minKey, true);
      if (node == nil || ! keyInRange(node.key))
        throw new NoSuchElementException();
      return node.key;
1624 1625
    }

1626
    public Object get(Object key)
1627 1628
    {
      if (keyInRange(key))
1629 1630
        return TreeMap.this.get(key);
      return null;
1631 1632
    }

1633
    public SortedMap headMap(Object toKey)
1634
    {
1635 1636 1637 1638
      if (! keyInRange(toKey))
        throw new IllegalArgumentException("key outside range");
      return new SubMap(minKey, toKey);
    }
1639

1640 1641 1642 1643 1644 1645
    public Set keySet()
    {
      if (this.keys == null)
        // Create an AbstractSet with custom implementations of those methods
        // that can be overriden easily and efficiently.
        this.keys = new AbstractSet()
1646
        {
1647 1648 1649 1650
          public int size()
          {
            return SubMap.this.size();
          }
1651

1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684
          public Iterator iterator()
          {
            Node first = lowestGreaterThan(minKey, true);
            Node max = lowestGreaterThan(maxKey, false);
            return new TreeIterator(KEYS, first, max);
          }

          public void clear()
          {
            SubMap.this.clear();
          }

          public boolean contains(Object o)
          {
            if (! keyInRange(o))
              return false;
            return getNode(o) != nil;
          }

          public boolean remove(Object o)
          {
            if (! keyInRange(o))
              return false;
            Node n = getNode(o);
            if (n != nil)
              {
                removeNode(n);
                return true;
              }
            return false;
          }
        };
      return this.keys;
1685 1686
    }

1687
    public Object lastKey()
1688
    {
1689 1690 1691 1692
      Node node = highestLessThan(maxKey);
      if (node == nil || ! keyInRange(node.key))
        throw new NoSuchElementException();
      return node.key;
1693 1694
    }

1695
    public Object put(Object key, Object value)
1696
    {
1697 1698 1699
      if (! keyInRange(key))
        throw new IllegalArgumentException("Key outside range");
      return TreeMap.this.put(key, value);
1700 1701
    }

1702
    public Object remove(Object key)
1703
    {
1704 1705 1706
      if (keyInRange(key))
        return TreeMap.this.remove(key);
      return null;
1707 1708
    }

1709
    public int size()
1710
    {
1711 1712 1713 1714 1715 1716 1717 1718 1719
      Node node = lowestGreaterThan(minKey, true);
      Node max = lowestGreaterThan(maxKey, false);
      int count = 0;
      while (node != max)
        {
          count++;
          node = successor(node);
        }
      return count;
1720 1721 1722 1723
    }

    public SortedMap subMap(Object fromKey, Object toKey)
    {
1724
      if (! keyInRange(fromKey) || ! keyInRange(toKey))
1725
        throw new IllegalArgumentException("key outside range");
1726
      return new SubMap(fromKey, toKey);
1727 1728
    }

1729
    public SortedMap tailMap(Object fromKey)
1730
    {
1731
      if (! keyInRange(fromKey))
1732
        throw new IllegalArgumentException("key outside range");
1733
      return new SubMap(fromKey, maxKey);
1734 1735
    }

1736
    public Collection values()
1737
    {
1738 1739 1740 1741 1742 1743 1744 1745 1746
      if (this.values == null)
        // Create an AbstractCollection with custom implementations of those
        // methods that can be overriden easily and efficiently.
        this.values = new AbstractCollection()
        {
          public int size()
          {
            return SubMap.this.size();
          }
1747

1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760
          public Iterator iterator()
          {
            Node first = lowestGreaterThan(minKey, true);
            Node max = lowestGreaterThan(maxKey, false);
            return new TreeIterator(VALUES, first, max);
          }

          public void clear()
          {
            SubMap.this.clear();
          }
        };
      return this.keys;
1761
    }
1762 1763
  } // class SubMap  
} // class TreeMap