Source for java.util.TreeMap

   1: /* TreeMap.java -- a class providing a basic Red-Black Tree data structure,
   2:    mapping Object --> Object
   3:    Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006  Free Software Foundation, Inc.
   4: 
   5: This file is part of GNU Classpath.
   6: 
   7: GNU Classpath is free software; you can redistribute it and/or modify
   8: it under the terms of the GNU General Public License as published by
   9: the Free Software Foundation; either version 2, or (at your option)
  10: any later version.
  11: 
  12: GNU Classpath is distributed in the hope that it will be useful, but
  13: WITHOUT ANY WARRANTY; without even the implied warranty of
  14: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15: General Public License for more details.
  16: 
  17: You should have received a copy of the GNU General Public License
  18: along with GNU Classpath; see the file COPYING.  If not, write to the
  19: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  20: 02110-1301 USA.
  21: 
  22: Linking this library statically or dynamically with other modules is
  23: making a combined work based on this library.  Thus, the terms and
  24: conditions of the GNU General Public License cover the whole
  25: combination.
  26: 
  27: As a special exception, the copyright holders of this library give you
  28: permission to link this library with independent modules to produce an
  29: executable, regardless of the license terms of these independent
  30: modules, and to copy and distribute the resulting executable under
  31: terms of your choice, provided that you also meet, for each linked
  32: independent module, the terms and conditions of the license of that
  33: module.  An independent module is a module which is not derived from
  34: or based on this library.  If you modify this library, you may extend
  35: this exception to your version of the library, but you are not
  36: obligated to do so.  If you do not wish to do so, delete this
  37: exception statement from your version. */
  38: 
  39: 
  40: package java.util;
  41: 
  42: import java.io.IOException;
  43: import java.io.ObjectInputStream;
  44: import java.io.ObjectOutputStream;
  45: import java.io.Serializable;
  46: 
  47: /**
  48:  * This class provides a red-black tree implementation of the SortedMap
  49:  * interface.  Elements in the Map will be sorted by either a user-provided
  50:  * Comparator object, or by the natural ordering of the keys.
  51:  *
  52:  * The algorithms are adopted from Corman, Leiserson, and Rivest's
  53:  * <i>Introduction to Algorithms.</i>  TreeMap guarantees O(log n)
  54:  * insertion and deletion of elements.  That being said, there is a large
  55:  * enough constant coefficient in front of that "log n" (overhead involved
  56:  * in keeping the tree balanced), that TreeMap may not be the best choice
  57:  * for small collections. If something is already sorted, you may want to
  58:  * just use a LinkedHashMap to maintain the order while providing O(1) access.
  59:  *
  60:  * TreeMap is a part of the JDK1.2 Collections API.  Null keys are allowed
  61:  * only if a Comparator is used which can deal with them; natural ordering
  62:  * cannot cope with null.  Null values are always allowed. Note that the
  63:  * ordering must be <i>consistent with equals</i> to correctly implement
  64:  * the Map interface. If this condition is violated, the map is still
  65:  * well-behaved, but you may have suprising results when comparing it to
  66:  * other maps.<p>
  67:  *
  68:  * This implementation is not synchronized. If you need to share this between
  69:  * multiple threads, do something like:<br>
  70:  * <code>SortedMap m
  71:  *       = Collections.synchronizedSortedMap(new TreeMap(...));</code><p>
  72:  *
  73:  * The iterators are <i>fail-fast</i>, meaning that any structural
  74:  * modification, except for <code>remove()</code> called on the iterator
  75:  * itself, cause the iterator to throw a
  76:  * <code>ConcurrentModificationException</code> rather than exhibit
  77:  * non-deterministic behavior.
  78:  *
  79:  * @author Jon Zeppieri
  80:  * @author Bryce McKinlay
  81:  * @author Eric Blake (ebb9@email.byu.edu)
  82:  * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
  83:  * @see Map
  84:  * @see HashMap
  85:  * @see Hashtable
  86:  * @see LinkedHashMap
  87:  * @see Comparable
  88:  * @see Comparator
  89:  * @see Collection
  90:  * @see Collections#synchronizedSortedMap(SortedMap)
  91:  * @since 1.2
  92:  * @status updated to 1.6
  93:  */
  94: public class TreeMap<K, V> extends AbstractMap<K, V>
  95:   implements NavigableMap<K, V>, Cloneable, Serializable
  96: {
  97:   // Implementation note:
  98:   // A red-black tree is a binary search tree with the additional properties
  99:   // that all paths to a leaf node visit the same number of black nodes,
 100:   // and no red node has red children. To avoid some null-pointer checks,
 101:   // we use the special node nil which is always black, has no relatives,
 102:   // and has key and value of null (but is not equal to a mapping of null).
 103: 
 104:   /**
 105:    * Compatible with JDK 1.2.
 106:    */
 107:   private static final long serialVersionUID = 919286545866124006L;
 108: 
 109:   /**
 110:    * Color status of a node. Package visible for use by nested classes.
 111:    */
 112:   static final int RED = -1,
 113:                    BLACK = 1;
 114: 
 115:   /**
 116:    * Sentinal node, used to avoid null checks for corner cases and make the
 117:    * delete rebalance code simpler. The rebalance code must never assign
 118:    * the parent, left, or right of nil, but may safely reassign the color
 119:    * to be black. This object must never be used as a key in a TreeMap, or
 120:    * it will break bounds checking of a SubMap.
 121:    */
 122:   static final Node nil = new Node(null, null, BLACK);
 123:   static
 124:     {
 125:       // Nil is self-referential, so we must initialize it after creation.
 126:       nil.parent = nil;
 127:       nil.left = nil;
 128:       nil.right = nil;
 129:     }
 130: 
 131:   /**
 132:    * The root node of this TreeMap.
 133:    */
 134:   private transient Node root;
 135: 
 136:   /**
 137:    * The size of this TreeMap. Package visible for use by nested classes.
 138:    */
 139:   transient int size;
 140: 
 141:   /**
 142:    * The cache for {@link #entrySet()}.
 143:    */
 144:   private transient Set<Map.Entry<K,V>> entries;
 145: 
 146:   /**
 147:    * The cache for {@link #descendingMap()}.
 148:    */
 149:   private transient NavigableMap<K,V> descendingMap;
 150: 
 151:   /**
 152:    * The cache for {@link #navigableKeySet()}.
 153:    */
 154:   private transient NavigableSet<K> nKeys;
 155: 
 156:   /**
 157:    * Counts the number of modifications this TreeMap has undergone, used
 158:    * by Iterators to know when to throw ConcurrentModificationExceptions.
 159:    * Package visible for use by nested classes.
 160:    */
 161:   transient int modCount;
 162: 
 163:   /**
 164:    * This TreeMap's comparator, or null for natural ordering.
 165:    * Package visible for use by nested classes.
 166:    * @serial the comparator ordering this tree, or null
 167:    */
 168:   final Comparator<? super K> comparator;
 169: 
 170:   /**
 171:    * Class to represent an entry in the tree. Holds a single key-value pair,
 172:    * plus pointers to parent and child nodes.
 173:    *
 174:    * @author Eric Blake (ebb9@email.byu.edu)
 175:    */
 176:   private static final class Node<K, V> extends AbstractMap.SimpleEntry<K, V>
 177:   {
 178:     // All fields package visible for use by nested classes.
 179:     /** The color of this node. */
 180:     int color;
 181: 
 182:     /** The left child node. */
 183:     Node<K, V> left = nil;
 184:     /** The right child node. */
 185:     Node<K, V> right = nil;
 186:     /** The parent node. */
 187:     Node<K, V> parent = nil;
 188: 
 189:     /**
 190:      * Simple constructor.
 191:      * @param key the key
 192:      * @param value the value
 193:      */
 194:     Node(K key, V value, int color)
 195:     {
 196:       super(key, value);
 197:       this.color = color;
 198:     }
 199:   }
 200: 
 201:   /**
 202:    * Instantiate a new TreeMap with no elements, using the keys' natural
 203:    * ordering to sort. All entries in the map must have a key which implements
 204:    * Comparable, and which are <i>mutually comparable</i>, otherwise map
 205:    * operations may throw a {@link ClassCastException}. Attempts to use
 206:    * a null key will throw a {@link NullPointerException}.
 207:    *
 208:    * @see Comparable
 209:    */
 210:   public TreeMap()
 211:   {
 212:     this((Comparator) null);
 213:   }
 214: 
 215:   /**
 216:    * Instantiate a new TreeMap with no elements, using the provided comparator
 217:    * to sort. All entries in the map must have keys which are mutually
 218:    * comparable by the Comparator, otherwise map operations may throw a
 219:    * {@link ClassCastException}.
 220:    *
 221:    * @param c the sort order for the keys of this map, or null
 222:    *        for the natural order
 223:    */
 224:   public TreeMap(Comparator<? super K> c)
 225:   {
 226:     comparator = c;
 227:     fabricateTree(0);
 228:   }
 229: 
 230:   /**
 231:    * Instantiate a new TreeMap, initializing it with all of the elements in
 232:    * the provided Map.  The elements will be sorted using the natural
 233:    * ordering of the keys. This algorithm runs in n*log(n) time. All entries
 234:    * in the map must have keys which implement Comparable and are mutually
 235:    * comparable, otherwise map operations may throw a
 236:    * {@link ClassCastException}.
 237:    *
 238:    * @param map a Map, whose entries will be put into this TreeMap
 239:    * @throws ClassCastException if the keys in the provided Map are not
 240:    *         comparable
 241:    * @throws NullPointerException if map is null
 242:    * @see Comparable
 243:    */
 244:   public TreeMap(Map<? extends K, ? extends V> map)
 245:   {
 246:     this((Comparator) null);
 247:     putAll(map);
 248:   }
 249: 
 250:   /**
 251:    * Instantiate a new TreeMap, initializing it with all of the elements in
 252:    * the provided SortedMap.  The elements will be sorted using the same
 253:    * comparator as in the provided SortedMap. This runs in linear time.
 254:    *
 255:    * @param sm a SortedMap, whose entries will be put into this TreeMap
 256:    * @throws NullPointerException if sm is null
 257:    */
 258:   public TreeMap(SortedMap<K, ? extends V> sm)
 259:   {
 260:     this(sm.comparator());
 261:     int pos = sm.size();
 262:     Iterator itr = sm.entrySet().iterator();
 263: 
 264:     fabricateTree(pos);
 265:     Node node = firstNode();
 266: 
 267:     while (--pos >= 0)
 268:       {
 269:         Map.Entry me = (Map.Entry) itr.next();
 270:         node.key = me.getKey();
 271:         node.value = me.getValue();
 272:         node = successor(node);
 273:       }
 274:   }
 275: 
 276:   /**
 277:    * Clears the Map so it has no keys. This is O(1).
 278:    */
 279:   public void clear()
 280:   {
 281:     if (size > 0)
 282:       {
 283:         modCount++;
 284:         root = nil;
 285:         size = 0;
 286:       }
 287:   }
 288: 
 289:   /**
 290:    * Returns a shallow clone of this TreeMap. The Map itself is cloned,
 291:    * but its contents are not.
 292:    *
 293:    * @return the clone
 294:    */
 295:   public Object clone()
 296:   {
 297:     TreeMap copy = null;
 298:     try
 299:       {
 300:         copy = (TreeMap) super.clone();
 301:       }
 302:     catch (CloneNotSupportedException x)
 303:       {
 304:       }
 305:     copy.entries = null;
 306:     copy.fabricateTree(size);
 307: 
 308:     Node node = firstNode();
 309:     Node cnode = copy.firstNode();
 310: 
 311:     while (node != nil)
 312:       {
 313:         cnode.key = node.key;
 314:         cnode.value = node.value;
 315:         node = successor(node);
 316:         cnode = copy.successor(cnode);
 317:       }
 318:     return copy;
 319:   }
 320: 
 321:   /**
 322:    * Return the comparator used to sort this map, or null if it is by
 323:    * natural order.
 324:    *
 325:    * @return the map's comparator
 326:    */
 327:   public Comparator<? super K> comparator()
 328:   {
 329:     return comparator;
 330:   }
 331: 
 332:   /**
 333:    * Returns true if the map contains a mapping for the given key.
 334:    *
 335:    * @param key the key to look for
 336:    * @return true if the key has a mapping
 337:    * @throws ClassCastException if key is not comparable to map elements
 338:    * @throws NullPointerException if key is null and the comparator is not
 339:    *         tolerant of nulls
 340:    */
 341:   public boolean containsKey(Object key)
 342:   {
 343:     return getNode((K) key) != nil;
 344:   }
 345: 
 346:   /**
 347:    * Returns true if the map contains at least one mapping to the given value.
 348:    * This requires linear time.
 349:    *
 350:    * @param value the value to look for
 351:    * @return true if the value appears in a mapping
 352:    */
 353:   public boolean containsValue(Object value)
 354:   {
 355:     Node node = firstNode();
 356:     while (node != nil)
 357:       {
 358:         if (equals(value, node.value))
 359:           return true;
 360:         node = successor(node);
 361:       }
 362:     return false;
 363:   }
 364: 
 365:   /**
 366:    * Returns a "set view" of this TreeMap's entries. The set is backed by
 367:    * the TreeMap, so changes in one show up in the other.  The set supports
 368:    * element removal, but not element addition.<p>
 369:    *
 370:    * Note that the iterators for all three views, from keySet(), entrySet(),
 371:    * and values(), traverse the TreeMap in sorted sequence.
 372:    *
 373:    * @return a set view of the entries
 374:    * @see #keySet()
 375:    * @see #values()
 376:    * @see Map.Entry
 377:    */
 378:   public Set<Map.Entry<K,V>> entrySet()
 379:   {
 380:     if (entries == null)
 381:       // Create an AbstractSet with custom implementations of those methods
 382:       // that can be overriden easily and efficiently.
 383:       entries = new NavigableEntrySet();
 384:     return entries;
 385:   }
 386: 
 387:   /**
 388:    * Returns the first (lowest) key in the map.
 389:    *
 390:    * @return the first key
 391:    * @throws NoSuchElementException if the map is empty
 392:    */
 393:   public K firstKey()
 394:   {
 395:     if (root == nil)
 396:       throw new NoSuchElementException();
 397:     return firstNode().key;
 398:   }
 399: 
 400:   /**
 401:    * Return the value in this TreeMap associated with the supplied key,
 402:    * or <code>null</code> if the key maps to nothing.  NOTE: Since the value
 403:    * could also be null, you must use containsKey to see if this key
 404:    * actually maps to something.
 405:    *
 406:    * @param key the key for which to fetch an associated value
 407:    * @return what the key maps to, if present
 408:    * @throws ClassCastException if key is not comparable to elements in the map
 409:    * @throws NullPointerException if key is null but the comparator does not
 410:    *         tolerate nulls
 411:    * @see #put(Object, Object)
 412:    * @see #containsKey(Object)
 413:    */
 414:   public V get(Object key)
 415:   {
 416:     // Exploit fact that nil.value == null.
 417:     return getNode((K) key).value;
 418:   }
 419: 
 420:   /**
 421:    * Returns a view of this Map including all entries with keys less than
 422:    * <code>toKey</code>. The returned map is backed by the original, so changes
 423:    * in one appear in the other. The submap will throw an
 424:    * {@link IllegalArgumentException} for any attempt to access or add an
 425:    * element beyond the specified cutoff. The returned map does not include
 426:    * the endpoint; if you want inclusion, pass the successor element
 427:    * or call <code>headMap(toKey, true)</code>.  This is equivalent to
 428:    * calling <code>headMap(toKey, false)</code>.
 429:    *
 430:    * @param toKey the (exclusive) cutoff point
 431:    * @return a view of the map less than the cutoff
 432:    * @throws ClassCastException if <code>toKey</code> is not compatible with
 433:    *         the comparator (or is not Comparable, for natural ordering)
 434:    * @throws NullPointerException if toKey is null, but the comparator does not
 435:    *         tolerate null elements
 436:    */
 437:   public SortedMap<K, V> headMap(K toKey)
 438:   {
 439:     return headMap(toKey, false);
 440:   }
 441: 
 442:   /**
 443:    * Returns a view of this Map including all entries with keys less than
 444:    * (or equal to, if <code>inclusive</code> is true) <code>toKey</code>.
 445:    * The returned map is backed by the original, so changes in one appear
 446:    * in the other. The submap will throw an {@link IllegalArgumentException}
 447:    * for any attempt to access or add an element beyond the specified cutoff. 
 448:    *
 449:    * @param toKey the cutoff point
 450:    * @param inclusive true if the cutoff point should be included.
 451:    * @return a view of the map less than (or equal to, if <code>inclusive</code>
 452:    *         is true) the cutoff.
 453:    * @throws ClassCastException if <code>toKey</code> is not compatible with
 454:    *         the comparator (or is not Comparable, for natural ordering)
 455:    * @throws NullPointerException if toKey is null, but the comparator does not
 456:    *         tolerate null elements
 457:    */
 458:   public NavigableMap<K, V> headMap(K toKey, boolean inclusive)
 459:   {
 460:     return new SubMap((K)(Object)nil, inclusive 
 461:               ? successor(getNode(toKey)).key : toKey);
 462:   }
 463: 
 464:   /**
 465:    * Returns a "set view" of this TreeMap's keys. The set is backed by the
 466:    * TreeMap, so changes in one show up in the other.  The set supports
 467:    * element removal, but not element addition.
 468:    *
 469:    * @return a set view of the keys
 470:    * @see #values()
 471:    * @see #entrySet()
 472:    */
 473:   public Set<K> keySet()
 474:   {
 475:     if (keys == null)
 476:       // Create an AbstractSet with custom implementations of those methods
 477:       // that can be overriden easily and efficiently.
 478:       keys = new KeySet();
 479:     return keys;
 480:   }
 481: 
 482:   /**
 483:    * Returns the last (highest) key in the map.
 484:    *
 485:    * @return the last key
 486:    * @throws NoSuchElementException if the map is empty
 487:    */
 488:   public K lastKey()
 489:   {
 490:     if (root == nil)
 491:       throw new NoSuchElementException("empty");
 492:     return lastNode().key;
 493:   }
 494: 
 495:   /**
 496:    * Puts the supplied value into the Map, mapped by the supplied key.
 497:    * The value may be retrieved by any object which <code>equals()</code>
 498:    * this key. NOTE: Since the prior value could also be null, you must
 499:    * first use containsKey if you want to see if you are replacing the
 500:    * key's mapping.
 501:    *
 502:    * @param key the key used to locate the value
 503:    * @param value the value to be stored in the Map
 504:    * @return the prior mapping of the key, or null if there was none
 505:    * @throws ClassCastException if key is not comparable to current map keys
 506:    * @throws NullPointerException if key is null, but the comparator does
 507:    *         not tolerate nulls
 508:    * @see #get(Object)
 509:    * @see Object#equals(Object)
 510:    */
 511:   public V put(K key, V value)
 512:   {
 513:     Node<K,V> current = root;
 514:     Node<K,V> parent = nil;
 515:     int comparison = 0;
 516: 
 517:     // Find new node's parent.
 518:     while (current != nil)
 519:       {
 520:         parent = current;
 521:         comparison = compare(key, current.key);
 522:         if (comparison > 0)
 523:           current = current.right;
 524:         else if (comparison < 0)
 525:           current = current.left;
 526:         else // Key already in tree.
 527:           return current.setValue(value);
 528:       }
 529: 
 530:     // Set up new node.
 531:     Node n = new Node(key, value, RED);
 532:     n.parent = parent;
 533: 
 534:     // Insert node in tree.
 535:     modCount++;
 536:     size++;
 537:     if (parent == nil)
 538:       {
 539:         // Special case inserting into an empty tree.
 540:         root = n;
 541:         return null;
 542:       }
 543:     if (comparison > 0)
 544:       parent.right = n;
 545:     else
 546:       parent.left = n;
 547: 
 548:     // Rebalance after insert.
 549:     insertFixup(n);
 550:     return null;
 551:   }
 552: 
 553:   /**
 554:    * Copies all elements of the given map into this TreeMap.  If this map
 555:    * already has a mapping for a key, the new mapping replaces the current
 556:    * one.
 557:    *
 558:    * @param m the map to be added
 559:    * @throws ClassCastException if a key in m is not comparable with keys
 560:    *         in the map
 561:    * @throws NullPointerException if a key in m is null, and the comparator
 562:    *         does not tolerate nulls
 563:    */
 564:   public void putAll(Map<? extends K, ? extends V> m)
 565:   {
 566:     Iterator itr = m.entrySet().iterator();
 567:     int pos = m.size();
 568:     while (--pos >= 0)
 569:       {
 570:         Map.Entry<K,V> e = (Map.Entry<K,V>) itr.next();
 571:         put(e.getKey(), e.getValue());
 572:       }
 573:   }
 574: 
 575:   /**
 576:    * Removes from the TreeMap and returns the value which is mapped by the
 577:    * supplied key. If the key maps to nothing, then the TreeMap remains
 578:    * unchanged, and <code>null</code> is returned. NOTE: Since the value
 579:    * could also be null, you must use containsKey to see if you are
 580:    * actually removing a mapping.
 581:    *
 582:    * @param key the key used to locate the value to remove
 583:    * @return whatever the key mapped to, if present
 584:    * @throws ClassCastException if key is not comparable to current map keys
 585:    * @throws NullPointerException if key is null, but the comparator does
 586:    *         not tolerate nulls
 587:    */
 588:   public V remove(Object key)
 589:   {
 590:     Node<K, V> n = getNode((K)key);
 591:     if (n == nil)
 592:       return null;
 593:     // Note: removeNode can alter the contents of n, so save value now.
 594:     V result = n.value;
 595:     removeNode(n);
 596:     return result;
 597:   }
 598: 
 599:   /**
 600:    * Returns the number of key-value mappings currently in this Map.
 601:    *
 602:    * @return the size
 603:    */
 604:   public int size()
 605:   {
 606:     return size;
 607:   }
 608: 
 609:   /**
 610:    * Returns a view of this Map including all entries with keys greater or
 611:    * equal to <code>fromKey</code> and less than <code>toKey</code> (a
 612:    * half-open interval). The returned map is backed by the original, so
 613:    * changes in one appear in the other. The submap will throw an
 614:    * {@link IllegalArgumentException} for any attempt to access or add an
 615:    * element beyond the specified cutoffs. The returned map includes the low
 616:    * endpoint but not the high; if you want to reverse this behavior on
 617:    * either end, pass in the successor element or call
 618:    * {@link #subMap(K,boolean,K,boolean)}.  This call is equivalent to
 619:    * <code>subMap(fromKey, true, toKey, false)</code>.
 620:    *
 621:    * @param fromKey the (inclusive) low cutoff point
 622:    * @param toKey the (exclusive) high cutoff point
 623:    * @return a view of the map between the cutoffs
 624:    * @throws ClassCastException if either cutoff is not compatible with
 625:    *         the comparator (or is not Comparable, for natural ordering)
 626:    * @throws NullPointerException if fromKey or toKey is null, but the
 627:    *         comparator does not tolerate null elements
 628:    * @throws IllegalArgumentException if fromKey is greater than toKey
 629:    */
 630:   public SortedMap<K, V> subMap(K fromKey, K toKey)
 631:   {
 632:     return subMap(fromKey, true, toKey, false);
 633:   }
 634: 
 635:   /**
 636:    * Returns a view of this Map including all entries with keys greater (or
 637:    * equal to, if <code>fromInclusive</code> is true) <code>fromKey</code> and
 638:    * less than (or equal to, if <code>toInclusive</code> is true)
 639:    * <code>toKey</code>. The returned map is backed by the original, so
 640:    * changes in one appear in the other. The submap will throw an
 641:    * {@link IllegalArgumentException} for any attempt to access or add an
 642:    * element beyond the specified cutoffs. 
 643:    *
 644:    * @param fromKey the low cutoff point
 645:    * @param fromInclusive true if the low cutoff point should be included.
 646:    * @param toKey the high cutoff point
 647:    * @param toInclusive true if the high cutoff point should be included.
 648:    * @return a view of the map for the specified range.
 649:    * @throws ClassCastException if either cutoff is not compatible with
 650:    *         the comparator (or is not Comparable, for natural ordering)
 651:    * @throws NullPointerException if fromKey or toKey is null, but the
 652:    *         comparator does not tolerate null elements
 653:    * @throws IllegalArgumentException if fromKey is greater than toKey
 654:    */
 655:   public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive,
 656:                    K toKey, boolean toInclusive)
 657:   {
 658:     return new SubMap(fromInclusive ? fromKey : successor(getNode(fromKey)).key,
 659:               toInclusive ? successor(getNode(toKey)).key : toKey);
 660:   }
 661: 
 662:   /**
 663:    * Returns a view of this Map including all entries with keys greater or
 664:    * equal to <code>fromKey</code>. The returned map is backed by the
 665:    * original, so changes in one appear in the other. The submap will throw an
 666:    * {@link IllegalArgumentException} for any attempt to access or add an
 667:    * element beyond the specified cutoff. The returned map includes the
 668:    * endpoint; if you want to exclude it, pass in the successor element.
 669:    * This is equivalent to calling <code>tailMap(fromKey, true)</code>.
 670:    *
 671:    * @param fromKey the (inclusive) low cutoff point
 672:    * @return a view of the map above the cutoff
 673:    * @throws ClassCastException if <code>fromKey</code> is not compatible with
 674:    *         the comparator (or is not Comparable, for natural ordering)
 675:    * @throws NullPointerException if fromKey is null, but the comparator
 676:    *         does not tolerate null elements
 677:    */
 678:   public SortedMap<K, V> tailMap(K fromKey)
 679:   {
 680:     return tailMap(fromKey, true);
 681:   }
 682: 
 683:   /**
 684:    * Returns a view of this Map including all entries with keys greater or
 685:    * equal to <code>fromKey</code>. The returned map is backed by the
 686:    * original, so changes in one appear in the other. The submap will throw an
 687:    * {@link IllegalArgumentException} for any attempt to access or add an
 688:    * element beyond the specified cutoff. The returned map includes the
 689:    * endpoint; if you want to exclude it, pass in the successor element.
 690:    *
 691:    * @param fromKey the low cutoff point
 692:    * @param inclusive true if the cutoff point should be included.
 693:    * @return a view of the map above the cutoff
 694:    * @throws ClassCastException if <code>fromKey</code> is not compatible with
 695:    *         the comparator (or is not Comparable, for natural ordering)
 696:    * @throws NullPointerException if fromKey is null, but the comparator
 697:    *         does not tolerate null elements
 698:    */
 699:   public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive)
 700:   {
 701:     return new SubMap(inclusive ? fromKey : successor(getNode(fromKey)).key,
 702:               (K)(Object)nil);
 703:   }
 704: 
 705:   /**
 706:    * Returns a "collection view" (or "bag view") of this TreeMap's values.
 707:    * The collection is backed by the TreeMap, so changes in one show up
 708:    * in the other.  The collection supports element removal, but not element
 709:    * addition.
 710:    *
 711:    * @return a bag view of the values
 712:    * @see #keySet()
 713:    * @see #entrySet()
 714:    */
 715:   public Collection<V> values()
 716:   {
 717:     if (values == null)
 718:       // We don't bother overriding many of the optional methods, as doing so
 719:       // wouldn't provide any significant performance advantage.
 720:       values = new AbstractCollection<V>()
 721:       {
 722:         public int size()
 723:         {
 724:           return size;
 725:         }
 726: 
 727:         public Iterator<V> iterator()
 728:         {
 729:           return new TreeIterator(VALUES);
 730:         }
 731: 
 732:         public void clear()
 733:         {
 734:           TreeMap.this.clear();
 735:         }
 736:       };
 737:     return values;
 738:   }
 739: 
 740:   /**
 741:    * Compares two elements by the set comparator, or by natural ordering.
 742:    * Package visible for use by nested classes.
 743:    *
 744:    * @param o1 the first object
 745:    * @param o2 the second object
 746:    * @throws ClassCastException if o1 and o2 are not mutually comparable,
 747:    *         or are not Comparable with natural ordering
 748:    * @throws NullPointerException if o1 or o2 is null with natural ordering
 749:    */
 750:   final int compare(K o1, K o2)
 751:   {
 752:     return (comparator == null
 753:             ? ((Comparable) o1).compareTo(o2)
 754:             : comparator.compare(o1, o2));
 755:   }
 756: 
 757:   /**
 758:    * Maintain red-black balance after deleting a node.
 759:    *
 760:    * @param node the child of the node just deleted, possibly nil
 761:    * @param parent the parent of the node just deleted, never nil
 762:    */
 763:   private void deleteFixup(Node<K,V> node, Node<K,V> parent)
 764:   {
 765:     // if (parent == nil)
 766:     //   throw new InternalError();
 767:     // If a black node has been removed, we need to rebalance to avoid
 768:     // violating the "same number of black nodes on any path" rule. If
 769:     // node is red, we can simply recolor it black and all is well.
 770:     while (node != root && node.color == BLACK)
 771:       {
 772:         if (node == parent.left)
 773:           {
 774:             // Rebalance left side.
 775:             Node<K,V> sibling = parent.right;
 776:             // if (sibling == nil)
 777:             //   throw new InternalError();
 778:             if (sibling.color == RED)
 779:               {
 780:                 // Case 1: Sibling is red.
 781:                 // Recolor sibling and parent, and rotate parent left.
 782:                 sibling.color = BLACK;
 783:                 parent.color = RED;
 784:                 rotateLeft(parent);
 785:                 sibling = parent.right;
 786:               }
 787: 
 788:             if (sibling.left.color == BLACK && sibling.right.color == BLACK)
 789:               {
 790:                 // Case 2: Sibling has no red children.
 791:                 // Recolor sibling, and move to parent.
 792:                 sibling.color = RED;
 793:                 node = parent;
 794:                 parent = parent.parent;
 795:               }
 796:             else
 797:               {
 798:                 if (sibling.right.color == BLACK)
 799:                   {
 800:                     // Case 3: Sibling has red left child.
 801:                     // Recolor sibling and left child, rotate sibling right.
 802:                     sibling.left.color = BLACK;
 803:                     sibling.color = RED;
 804:                     rotateRight(sibling);
 805:                     sibling = parent.right;
 806:                   }
 807:                 // Case 4: Sibling has red right child. Recolor sibling,
 808:                 // right child, and parent, and rotate parent left.
 809:                 sibling.color = parent.color;
 810:                 parent.color = BLACK;
 811:                 sibling.right.color = BLACK;
 812:                 rotateLeft(parent);
 813:                 node = root; // Finished.
 814:               }
 815:           }
 816:         else
 817:           {
 818:             // Symmetric "mirror" of left-side case.
 819:             Node<K,V> sibling = parent.left;
 820:             // if (sibling == nil)
 821:             //   throw new InternalError();
 822:             if (sibling.color == RED)
 823:               {
 824:                 // Case 1: Sibling is red.
 825:                 // Recolor sibling and parent, and rotate parent right.
 826:                 sibling.color = BLACK;
 827:                 parent.color = RED;
 828:                 rotateRight(parent);
 829:                 sibling = parent.left;
 830:               }
 831: 
 832:             if (sibling.right.color == BLACK && sibling.left.color == BLACK)
 833:               {
 834:                 // Case 2: Sibling has no red children.
 835:                 // Recolor sibling, and move to parent.
 836:                 sibling.color = RED;
 837:                 node = parent;
 838:                 parent = parent.parent;
 839:               }
 840:             else
 841:               {
 842:                 if (sibling.left.color == BLACK)
 843:                   {
 844:                     // Case 3: Sibling has red right child.
 845:                     // Recolor sibling and right child, rotate sibling left.
 846:                     sibling.right.color = BLACK;
 847:                     sibling.color = RED;
 848:                     rotateLeft(sibling);
 849:                     sibling = parent.left;
 850:                   }
 851:                 // Case 4: Sibling has red left child. Recolor sibling,
 852:                 // left child, and parent, and rotate parent right.
 853:                 sibling.color = parent.color;
 854:                 parent.color = BLACK;
 855:                 sibling.left.color = BLACK;
 856:                 rotateRight(parent);
 857:                 node = root; // Finished.
 858:               }
 859:           }
 860:       }
 861:     node.color = BLACK;
 862:   }
 863: 
 864:   /**
 865:    * Construct a perfectly balanced tree consisting of n "blank" nodes. This
 866:    * permits a tree to be generated from pre-sorted input in linear time.
 867:    *
 868:    * @param count the number of blank nodes, non-negative
 869:    */
 870:   private void fabricateTree(final int count)
 871:   {
 872:     if (count == 0)
 873:       {
 874:     root = nil;
 875:     size = 0;
 876:     return;
 877:       }
 878: 
 879:     // We color every row of nodes black, except for the overflow nodes.
 880:     // I believe that this is the optimal arrangement. We construct the tree
 881:     // in place by temporarily linking each node to the next node in the row,
 882:     // then updating those links to the children when working on the next row.
 883: 
 884:     // Make the root node.
 885:     root = new Node(null, null, BLACK);
 886:     size = count;
 887:     Node row = root;
 888:     int rowsize;
 889: 
 890:     // Fill each row that is completely full of nodes.
 891:     for (rowsize = 2; rowsize + rowsize <= count; rowsize <<= 1)
 892:       {
 893:         Node parent = row;
 894:         Node last = null;
 895:         for (int i = 0; i < rowsize; i += 2)
 896:           {
 897:             Node left = new Node(null, null, BLACK);
 898:             Node right = new Node(null, null, BLACK);
 899:             left.parent = parent;
 900:             left.right = right;
 901:             right.parent = parent;
 902:             parent.left = left;
 903:             Node next = parent.right;
 904:             parent.right = right;
 905:             parent = next;
 906:             if (last != null)
 907:               last.right = left;
 908:             last = right;
 909:           }
 910:         row = row.left;
 911:       }
 912: 
 913:     // Now do the partial final row in red.
 914:     int overflow = count - rowsize;
 915:     Node parent = row;
 916:     int i;
 917:     for (i = 0; i < overflow; i += 2)
 918:       {
 919:         Node left = new Node(null, null, RED);
 920:         Node right = new Node(null, null, RED);
 921:         left.parent = parent;
 922:         right.parent = parent;
 923:         parent.left = left;
 924:         Node next = parent.right;
 925:         parent.right = right;
 926:         parent = next;
 927:       }
 928:     // Add a lone left node if necessary.
 929:     if (i - overflow == 0)
 930:       {
 931:         Node left = new Node(null, null, RED);
 932:         left.parent = parent;
 933:         parent.left = left;
 934:         parent = parent.right;
 935:         left.parent.right = nil;
 936:       }
 937:     // Unlink the remaining nodes of the previous row.
 938:     while (parent != nil)
 939:       {
 940:         Node next = parent.right;
 941:         parent.right = nil;
 942:         parent = next;
 943:       }
 944:   }
 945: 
 946:   /**
 947:    * Returns the first sorted node in the map, or nil if empty. Package
 948:    * visible for use by nested classes.
 949:    *
 950:    * @return the first node
 951:    */
 952:   final Node<K, V> firstNode()
 953:   {
 954:     // Exploit fact that nil.left == nil.
 955:     Node node = root;
 956:     while (node.left != nil)
 957:       node = node.left;
 958:     return node;
 959:   }
 960: 
 961:   /**
 962:    * Return the TreeMap.Node associated with key, or the nil node if no such
 963:    * node exists in the tree. Package visible for use by nested classes.
 964:    *
 965:    * @param key the key to search for
 966:    * @return the node where the key is found, or nil
 967:    */
 968:   final Node<K, V> getNode(K key)
 969:   {
 970:     Node<K,V> current = root;
 971:     while (current != nil)
 972:       {
 973:         int comparison = compare(key, current.key);
 974:         if (comparison > 0)
 975:           current = current.right;
 976:         else if (comparison < 0)
 977:           current = current.left;
 978:         else
 979:           return current;
 980:       }
 981:     return current;
 982:   }
 983: 
 984:   /**
 985:    * Find the "highest" node which is &lt; key. If key is nil, return last
 986:    * node. Package visible for use by nested classes.
 987:    *
 988:    * @param key the upper bound, exclusive
 989:    * @return the previous node
 990:    */
 991:   final Node<K,V> highestLessThan(K key)
 992:   {
 993:     return highestLessThan(key, false);
 994:   }
 995: 
 996:   /**
 997:    * Find the "highest" node which is &lt; (or equal to,
 998:    * if <code>equal</code> is true) key. If key is nil,
 999:    * return last node. Package visible for use by nested
1000:    * classes.
1001:    *
1002:    * @param key the upper bound, exclusive
1003:    * @param equal true if the key should be returned if found.
1004:    * @return the previous node
1005:    */
1006:   final Node<K,V> highestLessThan(K key, boolean equal)
1007:   {
1008:     if (key == nil)
1009:       return lastNode();
1010: 
1011:     Node<K,V> last = nil;
1012:     Node<K,V> current = root;
1013:     int comparison = 0;
1014: 
1015:     while (current != nil)
1016:       {
1017:         last = current;
1018:         comparison = compare(key, current.key);
1019:         if (comparison > 0)
1020:           current = current.right;
1021:         else if (comparison < 0)
1022:           current = current.left;
1023:         else // Exact match.
1024:           return (equal ? last : predecessor(last));
1025:       }
1026:     return comparison < 0 ? predecessor(last) : last;
1027:   }
1028: 
1029:   /**
1030:    * Maintain red-black balance after inserting a new node.
1031:    *
1032:    * @param n the newly inserted node
1033:    */
1034:   private void insertFixup(Node<K,V> n)
1035:   {
1036:     // Only need to rebalance when parent is a RED node, and while at least
1037:     // 2 levels deep into the tree (ie: node has a grandparent). Remember
1038:     // that nil.color == BLACK.
1039:     while (n.parent.color == RED && n.parent.parent != nil)
1040:       {
1041:         if (n.parent == n.parent.parent.left)
1042:           {
1043:             Node uncle = n.parent.parent.right;
1044:             // Uncle may be nil, in which case it is BLACK.
1045:             if (uncle.color == RED)
1046:               {
1047:                 // Case 1. Uncle is RED: Change colors of parent, uncle,
1048:                 // and grandparent, and move n to grandparent.
1049:                 n.parent.color = BLACK;
1050:                 uncle.color = BLACK;
1051:                 uncle.parent.color = RED;
1052:                 n = uncle.parent;
1053:               }
1054:             else
1055:               {
1056:                 if (n == n.parent.right)
1057:                   {
1058:                     // Case 2. Uncle is BLACK and x is right child.
1059:                     // Move n to parent, and rotate n left.
1060:                     n = n.parent;
1061:                     rotateLeft(n);
1062:                   }
1063:                 // Case 3. Uncle is BLACK and x is left child.
1064:                 // Recolor parent, grandparent, and rotate grandparent right.
1065:                 n.parent.color = BLACK;
1066:                 n.parent.parent.color = RED;
1067:                 rotateRight(n.parent.parent);
1068:               }
1069:           }
1070:         else
1071:           {
1072:             // Mirror image of above code.
1073:             Node uncle = n.parent.parent.left;
1074:             // Uncle may be nil, in which case it is BLACK.
1075:             if (uncle.color == RED)
1076:               {
1077:                 // Case 1. Uncle is RED: Change colors of parent, uncle,
1078:                 // and grandparent, and move n to grandparent.
1079:                 n.parent.color = BLACK;
1080:                 uncle.color = BLACK;
1081:                 uncle.parent.color = RED;
1082:                 n = uncle.parent;
1083:               }
1084:             else
1085:               {
1086:                 if (n == n.parent.left)
1087:                 {
1088:                     // Case 2. Uncle is BLACK and x is left child.
1089:                     // Move n to parent, and rotate n right.
1090:                     n = n.parent;
1091:                     rotateRight(n);
1092:                   }
1093:                 // Case 3. Uncle is BLACK and x is right child.
1094:                 // Recolor parent, grandparent, and rotate grandparent left.
1095:                 n.parent.color = BLACK;
1096:                 n.parent.parent.color = RED;
1097:                 rotateLeft(n.parent.parent);
1098:               }
1099:           }
1100:       }
1101:     root.color = BLACK;
1102:   }
1103: 
1104:   /**
1105:    * Returns the last sorted node in the map, or nil if empty.
1106:    *
1107:    * @return the last node
1108:    */
1109:   private Node<K,V> lastNode()
1110:   {
1111:     // Exploit fact that nil.right == nil.
1112:     Node node = root;
1113:     while (node.right != nil)
1114:       node = node.right;
1115:     return node;
1116:   }
1117: 
1118:   /**
1119:    * Find the "lowest" node which is &gt;= key. If key is nil, return either
1120:    * nil or the first node, depending on the parameter first.  Package visible
1121:    * for use by nested classes.
1122:    *
1123:    * @param key the lower bound, inclusive
1124:    * @param first true to return the first element instead of nil for nil key
1125:    * @return the next node
1126:    */
1127:   final Node<K,V> lowestGreaterThan(K key, boolean first)
1128:   {
1129:     return lowestGreaterThan(key, first, true);
1130:   }
1131: 
1132:   /**
1133:    * Find the "lowest" node which is &gt; (or equal to, if <code>equal</code>
1134:    * is true) key. If key is nil, return either nil or the first node, depending
1135:    * on the parameter first.  Package visible for use by nested classes.
1136:    *
1137:    * @param key the lower bound, inclusive
1138:    * @param first true to return the first element instead of nil for nil key
1139:    * @param equal true if the key should be returned if found.
1140:    * @return the next node
1141:    */
1142:   final Node<K,V> lowestGreaterThan(K key, boolean first, boolean equal)
1143:   {
1144:     if (key == nil)
1145:       return first ? firstNode() : nil;
1146: 
1147:     Node<K,V> last = nil;
1148:     Node<K,V> current = root;
1149:     int comparison = 0;
1150: 
1151:     while (current != nil)
1152:       {
1153:         last = current;
1154:         comparison = compare(key, current.key);
1155:         if (comparison > 0)
1156:           current = current.right;
1157:         else if (comparison < 0)
1158:           current = current.left;
1159:         else
1160:           return (equal ? current : successor(current));
1161:       }
1162:     return comparison > 0 ? successor(last) : last;
1163:   }
1164: 
1165:   /**
1166:    * Return the node preceding the given one, or nil if there isn't one.
1167:    *
1168:    * @param node the current node, not nil
1169:    * @return the prior node in sorted order
1170:    */
1171:   private Node<K,V> predecessor(Node<K,V> node)
1172:   {
1173:     if (node.left != nil)
1174:       {
1175:         node = node.left;
1176:         while (node.right != nil)
1177:           node = node.right;
1178:         return node;
1179:       }
1180: 
1181:     Node parent = node.parent;
1182:     // Exploit fact that nil.left == nil and node is non-nil.
1183:     while (node == parent.left)
1184:       {
1185:         node = parent;
1186:         parent = node.parent;
1187:       }
1188:     return parent;
1189:   }
1190: 
1191:   /**
1192:    * Construct a tree from sorted keys in linear time. Package visible for
1193:    * use by TreeSet.
1194:    *
1195:    * @param s the stream to read from
1196:    * @param count the number of keys to read
1197:    * @param readValues true to read values, false to insert "" as the value
1198:    * @throws ClassNotFoundException if the underlying stream fails
1199:    * @throws IOException if the underlying stream fails
1200:    * @see #readObject(ObjectInputStream)
1201:    * @see TreeSet#readObject(ObjectInputStream)
1202:    */
1203:   final void putFromObjStream(ObjectInputStream s, int count,
1204:                               boolean readValues)
1205:     throws IOException, ClassNotFoundException
1206:   {
1207:     fabricateTree(count);
1208:     Node node = firstNode();
1209: 
1210:     while (--count >= 0)
1211:       {
1212:         node.key = s.readObject();
1213:         node.value = readValues ? s.readObject() : "";
1214:         node = successor(node);
1215:       }
1216:   }
1217: 
1218:   /**
1219:    * Construct a tree from sorted keys in linear time, with values of "".
1220:    * Package visible for use by TreeSet, which uses a value type of String.
1221:    *
1222:    * @param keys the iterator over the sorted keys
1223:    * @param count the number of nodes to insert
1224:    * @see TreeSet#TreeSet(SortedSet)
1225:    */
1226:   final void putKeysLinear(Iterator<K> keys, int count)
1227:   {
1228:     fabricateTree(count);
1229:     Node<K,V> node = firstNode();
1230: 
1231:     while (--count >= 0)
1232:       {
1233:         node.key = keys.next();
1234:         node.value = (V) "";
1235:         node = successor(node);
1236:       }
1237:   }
1238: 
1239:   /**
1240:    * Deserializes this object from the given stream.
1241:    *
1242:    * @param s the stream to read from
1243:    * @throws ClassNotFoundException if the underlying stream fails
1244:    * @throws IOException if the underlying stream fails
1245:    * @serialData the <i>size</i> (int), followed by key (Object) and value
1246:    *             (Object) pairs in sorted order
1247:    */
1248:   private void readObject(ObjectInputStream s)
1249:     throws IOException, ClassNotFoundException
1250:   {
1251:     s.defaultReadObject();
1252:     int size = s.readInt();
1253:     putFromObjStream(s, size, true);
1254:   }
1255: 
1256:   /**
1257:    * Remove node from tree. This will increment modCount and decrement size.
1258:    * Node must exist in the tree. Package visible for use by nested classes.
1259:    *
1260:    * @param node the node to remove
1261:    */
1262:   final void removeNode(Node<K,V> node)
1263:   {
1264:     Node<K,V> splice;
1265:     Node<K,V> child;
1266: 
1267:     modCount++;
1268:     size--;
1269: 
1270:     // Find splice, the node at the position to actually remove from the tree.
1271:     if (node.left == nil)
1272:       {
1273:         // Node to be deleted has 0 or 1 children.
1274:         splice = node;
1275:         child = node.right;
1276:       }
1277:     else if (node.right == nil)
1278:       {
1279:         // Node to be deleted has 1 child.
1280:         splice = node;
1281:         child = node.left;
1282:       }
1283:     else
1284:       {
1285:         // Node has 2 children. Splice is node's predecessor, and we swap
1286:         // its contents into node.
1287:         splice = node.left;
1288:         while (splice.right != nil)
1289:           splice = splice.right;
1290:         child = splice.left;
1291:         node.key = splice.key;
1292:         node.value = splice.value;
1293:       }
1294: 
1295:     // Unlink splice from the tree.
1296:     Node parent = splice.parent;
1297:     if (child != nil)
1298:       child.parent = parent;
1299:     if (parent == nil)
1300:       {
1301:         // Special case for 0 or 1 node remaining.
1302:         root = child;
1303:         return;
1304:       }
1305:     if (splice == parent.left)
1306:       parent.left = child;
1307:     else
1308:       parent.right = child;
1309: 
1310:     if (splice.color == BLACK)
1311:       deleteFixup(child, parent);
1312:   }
1313: 
1314:   /**
1315:    * Rotate node n to the left.
1316:    *
1317:    * @param node the node to rotate
1318:    */
1319:   private void rotateLeft(Node<K,V> node)
1320:   {
1321:     Node child = node.right;
1322:     // if (node == nil || child == nil)
1323:     //   throw new InternalError();
1324: 
1325:     // Establish node.right link.
1326:     node.right = child.left;
1327:     if (child.left != nil)
1328:       child.left.parent = node;
1329: 
1330:     // Establish child->parent link.
1331:     child.parent = node.parent;
1332:     if (node.parent != nil)
1333:       {
1334:         if (node == node.parent.left)
1335:           node.parent.left = child;
1336:         else
1337:           node.parent.right = child;
1338:       }
1339:     else
1340:       root = child;
1341: 
1342:     // Link n and child.
1343:     child.left = node;
1344:     node.parent = child;
1345:   }
1346: 
1347:   /**
1348:    * Rotate node n to the right.
1349:    *
1350:    * @param node the node to rotate
1351:    */
1352:   private void rotateRight(Node<K,V> node)
1353:   {
1354:     Node child = node.left;
1355:     // if (node == nil || child == nil)
1356:     //   throw new InternalError();
1357: 
1358:     // Establish node.left link.
1359:     node.left = child.right;
1360:     if (child.right != nil)
1361:       child.right.parent = node;
1362: 
1363:     // Establish child->parent link.
1364:     child.parent = node.parent;
1365:     if (node.parent != nil)
1366:       {
1367:         if (node == node.parent.right)
1368:           node.parent.right = child;
1369:         else
1370:           node.parent.left = child;
1371:       }
1372:     else
1373:       root = child;
1374: 
1375:     // Link n and child.
1376:     child.right = node;
1377:     node.parent = child;
1378:   }
1379: 
1380:   /**
1381:    * Return the node following the given one, or nil if there isn't one.
1382:    * Package visible for use by nested classes.
1383:    *
1384:    * @param node the current node, not nil
1385:    * @return the next node in sorted order
1386:    */
1387:   final Node<K,V> successor(Node<K,V> node)
1388:   {
1389:     if (node.right != nil)
1390:       {
1391:         node = node.right;
1392:         while (node.left != nil)
1393:           node = node.left;
1394:         return node;
1395:       }
1396: 
1397:     Node<K,V> parent = node.parent;
1398:     // Exploit fact that nil.right == nil and node is non-nil.
1399:     while (node == parent.right)
1400:       {
1401:         node = parent;
1402:         parent = parent.parent;
1403:       }
1404:     return parent;
1405:   }
1406: 
1407:   /**
1408:    * Serializes this object to the given stream.
1409:    *
1410:    * @param s the stream to write to
1411:    * @throws IOException if the underlying stream fails
1412:    * @serialData the <i>size</i> (int), followed by key (Object) and value
1413:    *             (Object) pairs in sorted order
1414:    */
1415:   private void writeObject(ObjectOutputStream s) throws IOException
1416:   {
1417:     s.defaultWriteObject();
1418: 
1419:     Node node = firstNode();
1420:     s.writeInt(size);
1421:     while (node != nil)
1422:       {
1423:         s.writeObject(node.key);
1424:         s.writeObject(node.value);
1425:         node = successor(node);
1426:       }
1427:   }
1428: 
1429:   /**
1430:    * Iterate over TreeMap's entries. This implementation is parameterized
1431:    * to give a sequential view of keys, values, or entries.
1432:    *
1433:    * @author Eric Blake (ebb9@email.byu.edu)
1434:    */
1435:   private final class TreeIterator implements Iterator
1436:   {
1437:     /**
1438:      * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
1439:      * or {@link #ENTRIES}.
1440:      */
1441:     private final int type;
1442:     /** The number of modifications to the backing Map that we know about. */
1443:     private int knownMod = modCount;
1444:     /** The last Entry returned by a next() call. */
1445:     private Node last;
1446:     /** The next entry that should be returned by next(). */
1447:     private Node next;
1448:     /**
1449:      * The last node visible to this iterator. This is used when iterating
1450:      * on a SubMap.
1451:      */
1452:     private final Node max;
1453: 
1454:     /**
1455:      * Construct a new TreeIterator with the supplied type.
1456:      * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
1457:      */
1458:     TreeIterator(int type)
1459:     {
1460:       this(type, firstNode(), nil);
1461:     }
1462: 
1463:     /**
1464:      * Construct a new TreeIterator with the supplied type. Iteration will
1465:      * be from "first" (inclusive) to "max" (exclusive).
1466:      *
1467:      * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
1468:      * @param first where to start iteration, nil for empty iterator
1469:      * @param max the cutoff for iteration, nil for all remaining nodes
1470:      */
1471:     TreeIterator(int type, Node first, Node max)
1472:     {
1473:       this.type = type;
1474:       this.next = first;
1475:       this.max = max;
1476:     }
1477: 
1478:     /**
1479:      * Returns true if the Iterator has more elements.
1480:      * @return true if there are more elements
1481:      */
1482:     public boolean hasNext()
1483:     {
1484:       return next != max;
1485:     }
1486: 
1487:     /**
1488:      * Returns the next element in the Iterator's sequential view.
1489:      * @return the next element
1490:      * @throws ConcurrentModificationException if the TreeMap was modified
1491:      * @throws NoSuchElementException if there is none
1492:      */
1493:     public Object next()
1494:     {
1495:       if (knownMod != modCount)
1496:         throw new ConcurrentModificationException();
1497:       if (next == max)
1498:         throw new NoSuchElementException();
1499:       last = next;
1500:       next = successor(last);
1501: 
1502:       if (type == VALUES)
1503:         return last.value;
1504:       else if (type == KEYS)
1505:         return last.key;
1506:       return last;
1507:     }
1508: 
1509:     /**
1510:      * Removes from the backing TreeMap the last element which was fetched
1511:      * with the <code>next()</code> method.
1512:      * @throws ConcurrentModificationException if the TreeMap was modified
1513:      * @throws IllegalStateException if called when there is no last element
1514:      */
1515:     public void remove()
1516:     {
1517:       if (last == null)
1518:         throw new IllegalStateException();
1519:       if (knownMod != modCount)
1520:         throw new ConcurrentModificationException();
1521: 
1522:       removeNode(last);
1523:       last = null;
1524:       knownMod++;
1525:     }
1526:   } // class TreeIterator
1527: 
1528:   /**
1529:    * Implementation of {@link #subMap(Object, Object)} and other map
1530:    * ranges. This class provides a view of a portion of the original backing
1531:    * map, and throws {@link IllegalArgumentException} for attempts to
1532:    * access beyond that range.
1533:    *
1534:    * @author Eric Blake (ebb9@email.byu.edu)
1535:    */
1536:   private final class SubMap
1537:     extends AbstractMap<K,V>
1538:     implements NavigableMap<K,V>
1539:   {
1540:     /**
1541:      * The lower range of this view, inclusive, or nil for unbounded.
1542:      * Package visible for use by nested classes.
1543:      */
1544:     final K minKey;
1545: 
1546:     /**
1547:      * The upper range of this view, exclusive, or nil for unbounded.
1548:      * Package visible for use by nested classes.
1549:      */
1550:     final K maxKey;
1551: 
1552:     /**
1553:      * The cache for {@link #entrySet()}.
1554:      */
1555:     private Set<Map.Entry<K,V>> entries;
1556: 
1557:     /**
1558:      * The cache for {@link #descendingMap()}.
1559:      */
1560:     private NavigableMap<K,V> descendingMap;
1561: 
1562:     /**
1563:      * The cache for {@link #navigableKeySet()}.
1564:      */
1565:     private NavigableSet<K> nKeys;
1566: 
1567:     /**
1568:      * Create a SubMap representing the elements between minKey (inclusive)
1569:      * and maxKey (exclusive). If minKey is nil, SubMap has no lower bound
1570:      * (headMap). If maxKey is nil, the SubMap has no upper bound (tailMap).
1571:      *
1572:      * @param minKey the lower bound
1573:      * @param maxKey the upper bound
1574:      * @throws IllegalArgumentException if minKey &gt; maxKey
1575:      */
1576:     SubMap(K minKey, K maxKey)
1577:     {
1578:       if (minKey != nil && maxKey != nil && compare(minKey, maxKey) > 0)
1579:         throw new IllegalArgumentException("fromKey > toKey");
1580:       this.minKey = minKey;
1581:       this.maxKey = maxKey;
1582:     }
1583: 
1584:     /**
1585:      * Check if "key" is in within the range bounds for this SubMap. The
1586:      * lower ("from") SubMap range is inclusive, and the upper ("to") bound
1587:      * is exclusive. Package visible for use by nested classes.
1588:      *
1589:      * @param key the key to check
1590:      * @return true if the key is in range
1591:      */
1592:     boolean keyInRange(K key)
1593:     {
1594:       return ((minKey == nil || compare(key, minKey) >= 0)
1595:               && (maxKey == nil || compare(key, maxKey) < 0));
1596:     }
1597: 
1598:     public Entry<K,V> ceilingEntry(K key)
1599:     {
1600:       Entry<K,V> n = TreeMap.this.ceilingEntry(key);
1601:       if (n != null && keyInRange(n.getKey()))
1602:     return n;
1603:       return null;
1604:     }
1605: 
1606:     public K ceilingKey(K key)
1607:     {
1608:       K found = TreeMap.this.ceilingKey(key);
1609:       if (keyInRange(found))
1610:     return found;
1611:       else
1612:     return null;
1613:     }
1614: 
1615:     public NavigableSet<K> descendingKeySet()
1616:     {
1617:       return descendingMap().navigableKeySet();
1618:     }
1619: 
1620:     public NavigableMap<K,V> descendingMap()
1621:     {
1622:       if (descendingMap == null)
1623:     descendingMap = new DescendingMap(this);
1624:       return descendingMap;
1625:     }
1626:     
1627:     public void clear()
1628:     {
1629:       Node next = lowestGreaterThan(minKey, true);
1630:       Node max = lowestGreaterThan(maxKey, false);
1631:       while (next != max)
1632:         {
1633:           Node current = next;
1634:           next = successor(current);
1635:           removeNode(current);
1636:         }
1637:     }
1638: 
1639:     public Comparator<? super K> comparator()
1640:     {
1641:       return comparator;
1642:     }
1643: 
1644:     public boolean containsKey(Object key)
1645:     {
1646:       return keyInRange((K) key) && TreeMap.this.containsKey(key);
1647:     }
1648: 
1649:     public boolean containsValue(Object value)
1650:     {
1651:       Node node = lowestGreaterThan(minKey, true);
1652:       Node max = lowestGreaterThan(maxKey, false);
1653:       while (node != max)
1654:         {
1655:           if (equals(value, node.getValue()))
1656:             return true;
1657:           node = successor(node);
1658:         }
1659:       return false;
1660:     }
1661: 
1662:     public Set<Map.Entry<K,V>> entrySet()
1663:     {
1664:       if (entries == null)
1665:         // Create an AbstractSet with custom implementations of those methods
1666:         // that can be overriden easily and efficiently.
1667:         entries = new SubMap.NavigableEntrySet();
1668:       return entries;
1669:     }
1670: 
1671:     public Entry<K,V> firstEntry()
1672:     {
1673:       Node<K,V> node = lowestGreaterThan(minKey, true);
1674:       if (node == nil || ! keyInRange(node.key))
1675:     return null;
1676:       return node;
1677:     }
1678: 
1679:     public K firstKey()
1680:     {
1681:       Entry<K,V> e = firstEntry();
1682:       if (e == null)
1683:         throw new NoSuchElementException();
1684:       return e.getKey();
1685:     }
1686: 
1687:     public Entry<K,V> floorEntry(K key)
1688:     {
1689:       Entry<K,V> n = TreeMap.this.floorEntry(key);
1690:       if (n != null && keyInRange(n.getKey()))
1691:     return n;
1692:       return null;
1693:     }
1694: 
1695:     public K floorKey(K key)
1696:     {
1697:       K found = TreeMap.this.floorKey(key);
1698:       if (keyInRange(found))
1699:     return found;
1700:       else
1701:     return null;
1702:     }
1703: 
1704:     public V get(Object key)
1705:     {
1706:       if (keyInRange((K) key))
1707:         return TreeMap.this.get(key);
1708:       return null;
1709:     }
1710: 
1711:     public SortedMap<K,V> headMap(K toKey)
1712:     {
1713:       return headMap(toKey, false);
1714:     }
1715: 
1716:     public NavigableMap<K,V> headMap(K toKey, boolean inclusive)
1717:     {
1718:       if (!keyInRange(toKey))
1719:         throw new IllegalArgumentException("Key outside submap range");
1720:       return new SubMap(minKey, (inclusive ? 
1721:                  successor(getNode(toKey)).key : toKey));
1722:     }
1723: 
1724:     public Set<K> keySet()
1725:     {
1726:       if (this.keys == null)
1727:         // Create an AbstractSet with custom implementations of those methods
1728:         // that can be overriden easily and efficiently.
1729:         this.keys = new SubMap.KeySet();
1730:       return this.keys;
1731:     }
1732: 
1733:     public Entry<K,V> higherEntry(K key)
1734:     {
1735:       Entry<K,V> n = TreeMap.this.higherEntry(key);
1736:       if (n != null && keyInRange(n.getKey()))
1737:     return n;
1738:       return null;
1739:     }
1740: 
1741:     public K higherKey(K key)
1742:     {
1743:       K found = TreeMap.this.higherKey(key);
1744:       if (keyInRange(found))
1745:     return found;
1746:       else
1747:     return null;
1748:     }
1749: 
1750:     public Entry<K,V> lastEntry()
1751:     {
1752:       return lowerEntry(maxKey);
1753:     }
1754: 
1755:     public K lastKey()
1756:     {
1757:       Entry<K,V> e = lastEntry();
1758:       if (e == null)
1759:         throw new NoSuchElementException();
1760:       return e.getKey();
1761:     }
1762: 
1763:     public Entry<K,V> lowerEntry(K key)
1764:     {
1765:       Entry<K,V> n = TreeMap.this.lowerEntry(key);
1766:       if (n != null && keyInRange(n.getKey()))
1767:     return n;
1768:       return null;
1769:     }
1770: 
1771:     public K lowerKey(K key)
1772:     {
1773:       K found = TreeMap.this.lowerKey(key);
1774:       if (keyInRange(found))
1775:     return found;
1776:       else
1777:     return null;
1778:     }
1779: 
1780:     public NavigableSet<K> navigableKeySet()
1781:     {
1782:       if (this.nKeys == null)
1783:         // Create an AbstractSet with custom implementations of those methods
1784:         // that can be overriden easily and efficiently.
1785:         this.nKeys = new SubMap.NavigableKeySet();
1786:       return this.nKeys;    
1787:     }
1788: 
1789:     public Entry<K,V> pollFirstEntry()
1790:     {
1791:       Entry<K,V> e = firstEntry();
1792:       if (e != null)
1793:     removeNode((Node<K,V>) e);
1794:       return e;
1795:     }
1796: 
1797:     public Entry<K,V> pollLastEntry()
1798:     {
1799:       Entry<K,V> e = lastEntry();
1800:       if (e != null)
1801:     removeNode((Node<K,V>) e);
1802:       return e;
1803:     }
1804: 
1805:     public V put(K key, V value)
1806:     {
1807:       if (! keyInRange(key))
1808:         throw new IllegalArgumentException("Key outside range");
1809:       return TreeMap.this.put(key, value);
1810:     }
1811: 
1812:     public V remove(Object key)
1813:     {
1814:       if (keyInRange((K)key))
1815:         return TreeMap.this.remove(key);
1816:       return null;
1817:     }
1818: 
1819:     public int size()
1820:     {
1821:       Node node = lowestGreaterThan(minKey, true);
1822:       Node max = lowestGreaterThan(maxKey, false);
1823:       int count = 0;
1824:       while (node != max)
1825:         {
1826:           count++;
1827:           node = successor(node);
1828:         }
1829:       return count;
1830:     }
1831: 
1832:     public SortedMap<K,V> subMap(K fromKey, K toKey)
1833:     {
1834:       return subMap(fromKey, true, toKey, false);
1835:     }
1836: 
1837:     public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1838:                     K toKey, boolean toInclusive)
1839:     {
1840:       if (! keyInRange(fromKey) || ! keyInRange(toKey))
1841:         throw new IllegalArgumentException("key outside range");
1842:       return new SubMap(fromInclusive ? fromKey : successor(getNode(fromKey)).key, 
1843:             toInclusive ? successor(getNode(toKey)).key : toKey);
1844:     }
1845: 
1846:     public SortedMap<K, V> tailMap(K fromKey)
1847:     {
1848:       return tailMap(fromKey, true);
1849:     }
1850:     
1851:     public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive)
1852:     {
1853:       if (! keyInRange(fromKey))
1854:         throw new IllegalArgumentException("key outside range");
1855:       return new SubMap(inclusive ? fromKey : successor(getNode(fromKey)).key,
1856:             maxKey);
1857:     }
1858: 
1859:     public Collection<V> values()
1860:     {
1861:       if (this.values == null)
1862:         // Create an AbstractCollection with custom implementations of those
1863:         // methods that can be overriden easily and efficiently.
1864:         this.values = new AbstractCollection()
1865:         {
1866:           public int size()
1867:           {
1868:             return SubMap.this.size();
1869:           }
1870: 
1871:           public Iterator<V> iterator()
1872:           {
1873:             Node first = lowestGreaterThan(minKey, true);
1874:             Node max = lowestGreaterThan(maxKey, false);
1875:             return new TreeIterator(VALUES, first, max);
1876:           }
1877: 
1878:           public void clear()
1879:           {
1880:             SubMap.this.clear();
1881:           }
1882:         };
1883:       return this.values;
1884:     }
1885:     
1886:     private class KeySet
1887:       extends AbstractSet<K>
1888:     {
1889:       public int size()
1890:       {
1891:     return SubMap.this.size();
1892:       }
1893:       
1894:       public Iterator<K> iterator()
1895:       {
1896:     Node first = lowestGreaterThan(minKey, true);
1897:     Node max = lowestGreaterThan(maxKey, false);
1898:     return new TreeIterator(KEYS, first, max);
1899:       }
1900:       
1901:       public void clear()
1902:       {
1903:     SubMap.this.clear();
1904:       }
1905:       
1906:       public boolean contains(Object o)
1907:       {
1908:     if (! keyInRange((K) o))
1909:       return false;
1910:     return getNode((K) o) != nil;
1911:       }
1912:       
1913:       public boolean remove(Object o)
1914:       {
1915:     if (! keyInRange((K) o))
1916:       return false;
1917:     Node n = getNode((K) o);
1918:     if (n != nil)
1919:       {
1920:         removeNode(n);
1921:         return true;
1922:       }
1923:     return false;
1924:       }
1925:       
1926:     } // class SubMap.KeySet
1927: 
1928:     private final class NavigableKeySet
1929:       extends KeySet
1930:       implements NavigableSet<K>
1931:     {
1932: 
1933:       public K ceiling(K k)
1934:       {
1935:     return SubMap.this.ceilingKey(k);
1936:       }
1937:       
1938:       public Comparator<? super K> comparator()
1939:       {
1940:     return comparator;
1941:       }
1942:       
1943:       public Iterator<K> descendingIterator()
1944:       {
1945:     return descendingSet().iterator();
1946:       }
1947:       
1948:       public NavigableSet<K> descendingSet()
1949:       {
1950:     return new DescendingSet(this);
1951:       }
1952:       
1953:       public K first()
1954:       {
1955:     return SubMap.this.firstKey();
1956:       }
1957:       
1958:       public K floor(K k)
1959:       {
1960:     return SubMap.this.floorKey(k);
1961:       }
1962:       
1963:       public SortedSet<K> headSet(K to)
1964:       {
1965:     return headSet(to, false);
1966:       }
1967: 
1968:       public NavigableSet<K> headSet(K to, boolean inclusive)
1969:       {
1970:     return SubMap.this.headMap(to, inclusive).navigableKeySet();
1971:       }
1972: 
1973:       public K higher(K k)
1974:       {
1975:     return SubMap.this.higherKey(k);
1976:       }
1977: 
1978:       public K last()
1979:       {
1980:     return SubMap.this.lastKey();
1981:       }
1982: 
1983:       public K lower(K k)
1984:       {
1985:     return SubMap.this.lowerKey(k);
1986:       }
1987: 
1988:       public K pollFirst()
1989:       {
1990:     return SubMap.this.pollFirstEntry().getKey();
1991:       }
1992: 
1993:       public K pollLast()
1994:       {
1995:     return SubMap.this.pollLastEntry().getKey();
1996:       }
1997: 
1998:       public SortedSet<K> subSet(K from, K to)
1999:       {
2000:     return subSet(from, true, to, false);
2001:       }
2002:       
2003:       public NavigableSet<K> subSet(K from, boolean fromInclusive,
2004:                     K to, boolean toInclusive)
2005:       {
2006:     return SubMap.this.subMap(from, fromInclusive,
2007:                   to, toInclusive).navigableKeySet();
2008:       }
2009: 
2010:       public SortedSet<K> tailSet(K from)
2011:       {
2012:     return tailSet(from, true);
2013:       }
2014:       
2015:       public NavigableSet<K> tailSet(K from, boolean inclusive)
2016:       {
2017:     return SubMap.this.tailMap(from, inclusive).navigableKeySet();
2018:       }
2019:       
2020:   } // class SubMap.NavigableKeySet
2021: 
2022:   /**
2023:    * Implementation of {@link #entrySet()}.
2024:    */
2025:   private class EntrySet
2026:     extends AbstractSet<Entry<K,V>>
2027:   {
2028:     
2029:     public int size()
2030:     {
2031:       return SubMap.this.size();
2032:     }
2033:     
2034:     public Iterator<Map.Entry<K,V>> iterator()
2035:     {
2036:       Node first = lowestGreaterThan(minKey, true);
2037:       Node max = lowestGreaterThan(maxKey, false);
2038:       return new TreeIterator(ENTRIES, first, max);
2039:     }
2040:     
2041:     public void clear()
2042:     {
2043:       SubMap.this.clear();
2044:     }
2045:     
2046:     public boolean contains(Object o)
2047:     {
2048:       if (! (o instanceof Map.Entry))
2049:     return false;
2050:       Map.Entry<K,V> me = (Map.Entry<K,V>) o;
2051:       K key = me.getKey();
2052:       if (! keyInRange(key))
2053:     return false;
2054:       Node<K,V> n = getNode(key);
2055:       return n != nil && AbstractSet.equals(me.getValue(), n.value);
2056:     }
2057:     
2058:     public boolean remove(Object o)
2059:     {
2060:       if (! (o instanceof Map.Entry))
2061:     return false;
2062:       Map.Entry<K,V> me = (Map.Entry<K,V>) o;
2063:       K key = me.getKey();
2064:       if (! keyInRange(key))
2065:     return false;
2066:       Node<K,V> n = getNode(key);
2067:       if (n != nil && AbstractSet.equals(me.getValue(), n.value))
2068:     {
2069:       removeNode(n);
2070:       return true;
2071:     }
2072:       return false;
2073:     }
2074:   } // class SubMap.EntrySet
2075:     
2076:     private final class NavigableEntrySet
2077:       extends EntrySet
2078:       implements NavigableSet<Entry<K,V>>
2079:     {
2080: 
2081:       public Entry<K,V> ceiling(Entry<K,V> e)
2082:       {
2083:     return SubMap.this.ceilingEntry(e.getKey());
2084:       }
2085:       
2086:       public Comparator<? super Entry<K,V>> comparator()
2087:       {
2088:     return new Comparator<Entry<K,V>>()
2089:       {
2090:         public int compare(Entry<K,V> t1, Entry<K,V> t2)
2091:           {
2092:         return comparator.compare(t1.getKey(), t2.getKey());
2093:           }
2094:       };
2095:       }
2096:       
2097:       public Iterator<Entry<K,V>> descendingIterator()
2098:       {
2099:     return descendingSet().iterator();
2100:       }
2101:       
2102:       public NavigableSet<Entry<K,V>> descendingSet()
2103:       {
2104:     return new DescendingSet(this);
2105:       }
2106:       
2107:       public Entry<K,V> first()
2108:       {
2109:     return SubMap.this.firstEntry();
2110:       }
2111:       
2112:       public Entry<K,V> floor(Entry<K,V> e)
2113:       {
2114:     return SubMap.this.floorEntry(e.getKey());
2115:       }
2116:       
2117:       public SortedSet<Entry<K,V>> headSet(Entry<K,V> to)
2118:       {
2119:     return headSet(to, false);
2120:       }
2121: 
2122:       public NavigableSet<Entry<K,V>> headSet(Entry<K,V> to, boolean inclusive)
2123:       {
2124:     return (NavigableSet<Entry<K,V>>)
2125:       SubMap.this.headMap(to.getKey(), inclusive).entrySet();
2126:       }
2127: 
2128:       public Entry<K,V> higher(Entry<K,V> e)
2129:       {
2130:     return SubMap.this.higherEntry(e.getKey());
2131:       }
2132: 
2133:       public Entry<K,V> last()
2134:       {
2135:     return SubMap.this.lastEntry();
2136:       }
2137: 
2138:       public Entry<K,V> lower(Entry<K,V> e)
2139:       {
2140:     return SubMap.this.lowerEntry(e.getKey());
2141:       }
2142: 
2143:       public Entry<K,V> pollFirst()
2144:       {
2145:     return SubMap.this.pollFirstEntry();
2146:       }
2147: 
2148:       public Entry<K,V> pollLast()
2149:       {
2150:     return SubMap.this.pollLastEntry();
2151:       }
2152: 
2153:       public SortedSet<Entry<K,V>> subSet(Entry<K,V> from, Entry<K,V> to)
2154:       {
2155:     return subSet(from, true, to, false);
2156:       }
2157:       
2158:       public NavigableSet<Entry<K,V>> subSet(Entry<K,V> from, boolean fromInclusive,
2159:                          Entry<K,V> to, boolean toInclusive)
2160:       {
2161:     return (NavigableSet<Entry<K,V>>)
2162:       SubMap.this.subMap(from.getKey(), fromInclusive,
2163:                  to.getKey(), toInclusive).entrySet();
2164:       }
2165: 
2166:       public SortedSet<Entry<K,V>> tailSet(Entry<K,V> from)
2167:       {
2168:     return tailSet(from, true);
2169:       }
2170:       
2171:       public NavigableSet<Entry<K,V>> tailSet(Entry<K,V> from, boolean inclusive)
2172:       {
2173:     return (NavigableSet<Entry<K,V>>)
2174:       SubMap.this.tailMap(from.getKey(), inclusive).navigableKeySet();
2175:       }
2176:       
2177:   } // class SubMap.NavigableEntrySet
2178: 
2179: } // class SubMap  
2180: 
2181:   /**
2182:    * Returns the entry associated with the least or lowest key
2183:    * that is greater than or equal to the specified key, or
2184:    * <code>null</code> if there is no such key.
2185:    *
2186:    * @param key the key relative to the returned entry.
2187:    * @return the entry with the least key greater than or equal
2188:    *         to the given key, or <code>null</code> if there is
2189:    *         no such key.
2190:    * @throws ClassCastException if the specified key can not
2191:    *                            be compared with those in the map.
2192:    * @throws NullPointerException if the key is <code>null</code>
2193:    *                              and this map either uses natural
2194:    *                              ordering or a comparator that does
2195:    *                              not permit null keys.
2196:    * @since 1.6
2197:    */
2198:   public Entry<K,V> ceilingEntry(K key)
2199:   {
2200:     Node<K,V> n = lowestGreaterThan(key, false);
2201:     return (n == nil) ? null : n;
2202:   }
2203: 
2204:   /**
2205:    * Returns the the least or lowest key that is greater than
2206:    * or equal to the specified key, or <code>null</code> if
2207:    * there is no such key.
2208:    *
2209:    * @param key the key relative to the returned entry.
2210:    * @return the least key greater than or equal to the given key,
2211:    *         or <code>null</code> if there is no such key.
2212:    * @throws ClassCastException if the specified key can not
2213:    *                            be compared with those in the map.
2214:    * @throws NullPointerException if the key is <code>null</code>
2215:    *                              and this map either uses natural
2216:    *                              ordering or a comparator that does
2217:    *                              not permit null keys.
2218:    * @since 1.6
2219:    */
2220:   public K ceilingKey(K key)
2221:   {
2222:     Entry<K,V> e = ceilingEntry(key);
2223:     return (e == null) ? null : e.getKey();
2224:   }
2225: 
2226:   /**
2227:    * Returns a reverse ordered {@link NavigableSet} view of this
2228:    * map's keys. The set is backed by the {@link TreeMap}, so changes
2229:    * in one show up in the other.  The set supports element removal,
2230:    * but not element addition.
2231:    *
2232:    * @return a reverse ordered set view of the keys.
2233:    * @since 1.6
2234:    * @see #descendingMap()
2235:    */
2236:   public NavigableSet<K> descendingKeySet()
2237:   {
2238:     return descendingMap().navigableKeySet();
2239:   }
2240: 
2241:   /**
2242:    * Returns a view of the map in reverse order.  The descending map
2243:    * is backed by the original map, so that changes affect both maps.
2244:    * Any changes occurring to either map while an iteration is taking
2245:    * place (with the exception of a {@link Iterator#remove()} operation)
2246:    * result in undefined behaviour from the iteration.  The ordering
2247:    * of the descending map is the same as for a map with a
2248:    * {@link Comparator} given by {@link Collections#reverseOrder()},
2249:    * and calling {@link #descendingMap()} on the descending map itself
2250:    * results in a view equivalent to the original map.
2251:    *
2252:    * @return a reverse order view of the map.
2253:    * @since 1.6
2254:    */
2255:   public NavigableMap<K,V> descendingMap()
2256:   {
2257:     if (descendingMap == null)
2258:       descendingMap = new DescendingMap<K,V>(this);
2259:     return descendingMap;
2260:   }
2261: 
2262:   /**
2263:    * Returns the entry associated with the least or lowest key
2264:    * in the map, or <code>null</code> if the map is empty.
2265:    *
2266:    * @return the lowest entry, or <code>null</code> if the map
2267:    *         is empty.
2268:    * @since 1.6
2269:    */
2270:   public Entry<K,V> firstEntry()
2271:   {
2272:     Node<K,V> n = firstNode();
2273:     return (n == nil) ? null : n;
2274:   }
2275: 
2276:   /**
2277:    * Returns the entry associated with the greatest or highest key
2278:    * that is less than or equal to the specified key, or
2279:    * <code>null</code> if there is no such key.
2280:    *
2281:    * @param key the key relative to the returned entry.
2282:    * @return the entry with the greatest key less than or equal
2283:    *         to the given key, or <code>null</code> if there is
2284:    *         no such key.
2285:    * @throws ClassCastException if the specified key can not
2286:    *                            be compared with those in the map.
2287:    * @throws NullPointerException if the key is <code>null</code>
2288:    *                              and this map either uses natural
2289:    *                              ordering or a comparator that does
2290:    *                              not permit null keys.
2291:    * @since 1.6
2292:    */
2293:   public Entry<K,V> floorEntry(K key)
2294:   {
2295:     Node<K,V> n = highestLessThan(key, true);
2296:     return (n == nil) ? null : n;
2297:   }
2298: 
2299:   /**
2300:    * Returns the the greatest or highest key that is less than
2301:    * or equal to the specified key, or <code>null</code> if
2302:    * there is no such key.
2303:    *
2304:    * @param key the key relative to the returned entry.
2305:    * @return the greatest key less than or equal to the given key,
2306:    *         or <code>null</code> if there is no such key.
2307:    * @throws ClassCastException if the specified key can not
2308:    *                            be compared with those in the map.
2309:    * @throws NullPointerException if the key is <code>null</code>
2310:    *                              and this map either uses natural
2311:    *                              ordering or a comparator that does
2312:    *                              not permit null keys.
2313:    * @since 1.6
2314:    */
2315:   public K floorKey(K key)
2316:   {
2317:     Entry<K,V> e = floorEntry(key);
2318:     return (e == null) ? null : e.getKey();
2319:   }
2320: 
2321:   /**
2322:    * Returns the entry associated with the least or lowest key
2323:    * that is strictly greater than the specified key, or
2324:    * <code>null</code> if there is no such key.
2325:    *
2326:    * @param key the key relative to the returned entry.
2327:    * @return the entry with the least key greater than 
2328:    *         the given key, or <code>null</code> if there is
2329:    *         no such key.
2330:    * @throws ClassCastException if the specified key can not
2331:    *                            be compared with those in the map.
2332:    * @throws NullPointerException if the key is <code>null</code>
2333:    *                              and this map either uses natural
2334:    *                              ordering or a comparator that does
2335:    *                              not permit null keys.
2336:    * @since 1.6
2337:    */
2338:   public Entry<K,V> higherEntry(K key)
2339:   {
2340:     Node<K,V> n = lowestGreaterThan(key, false, false);
2341:     return (n == nil) ? null : n;
2342:   }
2343: 
2344:   /**
2345:    * Returns the the least or lowest key that is strictly
2346:    * greater than the specified key, or <code>null</code> if
2347:    * there is no such key.
2348:    *
2349:    * @param key the key relative to the returned entry.
2350:    * @return the least key greater than the given key,
2351:    *         or <code>null</code> if there is no such key.
2352:    * @throws ClassCastException if the specified key can not
2353:    *                            be compared with those in the map.
2354:    * @throws NullPointerException if the key is <code>null</code>
2355:    *                              and this map either uses natural
2356:    *                              ordering or a comparator that does
2357:    *                              not permit null keys.
2358:    * @since 1.6
2359:    */
2360:   public K higherKey(K key)
2361:   {
2362:     Entry<K,V> e = higherEntry(key);
2363:     return (e == null) ? null : e.getKey();
2364:   }
2365: 
2366:   /**
2367:    * Returns the entry associated with the greatest or highest key
2368:    * in the map, or <code>null</code> if the map is empty.
2369:    *
2370:    * @return the highest entry, or <code>null</code> if the map
2371:    *         is empty.
2372:    * @since 1.6
2373:    */
2374:   public Entry<K,V> lastEntry()
2375:   {
2376:     Node<K,V> n = lastNode();
2377:     return (n == nil) ? null : n;
2378:   }
2379: 
2380:   /**
2381:    * Returns the entry associated with the greatest or highest key
2382:    * that is strictly less than the specified key, or
2383:    * <code>null</code> if there is no such key.
2384:    *
2385:    * @param key the key relative to the returned entry.
2386:    * @return the entry with the greatest key less than 
2387:    *         the given key, or <code>null</code> if there is
2388:    *         no such key.
2389:    * @throws ClassCastException if the specified key can not
2390:    *                            be compared with those in the map.
2391:    * @throws NullPointerException if the key is <code>null</code>
2392:    *                              and this map either uses natural
2393:    *                              ordering or a comparator that does
2394:    *                              not permit null keys.
2395:    * @since 1.6
2396:    */
2397:   public Entry<K,V> lowerEntry(K key)
2398:   {
2399:     Node<K,V> n = highestLessThan(key);
2400:     return (n == nil) ? null : n;
2401:   }
2402: 
2403:   /**
2404:    * Returns the the greatest or highest key that is strictly
2405:    * less than the specified key, or <code>null</code> if
2406:    * there is no such key.
2407:    *
2408:    * @param key the key relative to the returned entry.
2409:    * @return the greatest key less than the given key,
2410:    *         or <code>null</code> if there is no such key.
2411:    * @throws ClassCastException if the specified key can not
2412:    *                            be compared with those in the map.
2413:    * @throws NullPointerException if the key is <code>null</code>
2414:    *                              and this map either uses natural
2415:    *                              ordering or a comparator that does
2416:    *                              not permit null keys.
2417:    * @since 1.6
2418:    */
2419:   public K lowerKey(K key)
2420:   {
2421:     Entry<K,V> e = lowerEntry(key);
2422:     return (e == null) ? null : e.getKey();
2423:   }
2424: 
2425:   /**
2426:    * Returns a {@link NavigableSet} view of this map's keys. The set is
2427:    * backed by the {@link TreeMap}, so changes in one show up in the other.
2428:    * Any changes occurring to either while an iteration is taking
2429:    * place (with the exception of a {@link Iterator#remove()} operation)
2430:    * result in undefined behaviour from the iteration.  The ordering
2431:    * The set supports element removal, but not element addition.
2432:    *
2433:    * @return a {@link NavigableSet} view of the keys.
2434:    * @since 1.6
2435:    */
2436:   public NavigableSet<K> navigableKeySet()
2437:   {
2438:     if (nKeys == null)
2439:       nKeys = new NavigableKeySet();
2440:     return nKeys;
2441:   }
2442: 
2443:   /**
2444:    * Removes and returns the entry associated with the least
2445:    * or lowest key in the map, or <code>null</code> if the map
2446:    * is empty.
2447:    *
2448:    * @return the removed first entry, or <code>null</code> if the
2449:    *         map is empty.
2450:    * @since 1.6
2451:    */
2452:   public Entry<K,V> pollFirstEntry()
2453:   {
2454:     Entry<K,V> e = firstEntry();
2455:     if (e != null)
2456:       removeNode((Node<K,V>)e);
2457:     return e;
2458:   }
2459: 
2460:   /**
2461:    * Removes and returns the entry associated with the greatest
2462:    * or highest key in the map, or <code>null</code> if the map
2463:    * is empty.
2464:    *
2465:    * @return the removed last entry, or <code>null</code> if the
2466:    *         map is empty.
2467:    * @since 1.6
2468:    */
2469:   public Entry<K,V> pollLastEntry()
2470:   {
2471:     Entry<K,V> e = lastEntry();
2472:     if (e != null)
2473:       removeNode((Node<K,V>)e);
2474:     return e;    
2475:   }
2476: 
2477:   /**
2478:    * Implementation of {@link #descendingMap()} and associated
2479:    * derivatives. This class provides a view of the
2480:    * original backing map in reverse order, and throws
2481:    * {@link IllegalArgumentException} for attempts to
2482:    * access beyond that range.
2483:    *
2484:    * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
2485:    */
2486:   private static final class DescendingMap<DK,DV>
2487:     implements NavigableMap<DK,DV>
2488:   {
2489: 
2490:     /**
2491:      * The cache for {@link #entrySet()}.
2492:      */
2493:     private Set<Map.Entry<DK,DV>> entries;
2494: 
2495:     /**
2496:      * The cache for {@link #keySet()}.
2497:      */
2498:     private Set<DK> keys;
2499: 
2500:     /**
2501:      * The cache for {@link #navigableKeySet()}.
2502:      */
2503:     private NavigableSet<DK> nKeys;
2504: 
2505:     /**
2506:      * The cache for {@link #values()}.
2507:      */
2508:     private Collection<DV> values;
2509: 
2510:     /**
2511:      * The backing {@link NavigableMap}.
2512:      */
2513:     private NavigableMap<DK,DV> map;
2514: 
2515:     /**
2516:      * Create a {@link DescendingMap} around the specified
2517:      * map.
2518:      *
2519:      * @param map the map to wrap.
2520:      */
2521:     public DescendingMap(NavigableMap<DK,DV> map)
2522:     {
2523:       this.map = map;
2524:     }
2525:       
2526:     public Map.Entry<DK,DV> ceilingEntry(DK key)
2527:     {
2528:       return map.floorEntry(key);
2529:     }
2530: 
2531:     public DK ceilingKey(DK key)
2532:     {
2533:       return map.floorKey(key);
2534:     }
2535: 
2536:     public void clear()
2537:     {
2538:       map.clear();
2539:     }
2540: 
2541:     public Comparator<? super DK> comparator()
2542:     {
2543:       return Collections.reverseOrder(map.comparator());
2544:     }
2545: 
2546:     public boolean containsKey(Object o)
2547:     {
2548:       return map.containsKey(o);
2549:     }
2550:     
2551:     public boolean containsValue(Object o)
2552:     {
2553:       return map.containsValue(o);
2554:     }
2555: 
2556:     public NavigableSet<DK> descendingKeySet()
2557:     {
2558:       return descendingMap().navigableKeySet();
2559:     }
2560: 
2561:     public NavigableMap<DK,DV> descendingMap()
2562:     {
2563:       return map;
2564:     }
2565: 
2566:     public Set<Entry<DK,DV>> entrySet()
2567:     {
2568:       if (entries == null)
2569:     entries =
2570:       new DescendingSet<Entry<DK,DV>>((NavigableSet<Entry<DK,DV>>)
2571:                       map.entrySet());
2572:       return entries;
2573:     }
2574: 
2575:     public boolean equals(Object o)
2576:     {
2577:       return map.equals(o);
2578:     }
2579: 
2580:     public Entry<DK,DV> firstEntry()
2581:     {
2582:       return map.lastEntry();
2583:     }
2584: 
2585:     public DK firstKey()
2586:     {
2587:       return map.lastKey();
2588:     }
2589: 
2590:     public Entry<DK,DV> floorEntry(DK key)
2591:     {
2592:       return map.ceilingEntry(key);
2593:     }
2594: 
2595:     public DK floorKey(DK key)
2596:     {
2597:       return map.ceilingKey(key);
2598:     }
2599: 
2600:     public DV get(Object key)
2601:     {
2602:       return map.get(key);
2603:     }
2604: 
2605:     public int hashCode()
2606:     {
2607:       return map.hashCode();
2608:     }
2609: 
2610:     public SortedMap<DK,DV> headMap(DK toKey)
2611:     {
2612:       return headMap(toKey, false);
2613:     }
2614: 
2615:     public NavigableMap<DK,DV> headMap(DK toKey, boolean inclusive)
2616:     {
2617:       return new DescendingMap(map.tailMap(toKey, inclusive));
2618:     }
2619: 
2620:     public Entry<DK,DV> higherEntry(DK key)
2621:     {
2622:       return map.lowerEntry(key);
2623:     }
2624: 
2625:     public DK higherKey(DK key)
2626:     {
2627:       return map.lowerKey(key);
2628:     }
2629: 
2630:     public Set<DK> keySet()
2631:     {
2632:       if (keys == null)
2633:     keys = new DescendingSet<DK>(map.navigableKeySet());
2634:       return keys;
2635:     }
2636: 
2637:     public boolean isEmpty()
2638:     {
2639:       return map.isEmpty();
2640:     }
2641: 
2642:     public Entry<DK,DV> lastEntry()
2643:     {
2644:       return map.firstEntry();
2645:     }
2646: 
2647:     public DK lastKey()
2648:     {
2649:       return map.firstKey();
2650:     }
2651: 
2652:     public Entry<DK,DV> lowerEntry(DK key)
2653:     {
2654:       return map.higherEntry(key);
2655:     }
2656: 
2657:     public DK lowerKey(DK key)
2658:     {
2659:       return map.higherKey(key);
2660:     }
2661: 
2662:     public NavigableSet<DK> navigableKeySet()
2663:     {
2664:       if (nKeys == null)
2665:     nKeys = new DescendingSet<DK>(map.navigableKeySet());
2666:       return nKeys;
2667:     }
2668: 
2669:     public Entry<DK,DV> pollFirstEntry()
2670:     {
2671:       return pollLastEntry();
2672:     }
2673: 
2674:     public Entry<DK,DV> pollLastEntry()
2675:     {
2676:       return pollFirstEntry();
2677:     }
2678: 
2679:     public DV put(DK key, DV value)
2680:     {
2681:       return map.put(key, value);
2682:     }
2683: 
2684:     public void putAll(Map<? extends DK, ? extends DV> m)
2685:     {
2686:       map.putAll(m);
2687:     }
2688: 
2689:     public DV remove(Object key)
2690:     {
2691:       return map.remove(key);
2692:     }
2693: 
2694:     public int size()
2695:     {
2696:       return map.size();
2697:     }
2698: 
2699:     public SortedMap<DK,DV> subMap(DK fromKey, DK toKey)
2700:     {
2701:       return subMap(fromKey, true, toKey, false);
2702:     }
2703: 
2704:     public NavigableMap<DK,DV> subMap(DK fromKey, boolean fromInclusive,
2705:                       DK toKey, boolean toInclusive)
2706:     {
2707:       return new DescendingMap(map.subMap(fromKey, fromInclusive,
2708:                       toKey, toInclusive));
2709:     }
2710: 
2711:     public SortedMap<DK,DV> tailMap(DK fromKey)
2712:     {
2713:       return tailMap(fromKey, true);
2714:     }
2715: 
2716:     public NavigableMap<DK,DV> tailMap(DK fromKey, boolean inclusive)
2717:     {
2718:       return new DescendingMap(map.headMap(fromKey, inclusive));
2719:     }
2720: 
2721:     public String toString()
2722:     {
2723:       StringBuilder r = new StringBuilder("{");
2724:       final Iterator<Entry<DK,DV>> it = entrySet().iterator();
2725:       while (it.hasNext())
2726:       {
2727:     final Entry<DK,DV> e = it.next();
2728:         r.append(e.getKey());
2729:         r.append('=');
2730:         r.append(e.getValue());
2731:     r.append(", ");
2732:       }
2733:       r.replace(r.length() - 2, r.length(), "}");
2734:       return r.toString();
2735:     }
2736: 
2737:     public Collection<DV> values()
2738:     {
2739:       if (values == null)
2740:         // Create an AbstractCollection with custom implementations of those
2741:         // methods that can be overriden easily and efficiently.
2742:         values = new AbstractCollection()
2743:       {
2744:         public int size()
2745:         {
2746:           return size();
2747:         }
2748:         
2749:         public Iterator<DV> iterator()
2750:         {
2751:           return new Iterator<DV>()
2752:         {      
2753:           /** The last Entry returned by a next() call. */
2754:           private Entry<DK,DV> last;
2755:           
2756:           /** The next entry that should be returned by next(). */
2757:           private Entry<DK,DV> next = firstEntry();
2758:           
2759:           public boolean hasNext()
2760:           {
2761:             return next != null;
2762:           }
2763: 
2764:           public DV next()
2765:           {
2766:             if (next == null)
2767:               throw new NoSuchElementException();
2768:             last = next;
2769:             next = higherEntry(last.getKey());
2770:             
2771:             return last.getValue();
2772:           }
2773: 
2774:           public void remove()
2775:           {
2776:             if (last == null)
2777:               throw new IllegalStateException();
2778:             
2779:             DescendingMap.this.remove(last.getKey());
2780:             last = null;
2781:           }
2782:         };
2783:         }
2784:         
2785:         public void clear()
2786:         {
2787:           clear();
2788:         }
2789:       };
2790:       return values;
2791:     }
2792: 
2793:   } // class DescendingMap
2794: 
2795:   /**
2796:    * Implementation of {@link #keySet()}.
2797:    */
2798:   private class KeySet
2799:     extends AbstractSet<K>
2800:   {
2801: 
2802:     public int size()
2803:     {
2804:       return size;
2805:     }
2806: 
2807:     public Iterator<K> iterator()
2808:     {
2809:       return new TreeIterator(KEYS);
2810:     }
2811: 
2812:     public void clear()
2813:     {
2814:       TreeMap.this.clear();
2815:     }
2816:     
2817:     public boolean contains(Object o)
2818:     {
2819:       return containsKey(o);
2820:     }
2821:     
2822:     public boolean remove(Object key)
2823:     {
2824:       Node<K,V> n = getNode((K) key);
2825:       if (n == nil)
2826:     return false;
2827:       removeNode(n);
2828:       return true;
2829:     }
2830:   } // class KeySet
2831: 
2832:   /**
2833:    * Implementation of {@link #navigableKeySet()}.
2834:    *
2835:    * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
2836:    */
2837:   private final class NavigableKeySet
2838:     extends KeySet
2839:     implements NavigableSet<K>
2840:   {
2841: 
2842:     public K ceiling(K k)
2843:     {
2844:       return ceilingKey(k);
2845:     }
2846: 
2847:     public Comparator<? super K> comparator()
2848:     {
2849:       return comparator;
2850:     }
2851: 
2852:     public Iterator<K> descendingIterator()
2853:     {
2854:       return descendingSet().iterator();
2855:     }
2856: 
2857:     public NavigableSet<K> descendingSet()
2858:     {
2859:       return new DescendingSet<K>(this);
2860:     }
2861: 
2862:     public K first()
2863:     {
2864:       return firstKey();
2865:     }
2866: 
2867:     public K floor(K k)
2868:     {
2869:       return floorKey(k);
2870:     }
2871: 
2872:     public SortedSet<K> headSet(K to)
2873:     {
2874:       return headSet(to, false);
2875:     }
2876: 
2877:     public NavigableSet<K> headSet(K to, boolean inclusive)
2878:     {
2879:       return headMap(to, inclusive).navigableKeySet();
2880:     }
2881: 
2882:     public K higher(K k)
2883:     {
2884:       return higherKey(k);
2885:     }
2886: 
2887:     public K last()
2888:     {
2889:       return lastKey();
2890:     }
2891: 
2892:     public K lower(K k)
2893:     {
2894:       return lowerKey(k);
2895:     }
2896: 
2897:     public K pollFirst()
2898:     {
2899:       return pollFirstEntry().getKey();
2900:     }
2901: 
2902:     public K pollLast()
2903:     {
2904:       return pollLastEntry().getKey();
2905:     }
2906: 
2907:     public SortedSet<K> subSet(K from, K to)
2908:     {
2909:       return subSet(from, true, to, false);
2910:     }
2911: 
2912:     public NavigableSet<K> subSet(K from, boolean fromInclusive,
2913:                   K to, boolean toInclusive)
2914:     {
2915:       return subMap(from, fromInclusive,
2916:             to, toInclusive).navigableKeySet();
2917:     }
2918: 
2919:     public SortedSet<K> tailSet(K from)
2920:     {
2921:       return tailSet(from, true);
2922:     }
2923: 
2924:     public NavigableSet<K> tailSet(K from, boolean inclusive)
2925:     {
2926:       return tailMap(from, inclusive).navigableKeySet();
2927:     }
2928: 
2929: 
2930:   } // class NavigableKeySet
2931: 
2932:   /**
2933:    * Implementation of {@link #descendingSet()} and associated
2934:    * derivatives. This class provides a view of the
2935:    * original backing set in reverse order, and throws
2936:    * {@link IllegalArgumentException} for attempts to
2937:    * access beyond that range.
2938:    *
2939:    * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
2940:    */
2941:   private static final class DescendingSet<D>
2942:     implements NavigableSet<D>
2943:   {
2944: 
2945:     /**
2946:      * The backing {@link NavigableSet}.
2947:      */
2948:     private NavigableSet<D> set;
2949: 
2950:     /**
2951:      * Create a {@link DescendingSet} around the specified
2952:      * set.
2953:      *
2954:      * @param map the set to wrap.
2955:      */
2956:     public DescendingSet(NavigableSet<D> set)
2957:     {
2958:       this.set = set;
2959:     }
2960:     
2961:     public boolean add(D e)
2962:     {
2963:       return set.add(e);
2964:     }
2965: 
2966:     public boolean addAll(Collection<? extends D> c)
2967:     {
2968:       return set.addAll(c);
2969:     }
2970: 
2971:     public D ceiling(D e)
2972:     {
2973:       return set.floor(e);
2974:     }
2975: 
2976:     public void clear()
2977:     {
2978:       set.clear();
2979:     }
2980: 
2981:     public Comparator<? super D> comparator()
2982:     {
2983:       return Collections.reverseOrder(set.comparator());
2984:     }
2985: 
2986:     public boolean contains(Object o)
2987:     {
2988:       return set.contains(o);
2989:     }
2990: 
2991:     public boolean containsAll(Collection<?> c)
2992:     {
2993:       return set.containsAll(c);
2994:     }
2995: 
2996:     public Iterator<D> descendingIterator()
2997:     {
2998:       return descendingSet().iterator();
2999:     }
3000: 
3001:     public NavigableSet<D> descendingSet()
3002:     {
3003:       return set;
3004:     }
3005: 
3006:     public boolean equals(Object o)
3007:     {
3008:       return set.equals(o);
3009:     }
3010: 
3011:     public D first()
3012:     {
3013:       return set.last();
3014:     }
3015: 
3016:     public D floor(D e)
3017:     {
3018:       return set.ceiling(e);
3019:     }
3020: 
3021:     public int hashCode()
3022:     {
3023:       return set.hashCode();
3024:     }
3025: 
3026:     public SortedSet<D> headSet(D to)
3027:     {
3028:       return headSet(to, false);
3029:     }
3030: 
3031:     public NavigableSet<D> headSet(D to, boolean inclusive)
3032:     {
3033:       return new DescendingSet(set.tailSet(to, inclusive));
3034:     }
3035: 
3036:     public D higher(D e)
3037:     {
3038:       return set.lower(e);
3039:     }
3040: 
3041:     public boolean isEmpty()
3042:     {
3043:       return set.isEmpty();
3044:     }
3045: 
3046:     public Iterator<D> iterator()
3047:     {
3048:       return new Iterator<D>()
3049:     {
3050:             
3051:       /** The last element returned by a next() call. */
3052:       private D last;
3053:           
3054:       /** The next element that should be returned by next(). */
3055:       private D next = first();
3056:           
3057:       public boolean hasNext()
3058:       {
3059:         return next != null;
3060:       }
3061: 
3062:       public D next()
3063:       {
3064:         if (next == null)
3065:           throw new NoSuchElementException();
3066:         last = next;
3067:         next = higher(last);
3068:             
3069:         return last;
3070:       }
3071: 
3072:       public void remove()
3073:       {
3074:         if (last == null)
3075:           throw new IllegalStateException();
3076:         
3077:         DescendingSet.this.remove(last);
3078:         last = null;
3079:       }
3080:     };
3081:     }
3082: 
3083:     public D last()
3084:     {
3085:       return set.first();
3086:     }
3087: 
3088:     public D lower(D e)
3089:     {
3090:       return set.higher(e);
3091:     }
3092: 
3093:     public D pollFirst()
3094:     {
3095:       return set.pollLast();
3096:     }
3097: 
3098:     public D pollLast()
3099:     {
3100:       return set.pollFirst();
3101:     }
3102: 
3103:     public boolean remove(Object o)
3104:     {
3105:       return set.remove(o);
3106:     }
3107: 
3108:     public boolean removeAll(Collection<?> c)
3109:     {
3110:       return set.removeAll(c);
3111:     }
3112: 
3113:     public boolean retainAll(Collection<?> c)
3114:     {
3115:       return set.retainAll(c);
3116:     }
3117: 
3118:     public int size()
3119:     {
3120:       return set.size();
3121:     }
3122: 
3123:     public SortedSet<D> subSet(D from, D to)
3124:     {
3125:       return subSet(from, true, to, false);
3126:     }
3127: 
3128:     public NavigableSet<D> subSet(D from, boolean fromInclusive,
3129:                   D to, boolean toInclusive)
3130:     {
3131:       return new DescendingSet(set.subSet(from, fromInclusive,
3132:                       to, toInclusive));
3133:     }
3134: 
3135:     public SortedSet<D> tailSet(D from)
3136:     {
3137:       return tailSet(from, true);
3138:     }
3139: 
3140:     public NavigableSet<D> tailSet(D from, boolean inclusive)
3141:     {
3142:       return new DescendingSet(set.headSet(from, inclusive));
3143:     }
3144: 
3145:     public Object[] toArray()
3146:     {
3147:       D[] array = (D[]) set.toArray();
3148:       Arrays.sort(array, comparator());
3149:       return array;
3150:     }
3151: 
3152:     public <T> T[] toArray(T[] a)
3153:     {
3154:       T[] array = set.toArray(a);
3155:       Arrays.sort(array, (Comparator<? super T>) comparator());
3156:       return array;
3157:     }
3158: 
3159:     public String toString()
3160:     {
3161:       StringBuilder r = new StringBuilder("[");
3162:       final Iterator<D> it = iterator();
3163:       while (it.hasNext())
3164:       {
3165:     final D o = it.next();
3166:     if (o == this)
3167:       r.append("<this>");
3168:     else
3169:       r.append(o);
3170:     r.append(", ");
3171:       }
3172:       r.replace(r.length() - 2, r.length(), "]");
3173:       return r.toString();
3174:     }
3175: 
3176:   } // class DescendingSet
3177: 
3178:   private class EntrySet
3179:     extends AbstractSet<Entry<K,V>>
3180:   {
3181:     public int size()
3182:     {
3183:       return size;
3184:     }
3185:     
3186:     public Iterator<Map.Entry<K,V>> iterator()
3187:     {
3188:       return new TreeIterator(ENTRIES);
3189:     }
3190:     
3191:     public void clear()
3192:     {
3193:       TreeMap.this.clear();
3194:     }
3195: 
3196:     public boolean contains(Object o)
3197:     {
3198:       if (! (o instanceof Map.Entry))
3199:     return false;
3200:       Map.Entry<K,V> me = (Map.Entry<K,V>) o;
3201:       Node<K,V> n = getNode(me.getKey());
3202:       return n != nil && AbstractSet.equals(me.getValue(), n.value);
3203:     }
3204:     
3205:     public boolean remove(Object o)
3206:     {
3207:       if (! (o instanceof Map.Entry))
3208:     return false;
3209:       Map.Entry<K,V> me = (Map.Entry<K,V>) o;
3210:       Node<K,V> n = getNode(me.getKey());
3211:       if (n != nil && AbstractSet.equals(me.getValue(), n.value))
3212:     {
3213:       removeNode(n);
3214:       return true;
3215:     }
3216:       return false;
3217:     }
3218:   }
3219:   
3220:   private final class NavigableEntrySet
3221:     extends EntrySet
3222:     implements NavigableSet<Entry<K,V>>
3223:   {
3224:     
3225:     public Entry<K,V> ceiling(Entry<K,V> e)
3226:     {
3227:       return ceilingEntry(e.getKey());
3228:     }
3229:       
3230:     public Comparator<? super Entry<K,V>> comparator()
3231:     {
3232:       return new Comparator<Entry<K,V>>()
3233:     {
3234:       public int compare(Entry<K,V> t1, Entry<K,V> t2)
3235:       {
3236:         return comparator.compare(t1.getKey(), t2.getKey());
3237:       }
3238:     };
3239:     }
3240:     
3241:     public Iterator<Entry<K,V>> descendingIterator()
3242:     {
3243:       return descendingSet().iterator();
3244:     }
3245:     
3246:     public NavigableSet<Entry<K,V>> descendingSet()
3247:     {
3248:       return new DescendingSet(this);
3249:     }
3250:     
3251:     public Entry<K,V> first()
3252:     {
3253:       return firstEntry();
3254:     }
3255:       
3256:     public Entry<K,V> floor(Entry<K,V> e)
3257:     {
3258:       return floorEntry(e.getKey());
3259:     }
3260:       
3261:     public SortedSet<Entry<K,V>> headSet(Entry<K,V> to)
3262:     {
3263:       return headSet(to, false);
3264:     }
3265: 
3266:     public NavigableSet<Entry<K,V>> headSet(Entry<K,V> to, boolean inclusive)
3267:     {
3268:       return (NavigableSet<Entry<K,V>>) headMap(to.getKey(), inclusive).entrySet();
3269:     }
3270:     
3271:     public Entry<K,V> higher(Entry<K,V> e)
3272:     {
3273:       return higherEntry(e.getKey());
3274:     }
3275: 
3276:     public Entry<K,V> last()
3277:     {
3278:       return lastEntry();
3279:     }
3280: 
3281:     public Entry<K,V> lower(Entry<K,V> e)
3282:     {
3283:       return lowerEntry(e.getKey());
3284:     }
3285: 
3286:     public Entry<K,V> pollFirst()
3287:     {
3288:       return pollFirstEntry();
3289:     }
3290: 
3291:     public Entry<K,V> pollLast()
3292:     {
3293:       return pollLastEntry();
3294:     }
3295: 
3296:     public SortedSet<Entry<K,V>> subSet(Entry<K,V> from, Entry<K,V> to)
3297:     {
3298:       return subSet(from, true, to, false);
3299:     }
3300:     
3301:     public NavigableSet<Entry<K,V>> subSet(Entry<K,V> from, boolean fromInclusive,
3302:                        Entry<K,V> to, boolean toInclusive)
3303:     {
3304:       return (NavigableSet<Entry<K,V>>) subMap(from.getKey(), fromInclusive,
3305:                            to.getKey(), toInclusive).entrySet();
3306:     }
3307: 
3308:     public SortedSet<Entry<K,V>> tailSet(Entry<K,V> from)
3309:     {
3310:       return tailSet(from, true);
3311:     }
3312:     
3313:     public NavigableSet<Entry<K,V>> tailSet(Entry<K,V> from, boolean inclusive)
3314:     {
3315:       return (NavigableSet<Entry<K,V>>) tailMap(from.getKey(), inclusive).navigableKeySet();
3316:     }
3317:     
3318:   } // class NavigableEntrySet
3319: 
3320: } // class TreeMap