Java > Open Source Codes > java > util > TreeMap


1 /*
2  * @(#)TreeMap.java 1.65 04/02/19
3  *
4  * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
5  * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6  */
7
8 package java.util;
9
10 /**
11  * Red-Black tree based implementation of the <tt>SortedMap</tt> interface.
12  * This class guarantees that the map will be in ascending key order, sorted
13  * according to the <i>natural order</i> for the key's class (see
14  * <tt>Comparable</tt>), or by the comparator provided at creation time,
15  * depending on which constructor is used.<p>
16  *
17  * This implementation provides guaranteed log(n) time cost for the
18  * <tt>containsKey</tt>, <tt>get</tt>, <tt>put</tt> and <tt>remove</tt>
19  * operations. Algorithms are adaptations of those in Cormen, Leiserson, and
20  * Rivest's <I>Introduction to Algorithms</I>.<p>
21  *
22  * Note that the ordering maintained by a sorted map (whether or not an
23  * explicit comparator is provided) must be <i>consistent with equals</i> if
24  * this sorted map is to correctly implement the <tt>Map</tt> interface. (See
25  * <tt>Comparable</tt> or <tt>Comparator</tt> for a precise definition of
26  * <i>consistent with equals</i>.) This is so because the <tt>Map</tt>
27  * interface is defined in terms of the equals operation, but a map performs
28  * all key comparisons using its <tt>compareTo</tt> (or <tt>compare</tt>)
29  * method, so two keys that are deemed equal by this method are, from the
30  * standpoint of the sorted map, equal. The behavior of a sorted map
31  * <i>is</i> well-defined even if its ordering is inconsistent with equals; it
32  * just fails to obey the general contract of the <tt>Map</tt> interface.<p>
33  *
34  * <b>Note that this implementation is not synchronized.</b> If multiple
35  * threads access a map concurrently, and at least one of the threads modifies
36  * the map structurally, it <i>must</i> be synchronized externally. (A
37  * structural modification is any operation that adds or deletes one or more
38  * mappings; merely changing the value associated with an existing key is not
39  * a structural modification.) This is typically accomplished by
40  * synchronizing on some object that naturally encapsulates the map. If no
41  * such object exists, the map should be "wrapped" using the
42  * <tt>Collections.synchronizedMap</tt> method. This is best done at creation
43  * time, to prevent accidental unsynchronized access to the map:
44  * <pre>
45  * Map m = Collections.synchronizedMap(new TreeMap(...));
46  * </pre><p>
47  *
48  * The iterators returned by all of this class's "collection view methods" are
49  * <i>fail-fast</i>: if the map is structurally modified at any time after the
50  * iterator is created, in any way except through the iterator's own
51  * <tt>remove</tt> or <tt>add</tt> methods, the iterator throws a
52  * <tt>ConcurrentModificationException</tt>. Thus, in the face of concurrent
53  * modification, the iterator fails quickly and cleanly, rather than risking
54  * arbitrary, non-deterministic behavior at an undetermined time in the
55  * future.
56  *
57  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
58  * as it is, generally speaking, impossible to make any hard guarantees in the
59  * presence of unsynchronized concurrent modification. Fail-fast iterators
60  * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
61  * Therefore, it would be wrong to write a program that depended on this
62  * exception for its correctness: <i>the fail-fast behavior of iterators
63  * should be used only to detect bugs.</i><p>
64  *
65  * This class is a member of the
66  * <a HREF="{@docRoot}/../guide/collections/index.html">
67  * Java Collections Framework</a>.
68  *
69  * @author Josh Bloch and Doug Lea
70  * @version 1.65, 02/19/04
71  * @see Map
72  * @see HashMap
73  * @see Hashtable
74  * @see Comparable
75  * @see Comparator
76  * @see Collection
77  * @see Collections#synchronizedMap(Map)
78  * @since 1.2
79  */
80
81 public class TreeMap<K,V>
82     extends AbstractMap <K,V>
83     implements SortedMap <K,V>, Cloneable , java.io.Serializable
84 {
85     /**
86      * The Comparator used to maintain order in this TreeMap, or
87      * null if this TreeMap uses its elements natural ordering.
88      *
89      * @serial
90      */
91     private Comparator <? super K> comparator = null;
92
93     private transient Entry<K,V> root = null;
94
95     /**
96      * The number of entries in the tree
97      */
98     private transient int size = 0;
99
100     /**
101      * The number of structural modifications to the tree.
102      */
103     private transient int modCount = 0;
104
105     private void incrementSize() { modCount++; size++; }
106     private void decrementSize() { modCount++; size--; }
107
108     /**
109      * Constructs a new, empty map, sorted according to the keys' natural
110      * order. All keys inserted into the map must implement the
111      * <tt>Comparable</tt> interface. Furthermore, all such keys must be
112      * <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw a
113      * ClassCastException for any elements <tt>k1</tt> and <tt>k2</tt> in the
114      * map. If the user attempts to put a key into the map that violates this
115      * constraint (for example, the user attempts to put a string key into a
116      * map whose keys are integers), the <tt>put(Object key, Object
117      * value)</tt> call will throw a <tt>ClassCastException</tt>.
118      *
119      * @see Comparable
120      */
121     public TreeMap() {
122     }
123
124     /**
125      * Constructs a new, empty map, sorted according to the given comparator.
126      * All keys inserted into the map must be <i>mutually comparable</i> by
127      * the given comparator: <tt>comparator.compare(k1, k2)</tt> must not
128      * throw a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
129      * <tt>k2</tt> in the map. If the user attempts to put a key into the
130      * map that violates this constraint, the <tt>put(Object key, Object
131      * value)</tt> call will throw a <tt>ClassCastException</tt>.
132      *
133      * @param c the comparator that will be used to sort this map. A
134      * <tt>null</tt> value indicates that the keys' <i>natural
135      * ordering</i> should be used.
136      */
137     public TreeMap(Comparator <? super K> c) {
138         this.comparator = c;
139     }
140
141     /**
142      * Constructs a new map containing the same mappings as the given map,
143      * sorted according to the keys' <i>natural order</i>. All keys inserted
144      * into the new map must implement the <tt>Comparable</tt> interface.
145      * Furthermore, all such keys must be <i>mutually comparable</i>:
146      * <tt>k1.compareTo(k2)</tt> must not throw a <tt>ClassCastException</tt>
147      * for any elements <tt>k1</tt> and <tt>k2</tt> in the map. This method
148      * runs in n*log(n) time.
149      *
150      * @param m the map whose mappings are to be placed in this map.
151      * @throws ClassCastException the keys in t are not Comparable, or
152      * are not mutually comparable.
153      * @throws NullPointerException if the specified map is null.
154      */
155     public TreeMap(Map <? extends K, ? extends V> m) {
156         putAll(m);
157     }
158
159     /**
160      * Constructs a new map containing the same mappings as the given
161      * <tt>SortedMap</tt>, sorted according to the same ordering. This method
162      * runs in linear time.
163      *
164      * @param m the sorted map whose mappings are to be placed in this map,
165      * and whose comparator is to be used to sort this map.
166      * @throws NullPointerException if the specified sorted map is null.
167      */
168     public TreeMap(SortedMap <K, ? extends V> m) {
169         comparator = m.comparator();
170         try {
171             buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
172         } catch (java.io.IOException cannotHappen) {
173         } catch (ClassNotFoundException cannotHappen) {
174         }
175     }
176
177
178     // Query Operations
179
180     /**
181      * Returns the number of key-value mappings in this map.
182      *
183      * @return the number of key-value mappings in this map.
184      */
185     public int size() {
186         return size;
187     }
188
189     /**
190      * Returns <tt>true</tt> if this map contains a mapping for the specified
191      * key.
192      *
193      * @param key key whose presence in this map is to be tested.
194      *
195      * @return <tt>true</tt> if this map contains a mapping for the
196      * specified key.
197      * @throws ClassCastException if the key cannot be compared with the keys
198      * currently in the map.
199      * @throws NullPointerException key is <tt>null</tt> and this map uses
200      * natural ordering, or its comparator does not tolerate
201      * <tt>null</tt> keys.
202      */
203     public boolean containsKey(Object key) {
204         return getEntry(key) != null;
205     }
206
207     /**
208      * Returns <tt>true</tt> if this map maps one or more keys to the
209      * specified value. More formally, returns <tt>true</tt> if and only if
210      * this map contains at least one mapping to a value <tt>v</tt> such
211      * that <tt>(value==null ? v==null : value.equals(v))</tt>. This
212      * operation will probably require time linear in the Map size for most
213      * implementations of Map.
214      *
215      * @param value value whose presence in this Map is to be tested.
216      * @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
217      * <tt>false</tt> otherwise.
218      * @since 1.2
219      */
220     public boolean containsValue(Object value) {
221         return (root==null ? false :
222                 (value==null ? valueSearchNull(root)
223                              : valueSearchNonNull(root, value)));
224     }
225
226     private boolean valueSearchNull(Entry n) {
227         if (n.value == null)
228             return true;
229
230         // Check left and right subtrees for value
231 return (n.left != null && valueSearchNull(n.left)) ||
232                (n.right != null && valueSearchNull(n.right));
233     }
234
235     private boolean valueSearchNonNull(Entry n, Object value) {
236         // Check this node for the value
237 if (value.equals(n.value))
238             return true;
239
240         // Check left and right subtrees for value
241 return (n.left != null && valueSearchNonNull(n.left, value)) ||
242                (n.right != null && valueSearchNonNull(n.right, value));
243     }
244
245     /**
246      * Returns the value to which this map maps the specified key. Returns
247      * <tt>null</tt> if the map contains no mapping for this key. A return
248      * value of <tt>null</tt> does not <i>necessarily</i> indicate that the
249      * map contains no mapping for the key; it's also possible that the map
250      * explicitly maps the key to <tt>null</tt>. The <tt>containsKey</tt>
251      * operation may be used to distinguish these two cases.
252      *
253      * @param key key whose associated value is to be returned.
254      * @return the value to which this map maps the specified key, or
255      * <tt>null</tt> if the map contains no mapping for the key.
256      * @throws ClassCastException key cannot be compared with the keys
257      * currently in the map.
258      * @throws NullPointerException key is <tt>null</tt> and this map uses
259      * natural ordering, or its comparator does not tolerate
260      * <tt>null</tt> keys.
261      *
262      * @see #containsKey(Object)
263      */
264     public V get(Object key) {
265         Entry<K,V> p = getEntry(key);
266         return (p==null ? null : p.value);
267     }
268
269     /**
270      * Returns the comparator used to order this map, or <tt>null</tt> if this
271      * map uses its keys' natural order.
272      *
273      * @return the comparator associated with this sorted map, or
274      * <tt>null</tt> if it uses its keys' natural sort method.
275      */
276     public Comparator <? super K> comparator() {
277         return comparator;
278     }
279
280     /**
281      * Returns the first (lowest) key currently in this sorted map.
282      *
283      * @return the first (lowest) key currently in this sorted map.
284      * @throws NoSuchElementException Map is empty.
285      */
286     public K firstKey() {
287         return key(firstEntry());
288     }
289
290     /**
291      * Returns the last (highest) key currently in this sorted map.
292      *
293      * @return the last (highest) key currently in this sorted map.
294      * @throws NoSuchElementException Map is empty.
295      */
296     public K lastKey() {
297         return key(lastEntry());
298     }
299
300     /**
301      * Copies all of the mappings from the specified map to this map. These
302      * mappings replace any mappings that this map had for any of the keys
303      * currently in the specified map.
304      *
305      * @param map mappings to be stored in this map.
306      * @throws ClassCastException class of a key or value in the specified
307      * map prevents it from being stored in this map.
308      *
309      * @throws NullPointerException if the given map is <tt>null</tt> or
310      * this map does not permit <tt>null</tt> keys and a
311      * key in the specified map is <tt>null</tt>.
312      */
313     public void putAll(Map <? extends K, ? extends V> map) {
314         int mapSize = map.size();
315         if (size==0 && mapSize!=0 && map instanceof SortedMap ) {
316             Comparator c = ((SortedMap )map).comparator();
317             if (c == comparator || (c != null && c.equals(comparator))) {
318         ++modCount;
319         try {
320             buildFromSorted(mapSize, map.entrySet().iterator(),
321                     null, null);
322         } catch (java.io.IOException cannotHappen) {
323         } catch (ClassNotFoundException cannotHappen) {
324         }
325         return;
326             }
327         }
328         super.putAll(map);
329     }
330
331     /**
332      * Returns this map's entry for the given key, or <tt>null</tt> if the map
333      * does not contain an entry for the key.
334      *
335      * @return this map's entry for the given key, or <tt>null</tt> if the map
336      * does not contain an entry for the key.
337      * @throws ClassCastException if the key cannot be compared with the keys
338      * currently in the map.
339      * @throws NullPointerException key is <tt>null</tt> and this map uses
340      * natural order, or its comparator does not tolerate *
341      * <tt>null</tt> keys.
342      */
343     private Entry<K,V> getEntry(Object key) {
344         Entry<K,V> p = root;
345     K k = (K) key;
346         while (p != null) {
347             int cmp = compare(k, p.key);
348             if (cmp == 0)
349                 return p;
350             else if (cmp < 0)
351                 p = p.left;
352             else
353                 p = p.right;
354         }
355         return null;
356     }
357
358     /**
359      * Gets the entry corresponding to the specified key; if no such entry
360      * exists, returns the entry for the least key greater than the specified
361      * key; if no such entry exists (i.e., the greatest key in the Tree is less
362      * than the specified key), returns <tt>null</tt>.
363      */
364     private Entry<K,V> getCeilEntry(K key) {
365         Entry<K,V> p = root;
366         if (p==null)
367             return null;
368
369         while (true) {
370             int cmp = compare(key, p.key);
371             if (cmp == 0) {
372                 return p;
373             } else if (cmp < 0) {
374                 if (p.left != null)
375                     p = p.left;
376                 else
377                     return p;
378             } else {
379                 if (p.right != null) {
380                     p = p.right;
381                 } else {
382                     Entry<K,V> parent = p.parent;
383                     Entry<K,V> ch = p;
384                     while (parent != null && ch == parent.right) {
385                         ch = parent;
386                         parent = parent.parent;
387                     }
388                     return parent;
389                 }
390             }
391         }
392     }
393
394     /**
395      * Returns the entry for the greatest key less than the specified key; if
396      * no such entry exists (i.e., the least key in the Tree is greater than
397      * the specified key), returns <tt>null</tt>.
398      */
399     private Entry<K,V> getPrecedingEntry(K key) {
400         Entry<K,V> p = root;
401         if (p==null)
402             return null;
403
404         while (true) {
405             int cmp = compare(key, p.key);
406             if (cmp > 0) {
407                 if (p.right != null)
408                     p = p.right;
409                 else
410                     return p;
411             } else {
412                 if (p.left != null) {
413                     p = p.left;
414                 } else {
415                     Entry<K,V> parent = p.parent;
416                     Entry<K,V> ch = p;
417                     while (parent != null && ch == parent.left) {
418                         ch = parent;
419                         parent = parent.parent;
420                     }
421                     return parent;
422                 }
423             }
424         }
425     }
426
427     /**
428      * Returns the key corresponding to the specified Entry. Throw
429      * NoSuchElementException if the Entry is <tt>null</tt>.
430      */
431     private static <K> K key(Entry<K,?> e) {
432         if (e==null)
433             throw new NoSuchElementException ();
434         return e.key;
435     }
436
437     /**
438      * Associates the specified value with the specified key in this map.
439      * If the map previously contained a mapping for this key, the old
440      * value is replaced.
441      *
442      * @param key key with which the specified value is to be associated.
443      * @param value value to be associated with the specified key.
444      *
445      * @return previous value associated with specified key, or <tt>null</tt>
446      * if there was no mapping for key. A <tt>null</tt> return can
447      * also indicate that the map previously associated <tt>null</tt>
448      * with the specified key.
449      * @throws ClassCastException key cannot be compared with the keys
450      * currently in the map.
451      * @throws NullPointerException key is <tt>null</tt> and this map uses
452      * natural order, or its comparator does not tolerate
453      * <tt>null</tt> keys.
454      */
455     public V put(K key, V value) {
456         Entry<K,V> t = root;
457
458         if (t == null) {
459             incrementSize();
460             root = new Entry<K,V>(key, value, null);
461             return null;
462        }
463
464         while (true) {
465             int cmp = compare(key, t.key);
466             if (cmp == 0) {
467                 return t.setValue(value);
468             } else if (cmp < 0) {
469                 if (t.left != null) {
470                     t = t.left;
471                 } else {
472                     incrementSize();
473                     t.left = new Entry<K,V>(key, value, t);
474                     fixAfterInsertion(t.left);
475                     return null;
476                 }
477             } else { // cmp > 0
478 if (t.right != null) {
479                     t = t.right;
480                 } else {
481                     incrementSize();
482                     t.right = new Entry<K,V>(key, value, t);
483                     fixAfterInsertion(t.right);
484                     return null;
485                 }
486             }
487         }
488     }
489
490     /**
491      * Removes the mapping for this key from this TreeMap if present.
492      *
493      * @param key key for which mapping should be removed
494      * @return previous value associated with specified key, or <tt>null</tt>
495      * if there was no mapping for key. A <tt>null</tt> return can
496      * also indicate that the map previously associated
497      * <tt>null</tt> with the specified key.
498      *
499      * @throws ClassCastException key cannot be compared with the keys
500      * currently in the map.
501      * @throws NullPointerException key is <tt>null</tt> and this map uses
502      * natural order, or its comparator does not tolerate
503      * <tt>null</tt> keys.
504      */
505     public V remove(Object key) {
506         Entry<K,V> p = getEntry(key);
507         if (p == null)
508             return null;
509
510         V oldValue = p.value;
511         deleteEntry(p);
512         return oldValue;
513     }
514
515     /**
516      * Removes all mappings from this TreeMap.
517      */
518     public void clear() {
519         modCount++;
520         size = 0;
521         root = null;
522     }
523
524     /**
525      * Returns a shallow copy of this <tt>TreeMap</tt> instance. (The keys and
526      * values themselves are not cloned.)
527      *
528      * @return a shallow copy of this Map.
529      */
530     public Object clone() {
531         TreeMap <K,V> clone = null;
532         try {
533             clone = (TreeMap <K,V>) super.clone();
534         } catch (CloneNotSupportedException e) {
535             throw new InternalError ();
536         }
537
538         // Put clone into "virgin" state (except for comparator)
539 clone.root = null;
540         clone.size = 0;
541         clone.modCount = 0;
542         clone.entrySet = null;
543
544         // Initialize clone with our mappings
545 try {
546             clone.buildFromSorted(size, entrySet().iterator(), null, null);
547         } catch (java.io.IOException cannotHappen) {
548         } catch (ClassNotFoundException cannotHappen) {
549         }
550
551         return clone;
552     }
553
554
555     // Views
556
557     /**
558      * This field is initialized to contain an instance of the entry set
559      * view the first time this view is requested. The view is stateless,
560      * so there's no reason to create more than one.
561      */
562     private transient volatile Set <Map.Entry <K,V>> entrySet = null;
563
564     /**
565      * Returns a Set view of the keys contained in this map. The set's
566      * iterator will return the keys in ascending order. The map is backed by
567      * this <tt>TreeMap</tt> instance, so changes to this map are reflected in
568      * the Set, and vice-versa. The Set supports element removal, which
569      * removes the corresponding mapping from the map, via the
570      * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>,
571      * <tt>retainAll</tt>, and <tt>clear</tt> operations. It does not support
572      * the <tt>add</tt> or <tt>addAll</tt> operations.
573      *
574      * @return a set view of the keys contained in this TreeMap.
575      */
576     public Set <K> keySet() {
577         if (keySet == null) {
578             keySet = new AbstractSet <K>() {
579                 public Iterator <K> iterator() {
580                     return new KeyIterator();
581                 }
582
583                 public int size() {
584                     return TreeMap.this.size();
585                 }
586
587                 public boolean contains(Object o) {
588                     return containsKey(o);
589                 }
590
591                 public boolean remove(Object o) {
592                     int oldSize = size;
593                     TreeMap.this.remove(o);
594                     return size != oldSize;
595                 }
596
597                 public void clear() {
598                     TreeMap.this.clear();
599                 }
600             };
601         }
602         return keySet;
603     }
604
605     /**
606      * Returns a collection view of the values contained in this map. The
607      * collection's iterator will return the values in the order that their
608      * corresponding keys appear in the tree. The collection is backed by
609      * this <tt>TreeMap</tt> instance, so changes to this map are reflected in
610      * the collection, and vice-versa. The collection supports element
611      * removal, which removes the corresponding mapping from the map through
612      * the <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
613      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
614      * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
615      *
616      * @return a collection view of the values contained in this map.
617      */
618     public Collection <V> values() {
619         if (values == null) {
620             values = new AbstractCollection <V>() {
621                 public Iterator <V> iterator() {
622                     return new ValueIterator();
623                 }
624
625                 public int size() {
626                     return TreeMap.this.size();
627                 }
628
629                 public boolean contains(Object o) {
630                     for (Entry<K,V> e = firstEntry(); e != null; e = successor(e))
631                         if (valEquals(e.getValue(), o))
632                             return true;
633                     return false;
634                 }
635
636                 public boolean remove(Object o) {
637                     for (Entry<K,V> e = firstEntry(); e != null; e = successor(e)) {
638                         if (valEquals(e.getValue(), o)) {
639                             deleteEntry(e);
640                             return true;
641                         }
642                     }
643                     return false;
644                 }
645
646                 public void clear() {
647                     TreeMap.this.clear();
648                 }
649             };
650         }
651         return values;
652     }
653
654     /**
655      * Returns a set view of the mappings contained in this map. The set's
656      * iterator returns the mappings in ascending key order. Each element in
657      * the returned set is a <tt>Map.Entry</tt>. The set is backed by this
658      * map, so changes to this map are reflected in the set, and vice-versa.
659      * The set supports element removal, which removes the corresponding
660      * mapping from the TreeMap, through the <tt>Iterator.remove</tt>,
661      * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
662      * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
663      * <tt>addAll</tt> operations.
664      *
665      * @return a set view of the mappings contained in this map.
666      * @see Map.Entry
667      */
668     public Set <Map.Entry <K,V>> entrySet() {
669         if (entrySet == null) {
670             entrySet = new AbstractSet <Map.Entry <K,V>>() {
671         public Iterator <Map.Entry <K,V>> iterator() {
672                     return new EntryIterator();
673                 }
674
675                 public boolean contains(Object o) {
676                     if (!(o instanceof Map.Entry ))
677                         return false;
678                     Map.Entry <K,V> entry = (Map.Entry <K,V>) o;
679             V value = entry.getValue();
680                     Entry<K,V> p = getEntry(entry.getKey());
681                     return p != null && valEquals(p.getValue(), value);
682                 }
683
684                 public boolean remove(Object o) {
685                     if (!(o instanceof Map.Entry ))
686                         return false;
687                     Map.Entry <K,V> entry = (Map.Entry <K,V>) o;
688             V value = entry.getValue();
689                     Entry<K,V> p = getEntry(entry.getKey());
690                     if (p != null && valEquals(p.getValue(), value)) {
691                         deleteEntry(p);
692                         return true;
693                     }
694                     return false;
695                 }
696
697                 public int size() {
698                     return TreeMap.this.size();
699                 }
700
701                 public void clear() {
702                     TreeMap.this.clear();
703                 }
704             };
705         }
706         return entrySet;
707     }
708
709     /**
710      * Returns a view of the portion of this map whose keys range from
711      * <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive. (If
712      * <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned sorted map
713      * is empty.) The returned sorted map is backed by this map, so changes
714      * in the returned sorted map are reflected in this map, and vice-versa.
715      * The returned sorted map supports all optional map operations.<p>
716      *
717      * The sorted map returned by this method will throw an
718      * <tt>IllegalArgumentException</tt> if the user attempts to insert a key
719      * less than <tt>fromKey</tt> or greater than or equal to
720      * <tt>toKey</tt>.<p>
721      *
722      * Note: this method always returns a <i>half-open range</i> (which
723      * includes its low endpoint but not its high endpoint). If you need a
724      * <i>closed range</i> (which includes both endpoints), and the key type
725      * allows for calculation of the successor a given key, merely request the
726      * subrange from <tt>lowEndpoint</tt> to <tt>successor(highEndpoint)</tt>.
727      * For example, suppose that <tt>m</tt> is a sorted map whose keys are
728      * strings. The following idiom obtains a view containing all of the
729      * key-value mappings in <tt>m</tt> whose keys are between <tt>low</tt>
730      * and <tt>high</tt>, inclusive:
731      * <pre> SortedMap sub = m.submap(low, high+"\0");</pre>
732      * A similar technique can be used to generate an <i>open range</i> (which
733      * contains neither endpoint). The following idiom obtains a view
734      * containing all of the key-value mappings in <tt>m</tt> whose keys are
735      * between <tt>low</tt> and <tt>high</tt>, exclusive:
736      * <pre> SortedMap sub = m.subMap(low+"\0", high);</pre>
737      *
738      * @param fromKey low endpoint (inclusive) of the subMap.
739      * @param toKey high endpoint (exclusive) of the subMap.
740      *
741      * @return a view of the portion of this map whose keys range from
742      * <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.
743      *
744      * @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>
745      * cannot be compared to one another using this map's comparator
746      * (or, if the map has no comparator, using natural ordering).
747      * @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
748      * <tt>toKey</tt>.
749      * @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
750      * <tt>null</tt> and this map uses natural order, or its
751      * comparator does not tolerate <tt>null</tt> keys.
752      */
753     public SortedMap <K,V> subMap(K fromKey, K toKey) {
754         return new SubMap(fromKey, toKey);
755     }
756
757     /**
758      * Returns a view of the portion of this map whose keys are strictly less
759      * than <tt>toKey</tt>. The returned sorted map is backed by this map, so
760      * changes in the returned sorted map are reflected in this map, and
761      * vice-versa. The returned sorted map supports all optional map
762      * operations.<p>
763      *
764      * The sorted map returned by this method will throw an
765      * <tt>IllegalArgumentException</tt> if the user attempts to insert a key
766      * greater than or equal to <tt>toKey</tt>.<p>
767      *
768      * Note: this method always returns a view that does not contain its
769      * (high) endpoint. If you need a view that does contain this endpoint,
770      * and the key type allows for calculation of the successor a given key,
771      * merely request a headMap bounded by <tt>successor(highEndpoint)</tt>.
772      * For example, suppose that suppose that <tt>m</tt> is a sorted map whose
773      * keys are strings. The following idiom obtains a view containing all of
774      * the key-value mappings in <tt>m</tt> whose keys are less than or equal
775      * to <tt>high</tt>:
776      * <pre>
777      * SortedMap head = m.headMap(high+"\0");
778      * </pre>
779      *
780      * @param toKey high endpoint (exclusive) of the headMap.
781      * @return a view of the portion of this map whose keys are strictly
782      * less than <tt>toKey</tt>.
783      *
784      * @throws ClassCastException if <tt>toKey</tt> is not compatible
785      * with this map's comparator (or, if the map has no comparator,
786      * if <tt>toKey</tt> does not implement <tt>Comparable</tt>).
787      * @throws IllegalArgumentException if this map is itself a subMap,
788      * headMap, or tailMap, and <tt>toKey</tt> is not within the
789      * specified range of the subMap, headMap, or tailMap.
790      * @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt> and
791      * this map uses natural order, or its comparator does not
792      * tolerate <tt>null</tt> keys.
793      */
794     public SortedMap <K,V> headMap(K toKey) {
795         return new SubMap(toKey, true);
796     }
797
798     /**
799      * Returns a view of the portion of this map whose keys are greater than
800      * or equal to <tt>fromKey</tt>. The returned sorted map is backed by
801      * this map, so changes in the returned sorted map are reflected in this
802      * map, and vice-versa. The returned sorted map supports all optional map
803      * operations.<p>
804      *
805      * The sorted map returned by this method will throw an
806      * <tt>IllegalArgumentException</tt> if the user attempts to insert a key
807      * less than <tt>fromKey</tt>.<p>
808      *
809      * Note: this method always returns a view that contains its (low)
810      * endpoint. If you need a view that does not contain this endpoint, and
811      * the element type allows for calculation of the successor a given value,
812      * merely request a tailMap bounded by <tt>successor(lowEndpoint)</tt>.
813      * For example, suppose that <tt>m</tt> is a sorted map whose keys
814      * are strings. The following idiom obtains a view containing
815      * all of the key-value mappings in <tt>m</tt> whose keys are strictly
816      * greater than <tt>low</tt>: <pre>
817      * SortedMap tail = m.tailMap(low+"\0");
818      * </pre>
819      *
820      * @param fromKey low endpoint (inclusive) of the tailMap.
821      * @return a view of the portion of this map whose keys are greater
822      * than or equal to <tt>fromKey</tt>.
823      * @throws ClassCastException if <tt>fromKey</tt> is not compatible
824      * with this map's comparator (or, if the map has no comparator,
825      * if <tt>fromKey</tt> does not implement <tt>Comparable</tt>).
826      * @throws IllegalArgumentException if this map is itself a subMap,
827      * headMap, or tailMap, and <tt>fromKey</tt> is not within the
828      * specified range of the subMap, headMap, or tailMap.
829      * @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt> and
830      * this map uses natural order, or its comparator does not
831      * tolerate <tt>null</tt> keys.
832      */
833     public SortedMap <K,V> tailMap(K fromKey) {
834         return new SubMap(fromKey, false);
835     }
836
837     private class SubMap
838     extends AbstractMap <K,V>
839     implements SortedMap <K,V>, java.io.Serializable {
840         private static final long serialVersionUID = -6520786458950516097L;
841
842         /**
843          * fromKey is significant only if fromStart is false. Similarly,
844          * toKey is significant only if toStart is false.
845          */
846         private boolean fromStart = false, toEnd = false;
847         private K fromKey, toKey;
848
849         SubMap(K fromKey, K toKey) {
850             if (compare(fromKey, toKey) > 0)
851                 throw new IllegalArgumentException ("fromKey > toKey");
852             this.fromKey = fromKey;
853             this.toKey = toKey;
854         }
855
856         SubMap(K key, boolean headMap) {
857             compare(key, key); // Type-check key
858
859             if (headMap) {
860                 fromStart = true;
861                 toKey = key;
862             } else {
863                 toEnd = true;
864                 fromKey = key;
865             }
866         }
867
868         SubMap(boolean fromStart, K fromKey, boolean toEnd, K toKey) {
869             this.fromStart = fromStart;
870             this.fromKey= fromKey;
871             this.toEnd = toEnd;
872             this.toKey = toKey;
873         }
874
875         public boolean isEmpty() {
876             return entrySet.isEmpty();
877      &nbs