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  Free Software Foundation, Inc.
   4: 
   5: This file is part of GNU Classpath.
   6: 
   7: GNU Classpath is free software; you can redistribute it and/or modify
   8: it under the terms of the GNU General Public License as published by
   9: the Free Software Foundation; either version 2, or (at your option)
  10: any later version.
  11: 
  12: GNU Classpath is distributed in the hope that it will be useful, but
  13: WITHOUT ANY WARRANTY; without even the implied warranty of
  14: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15: General Public License for more details.
  16: 
  17: You should have received a copy of the GNU General Public License
  18: along with GNU Classpath; see the file COPYING.  If not, write to the
  19: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  20: 02110-1301 USA.
  21: 
  22: Linking this library statically or dynamically with other modules is
  23: making a combined work based on this library.  Thus, the terms and
  24: conditions of the GNU General Public License cover the whole
  25: combination.
  26: 
  27: As a special exception, the copyright holders of this library give you
  28: permission to link this library with independent modules to produce an
  29: executable, regardless of the license terms of these independent
  30: modules, and to copy and distribute the resulting executable under
  31: terms of your choice, provided that you also meet, for each linked
  32: independent module, the terms and conditions of the license of that
  33: module.  An independent module is a module which is not derived from
  34: or based on this library.  If you modify this library, you may extend
  35: this exception to your version of the library, but you are not
  36: obligated to do so.  If you do not wish to do so, delete this
  37: exception statement from your version. */
  38: 
  39: 
  40: package java.util;
  41: 
  42: import java.io.IOException;
  43: import java.io.ObjectInputStream;
  44: import java.io.ObjectOutputStream;
  45: import java.io.Serializable;
  46: 
  47: /**
  48:  * This class provides a red-black tree implementation of the SortedMap
  49:  * interface.  Elements in the Map will be sorted by either a user-provided
  50:  * Comparator object, or by the natural ordering of the keys.
  51:  *
  52:  * The algorithms are adopted from Corman, Leiserson, and Rivest's
  53:  * <i>Introduction to Algorithms.</i>  TreeMap guarantees O(log n)
  54:  * insertion and deletion of elements.  That being said, there is a large
  55:  * enough constant coefficient in front of that "log n" (overhead involved
  56:  * in keeping the tree balanced), that TreeMap may not be the best choice
  57:  * for small collections. If something is already sorted, you may want to
  58:  * just use a LinkedHashMap to maintain the order while providing O(1) access.
  59:  *
  60:  * TreeMap is a part of the JDK1.2 Collections API.  Null keys are allowed
  61:  * only if a Comparator is used which can deal with them; natural ordering
  62:  * cannot cope with null.  Null values are always allowed. Note that the
  63:  * ordering must be <i>consistent with equals</i> to correctly implement
  64:  * the Map interface. If this condition is violated, the map is still
  65:  * well-behaved, but you may have suprising results when comparing it to
  66:  * other maps.<p>
  67:  *
  68:  * This implementation is not synchronized. If you need to share this between
  69:  * multiple threads, do something like:<br>
  70:  * <code>SortedMap m
  71:  *       = Collections.synchronizedSortedMap(new TreeMap(...));</code><p>
  72:  *
  73:  * The iterators are <i>fail-fast</i>, meaning that any structural
  74:  * modification, except for <code>remove()</code> called on the iterator
  75:  * itself, cause the iterator to throw a
  76:  * <code>ConcurrentModificationException</code> rather than exhibit
  77:  * non-deterministic behavior.
  78:  *
  79:  * @author Jon Zeppieri
  80:  * @author Bryce McKinlay
  81:  * @author Eric Blake (ebb9@email.byu.edu)
  82:  * @see Map
  83:  * @see HashMap
  84:  * @see Hashtable
  85:  * @see LinkedHashMap
  86:  * @see Comparable
  87:  * @see Comparator
  88:  * @see Collection
  89:  * @see Collections#synchronizedSortedMap(SortedMap)
  90:  * @since 1.2
  91:  * @status updated to 1.4
  92:  */
  93: public class TreeMap extends AbstractMap
  94:   implements SortedMap, Cloneable, Serializable
  95: {
  96:   // Implementation note:
  97:   // A red-black tree is a binary search tree with the additional properties
  98:   // that all paths to a leaf node visit the same number of black nodes,
  99:   // and no red node has red children. To avoid some null-pointer checks,
 100:   // we use the special node nil which is always black, has no relatives,
 101:   // and has key and value of null (but is not equal to a mapping of null).
 102: 
 103:   /**
 104:    * Compatible with JDK 1.2.
 105:    */
 106:   private static final long serialVersionUID = 919286545866124006L;
 107: 
 108:   /**
 109:    * Color status of a node. Package visible for use by nested classes.
 110:    */
 111:   static final int RED = -1,
 112:                    BLACK = 1;
 113: 
 114:   /**
 115:    * Sentinal node, used to avoid null checks for corner cases and make the
 116:    * delete rebalance code simpler. The rebalance code must never assign
 117:    * the parent, left, or right of nil, but may safely reassign the color
 118:    * to be black. This object must never be used as a key in a TreeMap, or
 119:    * it will break bounds checking of a SubMap.
 120:    */
 121:   static final Node nil = new Node(null, null, BLACK);
 122:   static
 123:     {
 124:       // Nil is self-referential, so we must initialize it after creation.
 125:       nil.parent = nil;
 126:       nil.left = nil;
 127:       nil.right = nil;
 128:     }
 129: 
 130:   /**
 131:    * The root node of this TreeMap.
 132:    */
 133:   private transient Node root;
 134: 
 135:   /**
 136:    * The size of this TreeMap. Package visible for use by nested classes.
 137:    */
 138:   transient int size;
 139: 
 140:   /**
 141:    * The cache for {@link #entrySet()}.
 142:    */
 143:   private transient Set entries;
 144: 
 145:   /**
 146:    * Counts the number of modifications this TreeMap has undergone, used
 147:    * by Iterators to know when to throw ConcurrentModificationExceptions.
 148:    * Package visible for use by nested classes.
 149:    */
 150:   transient int modCount;
 151: 
 152:   /**
 153:    * This TreeMap's comparator, or null for natural ordering.
 154:    * Package visible for use by nested classes.
 155:    * @serial the comparator ordering this tree, or null
 156:    */
 157:   final Comparator comparator;
 158: 
 159:   /**
 160:    * Class to represent an entry in the tree. Holds a single key-value pair,
 161:    * plus pointers to parent and child nodes.
 162:    *
 163:    * @author Eric Blake (ebb9@email.byu.edu)
 164:    */
 165:   private static final class Node extends AbstractMap.BasicMapEntry
 166:   {
 167:     // All fields package visible for use by nested classes.
 168:     /** The color of this node. */
 169:     int color;
 170: 
 171:     /** The left child node. */
 172:     Node left = nil;
 173:     /** The right child node. */
 174:     Node right = nil;
 175:     /** The parent node. */
 176:     Node parent = nil;
 177: 
 178:     /**
 179:      * Simple constructor.
 180:      * @param key the key
 181:      * @param value the value
 182:      */
 183:     Node(Object key, Object value, int color)
 184:     {
 185:       super(key, value);
 186:       this.color = color;
 187:     }
 188:   }
 189: 
 190:   /**
 191:    * Instantiate a new TreeMap with no elements, using the keys' natural
 192:    * ordering to sort. All entries in the map must have a key which implements
 193:    * Comparable, and which are <i>mutually comparable</i>, otherwise map
 194:    * operations may throw a {@link ClassCastException}. Attempts to use
 195:    * a null key will throw a {@link NullPointerException}.
 196:    *
 197:    * @see Comparable
 198:    */
 199:   public TreeMap()
 200:   {
 201:     this((Comparator) null);
 202:   }
 203: 
 204:   /**
 205:    * Instantiate a new TreeMap with no elements, using the provided comparator
 206:    * to sort. All entries in the map must have keys which are mutually
 207:    * comparable by the Comparator, otherwise map operations may throw a
 208:    * {@link ClassCastException}.
 209:    *
 210:    * @param c the sort order for the keys of this map, or null
 211:    *        for the natural order
 212:    */
 213:   public TreeMap(Comparator c)
 214:   {
 215:     comparator = c;
 216:     fabricateTree(0);
 217:   }
 218: 
 219:   /**
 220:    * Instantiate a new TreeMap, initializing it with all of the elements in
 221:    * the provided Map.  The elements will be sorted using the natural
 222:    * ordering of the keys. This algorithm runs in n*log(n) time. All entries
 223:    * in the map must have keys which implement Comparable and are mutually
 224:    * comparable, otherwise map operations may throw a
 225:    * {@link ClassCastException}.
 226:    *
 227:    * @param map a Map, whose entries will be put into this TreeMap
 228:    * @throws ClassCastException if the keys in the provided Map are not
 229:    *         comparable
 230:    * @throws NullPointerException if map is null
 231:    * @see Comparable
 232:    */
 233:   public TreeMap(Map map)
 234:   {
 235:     this((Comparator) null);
 236:     putAll(map);
 237:   }
 238: 
 239:   /**
 240:    * Instantiate a new TreeMap, initializing it with all of the elements in
 241:    * the provided SortedMap.  The elements will be sorted using the same
 242:    * comparator as in the provided SortedMap. This runs in linear time.
 243:    *
 244:    * @param sm a SortedMap, whose entries will be put into this TreeMap
 245:    * @throws NullPointerException if sm is null
 246:    */
 247:   public TreeMap(SortedMap sm)
 248:   {
 249:     this(sm.comparator());
 250:     int pos = sm.size();
 251:     Iterator itr = sm.entrySet().iterator();
 252: 
 253:     fabricateTree(pos);
 254:     Node node = firstNode();
 255: 
 256:     while (--pos >= 0)
 257:       {
 258:         Map.Entry me = (Map.Entry) itr.next();
 259:         node.key = me.getKey();
 260:         node.value = me.getValue();
 261:         node = successor(node);
 262:       }
 263:   }
 264: 
 265:   /**
 266:    * Clears the Map so it has no keys. This is O(1).
 267:    */
 268:   public void clear()
 269:   {
 270:     if (size > 0)
 271:       {
 272:         modCount++;
 273:         root = nil;
 274:         size = 0;
 275:       }
 276:   }
 277: 
 278:   /**
 279:    * Returns a shallow clone of this TreeMap. The Map itself is cloned,
 280:    * but its contents are not.
 281:    *
 282:    * @return the clone
 283:    */
 284:   public Object clone()
 285:   {
 286:     TreeMap copy = null;
 287:     try
 288:       {
 289:         copy = (TreeMap) super.clone();
 290:       }
 291:     catch (CloneNotSupportedException x)
 292:       {
 293:       }
 294:     copy.entries = null;
 295:     copy.fabricateTree(size);
 296: 
 297:     Node node = firstNode();
 298:     Node cnode = copy.firstNode();
 299: 
 300:     while (node != nil)
 301:       {
 302:         cnode.key = node.key;
 303:         cnode.value = node.value;
 304:         node = successor(node);
 305:         cnode = copy.successor(cnode);
 306:       }
 307:     return copy;
 308:   }
 309: 
 310:   /**
 311:    * Return the comparator used to sort this map, or null if it is by
 312:    * natural order.
 313:    *
 314:    * @return the map's comparator
 315:    */
 316:   public Comparator comparator()
 317:   {
 318:     return comparator;
 319:   }
 320: 
 321:   /**
 322:    * Returns true if the map contains a mapping for the given key.
 323:    *
 324:    * @param key the key to look for
 325:    * @return true if the key has a mapping
 326:    * @throws ClassCastException if key is not comparable to map elements
 327:    * @throws NullPointerException if key is null and the comparator is not
 328:    *         tolerant of nulls
 329:    */
 330:   public boolean containsKey(Object key)
 331:   {
 332:     return getNode(key) != nil;
 333:   }
 334: 
 335:   /**
 336:    * Returns true if the map contains at least one mapping to the given value.
 337:    * This requires linear time.
 338:    *
 339:    * @param value the value to look for
 340:    * @return true if the value appears in a mapping
 341:    */
 342:   public boolean containsValue(Object value)
 343:   {
 344:     Node node = firstNode();
 345:     while (node != nil)
 346:       {
 347:         if (equals(value, node.value))
 348:           return true;
 349:         node = successor(node);
 350:       }
 351:     return false;
 352:   }
 353: 
 354:   /**
 355:    * Returns a "set view" of this TreeMap's entries. The set is backed by
 356:    * the TreeMap, so changes in one show up in the other.  The set supports
 357:    * element removal, but not element addition.<p>
 358:    *
 359:    * Note that the iterators for all three views, from keySet(), entrySet(),
 360:    * and values(), traverse the TreeMap in sorted sequence.
 361:    *
 362:    * @return a set view of the entries
 363:    * @see #keySet()
 364:    * @see #values()
 365:    * @see Map.Entry
 366:    */
 367:   public Set entrySet()
 368:   {
 369:     if (entries == null)
 370:       // Create an AbstractSet with custom implementations of those methods
 371:       // that can be overriden easily and efficiently.
 372:       entries = new AbstractSet()
 373:       {
 374:         public int size()
 375:         {
 376:           return size;
 377:         }
 378: 
 379:         public Iterator iterator()
 380:         {
 381:           return new TreeIterator(ENTRIES);
 382:         }
 383: 
 384:         public void clear()
 385:         {
 386:           TreeMap.this.clear();
 387:         }
 388: 
 389:         public boolean contains(Object o)
 390:         {
 391:           if (! (o instanceof Map.Entry))
 392:             return false;
 393:           Map.Entry me = (Map.Entry) o;
 394:           Node n = getNode(me.getKey());
 395:           return n != nil && AbstractSet.equals(me.getValue(), n.value);
 396:       }
 397: 
 398:         public boolean remove(Object o)
 399:         {
 400:           if (! (o instanceof Map.Entry))
 401:             return false;
 402:           Map.Entry me = (Map.Entry) o;
 403:           Node n = getNode(me.getKey());
 404:           if (n != nil && AbstractSet.equals(me.getValue(), n.value))
 405:             {
 406:               removeNode(n);
 407:               return true;
 408:             }
 409:           return false;
 410:         }
 411:       };
 412:     return entries;
 413:   }
 414: 
 415:   /**
 416:    * Returns the first (lowest) key in the map.
 417:    *
 418:    * @return the first key
 419:    * @throws NoSuchElementException if the map is empty
 420:    */
 421:   public Object firstKey()
 422:   {
 423:     if (root == nil)
 424:       throw new NoSuchElementException();
 425:     return firstNode().key;
 426:   }
 427: 
 428:   /**
 429:    * Return the value in this TreeMap associated with the supplied key,
 430:    * or <code>null</code> if the key maps to nothing.  NOTE: Since the value
 431:    * could also be null, you must use containsKey to see if this key
 432:    * actually maps to something.
 433:    *
 434:    * @param key the key for which to fetch an associated value
 435:    * @return what the key maps to, if present
 436:    * @throws ClassCastException if key is not comparable to elements in the map
 437:    * @throws NullPointerException if key is null but the comparator does not
 438:    *         tolerate nulls
 439:    * @see #put(Object, Object)
 440:    * @see #containsKey(Object)
 441:    */
 442:   public Object get(Object key)
 443:   {
 444:     // Exploit fact that nil.value == null.
 445:     return getNode(key).value;
 446:   }
 447: 
 448:   /**
 449:    * Returns a view of this Map including all entries with keys less than
 450:    * <code>toKey</code>. The returned map is backed by the original, so changes
 451:    * in one appear in the other. The submap will throw an
 452:    * {@link IllegalArgumentException} for any attempt to access or add an
 453:    * element beyond the specified cutoff. The returned map does not include
 454:    * the endpoint; if you want inclusion, pass the successor element.
 455:    *
 456:    * @param toKey the (exclusive) cutoff point
 457:    * @return a view of the map less than the cutoff
 458:    * @throws ClassCastException if <code>toKey</code> is not compatible with
 459:    *         the comparator (or is not Comparable, for natural ordering)
 460:    * @throws NullPointerException if toKey is null, but the comparator does not
 461:    *         tolerate null elements
 462:    */
 463:   public SortedMap headMap(Object toKey)
 464:   {
 465:     return new SubMap(nil, toKey);
 466:   }
 467: 
 468:   /**
 469:    * Returns a "set view" of this TreeMap's keys. The set is backed by the
 470:    * TreeMap, so changes in one show up in the other.  The set supports
 471:    * element removal, but not element addition.
 472:    *
 473:    * @return a set view of the keys
 474:    * @see #values()
 475:    * @see #entrySet()
 476:    */
 477:   public Set keySet()
 478:   {
 479:     if (keys == null)
 480:       // Create an AbstractSet with custom implementations of those methods
 481:       // that can be overriden easily and efficiently.
 482:       keys = new AbstractSet()
 483:       {
 484:         public int size()
 485:         {
 486:           return size;
 487:         }
 488: 
 489:         public Iterator iterator()
 490:         {
 491:           return new TreeIterator(KEYS);
 492:         }
 493: 
 494:         public void clear()
 495:         {
 496:           TreeMap.this.clear();
 497:         }
 498: 
 499:         public boolean contains(Object o)
 500:         {
 501:           return containsKey(o);
 502:         }
 503: 
 504:         public boolean remove(Object key)
 505:         {
 506:           Node n = getNode(key);
 507:           if (n == nil)
 508:             return false;
 509:           removeNode(n);
 510:           return true;
 511:         }
 512:       };
 513:     return keys;
 514:   }
 515: 
 516:   /**
 517:    * Returns the last (highest) key in the map.
 518:    *
 519:    * @return the last key
 520:    * @throws NoSuchElementException if the map is empty
 521:    */
 522:   public Object lastKey()
 523:   {
 524:     if (root == nil)
 525:       throw new NoSuchElementException("empty");
 526:     return lastNode().key;
 527:   }
 528: 
 529:   /**
 530:    * Puts the supplied value into the Map, mapped by the supplied key.
 531:    * The value may be retrieved by any object which <code>equals()</code>
 532:    * this key. NOTE: Since the prior value could also be null, you must
 533:    * first use containsKey if you want to see if you are replacing the
 534:    * key's mapping.
 535:    *
 536:    * @param key the key used to locate the value
 537:    * @param value the value to be stored in the Map
 538:    * @return the prior mapping of the key, or null if there was none
 539:    * @throws ClassCastException if key is not comparable to current map keys
 540:    * @throws NullPointerException if key is null, but the comparator does
 541:    *         not tolerate nulls
 542:    * @see #get(Object)
 543:    * @see Object#equals(Object)
 544:    */
 545:   public Object put(Object key, Object value)
 546:   {
 547:     Node current = root;
 548:     Node parent = nil;
 549:     int comparison = 0;
 550: 
 551:     // Find new node's parent.
 552:     while (current != nil)
 553:       {
 554:         parent = current;
 555:         comparison = compare(key, current.key);
 556:         if (comparison > 0)
 557:           current = current.right;
 558:         else if (comparison < 0)
 559:           current = current.left;
 560:         else // Key already in tree.
 561:           return current.setValue(value);
 562:       }
 563: 
 564:     // Set up new node.
 565:     Node n = new Node(key, value, RED);
 566:     n.parent = parent;
 567: 
 568:     // Insert node in tree.
 569:     modCount++;
 570:     size++;
 571:     if (parent == nil)
 572:       {
 573:         // Special case inserting into an empty tree.
 574:         root = n;
 575:         return null;
 576:       }
 577:     if (comparison > 0)
 578:       parent.right = n;
 579:     else
 580:       parent.left = n;
 581: 
 582:     // Rebalance after insert.
 583:     insertFixup(n);
 584:     return null;
 585:   }
 586: 
 587:   /**
 588:    * Copies all elements of the given map into this TreeMap.  If this map
 589:    * already has a mapping for a key, the new mapping replaces the current
 590:    * one.
 591:    *
 592:    * @param m the map to be added
 593:    * @throws ClassCastException if a key in m is not comparable with keys
 594:    *         in the map
 595:    * @throws NullPointerException if a key in m is null, and the comparator
 596:    *         does not tolerate nulls
 597:    */
 598:   public void putAll(Map m)
 599:   {
 600:     Iterator itr = m.entrySet().iterator();
 601:     int pos = m.size();
 602:     while (--pos >= 0)
 603:       {
 604:         Map.Entry e = (Map.Entry) itr.next();
 605:         put(e.getKey(), e.getValue());
 606:       }
 607:   }
 608: 
 609:   /**
 610:    * Removes from the TreeMap and returns the value which is mapped by the
 611:    * supplied key. If the key maps to nothing, then the TreeMap remains
 612:    * unchanged, and <code>null</code> is returned. NOTE: Since the value
 613:    * could also be null, you must use containsKey to see if you are
 614:    * actually removing a mapping.
 615:    *
 616:    * @param key the key used to locate the value to remove
 617:    * @return whatever the key mapped to, if present
 618:    * @throws ClassCastException if key is not comparable to current map keys
 619:    * @throws NullPointerException if key is null, but the comparator does
 620:    *         not tolerate nulls
 621:    */
 622:   public Object remove(Object key)
 623:   {
 624:     Node n = getNode(key);
 625:     if (n == nil)
 626:       return null;
 627:     // Note: removeNode can alter the contents of n, so save value now.
 628:     Object result = n.value;
 629:     removeNode(n);
 630:     return result;
 631:   }
 632: 
 633:   /**
 634:    * Returns the number of key-value mappings currently in this Map.
 635:    *
 636:    * @return the size
 637:    */
 638:   public int size()
 639:   {
 640:     return size;
 641:   }
 642: 
 643:   /**
 644:    * Returns a view of this Map including all entries with keys greater or
 645:    * equal to <code>fromKey</code> and less than <code>toKey</code> (a
 646:    * half-open interval). The returned map is backed by the original, so
 647:    * changes in one appear in the other. The submap will throw an
 648:    * {@link IllegalArgumentException} for any attempt to access or add an
 649:    * element beyond the specified cutoffs. The returned map includes the low
 650:    * endpoint but not the high; if you want to reverse this behavior on
 651:    * either end, pass in the successor element.
 652:    *
 653:    * @param fromKey the (inclusive) low cutoff point
 654:    * @param toKey the (exclusive) high cutoff point
 655:    * @return a view of the map between the cutoffs
 656:    * @throws ClassCastException if either cutoff is not compatible with
 657:    *         the comparator (or is not Comparable, for natural ordering)
 658:    * @throws NullPointerException if fromKey or toKey is null, but the
 659:    *         comparator does not tolerate null elements
 660:    * @throws IllegalArgumentException if fromKey is greater than toKey
 661:    */
 662:   public SortedMap subMap(Object fromKey, Object toKey)
 663:   {
 664:     return new SubMap(fromKey, toKey);
 665:   }
 666: 
 667:   /**
 668:    * Returns a view of this Map including all entries with keys greater or
 669:    * equal to <code>fromKey</code>. The returned map is backed by the
 670:    * original, so changes in one appear in the other. The submap will throw an
 671:    * {@link IllegalArgumentException} for any attempt to access or add an
 672:    * element beyond the specified cutoff. The returned map includes the
 673:    * endpoint; if you want to exclude it, pass in the successor element.
 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 tailMap(Object fromKey)
 683:   {
 684:     return new SubMap(fromKey, nil);
 685:   }
 686: 
 687:   /**
 688:    * Returns a "collection view" (or "bag view") of this TreeMap's values.
 689:    * The collection is backed by the TreeMap, so changes in one show up
 690:    * in the other.  The collection supports element removal, but not element
 691:    * addition.
 692:    *
 693:    * @return a bag view of the values
 694:    * @see #keySet()
 695:    * @see #entrySet()
 696:    */
 697:   public Collection values()
 698:   {
 699:     if (values == null)
 700:       // We don't bother overriding many of the optional methods, as doing so
 701:       // wouldn't provide any significant performance advantage.
 702:       values = new AbstractCollection()
 703:       {
 704:         public int size()
 705:         {
 706:           return size;
 707:         }
 708: 
 709:         public Iterator iterator()
 710:         {
 711:           return new TreeIterator(VALUES);
 712:         }
 713: 
 714:         public void clear()
 715:         {
 716:           TreeMap.this.clear();
 717:         }
 718:       };
 719:     return values;
 720:   }
 721: 
 722:   /**
 723:    * Compares two elements by the set comparator, or by natural ordering.
 724:    * Package visible for use by nested classes.
 725:    *
 726:    * @param o1 the first object
 727:    * @param o2 the second object
 728:    * @throws ClassCastException if o1 and o2 are not mutually comparable,
 729:    *         or are not Comparable with natural ordering
 730:    * @throws NullPointerException if o1 or o2 is null with natural ordering
 731:    */
 732:   final int compare(Object o1, Object o2)
 733:   {
 734:     return (comparator == null
 735:             ? ((Comparable) o1).compareTo(o2)
 736:             : comparator.compare(o1, o2));
 737:   }
 738: 
 739:   /**
 740:    * Maintain red-black balance after deleting a node.
 741:    *
 742:    * @param node the child of the node just deleted, possibly nil
 743:    * @param parent the parent of the node just deleted, never nil
 744:    */
 745:   private void deleteFixup(Node node, Node parent)
 746:   {
 747:     // if (parent == nil)
 748:     //   throw new InternalError();
 749:     // If a black node has been removed, we need to rebalance to avoid
 750:     // violating the "same number of black nodes on any path" rule. If
 751:     // node is red, we can simply recolor it black and all is well.
 752:     while (node != root && node.color == BLACK)
 753:       {
 754:         if (node == parent.left)
 755:           {
 756:             // Rebalance left side.
 757:             Node sibling = parent.right;
 758:             // if (sibling == nil)
 759:             //   throw new InternalError();
 760:             if (sibling.color == RED)
 761:               {
 762:                 // Case 1: Sibling is red.
 763:                 // Recolor sibling and parent, and rotate parent left.
 764:                 sibling.color = BLACK;
 765:                 parent.color = RED;
 766:                 rotateLeft(parent);
 767:                 sibling = parent.right;
 768:               }
 769: 
 770:             if (sibling.left.color == BLACK && sibling.right.color == BLACK)
 771:               {
 772:                 // Case 2: Sibling has no red children.
 773:                 // Recolor sibling, and move to parent.
 774:                 sibling.color = RED;
 775:                 node = parent;
 776:                 parent = parent.parent;
 777:               }
 778:             else
 779:               {
 780:                 if (sibling.right.color == BLACK)
 781:                   {
 782:                     // Case 3: Sibling has red left child.
 783:                     // Recolor sibling and left child, rotate sibling right.
 784:                     sibling.left.color = BLACK;
 785:                     sibling.color = RED;
 786:                     rotateRight(sibling);
 787:                     sibling = parent.right;
 788:                   }
 789:                 // Case 4: Sibling has red right child. Recolor sibling,
 790:                 // right child, and parent, and rotate parent left.
 791:                 sibling.color = parent.color;
 792:                 parent.color = BLACK;
 793:                 sibling.right.color = BLACK;
 794:                 rotateLeft(parent);
 795:                 node = root; // Finished.
 796:               }
 797:           }
 798:         else
 799:           {
 800:             // Symmetric "mirror" of left-side case.
 801:             Node sibling = parent.left;
 802:             // if (sibling == nil)
 803:             //   throw new InternalError();
 804:             if (sibling.color == RED)
 805:               {
 806:                 // Case 1: Sibling is red.
 807:                 // Recolor sibling and parent, and rotate parent right.
 808:                 sibling.color = BLACK;
 809:                 parent.color = RED;
 810:                 rotateRight(parent);
 811:                 sibling = parent.left;
 812:               }
 813: 
 814:             if (sibling.right.color == BLACK && sibling.left.color == BLACK)
 815:               {
 816:                 // Case 2: Sibling has no red children.
 817:                 // Recolor sibling, and move to parent.
 818:                 sibling.color = RED;
 819:                 node = parent;
 820:                 parent = parent.parent;
 821:               }
 822:             else
 823:               {
 824:                 if (sibling.left.color == BLACK)
 825:                   {
 826:                     // Case 3: Sibling has red right child.
 827:                     // Recolor sibling and right child, rotate sibling left.
 828:                     sibling.right.color = BLACK;
 829:                     sibling.color = RED;
 830:                     rotateLeft(sibling);
 831:                     sibling = parent.left;
 832:                   }
 833:                 // Case 4: Sibling has red left child. Recolor sibling,
 834:                 // left child, and parent, and rotate parent right.
 835:                 sibling.color = parent.color;
 836:                 parent.color = BLACK;
 837:                 sibling.left.color = BLACK;
 838:                 rotateRight(parent);
 839:                 node = root; // Finished.
 840:               }
 841:           }
 842:       }
 843:     node.color = BLACK;
 844:   }
 845: 
 846:   /**
 847:    * Construct a perfectly balanced tree consisting of n "blank" nodes. This
 848:    * permits a tree to be generated from pre-sorted input in linear time.
 849:    *
 850:    * @param count the number of blank nodes, non-negative
 851:    */
 852:   private void fabricateTree(final int count)
 853:   {
 854:     if (count == 0)
 855:       {
 856:     root = nil;
 857:     size = 0;
 858:     return;
 859:       }
 860: 
 861:     // We color every row of nodes black, except for the overflow nodes.
 862:     // I believe that this is the optimal arrangement. We construct the tree
 863:     // in place by temporarily linking each node to the next node in the row,
 864:     // then updating those links to the children when working on the next row.
 865: 
 866:     // Make the root node.
 867:     root = new Node(null, null, BLACK);
 868:     size = count;
 869:     Node row = root;
 870:     int rowsize;
 871: 
 872:     // Fill each row that is completely full of nodes.
 873:     for (rowsize = 2; rowsize + rowsize <= count; rowsize <<= 1)
 874:       {
 875:         Node parent = row;
 876:         Node last = null;
 877:         for (int i = 0; i < rowsize; i += 2)
 878:           {
 879:             Node left = new Node(null, null, BLACK);
 880:             Node right = new Node(null, null, BLACK);
 881:             left.parent = parent;
 882:             left.right = right;
 883:             right.parent = parent;
 884:             parent.left = left;
 885:             Node next = parent.right;
 886:             parent.right = right;
 887:             parent = next;
 888:             if (last != null)
 889:               last.right = left;
 890:             last = right;
 891:           }
 892:         row = row.left;
 893:       }
 894: 
 895:     // Now do the partial final row in red.
 896:     int overflow = count - rowsize;
 897:     Node parent = row;
 898:     int i;
 899:     for (i = 0; i < overflow; i += 2)
 900:       {
 901:         Node left = new Node(null, null, RED);
 902:         Node right = new Node(null, null, RED);
 903:         left.parent = parent;
 904:         right.parent = parent;
 905:         parent.left = left;
 906:         Node next = parent.right;
 907:         parent.right = right;
 908:         parent = next;
 909:       }
 910:     // Add a lone left node if necessary.
 911:     if (i - overflow == 0)
 912:       {
 913:         Node left = new Node(null, null, RED);
 914:         left.parent = parent;
 915:         parent.left = left;
 916:         parent = parent.right;
 917:         left.parent.right = nil;
 918:       }
 919:     // Unlink the remaining nodes of the previous row.
 920:     while (parent != nil)
 921:       {
 922:         Node next = parent.right;
 923:         parent.right = nil;
 924:         parent = next;
 925:       }
 926:   }
 927: 
 928:   /**
 929:    * Returns the first sorted node in the map, or nil if empty. Package
 930:    * visible for use by nested classes.
 931:    *
 932:    * @return the first node
 933:    */
 934:   final Node firstNode()
 935:   {
 936:     // Exploit fact that nil.left == nil.
 937:     Node node = root;
 938:     while (node.left != nil)
 939:       node = node.left;
 940:     return node;
 941:   }
 942: 
 943:   /**
 944:    * Return the TreeMap.Node associated with key, or the nil node if no such
 945:    * node exists in the tree. Package visible for use by nested classes.
 946:    *
 947:    * @param key the key to search for
 948:    * @return the node where the key is found, or nil
 949:    */
 950:   final Node getNode(Object key)
 951:   {
 952:     Node current = root;
 953:     while (current != nil)
 954:       {
 955:         int comparison = compare(key, current.key);
 956:         if (comparison > 0)
 957:           current = current.right;
 958:         else if (comparison < 0)
 959:           current = current.left;
 960:         else
 961:           return current;
 962:       }
 963:     return current;
 964:   }
 965: 
 966:   /**
 967:    * Find the "highest" node which is &lt; key. If key is nil, return last
 968:    * node. Package visible for use by nested classes.
 969:    *
 970:    * @param key the upper bound, exclusive
 971:    * @return the previous node
 972:    */
 973:   final Node highestLessThan(Object key)
 974:   {
 975:     if (key == nil)
 976:       return lastNode();
 977: 
 978:     Node last = nil;
 979:     Node current = root;
 980:     int comparison = 0;
 981: 
 982:     while (current != nil)
 983:       {
 984:         last = current;
 985:         comparison = compare(key, current.key);
 986:         if (comparison > 0)
 987:           current = current.right;
 988:         else if (comparison < 0)
 989:           current = current.left;
 990:         else // Exact match.
 991:           return predecessor(last);
 992:       }
 993:     return comparison <= 0 ? predecessor(last) : last;
 994:   }
 995: 
 996:   /**
 997:    * Maintain red-black balance after inserting a new node.
 998:    *
 999:    * @param n the newly inserted node
1000:    */
1001:   private void insertFixup(Node n)
1002:   {
1003:     // Only need to rebalance when parent is a RED node, and while at least
1004:     // 2 levels deep into the tree (ie: node has a grandparent). Remember
1005:     // that nil.color == BLACK.
1006:     while (n.parent.color == RED && n.parent.parent != nil)
1007:       {
1008:         if (n.parent == n.parent.parent.left)
1009:           {
1010:             Node uncle = n.parent.parent.right;
1011:             // Uncle may be nil, in which case it is BLACK.
1012:             if (uncle.color == RED)
1013:               {
1014:                 // Case 1. Uncle is RED: Change colors of parent, uncle,
1015:                 // and grandparent, and move n to grandparent.
1016:                 n.parent.color = BLACK;
1017:                 uncle.color = BLACK;
1018:                 uncle.parent.color = RED;
1019:                 n = uncle.parent;
1020:               }
1021:             else
1022:               {
1023:                 if (n == n.parent.right)
1024:                   {
1025:                     // Case 2. Uncle is BLACK and x is right child.
1026:                     // Move n to parent, and rotate n left.
1027:                     n = n.parent;
1028:                     rotateLeft(n);
1029:                   }
1030:                 // Case 3. Uncle is BLACK and x is left child.
1031:                 // Recolor parent, grandparent, and rotate grandparent right.
1032:                 n.parent.color = BLACK;
1033:                 n.parent.parent.color = RED;
1034:                 rotateRight(n.parent.parent);
1035:               }
1036:           }
1037:         else
1038:           {
1039:             // Mirror image of above code.
1040:             Node uncle = n.parent.parent.left;
1041:             // Uncle may be nil, in which case it is BLACK.
1042:             if (uncle.color == RED)
1043:               {
1044:                 // Case 1. Uncle is RED: Change colors of parent, uncle,
1045:                 // and grandparent, and move n to grandparent.
1046:                 n.parent.color = BLACK;
1047:                 uncle.color = BLACK;
1048:                 uncle.parent.color = RED;
1049:                 n = uncle.parent;
1050:               }
1051:             else
1052:               {
1053:                 if (n == n.parent.left)
1054:                 {
1055:                     // Case 2. Uncle is BLACK and x is left child.
1056:                     // Move n to parent, and rotate n right.
1057:                     n = n.parent;
1058:                     rotateRight(n);
1059:                   }
1060:                 // Case 3. Uncle is BLACK and x is right child.
1061:                 // Recolor parent, grandparent, and rotate grandparent left.
1062:                 n.parent.color = BLACK;
1063:                 n.parent.parent.color = RED;
1064:                 rotateLeft(n.parent.parent);
1065:               }
1066:           }
1067:       }
1068:     root.color = BLACK;
1069:   }
1070: 
1071:   /**
1072:    * Returns the last sorted node in the map, or nil if empty.
1073:    *
1074:    * @return the last node
1075:    */
1076:   private Node lastNode()
1077:   {
1078:     // Exploit fact that nil.right == nil.
1079:     Node node = root;
1080:     while (node.right != nil)
1081:       node = node.right;
1082:     return node;
1083:   }
1084: 
1085:   /**
1086:    * Find the "lowest" node which is &gt;= key. If key is nil, return either
1087:    * nil or the first node, depending on the parameter first.
1088:    * Package visible for use by nested classes.
1089:    *
1090:    * @param key the lower bound, inclusive
1091:    * @param first true to return the first element instead of nil for nil key
1092:    * @return the next node
1093:    */
1094:   final Node lowestGreaterThan(Object key, boolean first)
1095:   {
1096:     if (key == nil)
1097:       return first ? firstNode() : nil;
1098: 
1099:     Node last = nil;
1100:     Node current = root;
1101:     int comparison = 0;
1102: 
1103:     while (current != nil)
1104:       {
1105:         last = current;
1106:         comparison = compare(key, current.key);
1107:         if (comparison > 0)
1108:           current = current.right;
1109:         else if (comparison < 0)
1110:           current = current.left;
1111:         else
1112:           return current;
1113:       }
1114:     return comparison > 0 ? successor(last) : last;
1115:   }
1116: 
1117:   /**
1118:    * Return the node preceding the given one, or nil if there isn't one.
1119:    *
1120:    * @param node the current node, not nil
1121:    * @return the prior node in sorted order
1122:    */
1123:   private Node predecessor(Node node)
1124:   {
1125:     if (node.left != nil)
1126:       {
1127:         node = node.left;
1128:         while (node.right != nil)
1129:           node = node.right;
1130:         return node;
1131:       }
1132: 
1133:     Node parent = node.parent;
1134:     // Exploit fact that nil.left == nil and node is non-nil.
1135:     while (node == parent.left)
1136:       {
1137:         node = parent;
1138:         parent = node.parent;
1139:       }
1140:     return parent;
1141:   }
1142: 
1143:   /**
1144:    * Construct a tree from sorted keys in linear time. Package visible for
1145:    * use by TreeSet.
1146:    *
1147:    * @param s the stream to read from
1148:    * @param count the number of keys to read
1149:    * @param readValues true to read values, false to insert "" as the value
1150:    * @throws ClassNotFoundException if the underlying stream fails
1151:    * @throws IOException if the underlying stream fails
1152:    * @see #readObject(ObjectInputStream)
1153:    * @see TreeSet#readObject(ObjectInputStream)
1154:    */
1155:   final void putFromObjStream(ObjectInputStream s, int count,
1156:                               boolean readValues)
1157:     throws IOException, ClassNotFoundException
1158:   {
1159:     fabricateTree(count);
1160:     Node node = firstNode();
1161: 
1162:     while (--count >= 0)
1163:       {
1164:         node.key = s.readObject();
1165:         node.value = readValues ? s.readObject() : "";
1166:         node = successor(node);
1167:       }
1168:   }
1169: 
1170:   /**
1171:    * Construct a tree from sorted keys in linear time, with values of "".
1172:    * Package visible for use by TreeSet.
1173:    *
1174:    * @param keys the iterator over the sorted keys
1175:    * @param count the number of nodes to insert
1176:    * @see TreeSet#TreeSet(SortedSet)
1177:    */
1178:   final void putKeysLinear(Iterator keys, int count)
1179:   {
1180:     fabricateTree(count);
1181:     Node node = firstNode();
1182: 
1183:     while (--count >= 0)
1184:       {
1185:         node.key = keys.next();
1186:         node.value = "";
1187:         node = successor(node);
1188:       }
1189:   }
1190: 
1191:   /**
1192:    * Deserializes this object from the given stream.
1193:    *
1194:    * @param s the stream to read from
1195:    * @throws ClassNotFoundException if the underlying stream fails
1196:    * @throws IOException if the underlying stream fails
1197:    * @serialData the <i>size</i> (int), followed by key (Object) and value
1198:    *             (Object) pairs in sorted order
1199:    */
1200:   private void readObject(ObjectInputStream s)
1201:     throws IOException, ClassNotFoundException
1202:   {
1203:     s.defaultReadObject();
1204:     int size = s.readInt();
1205:     putFromObjStream(s, size, true);
1206:   }
1207: 
1208:   /**
1209:    * Remove node from tree. This will increment modCount and decrement size.
1210:    * Node must exist in the tree. Package visible for use by nested classes.
1211:    *
1212:    * @param node the node to remove
1213:    */
1214:   final void removeNode(Node node)
1215:   {
1216:     Node splice;
1217:     Node child;
1218: 
1219:     modCount++;
1220:     size--;
1221: 
1222:     // Find splice, the node at the position to actually remove from the tree.
1223:     if (node.left == nil)
1224:       {
1225:         // Node to be deleted has 0 or 1 children.
1226:         splice = node;
1227:         child = node.right;
1228:       }
1229:     else if (node.right == nil)
1230:       {
1231:         // Node to be deleted has 1 child.
1232:         splice = node;
1233:         child = node.left;
1234:       }
1235:     else
1236:       {
1237:         // Node has 2 children. Splice is node's predecessor, and we swap
1238:         // its contents into node.
1239:         splice = node.left;
1240:         while (splice.right != nil)
1241:           splice = splice.right;
1242:         child = splice.left;
1243:         node.key = splice.key;
1244:         node.value = splice.value;
1245:       }
1246: 
1247:     // Unlink splice from the tree.
1248:     Node parent = splice.parent;
1249:     if (child != nil)
1250:       child.parent = parent;
1251:     if (parent == nil)
1252:       {
1253:         // Special case for 0 or 1 node remaining.
1254:         root = child;
1255:         return;
1256:       }
1257:     if (splice == parent.left)
1258:       parent.left = child;
1259:     else
1260:       parent.right = child;
1261: 
1262:     if (splice.color == BLACK)
1263:       deleteFixup(child, parent);
1264:   }
1265: 
1266:   /**
1267:    * Rotate node n to the left.
1268:    *
1269:    * @param node the node to rotate
1270:    */
1271:   private void rotateLeft(Node node)
1272:   {
1273:     Node child = node.right;
1274:     // if (node == nil || child == nil)
1275:     //   throw new InternalError();
1276: 
1277:     // Establish node.right link.
1278:     node.right = child.left;
1279:     if (child.left != nil)
1280:       child.left.parent = node;
1281: 
1282:     // Establish child->parent link.
1283:     child.parent = node.parent;
1284:     if (node.parent != nil)
1285:       {
1286:         if (node == node.parent.left)
1287:           node.parent.left = child;
1288:         else
1289:           node.parent.right = child;
1290:       }
1291:     else
1292:       root = child;
1293: 
1294:     // Link n and child.
1295:     child.left = node;
1296:     node.parent = child;
1297:   }
1298: 
1299:   /**
1300:    * Rotate node n to the right.
1301:    *
1302:    * @param node the node to rotate
1303:    */
1304:   private void rotateRight(Node node)
1305:   {
1306:     Node child = node.left;
1307:     // if (node == nil || child == nil)
1308:     //   throw new InternalError();
1309: 
1310:     // Establish node.left link.
1311:     node.left = child.right;
1312:     if (child.right != nil)
1313:       child.right.parent = node;
1314: 
1315:     // Establish child->parent link.
1316:     child.parent = node.parent;
1317:     if (node.parent != nil)
1318:       {
1319:         if (node == node.parent.right)
1320:           node.parent.right = child;
1321:         else
1322:           node.parent.left = child;
1323:       }
1324:     else
1325:       root = child;
1326: 
1327:     // Link n and child.
1328:     child.right = node;
1329:     node.parent = child;
1330:   }
1331: 
1332:   /**
1333:    * Return the node following the given one, or nil if there isn't one.
1334:    * Package visible for use by nested classes.
1335:    *
1336:    * @param node the current node, not nil
1337:    * @return the next node in sorted order
1338:    */
1339:   final Node successor(Node node)
1340:   {
1341:     if (node.right != nil)
1342:       {
1343:         node = node.right;
1344:         while (node.left != nil)
1345:           node = node.left;
1346:         return node;
1347:       }
1348: 
1349:     Node parent = node.parent;
1350:     // Exploit fact that nil.right == nil and node is non-nil.
1351:     while (node == parent.right)
1352:       {
1353:         node = parent;
1354:         parent = parent.parent;
1355:       }
1356:     return parent;
1357:   }
1358: 
1359:   /**
1360:    * Serializes this object to the given stream.
1361:    *
1362:    * @param s the stream to write to
1363:    * @throws IOException if the underlying stream fails
1364:    * @serialData the <i>size</i> (int), followed by key (Object) and value
1365:    *             (Object) pairs in sorted order
1366:    */
1367:   private void writeObject(ObjectOutputStream s) throws IOException
1368:   {
1369:     s.defaultWriteObject();
1370: 
1371:     Node node = firstNode();
1372:     s.writeInt(size);
1373:     while (node != nil)
1374:       {
1375:         s.writeObject(node.key);
1376:         s.writeObject(node.value);
1377:         node = successor(node);
1378:       }
1379:   }
1380: 
1381:   /**
1382:    * Iterate over TreeMap's entries. This implementation is parameterized
1383:    * to give a sequential view of keys, values, or entries.
1384:    *
1385:    * @author Eric Blake (ebb9@email.byu.edu)
1386:    */
1387:   private final class TreeIterator implements Iterator
1388:   {
1389:     /**
1390:      * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
1391:      * or {@link #ENTRIES}.
1392:      */
1393:     private final int type;
1394:     /** The number of modifications to the backing Map that we know about. */
1395:     private int knownMod = modCount;
1396:     /** The last Entry returned by a next() call. */
1397:     private Node last;
1398:     /** The next entry that should be returned by next(). */
1399:     private Node next;
1400:     /**
1401:      * The last node visible to this iterator. This is used when iterating
1402:      * on a SubMap.
1403:      */
1404:     private final Node max;
1405: 
1406:     /**
1407:      * Construct a new TreeIterator with the supplied type.
1408:      * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
1409:      */
1410:     TreeIterator(int type)
1411:     {
1412:       // FIXME gcj cannot handle this. Bug java/4695
1413:       // this(type, firstNode(), nil);
1414:       this.type = type;
1415:       this.next = firstNode();
1416:       this.max = nil;
1417:     }
1418: 
1419:     /**
1420:      * Construct a new TreeIterator with the supplied type. Iteration will
1421:      * be from "first" (inclusive) to "max" (exclusive).
1422:      *
1423:      * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
1424:      * @param first where to start iteration, nil for empty iterator
1425:      * @param max the cutoff for iteration, nil for all remaining nodes
1426:      */
1427:     TreeIterator(int type, Node first, Node max)
1428:     {
1429:       this.type = type;
1430:       this.next = first;
1431:       this.max = max;
1432:     }
1433: 
1434:     /**
1435:      * Returns true if the Iterator has more elements.
1436:      * @return true if there are more elements
1437:      * @throws ConcurrentModificationException if the TreeMap was modified
1438:      */
1439:     public boolean hasNext()
1440:     {
1441:       if (knownMod != modCount)
1442:         throw new ConcurrentModificationException();
1443:       return next != max;
1444:     }
1445: 
1446:     /**
1447:      * Returns the next element in the Iterator's sequential view.
1448:      * @return the next element
1449:      * @throws ConcurrentModificationException if the TreeMap was modified
1450:      * @throws NoSuchElementException if there is none
1451:      */
1452:     public Object next()
1453:     {
1454:       if (knownMod != modCount)
1455:         throw new ConcurrentModificationException();
1456:       if (next == max)
1457:         throw new NoSuchElementException();
1458:       last = next;
1459:       next = successor(last);
1460: 
1461:       if (type == VALUES)
1462:         return last.value;
1463:       else if (type == KEYS)
1464:         return last.key;
1465:       return last;
1466:     }
1467: 
1468:     /**
1469:      * Removes from the backing TreeMap the last element which was fetched
1470:      * with the <code>next()</code> method.
1471:      * @throws ConcurrentModificationException if the TreeMap was modified
1472:      * @throws IllegalStateException if called when there is no last element
1473:      */
1474:     public void remove()
1475:     {
1476:       if (last == null)
1477:         throw new IllegalStateException();
1478:       if (knownMod != modCount)
1479:         throw new ConcurrentModificationException();
1480: 
1481:       removeNode(last);
1482:       last = null;
1483:       knownMod++;
1484:     }
1485:   } // class TreeIterator
1486: 
1487:   /**
1488:    * Implementation of {@link #subMap(Object, Object)} and other map
1489:    * ranges. This class provides a view of a portion of the original backing
1490:    * map, and throws {@link IllegalArgumentException} for attempts to
1491:    * access beyond that range.
1492:    *
1493:    * @author Eric Blake (ebb9@email.byu.edu)
1494:    */
1495:   private final class SubMap extends AbstractMap implements SortedMap
1496:   {
1497:     /**
1498:      * The lower range of this view, inclusive, or nil for unbounded.
1499:      * Package visible for use by nested classes.
1500:      */
1501:     final Object minKey;
1502: 
1503:     /**
1504:      * The upper range of this view, exclusive, or nil for unbounded.
1505:      * Package visible for use by nested classes.
1506:      */
1507:     final Object maxKey;
1508: 
1509:     /**
1510:      * The cache for {@link #entrySet()}.
1511:      */
1512:     private Set entries;
1513: 
1514:     /**
1515:      * Create a SubMap representing the elements between minKey (inclusive)
1516:      * and maxKey (exclusive). If minKey is nil, SubMap has no lower bound
1517:      * (headMap). If maxKey is nil, the SubMap has no upper bound (tailMap).
1518:      *
1519:      * @param minKey the lower bound
1520:      * @param maxKey the upper bound
1521:      * @throws IllegalArgumentException if minKey &gt; maxKey
1522:      */
1523:     SubMap(Object minKey, Object maxKey)
1524:     {
1525:       if (minKey != nil && maxKey != nil && compare(minKey, maxKey) > 0)
1526:         throw new IllegalArgumentException("fromKey > toKey");
1527:       this.minKey = minKey;
1528:       this.maxKey = maxKey;
1529:     }
1530: 
1531:     /**
1532:      * Check if "key" is in within the range bounds for this SubMap. The
1533:      * lower ("from") SubMap range is inclusive, and the upper ("to") bound
1534:      * is exclusive. Package visible for use by nested classes.
1535:      *
1536:      * @param key the key to check
1537:      * @return true if the key is in range
1538:      */
1539:     boolean keyInRange(Object key)
1540:     {
1541:       return ((minKey == nil || compare(key, minKey) >= 0)
1542:               && (maxKey == nil || compare(key, maxKey) < 0));
1543:     }
1544: 
1545:     public void clear()
1546:     {
1547:       Node next = lowestGreaterThan(minKey, true);
1548:       Node max = lowestGreaterThan(maxKey, false);
1549:       while (next != max)
1550:         {
1551:           Node current = next;
1552:           next = successor(current);
1553:           removeNode(current);
1554:         }
1555:     }
1556: 
1557:     public Comparator comparator()
1558:     {
1559:       return comparator;
1560:     }
1561: 
1562:     public boolean containsKey(Object key)
1563:     {
1564:       return keyInRange(key) && TreeMap.this.containsKey(key);
1565:     }
1566: 
1567:     public boolean containsValue(Object value)
1568:     {
1569:       Node node = lowestGreaterThan(minKey, true);
1570:       Node max = lowestGreaterThan(maxKey, false);
1571:       while (node != max)
1572:         {
1573:           if (equals(value, node.getValue()))
1574:             return true;
1575:           node = successor(node);
1576:         }
1577:       return false;
1578:     }
1579: 
1580:     public Set entrySet()
1581:     {
1582:       if (entries == null)
1583:         // Create an AbstractSet with custom implementations of those methods
1584:         // that can be overriden easily and efficiently.
1585:         entries = new AbstractSet()
1586:         {
1587:           public int size()
1588:           {
1589:             return SubMap.this.size();
1590:           }
1591: 
1592:           public Iterator iterator()
1593:           {
1594:             Node first = lowestGreaterThan(minKey, true);
1595:             Node max = lowestGreaterThan(maxKey, false);
1596:             return new TreeIterator(ENTRIES, first, max);
1597:           }
1598: 
1599:           public void clear()
1600:           {
1601:             SubMap.this.clear();
1602:           }
1603: 
1604:           public boolean contains(Object o)
1605:           {
1606:             if (! (o instanceof Map.Entry))
1607:               return false;
1608:             Map.Entry me = (Map.Entry) o;
1609:             Object key = me.getKey();
1610:             if (! keyInRange(key))
1611:               return false;
1612:             Node n = getNode(key);
1613:             return n != nil && AbstractSet.equals(me.getValue(), n.value);
1614:           }
1615: 
1616:           public boolean remove(Object o)
1617:           {
1618:             if (! (o instanceof Map.Entry))
1619:               return false;
1620:             Map.Entry me = (Map.Entry) o;
1621:             Object key = me.getKey();
1622:             if (! keyInRange(key))
1623:               return false;
1624:             Node n = getNode(key);
1625:             if (n != nil && AbstractSet.equals(me.getValue(), n.value))
1626:               {
1627:                 removeNode(n);
1628:                 return true;
1629:               }
1630:             return false;
1631:           }
1632:         };
1633:       return entries;
1634:     }
1635: 
1636:     public Object firstKey()
1637:     {
1638:       Node node = lowestGreaterThan(minKey, true);
1639:       if (node == nil || ! keyInRange(node.key))
1640:         throw new NoSuchElementException();
1641:       return node.key;
1642:     }
1643: 
1644:     public Object get(Object key)
1645:     {
1646:       if (keyInRange(key))
1647:         return TreeMap.this.get(key);
1648:       return null;
1649:     }
1650: 
1651:     public SortedMap headMap(Object toKey)
1652:     {
1653:       if (! keyInRange(toKey))
1654:         throw new IllegalArgumentException("key outside range");
1655:       return new SubMap(minKey, toKey);
1656:     }
1657: 
1658:     public Set keySet()
1659:     {
1660:       if (this.keys == null)
1661:         // Create an AbstractSet with custom implementations of those methods
1662:         // that can be overriden easily and efficiently.
1663:         this.keys = new AbstractSet()
1664:         {
1665:           public int size()
1666:           {
1667:             return SubMap.this.size();
1668:           }
1669: 
1670:           public Iterator iterator()
1671:           {
1672:             Node first = lowestGreaterThan(minKey, true);
1673:             Node max = lowestGreaterThan(maxKey, false);
1674:             return new TreeIterator(KEYS, first, max);
1675:           }
1676: 
1677:           public void clear()
1678:           {
1679:             SubMap.this.clear();
1680:           }
1681: 
1682:           public boolean contains(Object o)
1683:           {
1684:             if (! keyInRange(o))
1685:               return false;
1686:             return getNode(o) != nil;
1687:           }
1688: 
1689:           public boolean remove(Object o)
1690:           {
1691:             if (! keyInRange(o))
1692:               return false;
1693:             Node n = getNode(o);
1694:             if (n != nil)
1695:               {
1696:                 removeNode(n);
1697:                 return true;
1698:               }
1699:             return false;
1700:           }
1701:         };
1702:       return this.keys;
1703:     }
1704: 
1705:     public Object lastKey()
1706:     {
1707:       Node node = highestLessThan(maxKey);
1708:       if (node == nil || ! keyInRange(node.key))
1709:         throw new NoSuchElementException();
1710:       return node.key;
1711:     }
1712: 
1713:     public Object put(Object key, Object value)
1714:     {
1715:       if (! keyInRange(key))
1716:         throw new IllegalArgumentException("Key outside range");
1717:       return TreeMap.this.put(key, value);
1718:     }
1719: 
1720:     public Object remove(Object key)
1721:     {
1722:       if (keyInRange(key))
1723:         return TreeMap.this.remove(key);
1724:       return null;
1725:     }
1726: 
1727:     public int size()
1728:     {
1729:       Node node = lowestGreaterThan(minKey, true);
1730:       Node max = lowestGreaterThan(maxKey, false);
1731:       int count = 0;
1732:       while (node != max)
1733:         {
1734:           count++;
1735:           node = successor(node);
1736:         }
1737:       return count;
1738:     }
1739: 
1740:     public SortedMap subMap(Object fromKey, Object toKey)
1741:     {
1742:       if (! keyInRange(fromKey) || ! keyInRange(toKey))
1743:         throw new IllegalArgumentException("key outside range");
1744:       return new SubMap(fromKey, toKey);
1745:     }
1746: 
1747:     public SortedMap tailMap(Object fromKey)
1748:     {
1749:       if (! keyInRange(fromKey))
1750:         throw new IllegalArgumentException("key outside range");
1751:       return new SubMap(fromKey, maxKey);
1752:     }
1753: 
1754:     public Collection values()
1755:     {
1756:       if (this.values == null)
1757:         // Create an AbstractCollection with custom implementations of those
1758:         // methods that can be overriden easily and efficiently.
1759:         this.values = new AbstractCollection()
1760:         {
1761:           public int size()
1762:           {
1763:             return SubMap.this.size();
1764:           }
1765: 
1766:           public Iterator iterator()
1767:           {
1768:             Node first = lowestGreaterThan(minKey, true);
1769:             Node max = lowestGreaterThan(maxKey, false);
1770:             return new TreeIterator(VALUES, first, max);
1771:           }
1772: 
1773:           public void clear()
1774:           {
1775:             SubMap.this.clear();
1776:           }
1777:         };
1778:       return this.values;
1779:     }
1780:   } // class SubMap  
1781: } // class TreeMap