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