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         }
878 
879         public boolean containsKey(Object   key) {
880             return inRange((K) key) && TreeMap.this.containsKey(key);
881         }
882 
883         public V get(Object   key) {
884             if (!inRange((K) key))
885                 return null;
886             return TreeMap.this.get(key);
887         }
888 
889         public V put(K key, V value) {
890             if (!inRange(key))
891                 throw new IllegalArgumentException  ("key out of range");
892             return TreeMap.this.put(key, value);
893         }
894 
895         public Comparator  <? super K> comparator() {
896             return comparator;
897         }
898 
899         public K firstKey() {
900         TreeMap.Entry  <K,V> e = fromStart ? firstEntry() : getCeilEntry(fromKey);
901             K first = key(e);
902             if (!toEnd && compare(first, toKey) >= 0)
903                 throw(new NoSuchElementException  ());
904             return first;
905         }
906 
907         public K lastKey() {
908         TreeMap.Entry  <K,V> e = toEnd ? lastEntry() : getPrecedingEntry(toKey);
909             K last = key(e);
910             if (!fromStart && compare(last, fromKey) < 0)
911                 throw(new NoSuchElementException  ());
912             return last;
913         }
914 
915         private transient Set  <Map.Entry  <K,V>> entrySet = new EntrySetView();
916 
917         public Set  <Map.Entry  <K,V>> entrySet() {
918             return entrySet;
919         }
920 
921         private class EntrySetView extends AbstractSet  <Map.Entry  <K,V>> {
922             private transient int size = -1, sizeModCount;
923 
924             public int size() {
925                 if (size == -1 || sizeModCount != TreeMap.this.modCount) {
926                     size = 0;  sizeModCount = TreeMap.this.modCount;
927                     Iterator   i = iterator();
928                     while (i.hasNext()) {
929                         size++;
930                         i.next();
931                     }
932                 }
933                 return size;
934             }
935 
936             public boolean isEmpty() {
937                 return !iterator().hasNext();
938             }
939 
940             public boolean contains(Object   o) {
941                 if (!(o instanceof Map.Entry  ))
942                     return false;
943                 Map.Entry  <K,V> entry = (Map.Entry  <K,V>) o;
944                 K key = entry.getKey();
945                 if (!inRange(key))
946                     return false;
947                 TreeMap.Entry   node = getEntry(key);
948                 return node != null &&
949                        valEquals(node.getValue(), entry.getValue());
950             }
951 
952             public boolean remove(Object   o) {
953                 if (!(o instanceof Map.Entry  ))
954                     return false;
955                 Map.Entry  <K,V> entry = (Map.Entry  <K,V>) o;
956                 K key = entry.getKey();
957                 if (!inRange(key))
958                     return false;
959                 TreeMap.Entry  <K,V> node = getEntry(key);
960                 if (node!=null && valEquals(node.getValue(),entry.getValue())){
961                     deleteEntry(node);
962                     return true;
963                 }
964                 return false;
965             }
966 
967             public Iterator  <Map.Entry  <K,V>> iterator() {
968                 return new SubMapEntryIterator(
969                     (fromStart ? firstEntry() : getCeilEntry(fromKey)),
970                     (toEnd     ? null         : getCeilEntry(toKey)));
971             }
972         }
973 
974         public SortedMap  <K,V> subMap(K fromKey, K toKey) {
975             if (!inRange2(fromKey))
976                 throw new IllegalArgumentException  ("fromKey out of range");
977             if (!inRange2(toKey))
978                 throw new IllegalArgumentException  ("toKey out of range");
979             return new SubMap(fromKey, toKey);
980         }
981 
982         public SortedMap  <K,V> headMap(K toKey) {
983             if (!inRange2(toKey))
984                 throw new IllegalArgumentException  ("toKey out of range");
985             return new SubMap(fromStart, fromKey, false, toKey);
986         }
987 
988         public SortedMap  <K,V> tailMap(K fromKey) {
989             if (!inRange2(fromKey))
990                 throw new IllegalArgumentException  ("fromKey out of range");
991             return new SubMap(false, fromKey, toEnd, toKey);
992         }
993 
994         private boolean inRange(K key) {
995             return (fromStart || compare(key, fromKey) >= 0) &&
996                    (toEnd     || compare(key, toKey)   <  0);
997         }
998 
999         // This form allows the high endpoint (as well as all legit keys)
1000        private boolean inRange2(K key) {
1001            return (fromStart || compare(key, fromKey) >= 0) &&
1002                   (toEnd     || compare(key, toKey)   <= 0);
1003        }
1004    }
1005
1006    /**
1007     * TreeMap Iterator.
1008     */
1009    private abstract class PrivateEntryIterator<T> implements Iterator  <T> {
1010        private int expectedModCount = TreeMap.this.modCount;
1011        private Entry<K,V> lastReturned = null;
1012        Entry<K,V> next;
1013
1014        PrivateEntryIterator() {
1015            next = firstEntry();
1016        }
1017
1018        // Used by SubMapEntryIterator
1019        PrivateEntryIterator(Entry<K,V> first) {
1020            next = first;
1021        }
1022
1023        public boolean hasNext() {
1024            return next != null;
1025        }
1026
1027        final Entry<K,V> nextEntry() {
1028            if (next == null)
1029                throw new NoSuchElementException  ();
1030            if (modCount != expectedModCount)
1031                throw new ConcurrentModificationException  ();
1032            lastReturned = next;
1033            next = successor(next);
1034            return lastReturned;
1035        }
1036
1037        public void remove() {
1038            if (lastReturned == null)
1039                throw new IllegalStateException  ();
1040            if (modCount != expectedModCount)
1041                throw new ConcurrentModificationException  ();
1042            if (lastReturned.left != null && lastReturned.right != null)
1043                next = lastReturned;
1044            deleteEntry(lastReturned);
1045            expectedModCount++;
1046            lastReturned = null;
1047        }
1048    }
1049
1050    private class EntryIterator extends PrivateEntryIterator<Map.Entry  <K,V>> {
1051        public Map.Entry  <K,V> next() {
1052            return nextEntry();
1053        }
1054    }
1055
1056    private class KeyIterator extends PrivateEntryIterator<K> {
1057        public K next() {
1058            return nextEntry().key;
1059        }
1060    }
1061
1062    private class ValueIterator extends PrivateEntryIterator<V> {
1063        public V next() {
1064            return nextEntry().value;
1065        }
1066    }
1067
1068    private class SubMapEntryIterator extends PrivateEntryIterator<Map.Entry  <K,V>> {
1069        private final K firstExcludedKey;
1070
1071        SubMapEntryIterator(Entry<K,V> first, Entry<K,V> firstExcluded) {
1072            super(first);
1073            firstExcludedKey = (firstExcluded == null
1074                ? null
1075                : firstExcluded.key);
1076        }
1077
1078        public boolean hasNext() {
1079            return next != null && next.key != firstExcludedKey;
1080        }
1081
1082        public Map.Entry  <K,V> next() {
1083            if (next == null || next.key == firstExcludedKey)
1084                throw new NoSuchElementException  ();
1085            return nextEntry();
1086        }
1087    }
1088
1089    /**
1090     * Compares two keys using the correct comparison method for this TreeMap.
1091     */
1092    private int compare(K k1, K k2) {
1093        return (comparator==null ? ((Comparable  </*-*/K>)k1).compareTo(k2)
1094                                 : comparator.compare((K)k1, (K)k2));
1095    }
1096
1097    /**
1098     * Test two values  for equality.  Differs from o1.equals(o2) only in
1099     * that it copes with <tt>null</tt> o1 properly.
1100     */
1101    private static boolean valEquals(Object   o1, Object   o2) {
1102        return (o1==null ? o2==null : o1.equals(o2));
1103    }
1104
1105    private static final boolean RED   = false;
1106    private static final boolean BLACK = true;
1107
1108    /**
1109     * Node in the Tree.  Doubles as a means to pass key-value pairs back to
1110     * user (see Map.Entry).
1111     */
1112
1113    static class Entry<K,V> implements Map.Entry  <K,V> {
1114    K key;
1115        V value;
1116        Entry<K,V> left = null;
1117        Entry<K,V> right = null;
1118        Entry<K,V> parent;
1119        boolean color = BLACK;
1120
1121        /**
1122         * Make a new cell with given key, value, and parent, and with
1123         * <tt>null</tt> child links, and BLACK color.
1124         */
1125        Entry(K key, V value, Entry<K,V> parent) {
1126            this.key = key;
1127            this.value = value;
1128            this.parent = parent;
1129        }
1130
1131        /**
1132         * Returns the key.
1133         *
1134         * @return the key.
1135         */
1136        public K getKey() {
1137            return key;
1138        }
1139
1140        /**
1141         * Returns the value associated with the key.
1142         *
1143         * @return the value associated with the key.
1144         */
1145        public V getValue() {
1146            return value;
1147        }
1148
1149        /**
1150         * Replaces the value currently associated with the key with the given
1151         * value.
1152         *
1153         * @return the value associated with the key before this method was
1154         *           called.
1155         */
1156        public V setValue(V value) {
1157            V oldValue = this.value;
1158            this.value = value;
1159            return oldValue;
1160        }
1161
1162        public boolean equals(Object   o) {
1163            if (!(o instanceof Map.Entry  ))
1164                return false;
1165            Map.Entry   e = (Map.Entry  )o;
1166
1167            return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
1168        }
1169
1170        public int hashCode() {
1171            int keyHash = (key==null ? 0 : key.hashCode());
1172            int valueHash = (value==null ? 0 : value.hashCode());
1173            return keyHash ^ valueHash;
1174        }
1175
1176        public String   toString() {
1177            return key + "=" + value;
1178        }
1179    }
1180
1181    /**
1182     * Returns the first Entry in the TreeMap (according to the TreeMap's
1183     * key-sort function).  Returns null if the TreeMap is empty.
1184     */
1185    private Entry<K,V> firstEntry() {
1186        Entry<K,V> p = root;
1187        if (p != null)
1188            while (p.left != null)
1189                p = p.left;
1190        return p;
1191    }
1192
1193    /**
1194     * Returns the last Entry in the TreeMap (according to the TreeMap's
1195     * key-sort function).  Returns null if the TreeMap is empty.
1196     */
1197    private Entry<K,V> lastEntry() {
1198        Entry<K,V> p = root;
1199        if (p != null)
1200            while (p.right != null)
1201                p = p.right;
1202        return p;
1203    }
1204
1205    /**
1206     * Returns the successor of the specified Entry, or null if no such.
1207     */
1208    private Entry<K,V> successor(Entry<K,V> t) {
1209        if (t == null)
1210            return null;
1211        else if (t.right != null) {
1212            Entry<K,V> p = t.right;
1213            while (p.left != null)
1214                p = p.left;
1215            return p;
1216        } else {
1217            Entry<K,V> p = t.parent;
1218            Entry<K,V> ch = t;
1219            while (p != null && ch == p.right) {
1220                ch = p;
1221                p = p.parent;
1222            }
1223            return p;
1224        }
1225    }
1226
1227    /**
1228     * Balancing operations.
1229     *
1230     * Implementations of rebalancings during insertion and deletion are
1231     * slightly different than the CLR version.  Rather than using dummy
1232     * nilnodes, we use a set of accessors that deal properly with null.  They
1233     * are used to avoid messiness surrounding nullness checks in the main
1234     * algorithms.
1235     */
1236
1237    private static <K,V> boolean colorOf(Entry<K,V> p) {
1238        return (p == null ? BLACK : p.color);
1239    }
1240
1241    private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {
1242        return (p == null ? null: p.parent);
1243    }
1244
1245    private static <K,V> void setColor(Entry<K,V> p, boolean c) {
1246        if (p != null)
1247        p.color = c;
1248    }
1249
1250    private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
1251        return (p == null) ? null: p.left;
1252    }
1253
1254    private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {
1255        return (p == null) ? null: p.right;
1256    }
1257
1258    /** From CLR **/
1259    private void rotateLeft(Entry<K,V> p) {
1260        Entry<K,V> r = p.right;
1261        p.right = r.left;
1262        if (r.left != null)
1263            r.left.parent = p;
1264        r.parent = p.parent;
1265        if (p.parent == null)
1266            root = r;
1267        else if (p.parent.left == p)
1268            p.parent.left = r;
1269        else
1270            p.parent.right = r;
1271        r.left = p;
1272        p.parent = r;
1273    }
1274
1275    /** From CLR **/
1276    private void rotateRight(Entry<K,V> p) {
1277        Entry<K,V> l = p.left;
1278        p.left = l.right;
1279        if (l.right != null) l.right.parent = p;
1280        l.parent = p.parent;
1281        if (p.parent == null)
1282            root = l;
1283        else if (p.parent.right == p)
1284            p.parent.right = l;
1285        else p.parent.left = l;
1286        l.right = p;
1287        p.parent = l;
1288    }
1289
1290
1291    /** From CLR **/
1292    private void fixAfterInsertion(Entry<K,V> x) {
1293        x.color = RED;
1294
1295        while (x != null && x != root && x.parent.color == RED) {
1296            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
1297                Entry<K,V> y = rightOf(parentOf(parentOf(x)));
1298                if (colorOf(y) == RED) {
1299                    setColor(parentOf(x), BLACK);
1300                    setColor(y, BLACK);
1301                    setColor(parentOf(parentOf(x)), RED);
1302                    x = parentOf(parentOf(x));
1303                } else {
1304                    if (x == rightOf(parentOf(x))) {
1305                        x = parentOf(x);
1306                        rotateLeft(x);
1307                    }
1308                    setColor(parentOf(x), BLACK);
1309                    setColor(parentOf(parentOf(x)), RED);
1310                    if (parentOf(parentOf(x)) != null)
1311                        rotateRight(parentOf(parentOf(x)));
1312                }
1313            } else {
1314                Entry<K,V> y = leftOf(parentOf(parentOf(x)));
1315                if (colorOf(y) == RED) {
1316                    setColor(parentOf(x), BLACK);
1317                    setColor(y, BLACK);
1318                    setColor(parentOf(parentOf(x)), RED);
1319                    x = parentOf(parentOf(x));
1320                } else {
1321                    if (x == leftOf(parentOf(x))) {
1322                        x = parentOf(x);
1323                        rotateRight(x);
1324                    }
1325                    setColor(parentOf(x),  BLACK);
1326                    setColor(parentOf(parentOf(x)), RED);
1327                    if (parentOf(parentOf(x)) != null)
1328                        rotateLeft(parentOf(parentOf(x)));
1329                }
1330            }
1331        }
1332        root.color = BLACK;
1333    }
1334
1335    /**
1336     * Delete node p, and then rebalance the tree.
1337     */
1338
1339    private void deleteEntry(Entry<K,V> p) {
1340        decrementSize();
1341
1342        // If strictly internal, copy successor's element to p and then make p
1343        // point to successor.
1344        if (p.left != null && p.right != null) {
1345            Entry<K,V> s = successor (p);
1346            p.key = s.key;
1347            p.value = s.value;
1348            p = s;
1349        } // p has 2 children
1350
1351        // Start fixup at replacement node, if it exists.
1352        Entry<K,V> replacement = (p.left != null ? p.left : p.right);
1353
1354        if (replacement != null) {
1355            // Link replacement to parent
1356            replacement.parent = p.parent;
1357            if (p.parent == null)
1358                root = replacement;
1359            else if (p == p.parent.left)
1360                p.parent.left  = replacement;
1361            else
1362                p.parent.right = replacement;
1363
1364            // Null out links so they are OK to use by fixAfterDeletion.
1365            p.left = p.right = p.parent = null;
1366
1367            // Fix replacement
1368            if (p.color == BLACK)
1369                fixAfterDeletion(replacement);
1370        } else if (p.parent == null) { // return if we are the only node.
1371            root = null;
1372        } else { //  No children. Use self as phantom replacement and unlink.
1373            if (p.color == BLACK)
1374                fixAfterDeletion(p);
1375
1376            if (p.parent != null) {
1377                if (p == p.parent.left)
1378                    p.parent.left = null;
1379                else if (p == p.parent.right)
1380                    p.parent.right = null;
1381                p.parent = null;
1382            }
1383        }
1384    }
1385
1386    /** From CLR **/
1387    private void fixAfterDeletion(Entry<K,V> x) {
1388        while (x != root && colorOf(x) == BLACK) {
1389            if (x == leftOf(parentOf(x))) {
1390                Entry<K,V> sib = rightOf(parentOf(x));
1391
1392                if (colorOf(sib) == RED) {
1393                    setColor(sib, BLACK);
1394                    setColor(parentOf(x), RED);
1395                    rotateLeft(parentOf(x));
1396                    sib = rightOf(parentOf(x));
1397                }
1398
1399                if (colorOf(leftOf(sib))  == BLACK &&
1400                    colorOf(rightOf(sib)) == BLACK) {
1401                    setColor(sib,  RED);
1402                    x = parentOf(x);
1403                } else {
1404                    if (colorOf(rightOf(sib)) == BLACK) {
1405                        setColor(leftOf(sib), BLACK);
1406                        setColor(sib, RED);
1407                        rotateRight(sib);
1408                        sib = rightOf(parentOf(x));
1409                    }
1410                    setColor(sib, colorOf(parentOf(x)));
1411                    setColor(parentOf(x), BLACK);
1412                    setColor(rightOf(sib), BLACK);
1413                    rotateLeft(parentOf(x));
1414                    x = root;
1415                }
1416            } else { // symmetric
1417                Entry<K,V> sib = leftOf(parentOf(x));
1418
1419                if (colorOf(sib) == RED) {
1420                    setColor(sib, BLACK);
1421                    setColor(parentOf(x), RED);
1422                    rotateRight(parentOf(x));
1423                    sib = leftOf(parentOf(x));
1424                }
1425
1426                if (colorOf(rightOf(sib)) == BLACK &&
1427                    colorOf(leftOf(sib)) == BLACK) {
1428                    setColor(sib,  RED);
1429                    x = parentOf(x);
1430                } else {
1431                    if (colorOf(leftOf(sib)) == BLACK) {
1432                        setColor(rightOf(sib), BLACK);
1433                        setColor(sib, RED);
1434                        rotateLeft(sib);
1435                        sib = leftOf(parentOf(x));
1436                    }
1437                    setColor(sib, colorOf(parentOf(x)));
1438                    setColor(parentOf(x), BLACK);
1439                    setColor(leftOf(sib), BLACK);
1440                    rotateRight(parentOf(x));
1441                    x = root;
1442                }
1443            }
1444        }
1445
1446        setColor(x, BLACK);
1447    }
1448
1449    private static final long serialVersionUID = 919286545866124006L;
1450
1451    /**
1452     * Save the state of the <tt>TreeMap</tt> instance to a stream (i.e.,
1453     * serialize it).
1454     *
1455     * @serialData The <i>size</i> of the TreeMap (the number of key-value
1456     *             mappings) is emitted (int), followed by the key (Object)
1457     *             and value (Object) for each key-value mapping represented
1458     *             by the TreeMap. The key-value mappings are emitted in
1459     *             key-order (as determined by the TreeMap's Comparator,
1460     *             or by the keys' natural ordering if the TreeMap has no
1461     *             Comparator).
1462     */
1463    private void writeObject(java.io.ObjectOutputStream   s)
1464        throws java.io.IOException   {
1465        // Write out the Comparator and any hidden stuff
1466        s.defaultWriteObject();
1467
1468        // Write out size (number of Mappings)
1469        s.writeInt(size);
1470
1471        // Write out keys and values (alternating)
1472        for (Iterator  <Map.Entry  <K,V>> i = entrySet().iterator(); i.hasNext(); ) {
1473            Map.Entry  <K,V> e = i.next();
1474            s.writeObject(e.getKey());
1475            s.writeObject(e.getValue());
1476        }
1477    }
1478
1479
1480
1481    /**
1482     * Reconstitute the <tt>TreeMap</tt> instance from a stream (i.e.,
1483     * deserialize it).
1484     */
1485    private void readObject(final java.io.ObjectInputStream   s)
1486        throws java.io.IOException  , ClassNotFoundException   {
1487        // Read in the Comparator and any hidden stuff
1488        s.defaultReadObject();
1489
1490        // Read in size
1491        int size = s.readInt();
1492
1493        buildFromSorted(size, null, s, null);
1494    }
1495
1496    /** Intended to be called only from TreeSet.readObject **/
1497    void readTreeSet(int size, java.io.ObjectInputStream   s, V defaultVal)
1498        throws java.io.IOException  , ClassNotFoundException   {
1499        buildFromSorted(size, null, s, defaultVal);
1500    }
1501
1502    /** Intended to be called only from TreeSet.addAll **/
1503    void addAllForTreeSet(SortedSet  <Map.Entry  <K,V>> set, V defaultVal) {
1504    try {
1505        buildFromSorted(set.size(), set.iterator(), null, defaultVal);
1506    } catch (java.io.IOException   cannotHappen) {
1507    } catch (ClassNotFoundException   cannotHappen) {
1508    }
1509    }
1510
1511
1512    /**
1513     * Linear time tree building algorithm from sorted data.  Can accept keys
1514     * and/or values from iterator or stream. This leads to too many
1515     * parameters, but seems better than alternatives.  The four formats
1516     * that this method accepts are:
1517     *
1518     *    1) An iterator of Map.Entries.  (it != null, defaultVal == null).
1519     *    2) An iterator of keys.         (it != null, defaultVal != null).
1520     *    3) A stream of alternating serialized keys and values.
1521     *                                   (it == null, defaultVal == null).
1522     *    4) A stream of serialized keys. (it == null, defaultVal != null).
1523     *
1524     * It is assumed that the comparator of the TreeMap is already set prior
1525     * to calling this method.
1526     *
1527     * @param size the number of keys (or key-value pairs) to be read from
1528     *        the iterator or stream.
1529     * @param it If non-null, new entries are created from entries
1530     *        or keys read from this iterator.
1531     * @param str If non-null, new entries are created from keys and
1532     *        possibly values read from this stream in serialized form.
1533     *        Exactly one of it and str should be non-null.
1534     * @param defaultVal if non-null, this default value is used for
1535     *        each value in the map.  If null, each value is read from
1536     *        iterator or stream, as described above.
1537     * @throws IOException propagated from stream reads. This cannot
1538     *         occur if str is null.
1539     * @throws ClassNotFoundException propagated from readObject.
1540     *         This cannot occur if str is null.
1541     */
1542    private
1543    void buildFromSorted(int size, Iterator   it,
1544             java.io.ObjectInputStream   str,
1545             V defaultVal)
1546        throws  java.io.IOException  , ClassNotFoundException   {
1547        this.size = size;
1548        root =
1549        buildFromSorted(0, 0, size-1, computeRedLevel(size),
1550                it, str, defaultVal);
1551    }
1552
1553    /**
1554     * Recursive "helper method" that does the real work of the
1555     * of the previous method.  Identically named parameters have
1556     * identical definitions.  Additional parameters are documented below.
1557     * It is assumed that the comparator and size fields of the TreeMap are
1558     * already set prior to calling this method.  (It ignores both fields.)
1559     *
1560     * @param level the current level of tree. Initial call should be 0.
1561     * @param lo the first element index of this subtree. Initial should be 0.
1562     * @param hi the last element index of this subtree.  Initial should be
1563     *              size-1.
1564     * @param redLevel the level at which nodes should be red.
1565     *        Must be equal to computeRedLevel for tree of this size.
1566     */
1567    private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
1568                         int redLevel,
1569                         Iterator   it,
1570                         java.io.ObjectInputStream   str,
1571                         V defaultVal)
1572        throws  java.io.IOException  , ClassNotFoundException   {
1573        /*
1574         * Strategy: The root is the middlemost element. To get to it, we
1575         * have to first recursively construct the entire left subtree,
1576         * so as to grab all of its elements. We can then proceed with right
1577         * subtree.
1578         *
1579         * The lo and hi arguments are the minimum and maximum
1580         * indices to pull out of the iterator or stream for current subtree.
1581         * They are not actually indexed, we just proceed sequentially,
1582         * ensuring that items are extracted in corresponding order.
1583         */
1584
1585        if (hi < lo) return null;
1586
1587        int mid = (lo + hi) / 2;
1588
1589        Entry<K,V> left  = null;
1590        if (lo < mid)
1591            left = buildFromSorted(level+1, lo, mid - 1, redLevel,
1592                   it, str, defaultVal);
1593
1594        // extract key and/or value from iterator or stream
1595        K key;
1596        V value;
1597        if (it != null) {
1598            if (defaultVal==null) {
1599                Map.Entry  <K,V> entry = (Map.Entry  <K,V>)it.next();
1600                key = entry.getKey();
1601                value = entry.getValue();
1602            } else {
1603                key = (K)it.next();
1604                value = defaultVal;
1605            }
1606        } else { // use stream
1607            key = (K) str.readObject();
1608            value = (defaultVal != null ? defaultVal : (V) str.readObject());
1609        }
1610
1611        Entry<K,V> middle =  new Entry<K,V>(key, value, null);
1612
1613        // color nodes in non-full bottommost level red
1614        if (level == redLevel)
1615            middle.color = RED;
1616
1617        if (left != null) {
1618            middle.left = left;
1619            left.parent = middle;
1620        }
1621
1622        if (mid < hi) {
1623            Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
1624                           it, str, defaultVal);
1625            middle.right = right;
1626            right.parent = middle;
1627        }
1628
1629        return middle;
1630    }
1631
1632    /**
1633     * Find the level down to which to assign all nodes BLACK.  This is the
1634     * last `full' level of the complete binary tree produced by
1635     * buildTree. The remaining nodes are colored RED. (This makes a `nice'
1636     * set of color assignments wrt future insertions.) This level number is
1637     * computed by finding the number of splits needed to reach the zeroeth
1638     * node.  (The answer is ~lg(N), but in any case must be computed by same
1639     * quick O(lg(N)) loop.)
1640     */
1641    private static int computeRedLevel(int sz) {
1642        int level = 0;
1643        for (int m = sz - 1; m >= 0; m = m / 2 - 1)
1644            level++;
1645        return level;
1646    }
1647}
1648
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags