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