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