Java > Open Source Codes > com > jofti > util > ValueTreeMap


1 package com.jofti.util;
2
3 import java.util.AbstractCollection ;
4 import java.util.AbstractMap ;
5 import java.util.AbstractSet ;
6 import java.util.ArrayList ;
7 import java.util.Collection ;
8 import java.util.Comparator ;
9 import java.util.ConcurrentModificationException ;
10 import java.util.HashMap ;
11 import java.util.Iterator ;
12 import java.util.List ;
13 import java.util.Map ;
14 import java.util.NoSuchElementException ;
15 import java.util.Set ;
16 import java.util.SortedMap ;
17 import java.util.SortedSet ;
18
19
20 /*
21  * @(#)TreeMap.java 1.56 03/01/23
22  *
23  * Copyright 2003 Sun Microsystems, Inc. All rights reserved.
24  * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
25  */
26
27
28 /**
29
30  *
31  * This class is a modified version of the TreeMap class from the
32  * Java Collections Framework</a>.
33  * <p>
34  * The changes are to allow SQL type multi-attribute sorting by ordering the entries based on a
35  * modified comparator/search method that allows value ordering as well as key ordering. However, this slightly breaks
36  * the Map semantics as it enables two objects with the same key to be placed in the Map. As this class is not desgned as a general
37  * Map this is not a problem as it should be used as am immutable result Map. This may be formalised more closely later on.
38  * </p>
39  *
40  * @author Steve Woodcock
41  * @author Josh Bloch and Doug Lea
42  * @version 1.56, 01/23/03
43  * @see Map
44  * @see HashMap
45  * @see Hashtable
46  * @see Comparable
47  * @see Comparator
48  * @see Collection
49  * @see Collections#synchronizedMap(Map)
50  * @since 1.2
51  */
52
53 public class ValueTreeMap extends AbstractMap
54                      implements Cloneable , java.io.Serializable
55 {
56     /**
57      * The Comparator used to maintain order in this TreeMap, or
58      * null if this TreeMap uses its elements natural ordering.
59      *
60      * @serial
61      */
62     
63     private final DefaultComparator DEFAULT_COMPARATOR = new DefaultComparator();
64     private Comparator comparator = DEFAULT_COMPARATOR;
65
66     private transient Entry root = null;
67
68     /**
69      * The number of entries in the tree
70      */
71     private transient int size = 0;
72
73     /**
74      * The number of structural modifications to the tree.
75      */
76     private transient int modCount = 0;
77
78     private void incrementSize() { modCount++; size++; }
79     private void decrementSize() { modCount++; size--; }
80
81     //override the ones in the super class as they are not visible
82 transient volatile Set keySet = null;
83     transient volatile Collection values = null;
84       
85     
86    
87     /**
88      * Constructs a new, empty map, sorted according to the keys' natural
89      * order. All keys inserted into the map must implement the
90      * <tt>Comparable</tt> interface. Furthermore, all such keys must be
91      * <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw a
92      * ClassCastException for any elements <tt>k1</tt> and <tt>k2</tt> in the
93      * map. If the user attempts to put a key into the map that violates this
94      * constraint (for example, the user attempts to put a string key into a
95      * map whose keys are integers), the <tt>put(Object key, Object
96      * value)</tt> call will throw a <tt>ClassCastException</tt>.
97      *
98      * @see Comparable
99      */
100     public ValueTreeMap() {
101     }
102
103     /**
104      * Constructs a new, empty map, sorted according to the given comparator.
105      * All keys inserted into the map must be <i>mutually comparable</i> by
106      * the given comparator: <tt>comparator.compare(k1, k2)</tt> must not
107      * throw a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
108      * <tt>k2</tt> in the map. If the user attempts to put a key into the
109      * map that violates this constraint, the <tt>put(Object key, Object
110      * value)</tt> call will throw a <tt>ClassCastException</tt>.
111      *
112      * @param c the comparator that will be used to sort this map. A
113      * <tt>null</tt> value indicates that the keys' <i>natural
114      * ordering</i> should be used.
115      */
116     public ValueTreeMap(Comparator c) {
117         this.comparator = c;
118     }
119
120     /**
121      * Constructs a new map containing the same mappings as the given map,
122      * sorted according to the keys' <i>natural order</i>. All keys inserted
123      * into the new map must implement the <tt>Comparable</tt> interface.
124      * Furthermore, all such keys must be <i>mutually comparable</i>:
125      * <tt>k1.compareTo(k2)</tt> must not throw a <tt>ClassCastException</tt>
126      * for any elements <tt>k1</tt> and <tt>k2</tt> in the map. This method
127      * runs in n*log(n) time.
128      *
129      * @param m the map whose mappings are to be placed in this map.
130      * @throws ClassCastException the keys in t are not Comparable, or
131      * are not mutually comparable.
132      * @throws NullPointerException if the specified map is null.
133      */
134     public ValueTreeMap(Map m) {
135         putAll(m);
136     }
137
138     /**
139      * Constructs a new map containing the same mappings as the given
140      * <tt>SortedMap</tt>, sorted according to the same ordering. This method
141      * runs in linear time.
142      *
143      * @param m the sorted map whose mappings are to be placed in this map,
144      * and whose comparator is to be used to sort this map.
145      * @throws NullPointerException if the specified sorted map is null.
146      */
147     public ValueTreeMap(SortedMap m) {
148         comparator = m.comparator();
149         try {
150             buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
151         } catch (java.io.IOException cannotHappen) {
152         } catch (ClassNotFoundException cannotHappen) {
153         }
154     }
155
156
157     // Query Operations
158
159     /**
160      * Returns the number of key-value mappings in this map.
161      *
162      * @return the number of key-value mappings in this map.
163      */
164     public int size() {
165         return size;
166     }
167
168     /**
169      * Returns <tt>true</tt> if this map contains a mapping for the specified
170      * key.
171      *
172      * @param key key whose presence in this map is to be tested.
173      *
174      * @return <tt>true</tt> if this map contains a mapping for the
175      * specified key.
176      * @throws ClassCastException if the key cannot be compared with the keys
177      * currently in the map.
178      * @throws NullPointerException key is <tt>null</tt> and this map uses
179      * natural ordering, or its comparator does not tolerate
180      * <tt>null</tt> keys.
181      */
182     public boolean containsKey(Object key) {
183         return getEntry(key) != null;
184     }
185
186     /**
187      * Returns <tt>true</tt> if this map maps one or more keys to the
188      * specified value. More formally, returns <tt>true</tt> if and only if
189      * this map contains at least one mapping to a value <tt>v</tt> such
190      * that <tt>(value==null ? v==null : value.equals(v))</tt>. This
191      * operation will probably require time linear in the Map size for most
192      * implementations of Map.
193      *
194      * @param value value whose presence in this Map is to be tested.
195      * @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
196      * <tt>false</tt> otherwise.
197      * @since 1.2
198      */
199     public boolean containsValue(Object value) {
200         return (root==null ? false :
201                 (value==null ? valueSearchNull(root)
202                              : valueSearchNonNull(root, value)));
203     }
204
205     private boolean valueSearchNull(Entry n) {
206         if (n.value == null)
207             return true;
208
209         // Check left and right subtrees for value
210 return (n.left != null && valueSearchNull(n.left)) ||
211                (n.right != null && valueSearchNull(n.right));
212     }
213
214     private boolean valueSearchNonNull(Entry n, Object value) {
215         // Check this node for the value
216 if (value.equals(n.value))
217             return true;
218
219         // Check left and right subtrees for value
220 return (n.left != null && valueSearchNonNull(n.left, value)) ||
221                (n.right != null && valueSearchNonNull(n.right, value));
222     }
223
224     private Entry keySearchNonNull(Entry n, Object key) {
225         // Check this node for the value
226 if (key.equals(n.key))
227             return n;
228
229         Entry temp =null;
230         if (n.left != null ){
231             temp= keySearchNonNull(n.left, key);
232         }if (temp == null && n.right != null){
233             temp=keySearchNonNull(n.right, key);
234         }else if (temp ==null){
235             return null;
236         }
237         return temp;
238     }
239     
240     
241     private Entry keyGetListNonNull(Entry n, Object key,List values) {
242         // Check this node for the value
243 if (key.equals(n.key)){
244             values.add(n.value);
245         }
246         Entry temp =null;
247         if (n.left != null ){
248             temp= keyGetListNonNull(n.left, key,values);
249         }if (temp ==null && n.right != null){
250             temp=keyGetListNonNull(n.right, key,values);
251         }else{
252             return null;
253         }
254         return temp;
255     }
256     
257     /**
258      * Returns the value to which this map maps the specified key. Returns
259      * <tt>null</tt> if the map contains no mapping for this key. A return
260      * value of <tt>null</tt> does not <i>necessarily</i> indicate that the
261      * map contains no mapping for the key; it's also possible that the map
262      * explicitly maps the key to <tt>null</tt>. The <tt>containsKey</tt>
263      * operation may be used to distinguish these two cases.
264      *
265      * @param key key whose associated value is to be returned.
266      * @return the value to which this map maps the specified key, or
267      * <tt>null</tt> if the map contains no mapping for the key.
268      * @throws ClassCastException key cannot be compared with the keys
269      * currently in the map.
270      * @throws NullPointerException key is <tt>null</tt> and this map uses
271      * natural ordering, or its comparator does not tolerate
272      * <tt>null</tt> keys.
273      *
274      * @see #containsKey(Object)
275      */
276     public Object get(Object key) {
277         return getEntryList(key);
278     }
279
280     /**
281      * Returns the comparator used to order this map, or <tt>null</tt> if this
282      * map uses its keys' natural order.
283      *
284      * @return the comparator associated with this sorted map, or
285      * <tt>null</tt> if it uses its keys' natural sort method.
286      */
287     public Comparator comparator() {
288         return comparator;
289     }
290
291     /**
292      * Returns the first (lowest) key currently in this sorted map.
293      *
294      * @return the first (lowest) key currently in this sorted map.
295      * @throws NoSuchElementException Map is empty.
296      */
297     public Object firstKey() {
298         return key(firstEntry());
299     }
300
301     /**
302      * Returns the last (highest) key currently in this sorted map.
303      *
304      * @return the last (highest) key currently in this sorted map.
305      * @throws NoSuchElementException Map is empty.
306      */
307     public Object lastKey() {
308         return key(lastEntry());
309     }
310
311     /**
312      
313      */
314     public void putAll(Map map) {
315         throw new UnsupportedOperationException ("ValueTreeMap is readonly");
316     }
317
318     /**
319      * Returns this map's entry for the given key, or <tt>null</tt> if the map
320      * does not contain an entry for the key.
321      *
322      * @return this map's entry for the given key, or <tt>null</tt> if the map
323      * does not contain an entry for the key.
324      * @throws ClassCastException if the key cannot be compared with the keys
325      * currently in the map.
326      * @throws NullPointerException key is <tt>null</tt> and this map uses
327      * natural order, or its comparator does not tolerate *
328      * <tt>null</tt> keys.
329      */
330     private Entry getEntry(Object key) {
331         
332         
333         Entry p = root;
334         
335         // if we are ordered by keys then as normal
336 if (comparator == DEFAULT_COMPARATOR){
337         
338             Entry temp = new Entry(key,null,null);
339             while (p != null) {
340                 int cmp = compare(temp,p);
341                 if (cmp == 0)
342                     return p;
343                 else if (cmp < 0)
344                     p = p.left;
345                 else
346                     p = p.right;
347             }
348             return null;
349             // otherwise we need to search for the key
350 }else{
351             return (root==null ? null :
352                 (key==null ? null
353                              : keySearchNonNull(root, key)));
354         }
355         
356     }
357     
358  private List getEntryList(Object key) {
359         
360         
361         Entry p = root;
362         List tempList = new ArrayList ();
363         // if we are ordered by keys then as normal
364 if (comparator == DEFAULT_COMPARATOR){
365         
366             Entry temp = new Entry(key,null,null);
367             while (p != null) {
368                 int cmp = compare(temp,p);
369                 if (cmp == 0){
370                     tempList.add(p.value);
371                     return tempList;}
372                 else if (cmp < 0)
373                     p = p.left;
374                 else
375                     p = p.right;
376             }
377             return null;
378             // otherwise we need to search for the key
379 }else{
380             if (key ==null || root ==null){
381                 return tempList;
382             }else{
383                 keyGetListNonNull(root, key,tempList);
384                 return tempList;
385             }
386         }
387         
388     }
389  private Entry getTreeEntry(Map.Entry temp) {
390         
391         
392         Entry p = root;
393         
394             while (p != null) {
395                 int cmp = compare(temp,p);
396                 if (cmp == 0)
397                     return p;
398                 else if (cmp < 0)
399                     p = p.left;
400                 else
401                     p = p.right;
402             }
403             return null;
404         
405     }
406
407
408  /* *//**
409      * Gets the entry corresponding to the specified key; if no such entry
410      * exists, returns the entry for the least key greater than the specified
411      * key; if no such entry exists (i.e., the greatest key in the Tree is less
412      * than the specified key), returns <tt>null</tt>.
413      *//*
414     private Entry getCeilEntry(Object key) {
415         Entry p = root;
416         if (p==null)
417             return null;
418
419         Object o = valueMap.get(key);
420         
421         if (o ==null){
422             return null;
423         }
424         Entry temp = new Entry(key,o,null);
425         while (true) {
426             int cmp = compare(temp,p);
427             if (cmp == 0) {
428                 return p;
429             } else if (cmp < 0) {
430                 if (p.left != null)
431                     p = p.left;
432                 else
433                     return p;
434             } else {
435                 if (p.right != null) {
436                     p = p.right;
437                 } else {
438                     Entry parent = p.parent;
439                     Entry ch = p;
440                     while (parent != null && ch == parent.right) {
441                         ch = parent;
442                         parent = parent.parent;
443                     }
444                     return parent;
445                 }
446             }
447         }
448     }
449
450     *//**
451      * Returns the entry for the greatest key less than the specified key; if
452      * no such entry exists (i.e., the least key in the Tree is greater than
453      * the specified key), returns <tt>null</tt>.
454      *//*
455     private Entry getPrecedingEntry(Object key) {
456         Entry p = root;
457         if (p==null)
458             return null;
459         
460         Object o = valueMap.get(key);
461         
462         if (o ==null){
463             return null;
464         }
465         Entry temp = new Entry(key,o,null);
466         while (true) {
467             int cmp = compare(temp,p);
468             if (cmp > 0) {
469                 if (p.right != null)
470                     p = p.right;
471                 else
472                     return p;
473             } else {
474                 if (p.left != null) {
475                     p = p.left;
476                 } else {
477                     Entry parent = p.parent;
478                     Entry ch = p;
479                     while (parent != null && ch == parent.left) {
480                         ch = parent;
481                         parent = parent.parent;
482                     }
483                     return parent;
484                 }
485             }
486         }
487     }
488 */
489     /**
490      * Returns the key corresonding to the specified Entry. Throw
491      * NoSuchElementException if the Entry is <tt>null</tt>.
492      */
493     private static Object key(Entry e) {
494         if (e==null)
495             throw new NoSuchElementException ();
496         return e.key;
497     }
498
499     /**
500      * Associates the specified value with the specified key in this map.
501      * If the map previously contained a mapping for this key, the old
502      * value is replaced.
503      *
504      * @param key key with which the specified value is to be associated.
505      * @param value value to be associated with the specified key.
506      *
507      * @return previous value associated with specified key, or <tt>null</tt>
508      * if there was no mapping for key. A <tt>null</tt> return can
509      * also indicate that the map previously associated <tt>null</tt>
510      * with the specified key.
511      * @throws ClassCastException key cannot be compared with the keys
512      * currently in the map.
513      * @throws NullPointerException key is <tt>null</tt> and this map uses
514      * natural order, or its comparator does not tolerate
515      * <tt>null</tt> keys.
516      */
517     public Object put(Object key, Object value) {
518       
519         Entry t = root;
520
521         if (t == null) {
522             incrementSize();
523             root = new Entry(key, value, null);
524             return null;
525        }
526         Entry temp = new Entry(key,value,null);
527         while (true) {
528             int cmp = compare(temp, t);
529             if (cmp == 0) {
530                 return t.setValue(value);
531             } else if (cmp < 0) {
532                 if (t.left != null) {
533                     t = t.left;
534                 } else {
535                     incrementSize();
536                     
537                     t.left = new Entry(key, value, t);
538                     fixAfterInsertion(t.left);
539                     return null;
540                 }
541             } else { // cmp > 0
542 if (t.right != null) {
543                     t = t.right;
544                 } else {
545                     incrementSize();
546                     
547                     t.right = new Entry(key, value, t);
548                     fixAfterInsertion(t.right);
549                     return null;
550                 }
551             }
552         }
553     }
554
555     /**
556      * Removes the mapping for this key from this TreeMap if present.
557      *
558      * @param key key for which mapping should be removed
559      * @return previous value associated with specified key, or <tt>null</tt>
560      * if there was no mapping for key. A <tt>null</tt> return can
561      * also indicate that the map previously associated
562      * <tt>null</tt> with the specified key.
563      *
564      * @throws ClassCastException key cannot be compared with the keys
565      * currently in the map.
566      * @throws NullPointerException key is <tt>null</tt> and this map uses
567      * natural order, or its comparator does not tolerate
568      * <tt>null</tt> keys.
569      */
570     public Object remove(Object key) {
571         Entry p = getEntry(key);
572         List oldValues =new ArrayList ();
573         
574         while (p != null){
575             
576             oldValues.add(p.value);
577             deleteEntry(p);
578             p = getEntry(key);
579         }
580         return oldValues;
581     }
582
583     public Object removeEntry(Object key,Object value) {
584        Entry p = getTreeEntry(new Entry(key,value,null));
585         Object oldValue = p.value;
586         deleteEntry(p);
587         return oldValue;
588     }
589     /**
590      * Removes all mappings from this TreeMap.
591      */
592     public void clear() {
593         modCount++;
594         size = 0;
595         root = null;
596         
597     }
598
599     /**
600      * Returns a shallow copy of this <tt>TreeMap</tt> instance. (The keys and
601      * values themselves are not cloned.)
602      *
603      * @return a shallow copy of this Map.
604      */
605     public Object clone() {
606         ValueTreeMap clone = null;
607         try {
608             clone = (ValueTreeMap)super.clone();
609         } catch (CloneNotSupportedException e) {
610             throw new InternalError ();
611         }
612
613         // Put clone into "virgin" state (except for comparator)
614 clone.root = null;
615         clone.size = 0;
616         clone.modCount = 0;
617         clone.entrySet = null;
618
619         // Initialize clone with our mappings
620 try {
621             clone.buildFromSorted(size, entrySet().iterator(), null, null);
622         } catch (java.io.IOException cannotHappen) {
623         } catch (ClassNotFoundException cannotHappen) {
624         }
625         return clone;
626     }
627
628
629     // Views
630
631     /**
632      * This field is initialized to contain an instance of the entry set
633      * view the first time this view is requested. The view is stateless,
634      * so there's no reason to create more than one.
635      */
636     private transient volatile Set entrySet = null;
637
638     /**
639      * Returns a Set view of the keys contained in this map. The set's
640      * iterator will return the keys in ascending order. The map is backed by
641      * this <tt>TreeMap</tt> instance, so changes to this map are reflected in
642      * the Set, and vice-versa. The Set supports element removal, which
643      * removes the corresponding mapping from the map, via the
644      * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>,
645      * <tt>retainAll</tt>, and <tt>clear</tt> operations. It does not support
646      * the <tt>add</tt> or <tt>addAll</tt> operations.
647      *
648      * @return a set view of the keys contained in this TreeMap.
649      */
650     public Set keySet() {
651         if (keySet == null) {
652             keySet = new AbstractSet () {
653                 public Iterator iterator() {
654                     return new KeyIterator();
655                 }
656
657                 public int size() {
658                     return ValueTreeMap.this.size();
659                 }
660
661                 public boolean contains(Object o) {
662                     return containsKey(o);
663                 }
664
665                 public boolean remove(Object o) {
666                     if (o != null) {
667                         return ValueTreeMap.this.remove(o) ==null;
668                     }
669                     return false;
670                 }
671
672                 public void clear() {
673                     ValueTreeMap.this.clear();
674                 }
675             };
676         }
677         return keySet;
678     }
679
680     /**
681      * Returns a collection view of the values contained in this map. The
682      * collection's iterator will return the values in the order that their
683      * corresponding keys appear in the tree. The collection is backed by
684      * this <tt>TreeMap</tt> instance, so changes to this map are reflected in
685      * the collection, and vice-versa. The collection supports element
686      * removal, which removes the corresponding mapping from the map through
687      * the <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
688      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
689      * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
690      *
691      * @return a collection view of the values contained in this map.
692      */
693     public Collection values() {
694         if (values == null) {
695             values = new AbstractCollection () {
696                 public Iterator iterator() {
697                     return new ValueIterator();
698                 }
699
700                 public int size() {
701                     return ValueTreeMap.this.size();
702                 }
703
704                 public boolean contains(Object o) {
705                     for (Entry e = firstEntry(); e != null; e = successor(e))
706                         if (valEquals(e.getValue(), o))
707                             return true;
708                     return false;
709                 }
710
711                 public boolean remove(Object o) {
712                     for (Entry e = firstEntry(); e != null; e = successor(e)) {
713                         if (valEquals(e.getValue(), o)) {
714                             deleteEntry(e);
715                             return true;
716                         }
717                     }
718                     return false;
719                 }
720
721                 public void clear() {
722                     ValueTreeMap.this.clear();
723                 }
724             };
725         }
726         return values;
727     }
728
729     /**
730      * Returns a set view of the mappings contained in this map. The set's
731      * iterator returns the mappings in ascending key order. Each element in
732      * the returned set is a <tt>Map.Entry</tt>. The set is backed by this
733      * map, so changes to this map are reflected in the set, and vice-versa.
734      * The set supports element removal, which removes the corresponding
735      * mapping from the TreeMap, through the <tt>Iterator.remove</tt>,
736      * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
737      * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
738      * <tt>addAll</tt> operations.
739      *
740      * @return a set view of the mappings contained in this map.
741      * @see Map.Entry
742      */
743     public Set entrySet() {
744         if (entrySet == null) {
745             entrySet = new AbstractSet () {
746                 public Iterator iterator() {
747                     return new EntryIterator();
748                 }
749
750                 public boolean contains(Object o) {
751                     if (!(o instanceof Map.Entry ))
752                         return false;
753                     Map.Entry entry = (Map.Entry )o;
754                     
755                     Entry p = getTreeEntry(entry);
756                     return p != null;
757                 }
758
759                 public boolean remove(Object o) {
760                     if (!(o instanceof Map.Entry ))
761                         return false;
762                     Map.Entry entry = (Map.Entry )o;
763                     Entry p = getTreeEntry(entry);
764                     if (p != null) {
765                         deleteEntry(p);
766                        
767                         return true;
768                     }
769                     return false;
770                 }
771
772                 public int size() {
773                     return ValueTreeMap.this.size();
774                 }
775
776                 public void clear() {
777                     ValueTreeMap.this.clear();
778                 }
779             };
780         }
781         return entrySet;
782     }
783
784     /**
785      * Returns a view of the portion of this map whose keys range from
786      * <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive. (If
787      * <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned sorted map
788      * is empty.) The returned sorted map is backed by this map, so changes
789      * in the returned sorted map are reflected in this map, and vice-versa.
790      * The returned sorted map supports all optional map operations.<p>
791      *
792      * The sorted map returned by this method will throw an
793      * <tt>IllegalArgumentException</tt> if the user attempts to insert a key
794      * less than <tt>fromKey</tt> or greater than or equal to
795      * <tt>toKey</tt>.<p>
796      *
797      * Note: this method always returns a <i>half-open range</i> (which
798      * includes its low endpoint but not its high endpoint). If you need a
799      * <i>closed range</i> (which includes both endpoints), and the key type
800      * allows for calculation of the successor a given key, merely request the
801      * subrange from <tt>lowEndpoint</tt> to <tt>successor(highEndpoint)</tt>.
802      * For example, suppose that <tt>m</tt> is a sorted map whose keys are
803      * strings. The following idiom obtains a view containing all of the
804      * key-value mappings in <tt>m</tt> whose keys are between <tt>low</tt>
805      * and <tt>high</tt>, inclusive:
806      * <pre> SortedMap sub = m.submap(low, high+"\0");</pre>
807      * A similar technique can be used to generate an <i>open range</i> (which
808      * contains neither endpoint). The following idiom obtains a view
809      * containing all of the key-value mappings in <tt>m</tt> whose keys are
810      * between <tt>low</tt> and <tt>high</tt>, exclusive:
811      * <pre> SortedMap sub = m.subMap(low+"\0", high);</pre>
812      *
813      * @param fromKey low endpoint (inclusive) of the subMap.
814      * @param toKey high endpoint (exclusive) of the subMap.
815      *
816      * @return a view of the portion of this map whose keys range from
817      * <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.
818      *
819      * @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>
820      * cannot be compared to one another using this map's comparator
821      * (or, if the map has no comparator, using natural ordering).
822      * @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
823      * <tt>toKey</tt>.
824      * @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
825      * <tt>null</tt> and this map uses natural order, or its
826      * comparator does not tolerate <tt>null</tt> keys.
827      */
828   /* public SortedMap subMap(Object fromValue, Object toValue) {
829         return new SubMap(fromValue, toValue);
830     }
831
832     *//**
833      * Returns a view of the portion of this map whose keys are strictly less
834      * than <tt>toKey</tt>. The returned sorted map is backed by this map, so
835      * changes in the returned sorted map are reflected in this map, and
836      * vice-versa. The returned sorted map supports all optional map
837      * operations.<p>
838      *
839      * The sorted map returned by this method will throw an
840      * <tt>IllegalArgumentException</tt> if the user attempts to insert a key
841      * greater than or equal to <tt>toKey</tt>.<p>
842      *
843      * Note: this method always returns a view that does not contain its
844      * (high) endpoint. If you need a view that does contain this endpoint,
845      * and the key type allows for calculation of the successor a given key,
846      * merely request a headMap bounded by <tt>successor(highEndpoint)</tt>.
847      * For example, suppose that suppose that <tt>m</tt> is a sorted map whose
848      * keys are strings. The following idiom obtains a view containing all of
849      * the key-value mappings in <tt>m</tt> whose keys are less than or equal
850      * to <tt>high</tt>:
851      * <pre>
852      * SortedMap head = m.headMap(high+"\0");
853      * </pre>
854      *
855      * @param toKey high endpoint (exclusive) of the headMap.
856      * @return a view of the portion of this map whose keys are strictly
857      * less than <tt>toKey</tt>.
858      *
859      * @throws ClassCastException if <tt>toKey</tt> is not compatible
860      * with this map's comparator (or, if the map has no comparator,
861      * if <tt>toKey</tt> does not implement <tt>Comparable</tt>).
862      * @throws IllegalArgumentException if this map is itself a subMap,
863      * headMap, or tailMap, and <tt>toKey</tt> is not within the
864      * specified range of the subMap, headMap, or tailMap.
865      * @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt> and
866      * this map uses natural order, or its comparator does not
867      * tolerate <tt>null</tt> keys.
868      *//*
869     public SortedMap headMap(Object toValue) {
870         return new SubMap(toValue, true);
871     }
872
873     *//**
874      * Returns a view of the portion of this map whose keys are greater than
875      * or equal to <tt>fromKey</tt>. The returned sorted map is backed by
876      * this map, so changes in the returned sorted map are reflected in this
877      * map, and vice-versa. The returned sorted map supports all optional map
878      * operations.<p>
879      *
880      * The sorted map returned by this method will throw an
881      * <tt>IllegalArgumentException</tt> if the user attempts to insert a key
882      * less than <tt>fromKey</tt>.<p>
883      *
884      * Note: this method always returns a view that contains its (low)
885      * endpoint. If you need a view that does not contain this endpoint, and
886      * the element type allows for calculation of the successor a given value,
887      * merely request a tailMap bounded by <tt>successor(lowEndpoint)</tt>.
888      * For For example, suppose that suppose that <tt>m</tt> is a sorted map
889      * whose keys are strings. The following idiom obtains a view containing
890      * all of the key-value mappings in <tt>m</tt> whose keys are strictly
891      * greater than <tt>low</tt>: <pre>
892      * SortedMap tail = m.tailMap(low+"\0");
893      * </pre>
894      *
895      * @param fromKey low endpoint (inclusive) of the tailMap.
896      * @return a view of the portion of this map whose keys are greater
897      * than or equal to <tt>fromKey</tt>.
898      * @throws ClassCastException if <tt>fromKey</tt> is not compatible
899      * with this map's comparator (or, if the map has no comparator,
900      * if <tt>fromKey</tt> does not implement <tt>Comparable</tt>).
901      * @throws IllegalArgumentException if this map is itself a subMap,
902      * headMap, or tailMap, and <tt>fromKey</tt> is not within the
903      * specified range of the subMap, headMap, or tailMap.
904      * @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt> and
905      * this map uses natural order, or its comparator does not
906      * tolerate <tt>null</tt> keys.
907      *//*
908     public SortedMap tailMap(Object fromValue) {
909         return new SubMap(fromValue, false);
910     }
911
912     private class SubMap extends AbstractMap
913                              implements SortedMap, java.io.Serializable {
914         private static final long serialVersionUID = -6520786458950516097L;
915
916         *//**
917          * fromKey is significant only if fromStart is false. Similarly,
918          * toKey is significant only if toStart is false.
919          *//*
920         private boolean fromStart = false, toEnd = false;
921         private Object fromValue, toValue;
922
923         SubMap(Object fromKey, Object toKey) {
924             if (compare(fromKey, toKey) > 0)
925                 throw new IllegalArgumentException("fromKey > toKey");
926             this.fromKey = fromKey;
927             this.toKey = toKey;
928         }
929
930         SubMap(Object key, boolean headMap) {
931             compare(key, key); // Type-check key
932
933             if (headMap) {
934                 fromStart = true;
935                 toValue = key;
936             } else {
937                 toEnd = true;
938                 fromKey = key;
939             }
940         }
941
942         SubMap(boolean fromStart, Object fromKey, boolean toEnd, Object toKey){
943             this.fromStart = fromStart;
944             this.fromKey= fromKey;
945             this.toEnd = toEnd;
946             this.toKey = toKey;
947         }
948
949         public boolean isEmpty() {
950             return entrySet.isEmpty();
951         }
952
953         public boolean containsKey(Object key) {
954             return inRange(key) && ValueTreeMap.this.containsKey(key);
955         }
956
957         public Object get(Object key) {
958             if (!inRange(key))
959                 return null;
960             return ValueTreeMap.this.get(key);
961         }
962
963         public Object put(Object key, Object value) {
964             if (!inRange(key))
965                 throw new IllegalArgumentException("key out of range");
966             return ValueTreeMap.this.put(key, value);
967         }
968
969         public Comparator comparator() {
970             return comparator;
971         }
972
973         public Object firstKey() {
974             Object first = key(fromStart ? firstEntry():getCeilEntry(fromKey));
975             if (!toEnd && compare(first, toKey) >= 0)
976                 throw(new NoSuchElementException());
977             return first;
978         }
979
980         public Object lastKey() {
981             Object last = key(toEnd ? lastEntry() : getPrecedingEntry(toKey));
982             if (!fromStart && compare(last, fromKey) < 0)
983                 throw(new NoSuchElementException());
984             return last;
985         }
986
987         private transient Set entrySet = new EntrySetView();
988
989         public Set entrySet() {
990             return entrySet;
991         }
992
993         private class EntrySetView extends AbstractSet {
994             private transient int size = -1, sizeModCount;
995
996             public int size() {
997                 if (size == -1 || sizeModCount != ValueTreeMap.this.modCount) {
998                     size = 0; sizeModCount = ValueTreeMap.this.modCount;
999                     Iterator i = iterator();
1000                    while (i.hasNext()) {
1001                        size++;
1002                        i.next();
1003                    }
1004                }
1005                return size;
1006            }
1007
1008            public boolean isEmpty() {
1009                return !iterator().hasNext();
1010            }
1011
1012            public boolean contains(Object o) {
1013                if (!(o instanceof Map.Entry))
1014                    return false;
1015                Map.Entry entry = (Map.Entry)o;
1016                Object key = entry.getKey();
1017                if (!inRange(key))
1018                    return false;
1019                ValueTreeMap.Entry node = getEntry(key);
1020                return node != null &&
1021                       valEquals(node.getValue(), entry.getValue());
1022            }
1023
1024            public boolean remove(Object o) {
1025                if (!(o instanceof Map.Entry))
1026                    return false;
1027                Map.Entry entry = (Map.Entry)o;
1028                Object key = entry.getKey();
1029                if (!inRange(key))
1030                    return false;
1031                ValueTreeMap.Entry node = getEntry(key);
1032                if (node!=null && valEquals(node.getValue(),entry.getValue())){
1033                    deleteEntry(node);
1034                    return true;
1035                }
1036                return false;
1037            }
1038
1039            public Iterator iterator() {
1040                return new SubMapEntryIterator(
1041                    (fromStart ? firstEntry() : getCeilEntry(fromKey)),
1042                    (toEnd ? null : getCeilEntry(toKey)));
1043            }
1044        }
1045
1046        public SortedMap subMap(Object fromKey, Object toKey) {
1047            if (!inRange2(fromKey))
1048                throw new IllegalArgumentException("fromKey out of range");
1049            if (!inRange2(toKey))
1050                throw new IllegalArgumentException("toKey out of range");
1051            return new SubMap(fromKey, toKey);
1052        }
1053
1054        public SortedMap headMap(Object toKey) {
1055            if (!inRange2(toKey))
1056                throw new IllegalArgumentException("toKey out of range");
1057            return new SubMap(fromStart, fromKey, false, toKey);
1058        }
1059
1060        public SortedMap tailMap(Object fromKey) {
1061            if (!inRange2(fromKey))
1062                throw new IllegalArgumentException("fromKey out of range");
1063            return new SubMap(false, fromKey, toEnd, toKey);
1064        }
1065
1066        private boolean inRange(Object key) {
1067            return (fromStart || compare(key, fromKey) >= 0) &&
1068                   (toEnd || compare(key, toKey) < 0);
1069        }
1070
1071        // This form allows the high endpoint (as well as all legit keys)
1072        private boolean inRange2(Object key) {
1073            return (fromStart || compare(key, fromKey) >= 0) &&
1074                   (toEnd || compare(key, toKey) <= 0);
1075        }
1076    }
1077*/
1078    /**
1079     * TreeMap Iterator.
1080     */
1081    private class EntryIterator implements Iterator {
1082        private int expectedModCount = ValueTreeMap.this.modCount;
1083        private Entry lastReturned = null;
1084        Entry next;
1085
1086        EntryIterator() {
1087            next = firstEntry();
1088        }
1089
1090        // Used by SubMapEntryIterator
1091 EntryIterator(Entry first) {
1092            next = first;
1093        }
1094
1095        public boolean hasNext() {
1096            return next != null;
1097        }
1098
1099        final Entry nextEntry() {
1100            if (next == null)
1101                throw new NoSuchElementException ();
1102            if (modCount != expectedModCount)
1103                throw new ConcurrentModificationException ();
1104            lastReturned = next;
1105            next = successor(next);
1106            return lastReturned;
1107        }
1108
1109        public Object next() {
1110            return nextEntry();
1111        }
1112
1113        public void remove() {
1114            if (lastReturned == null)
1115                throw new IllegalStateException ();
1116            if (modCount != expectedModCount)
1117                throw new ConcurrentModificationException ();
1118            if (lastReturned.left != null && lastReturned.right != null)
1119                next = lastReturned;
1120            deleteEntry(lastReturned);
1121            expectedModCount++;
1122            lastReturned = null;
1123        }
1124    }
1125
1126    private class KeyIterator extends EntryIterator {
1127        public Object next() {
1128            return nextEntry().key;
1129        }
1130    }
1131
1132    private class ValueIterator extends EntryIterator {
1133        public Object next() {
1134            return nextEntry().value;
1135        }
1136    }
1137
1138    private class SubMapEntryIterator extends EntryIterator {
1139        private final Object firstExcludedKey;
1140
1141        SubMapEntryIterator(Entry first, Entry firstExcluded) {
1142            super(first);
1143            firstExcludedKey = (firstExcluded == null ?
1144                                firstExcluded : firstExcluded.key);
1145        }
1146
1147        public boolean hasNext() {
1148            return next != null && next.key != firstExcludedKey;
1149        }
1150
1151        public Object next() {
1152            if (next == null || next.key == firstExcludedKey)
1153                throw new NoSuchElementException ();
1154            return nextEntry();
1155        }
1156    }
1157
1158    /**
1159     * Compares two keys using the correct comparison method for this TreeMap.
1160     */
1161    private int compare(Map.Entry k1, Map.Entry k2) {
1162        int res = (comparator==null ? ((Comparable )k1.getKey()).compareTo(k2.getKey())
1163                                 : comparator.compare(k1, k2));
1164        if (res ==0 && comparator != DEFAULT_COMPARATOR){
1165            res =((Comparable )k1.getKey()).compareTo(k2.getKey());
1166        }
1167        return res;
1168    }
1169    
1170   
1171    /**
1172     * Test two values for equality. Differs from o1.equals(o2) only in
1173     * that it copes with with <tt>null</tt> o1 properly.
1174     */
1175    private static boolean valEquals(Object o1, Object o2) {
1176        return (o1==null ? o2==null : o1.equals(o2));
1177    }
1178
1179    private static final boolean RED = false;
1180    private static final boolean BLACK = true;
1181
1182    /**
1183     * Node in the Tree. Doubles as a means to pass key-value pairs back to
1184     * user (see Map.Entry).
1185     */
1186
1187    static class Entry implements Map.Entry {
1188        Object key;
1189        Object value;
1190        Entry left = null;
1191        Entry right = null;
1192        Entry parent;
1193        boolean color = BLACK;
1194
1195        /**
1196         * Make a new cell with given key, value, and parent, and with
1197         * <tt>null</tt> child links, and BLACK color.
1198         */
1199        Entry(Object key, Object value, Entry parent) {
1200            this.key = key;
1201            this.value = value;
1202            this.parent = parent;
1203        }
1204
1205        /**
1206         * Returns the key.
1207         *
1208         * @return the key.
1209         */
1210        public Object getKey() {
1211            return key;
1212        }
1213
1214        /**
1215         * Returns the value associated with the key.
1216         *
1217         * @return the value associated with the key.
1218         */
1219        public Object getValue() {
1220            return value;
1221        }
1222
1223        /**
1224         * Replaces the value currently associated with the key with the given
1225         * value.
1226         *
1227         * @return the value associated with the key before this method was
1228         * called.
1229         */
1230        public Object setValue(Object value) {
1231            Object oldValue = this.value;
1232            this.value = value;
1233            return oldValue;
1234        }
1235
1236        public boolean equals(Object o) {
1237            if (!(o instanceof Map.Entry ))
1238                return false;
1239            Map.Entry e = (Map.Entry )o;
1240
1241            return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
1242        }
1243
1244        public int hashCode() {
1245            int keyHash = (key==null ? 0 : key.hashCode());
1246            int valueHash = (value==null ? 0 : value.hashCode());
1247            return keyHash ^ valueHash;
1248        }
1249
1250        public String toString() {
1251            return key + "=" + value;
1252        }
1253    }
1254
1255    /**
1256     * Returns the first Entry in the TreeMap (according to the TreeMap's
1257     * key-sort function). Returns null if the TreeMap is empty.
1258     */
1259    private Entry firstEntry() {
1260        Entry p = root;
1261        if (p != null)
1262            while (p.left != null)
1263                p = p.left;
1264        return p;
1265    }
1266
1267    public Map getSubMap(int startEntry, int maxNumber){
1268        int count =0;
1269        
1270        if (startEntry <0){
1271            throw new RuntimeException ("the start entry for a subset limit cannot be negative: "+startEntry);
1272        }
1273        if(maxNumber <0){
1274            throw new RuntimeException ("the max number of entries cannot be negative:" + maxNumber);
1275        }
1276        
1277        Map returnMap = new ValueTreeMap(comparator);
1278        
1279        // get the first node
1280 Entry t = firstEntry();
1281        
1282        while (count < startEntry){
1283            t = successor(t);
1284            if (t ==null){
1285                return returnMap;
1286            }
1287            count++;
1288        }
1289        // this should be the start entry
1290 returnMap.put(t.key, t.value);
1291        
1292        count =1;
1293        
1294        while(count < maxNumber){
1295            t =successor(t);
1296            if (t != null){
1297                returnMap.put(t.key, t.value);
1298            }else{
1299                // we have run out of entries
1300 break;
1301            }
1302            count++;
1303        }
1304        
1305        
1306        return returnMap;
1307    }
1308    /**
1309     * Returns the last Entry in the TreeMap (according to the TreeMap's
1310     * key-sort function). Returns null if the TreeMap is empty.
1311     */
1312    private Entry lastEntry() {
1313        Entry p = root;
1314        if (p != null)
1315            while (p.right != null)
1316                p = p.right;
1317        return p;
1318    }
1319
1320    /**
1321     * Returns the successor of the specified Entry, or null if no such.
1322     */
1323    private Entry successor(Entry t) {
1324        if (t == null)
1325            return null;
1326        else if (t.right != null) {
1327            Entry p = t.right;
1328            while (p.left != null)
1329                p = p.left;
1330            return p;
1331        } else {
1332            Entry p = t.parent;
1333            Entry ch = t;
1334            while (p != null && ch == p.right) {
1335                ch = p;
1336                p = p.parent;
1337            }
1338            return p;
1339        }
1340    }
1341
1342    /**
1343     * Balancing operations.
1344     *
1345     * Implementations of rebalancings during insertion and deletion are
1346     * slightly different than the CLR version. Rather than using dummy
1347     * nilnodes, we use a set of accessors that deal properly with null. They
1348     * are used to avoid messiness surrounding nullness checks in the main
1349     * algorithms.
1350     */
1351
1352    private static boolean colorOf(Entry p) {
1353        return (p == null ? BLACK : p.color);
1354    }
1355
1356    private static Entry parentOf(Entry p) {
1357        return (p == null ? null: p.parent);
1358    }
1359
1360    private static void setColor(Entry p, boolean c) {
1361        if (p != null) p.color = c;
1362    }
1363
1364    private static Entry leftOf(Entry p) {
1365        return (p == null)? null: p.left;
1366    }
1367
1368    private static Entry rightOf(Entry p) {
1369        return (p == null)? null: p.right;
1370    }
1371
1372    /** From CLR **/
1373    private void rotateLeft(Entry p) {
1374        Entry r = p.right;
1375        p.right = r.left;
1376        if (r.left != null)
1377            r.left.parent = p;
1378        r.parent = p.parent;
1379        if (p.parent == null)
1380            root = r;
1381        else if (p.parent.left == p)
1382            p.parent.left = r;
1383        else
1384            p.parent.right = r;
1385        r.left = p;
1386        p.parent = r;
1387    }
1388
1389    /** From CLR **/
1390    private void rotateRight(Entry p) {
1391        Entry l = p.left;
1392        p.left = l.right;
1393        if (l.right != null) l.right.parent = p;
1394        l.parent = p.parent;
1395        if (p.parent == null)
1396            root = l;
1397        else if (p.parent.right == p)
1398            p.parent.right = l;
1399        else p.parent.left = l;
1400        l.right = p;
1401        p.parent = l;
1402    }
1403
1404
1405    /** From CLR **/
1406    private void fixAfterInsertion(Entry x) {
1407        x.color = RED;
1408
1409        while (x != null && x != root && x.parent.color == RED) {
1410            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
1411                Entry y = rightOf(parentOf(parentOf(x)));
1412                if (colorOf(y) == RED) {
1413                    setColor(parentOf(x), BLACK);
1414                    setColor(y, BLACK);
1415                    setColor(parentOf(parentOf(x)), RED);
1416                    x = parentOf(parentOf(x));
1417                } else {
1418                    if (x == rightOf(parentOf(x))) {
1419                        x = parentOf(x);
1420                        rotateLeft(x);
1421                    }
1422                    setColor(parentOf(x), BLACK);
1423                    setColor(parentOf(parentOf(x)), RED);
1424                    if (parentOf(parentOf(x)) != null)
1425                        rotateRight(parentOf(parentOf(x)));
1426                }
1427            } else {
1428                Entry y = leftOf(parentOf(parentOf(x)));
1429                if (colorOf(y) == RED) {
1430                    setColor(parentOf(x), BLACK);
1431                    setColor(y, BLACK);
1432                    setColor(parentOf(parentOf(x)), RED);
1433                    x = parentOf(parentOf(x));
1434                } else {
1435                    if (x == leftOf(parentOf(x))) {
1436                        x = parentOf(x);
1437                        rotateRight(x);
1438                    }
1439                    setColor(parentOf(x), BLACK);
1440                    setColor(parentOf(parentOf(x)), RED);
1441                    if (parentOf(parentOf(x)) != null)
1442                        rotateLeft(parentOf(parentOf(x)));
1443                }
1444            }
1445        }
1446        root.color = BLACK;
1447    }
1448
1449    /**
1450     * Delete node p, and then rebalance the tree.
1451     */
1452
1453    private void deleteEntry(Entry p) {
1454        decrementSize();
1455
1456        // If strictly internal, copy successor's element to p and then make p
1457 // point to successor.
1458 if (p.left != null && p.right != null) {
1459            Entry s = successor (p);
1460            p.key = s.key;
1461            p.value = s.value;
1462            p = s;
1463        } // p has 2 children
1464
1465        // Start fixup at replacement node, if it exists.
1466 Entry replacement = (p.left != null ? p.left : p.right);
1467
1468        if (replacement != null) {
1469            // Link replacement to parent
1470 replacement.parent = p.parent;
1471            if (p.parent == null)
1472                root = replacement;
1473            else if (p == p.parent.left)
1474                p.parent.left = replacement;
1475            else
1476                p.parent.right = replacement;
1477
1478            // Null out links so they are OK to use by fixAfterDeletion.
1479 p.left = p.right = p.parent = null;
1480
1481            // Fix replacement
1482 if (p.color == BLACK)
1483                fixAfterDeletion(replacement);
1484        } else if (p.parent == null) { // return if we are the only node.
1485 root = null;
1486        } else { // No children. Use self as phantom replacement and unlink.
1487 if (p.color == BLACK)
1488                fixAfterDeletion(p);
1489
1490            if (p.parent != null) {
1491                if (p == p.parent.left)
1492                    p.parent.left = null;
1493                else if (p == p.parent.right)
1494                    p.parent.right = null;
1495                p.parent = null;
1496            }
1497        }
1498    }
1499
1500    /** From CLR **/
1501    private void fixAfterDeletion(Entry x) {
1502        while (x != root && colorOf(x) == BLACK) {
1503            if (x == leftOf(parentOf(x))) {
1504                Entry sib = rightOf(parentOf(x));
1505
1506                if (colorOf(sib) == RED) {
1507                    setColor(sib, BLACK);
1508                    setColor(parentOf(x), RED);
1509                    rotateLeft(parentOf(x));
1510                    sib = rightOf(parentOf(x));
1511                }
1512
1513                if (colorOf(leftOf(sib)) == BLACK &&
1514                    colorOf(rightOf(sib)) == BLACK) {
1515                    setColor(sib, RED);
1516                    x = parentOf(x);
1517                } else {
1518                    if (colorOf(rightOf(sib)) == BLACK) {
1519                        setColor(leftOf(sib), BLACK);
1520                        setColor(sib, RED);
1521                        rotateRight(sib);
1522                        sib = rightOf(parentOf(x));
1523                    }
1524                    setColor(sib, colorOf(parentOf(x)));
1525                    setColor(parentOf(x), BLACK);
1526                    setColor(rightOf(sib), BLACK);
1527                    rotateLeft(parentOf(x));
1528                    x = root;
1529                }
1530            } else { // symmetric
1531 Entry sib = leftOf(parentOf(x));
1532
1533                if (colorOf(sib) == RED) {
1534                    setColor(sib, BLACK);
1535                    setColor(parentOf(x), RED);
1536                    rotateRight(parentOf(x));
1537                    sib = leftOf(parentOf(x));
1538                }
1539
1540                if (colorOf(rightOf(sib)) == BLACK &&
1541                    colorOf(leftOf(sib)) == BLACK) {
1542                    setColor(sib, RED);
1543                    x = parentOf(x);
1544                } else {
1545                    if (colorOf(leftOf(sib)) == BLACK) {
1546                        setColor(rightOf(sib), BLACK);
1547                        setColor(sib, RED);
1548                        rotateLeft(sib);
1549                        sib = leftOf(parentOf(x));
1550                    }
1551                    setColor(sib, colorOf(parentOf(x)));
1552                    setColor(parentOf(x), BLACK);
1553                    setColor(leftOf(sib), BLACK);
1554                    rotateRight(parentOf(x));
1555                    x = root;
1556                }
1557            }
1558        }
1559
1560        setColor(x, BLACK);
1561    }
1562
1563    private static final long serialVersionUID = 919286545866124006L;
1564
1565    /**
1566     * Save the state of the <tt>TreeMap</tt> instance to a stream (i.e.,
1567     * serialize it).
1568     *
1569     * @serialData The <i>size</i> of the TreeMap (the number of key-value
1570     * mappings) is emitted (int), followed by the key (Object)
1571     * and value (Object) for each key-value mapping represented
1572     * by the TreeMap. The key-value mappings are emitted in
1573     * key-order (as determined by the TreeMap's Comparator,
1574     * or by the keys' natural ordering if the TreeMap has no
1575     * Comparator).
1576     */
1577    private void writeObject(java.io.ObjectOutputStream s)
1578        throws java.io.IOException {
1579        // Write out the Comparator and any hidden stuff
1580 s.defaultWriteObject();
1581
1582        // Write out size (number of Mappings)
1583 s.writeInt(size);
1584
1585        // Write out keys and values (alternating)
1586 for (Iterator i = entrySet().iterator(); i.hasNext(); ) {
1587            Entry e = (Entry)i.next();
1588            s.writeObject(e.key);
1589            s.writeObject(e.value);
1590        }
1591    }
1592
1593
1594
1595    /**
1596     * Reconstitute the <tt>TreeMap</tt> instance from a stream (i.e.,
1597     * deserialize it).
1598     */
1599    private void readObject(final java.io.ObjectInputStream s)
1600        throws java.io.IOException , ClassNotFoundException {
1601        // Read in the Comparator and any hidden stuff
1602 s.defaultReadObject();
1603
1604        // Read in size
1605 int size = s.readInt();
1606
1607        buildFromSorted(size, null, s, null);
1608    }
1609
1610    /** Intended to be called only from TreeSet.readObject **/
1611    void readTreeSet(int size, java.io.ObjectInputStream s, Object defaultVal)
1612        throws java.io.IOException , ClassNotFoundException {
1613        buildFromSorted(size, null, s, defaultVal);
1614    }
1615
1616    /** Intended to be called only from TreeSet.addAll **/
1617    void addAllForTreeSet(SortedSet set, Object defaultVal) {
1618      try {
1619          buildFromSorted(set.size(), set.iterator(), null, defaultVal);
1620      } catch (java.io.IOException cannotHappen) {
1621      } catch (ClassNotFoundException cannotHappen) {
1622      }
1623    }
1624
1625
1626    /**
1627     * Linear time tree building algorithm from sorted data. Can accept keys
1628     * and/or values from iterator or stream. This leads to too many
1629     * parameters, but seems better than alternatives. The four formats
1630     * that this method accepts are:
1631     *
1632     * 1) An iterator of Map.Entries. (it != null, defaultVal == null).
1633     * 2) An iterator of keys. (it != null, defaultVal != null).
1634     * 3) A stream of alternating serialized keys and values.
1635     * (it == null, defaultVal == null).
1636     * 4) A stream of serialized keys. (it == null, defaultVal != null).
1637     *
1638     * It is assumed that the comparator of the TreeMap is already set prior
1639     * to calling this method.
1640     *
1641     * @param size the number of keys (or key-value pairs) to be read from
1642     * the iterator or stream.
1643     * @param it If non-null, new entries are created from entries
1644     * or keys read from this iterator.
1645     * @param it If non-null, new entries are created from keys and
1646     * possibly values read from this stream in serialized form.
1647     * Exactly one of it and str should be non-null.
1648     * @param defaultVal if non-null, this default value is used for
1649     * each value in the map. If null, each value is read from
1650     * iterator or stream, as described above.
1651     * @throws IOException propagated from stream reads. This cannot
1652     * occur if str is null.
1653     * @throws ClassNotFoundException propagated from readObject.
1654     * This cannot occur if str is null.
1655     */
1656    private void buildFromSorted(int size, Iterator it,
1657                                  java.io.ObjectInputStream str,
1658                                  Object defaultVal)
1659        throws java.io.IOException , ClassNotFoundException {
1660        this.size = size;
1661        root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
1662                               it, str, defaultVal);
1663    }
1664
1665    /**
1666     * Recursive "helper method" that does the real work of the
1667     * of the previous method. Identically named parameters have
1668     * identical definitions. Additional parameters are documented below.
1669     * It is assumed that the comparator and size fields of the TreeMap are
1670     * already set prior to calling this method. (It ignores both fields.)
1671     *
1672     * @param level the current level of tree. Initial call should be 0.
1673     * @param lo the first element index of this subtree. Initial should be 0.
1674     * @param hi the last element index of this subtree. Initial should be
1675     * size-1.
1676     * @param redLevel the level at which nodes should be red.
1677     * Must be equal to computeRedLevel for tree of this size.
1678     */
1679    private static Entry buildFromSorted(int level, int lo, int hi,
1680                                         int redLevel,
1681                                         Iterator it,
1682                                         java.io.ObjectInputStream str,
1683                                         Object defaultVal)
1684        throws java.io.IOException , ClassNotFoundException {
1685        /*
1686         * Strategy: The root is the middlemost element. To get to it, we
1687         * have to first recursively construct the entire left subtree,
1688         * so as to grab all of its elements. We can then proceed with right
1689         * subtree.
1690         *
1691         * The lo and hi arguments are the minimum and maximum
1692         * indices to pull out of the iterator or stream for current subtree.
1693         * They are not actually indexed, we just proceed sequentially,
1694         * ensuring that items are extracted in corresponding order.
1695         */
1696
1697        if (hi < lo) return null;
1698
1699        int mid = (lo + hi) / 2;
1700        
1701        Entry left = null;
1702        if (lo < mid)
1703            left = buildFromSorted(level+1, lo, mid - 1, redLevel,
1704                                   it, str, defaultVal);
1705        
1706        // extract key and/or value from iterator or stream
1707 Object key;
1708        Object value;
1709        if (it != null) { // use iterator
1710 if (defaultVal==null) {
1711                Map.Entry entry = (Map.Entry ) it.next();
1712                key = entry.getKey();
1713                value = entry.getValue();
1714            } else {
1715                key = it.next();
1716                value = defaultVal;
1717            }
1718        } else { // use stream
1719 key = str.readObject();
1720            value = (defaultVal != null ? defaultVal : str.readObject());
1721        }
1722
1723        Entry middle = new Entry(key, value, null);
1724        // color nodes in non-full bottommost level red
1725 if (level == redLevel)
1726            middle.color = RED;
1727        
1728        if (left != null) {
1729            middle.left = left;
1730            left.parent = middle;
1731        }
1732        
1733        if (mid < hi) {
1734            Entry right = buildFromSorted(level+1, mid+1, hi, redLevel,
1735                                          it, str, defaultVal);
1736            middle.right = right;
1737            right.parent = middle;
1738        }
1739        
1740        return middle;
1741    }
1742
1743    /**
1744     * Find the level down to which to assign all nodes BLACK. This is the
1745     * last `full' level of the complete binary tree produced by
1746     * buildTree. The remaining nodes are colored RED. (This makes a `nice'
1747     * set of color assignments wrt future insertions.) This level number is
1748     * computed by finding the number of splits needed to reach the zeroeth
1749     * node. (The answer is ~lg(N), but in any case must be computed by same
1750     * quick O(lg(N)) loop.)
1751     */
1752    private static int computeRedLevel(int sz) {
1753        int level = 0;
1754        for (int m = sz - 1; m >= 0; m = m / 2 - 1)
1755            level++;
1756        return level;
1757    }
1758    
1759    class DefaultComparator implements Comparator {
1760
1761        public int compare(Object o1, Object o2)
1762        {
1763            Map.Entry entry1 = (Map.Entry )o1;
1764            Map.Entry entry2 = (Map.Entry )o2;
1765            
1766            
1767                return ((Comparable )entry1.getKey()).compareTo(entry2.getKey());
1768           
1769        }
1770        
1771    };
1772}
1773

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags