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