1 |
/* TreeMap.java -- a class providing a basic Red-Black Tree data structure, |
2 |
mapping Object --> Object |
3 |
Copyright (C) 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc. |
4 |
|
5 |
This file is part of GNU Classpath. |
6 |
|
7 |
GNU Classpath is free software; you can redistribute it and/or modify |
8 |
it under the terms of the GNU General Public License as published by |
9 |
the Free Software Foundation; either version 2, or (at your option) |
10 |
any later version. |
11 |
|
12 |
GNU Classpath is distributed in the hope that it will be useful, but |
13 |
WITHOUT ANY WARRANTY; without even the implied warranty of |
14 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
15 |
General Public License for more details. |
16 |
|
17 |
You should have received a copy of the GNU General Public License |
18 |
along with GNU Classpath; see the file COPYING. If not, write to the |
19 |
Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA |
20 |
02111-1307 USA. |
21 |
|
22 |
Linking this library statically or dynamically with other modules is |
23 |
making a combined work based on this library. Thus, the terms and |
24 |
conditions of the GNU General Public License cover the whole |
25 |
combination. |
26 |
|
27 |
As a special exception, the copyright holders of this library give you |
28 |
permission to link this library with independent modules to produce an |
29 |
executable, regardless of the license terms of these independent |
30 |
modules, and to copy and distribute the resulting executable under |
31 |
terms of your choice, provided that you also meet, for each linked |
32 |
independent module, the terms and conditions of the license of that |
33 |
module. An independent module is a module which is not derived from |
34 |
or based on this library. If you modify this library, you may extend |
35 |
this exception to your version of the library, but you are not |
36 |
obligated to do so. If you do not wish to do so, delete this |
37 |
exception statement from your version. */ |
38 |
|
39 |
|
40 |
package java.util; |
41 |
|
42 |
import java.io.Serializable; |
43 |
import java.io.ObjectOutputStream; |
44 |
import java.io.ObjectInputStream; |
45 |
import java.io.IOException; |
46 |
|
47 |
/** |
48 |
* This class provides a red-black tree implementation of the SortedMap |
49 |
* interface. Elements in the Map will be sorted by either a user-provided |
50 |
* Comparator object, or by the natural ordering of the keys. |
51 |
* |
52 |
* The algorithms are adopted from Corman, Leiserson, and Rivest's |
53 |
* <i>Introduction to Algorithms.</i> TreeMap guarantees O(log n) |
54 |
* insertion and deletion of elements. That being said, there is a large |
55 |
* enough constant coefficient in front of that "log n" (overhead involved |
56 |
* in keeping the tree balanced), that TreeMap may not be the best choice |
57 |
* for small collections. If something is already sorted, you may want to |
58 |
* just use a LinkedHashMap to maintain the order while providing O(1) access. |
59 |
* |
60 |
* TreeMap is a part of the JDK1.2 Collections API. Null keys are allowed |
61 |
* only if a Comparator is used which can deal with them; natural ordering |
62 |
* cannot cope with null. Null values are always allowed. Note that the |
63 |
* ordering must be <i>consistent with equals</i> to correctly implement |
64 |
* the Map interface. If this condition is violated, the map is still |
65 |
* well-behaved, but you may have suprising results when comparing it to |
66 |
* other maps.<p> |
67 |
* |
68 |
* This implementation is not synchronized. If you need to share this between |
69 |
* multiple threads, do something like:<br> |
70 |
* <code>SortedMap m |
71 |
* = Collections.synchronizedSortedMap(new TreeMap(...));</code><p> |
72 |
* |
73 |
* The iterators are <i>fail-fast</i>, meaning that any structural |
74 |
* modification, except for <code>remove()</code> called on the iterator |
75 |
* itself, cause the iterator to throw a |
76 |
* <code>ConcurrentModificationException</code> rather than exhibit |
77 |
* non-deterministic behavior. |
78 |
* |
79 |
* @author Jon Zeppieri |
80 |
* @author Bryce McKinlay |
81 |
* @author Eric Blake <ebb9@email.byu.edu> |
82 |
* @see Map |
83 |
* @see HashMap |
84 |
* @see Hashtable |
85 |
* @see LinkedHashMap |
86 |
* @see Comparable |
87 |
* @see Comparator |
88 |
* @see Collection |
89 |
* @see Collections#synchronizedSortedMap(SortedMap) |
90 |
* @since 1.2 |
91 |
* @status updated to 1.4 |
92 |
*/ |
93 |
public class TreeMap extends AbstractMap |
94 |
implements SortedMap, Cloneable, Serializable |
95 |
{ |
96 |
// Implementation note: |
97 |
// A red-black tree is a binary search tree with the additional properties |
98 |
// that all paths to a leaf node visit the same number of black nodes, |
99 |
// and no red node has red children. To avoid some null-pointer checks, |
100 |
// we use the special node nil which is always black, has no relatives, |
101 |
// and has key and value of null (but is not equal to a mapping of null). |
102 |
|
103 |
/** |
104 |
* Compatible with JDK 1.2. |
105 |
*/ |
106 |
private static final long serialVersionUID = 919286545866124006L; |
107 |
|
108 |
/** |
109 |
* Color status of a node. Package visible for use by nested classes. |
110 |
*/ |
111 |
static final int RED = -1, |
112 |
BLACK = 1; |
113 |
|
114 |
/** |
115 |
* Sentinal node, used to avoid null checks for corner cases and make the |
116 |
* delete rebalance code simpler. The rebalance code must never assign |
117 |
* the parent, left, or right of nil, but may safely reassign the color |
118 |
* to be black. This object must never be used as a key in a TreeMap, or |
119 |
* it will break bounds checking of a SubMap. |
120 |
*/ |
121 |
static final Node nil = new Node(null, null, BLACK); |
122 |
static |
123 |
{ |
124 |
// Nil is self-referential, so we must initialize it after creation. |
125 |
nil.parent = nil; |
126 |
nil.left = nil; |
127 |
nil.right = nil; |
128 |
} |
129 |
|
130 |
/** |
131 |
* The root node of this TreeMap. |
132 |
*/ |
133 |
private transient Node root = nil; |
134 |
|
135 |
/** |
136 |
* The size of this TreeMap. Package visible for use by nested classes. |
137 |
*/ |
138 |
transient int size; |
139 |
|
140 |
/** |
141 |
* The cache for {@link #entrySet()}. |
142 |
*/ |
143 |
private transient Set entries; |
144 |
|
145 |
/** |
146 |
* Counts the number of modifications this TreeMap has undergone, used |
147 |
* by Iterators to know when to throw ConcurrentModificationExceptions. |
148 |
* Package visible for use by nested classes. |
149 |
*/ |
150 |
transient int modCount; |
151 |
|
152 |
/** |
153 |
* This TreeMap's comparator, or null for natural ordering. |
154 |
* Package visible for use by nested classes. |
155 |
* @serial the comparator ordering this tree, or null |
156 |
*/ |
157 |
final Comparator comparator; |
158 |
|
159 |
/** |
160 |
* Class to represent an entry in the tree. Holds a single key-value pair, |
161 |
* plus pointers to parent and child nodes. |
162 |
* |
163 |
* @author Eric Blake <ebb9@email.byu.edu> |
164 |
*/ |
165 |
private static final class Node extends AbstractMap.BasicMapEntry |
166 |
{ |
167 |
// All fields package visible for use by nested classes. |
168 |
/** The color of this node. */ |
169 |
int color; |
170 |
|
171 |
/** The left child node. */ |
172 |
Node left = nil; |
173 |
/** The right child node. */ |
174 |
Node right = nil; |
175 |
/** The parent node. */ |
176 |
Node parent = nil; |
177 |
|
178 |
/** |
179 |
* Simple constructor. |
180 |
* @param key the key |
181 |
* @param value the value |
182 |
*/ |
183 |
Node(Object key, Object value, int color) |
184 |
{ |
185 |
super(key, value); |
186 |
this.color = color; |
187 |
} |
188 |
} |
189 |
|
190 |
/** |
191 |
* Instantiate a new TreeMap with no elements, using the keys' natural |
192 |
* ordering to sort. All entries in the map must have a key which implements |
193 |
* Comparable, and which are <i>mutually comparable</i>, otherwise map |
194 |
* operations may throw a {@link ClassCastException}. Attempts to use |
195 |
* a null key will throw a {@link NullPointerException}. |
196 |
* |
197 |
* @see Comparable |
198 |
*/ |
199 |
public TreeMap() |
200 |
{ |
201 |
this((Comparator) null); |
202 |
} |
203 |
|
204 |
/** |
205 |
* Instantiate a new TreeMap with no elements, using the provided comparator |
206 |
* to sort. All entries in the map must have keys which are mutually |
207 |
* comparable by the Comparator, otherwise map operations may throw a |
208 |
* {@link ClassCastException}. |
209 |
* |
210 |
* @param comparator the sort order for the keys of this map, or null |
211 |
* for the natural order |
212 |
*/ |
213 |
public TreeMap(Comparator c) |
214 |
{ |
215 |
comparator = c; |
216 |
} |
217 |
|
218 |
/** |
219 |
* Instantiate a new TreeMap, initializing it with all of the elements in |
220 |
* the provided Map. The elements will be sorted using the natural |
221 |
* ordering of the keys. This algorithm runs in n*log(n) time. All entries |
222 |
* in the map must have keys which implement Comparable and are mutually |
223 |
* comparable, otherwise map operations may throw a |
224 |
* {@link ClassCastException}. |
225 |
* |
226 |
* @param map a Map, whose entries will be put into this TreeMap |
227 |
* @throws ClassCastException if the keys in the provided Map are not |
228 |
* comparable |
229 |
* @throws NullPointerException if map is null |
230 |
* @see Comparable |
231 |
*/ |
232 |
public TreeMap(Map map) |
233 |
{ |
234 |
this((Comparator) null); |
235 |
putAll(map); |
236 |
} |
237 |
|
238 |
/** |
239 |
* Instantiate a new TreeMap, initializing it with all of the elements in |
240 |
* the provided SortedMap. The elements will be sorted using the same |
241 |
* comparator as in the provided SortedMap. This runs in linear time. |
242 |
* |
243 |
* @param sm a SortedMap, whose entries will be put into this TreeMap |
244 |
* @throws NullPointerException if sm is null |
245 |
*/ |
246 |
public TreeMap(SortedMap sm) |
247 |
{ |
248 |
this(sm.comparator()); |
249 |
int pos = sm.size(); |
250 |
Iterator itr = sm.entrySet().iterator(); |
251 |
|
252 |
fabricateTree(pos); |
253 |
Node node = firstNode(); |
254 |
|
255 |
while (--pos >= 0) |
256 |
{ |
257 |
Map.Entry me = (Map.Entry) itr.next(); |
258 |
node.key = me.getKey(); |
259 |
node.value = me.getValue(); |
260 |
node = successor(node); |
261 |
} |
262 |
} |
263 |
|
264 |
/** |
265 |
* Clears the Map so it has no keys. This is O(1). |
266 |
*/ |
267 |
public void clear() |
268 |
{ |
269 |
if (size > 0) |
270 |
{ |
271 |
modCount++; |
272 |
root = nil; |
273 |
size = 0; |
274 |
} |
275 |
} |
276 |
|
277 |
/** |
278 |
* Returns a shallow clone of this TreeMap. The Map itself is cloned, |
279 |
* but its contents are not. |
280 |
* |
281 |
* @return the clone |
282 |
*/ |
283 |
public Object clone() |
284 |
{ |
285 |
TreeMap copy = null; |
286 |
try |
287 |
{ |
288 |
copy = (TreeMap) super.clone(); |
289 |
} |
290 |
catch (CloneNotSupportedException x) |
291 |
{ |
292 |
} |
293 |
copy.entries = null; |
294 |
copy.fabricateTree(size); |
295 |
|
296 |
Node node = firstNode(); |
297 |
Node cnode = copy.firstNode(); |
298 |
|
299 |
while (node != nil) |
300 |
{ |
301 |
cnode.key = node.key; |
302 |
cnode.value = node.value; |
303 |
node = successor(node); |
304 |
cnode = copy.successor(cnode); |
305 |
} |
306 |
return copy; |
307 |
} |
308 |
|
309 |
/** |
310 |
* Return the comparator used to sort this map, or null if it is by |
311 |
* natural order. |
312 |
* |
313 |
* @return the map's comparator |
314 |
*/ |
315 |
public Comparator comparator() |
316 |
{ |
317 |
return comparator; |
318 |
} |
319 |
|
320 |
/** |
321 |
* Returns true if the map contains a mapping for the given key. |
322 |
* |
323 |
* @param key the key to look for |
324 |
* @return true if the key has a mapping |
325 |
* @throws ClassCastException if key is not comparable to map elements |
326 |
* @throws NullPointerException if key is null and the comparator is not |
327 |
* tolerant of nulls |
328 |
*/ |
329 |
public boolean containsKey(Object key) |
330 |
{ |
331 |
return getNode(key) != nil; |
332 |
} |
333 |
|
334 |
/** |
335 |
* Returns true if the map contains at least one mapping to the given value. |
336 |
* This requires linear time. |
337 |
* |
338 |
* @param value the value to look for |
339 |
* @return true if the value appears in a mapping |
340 |
*/ |
341 |
public boolean containsValue(Object value) |
342 |
{ |
343 |
Node node = firstNode(); |
344 |
while (node != nil) |
345 |
{ |
346 |
if (equals(value, node.value)) |
347 |
return true; |
348 |
node = successor(node); |
349 |
} |
350 |
return false; |
351 |
} |
352 |
|
353 |
/** |
354 |
* Returns a "set view" of this TreeMap's entries. The set is backed by |
355 |
* the TreeMap, so changes in one show up in the other. The set supports |
356 |
* element removal, but not element addition.<p> |
357 |
* |
358 |
* Note that the iterators for all three views, from keySet(), entrySet(), |
359 |
* and values(), traverse the TreeMap in sorted sequence. |
360 |
* |
361 |
* @return a set view of the entries |
362 |
* @see #keySet() |
363 |
* @see #values() |
364 |
* @see Map.Entry |
365 |
*/ |
366 |
public Set entrySet() |
367 |
{ |
368 |
if (entries == null) |
369 |
// Create an AbstractSet with custom implementations of those methods |
370 |
// that can be overriden easily and efficiently. |
371 |
entries = new AbstractSet() |
372 |
{ |
373 |
public int size() |
374 |
{ |
375 |
return size; |
376 |
} |
377 |
|
378 |
public Iterator iterator() |
379 |
{ |
380 |
return new TreeIterator(ENTRIES); |
381 |
} |
382 |
|
383 |
public void clear() |
384 |
{ |
385 |
TreeMap.this.clear(); |
386 |
} |
387 |
|
388 |
public boolean contains(Object o) |
389 |
{ |
390 |
if (! (o instanceof Map.Entry)) |
391 |
return false; |
392 |
Map.Entry me = (Map.Entry) o; |
393 |
Node n = getNode(me.getKey()); |
394 |
return n != nil && AbstractSet.equals(me.getValue(), n.value); |
395 |
} |
396 |
|
397 |
public boolean remove(Object o) |
398 |
{ |
399 |
if (! (o instanceof Map.Entry)) |
400 |
return false; |
401 |
Map.Entry me = (Map.Entry) o; |
402 |
Node n = getNode(me.getKey()); |
403 |
if (n != nil && AbstractSet.equals(me.getValue(), n.value)) |
404 |
{ |
405 |
removeNode(n); |
406 |
return true; |
407 |
} |
408 |
return false; |
409 |
} |
410 |
}; |
411 |
return entries; |
412 |
} |
413 |
|
414 |
/** |
415 |
* Returns the first (lowest) key in the map. |
416 |
* |
417 |
* @return the first key |
418 |
* @throws NoSuchElementException if the map is empty |
419 |
*/ |
420 |
public Object firstKey() |
421 |
{ |
422 |
if (root == nil) |
423 |
throw new NoSuchElementException(); |
424 |
return firstNode().key; |
425 |
} |
426 |
|
427 |
/** |
428 |
* Return the value in this TreeMap associated with the supplied key, |
429 |
* or <code>null</code> if the key maps to nothing. NOTE: Since the value |
430 |
* could also be null, you must use containsKey to see if this key |
431 |
* actually maps to something. |
432 |
* |
433 |
* @param key the key for which to fetch an associated value |
434 |
* @return what the key maps to, if present |
435 |
* @throws ClassCastException if key is not comparable to elements in the map |
436 |
* @throws NullPointerException if key is null but the comparator does not |
437 |
* tolerate nulls |
438 |
* @see #put(Object, Object) |
439 |
* @see #containsKey(Object) |
440 |
*/ |
441 |
public Object get(Object key) |
442 |
{ |
443 |
// Exploit fact that nil.value == null. |
444 |
return getNode(key).value; |
445 |
} |
446 |
|
447 |
/** |
448 |
* Returns a view of this Map including all entries with keys less than |
449 |
* <code>toKey</code>. The returned map is backed by the original, so changes |
450 |
* in one appear in the other. The submap will throw an |
451 |
* {@link IllegalArgumentException} for any attempt to access or add an |
452 |
* element beyond the specified cutoff. The returned map does not include |
453 |
* the endpoint; if you want inclusion, pass the successor element. |
454 |
* |
455 |
* @param toKey the (exclusive) cutoff point |
456 |
* @return a view of the map less than the cutoff |
457 |
* @throws ClassCastException if <code>toKey</code> is not compatible with |
458 |
* the comparator (or is not Comparable, for natural ordering) |
459 |
* @throws NullPointerException if toKey is null, but the comparator does not |
460 |
* tolerate null elements |
461 |
*/ |
462 |
public SortedMap headMap(Object toKey) |
463 |
{ |
464 |
return new SubMap(nil, toKey); |
465 |
} |
466 |
|
467 |
/** |
468 |
* Returns a "set view" of this TreeMap's keys. The set is backed by the |
469 |
* TreeMap, so changes in one show up in the other. The set supports |
470 |
* element removal, but not element addition. |
471 |
* |
472 |
* @return a set view of the keys |
473 |
* @see #values() |
474 |
* @see #entrySet() |
475 |
*/ |
476 |
public Set keySet() |
477 |
{ |
478 |
if (keys == null) |
479 |
// Create an AbstractSet with custom implementations of those methods |
480 |
// that can be overriden easily and efficiently. |
481 |
keys = new AbstractSet() |
482 |
{ |
483 |
public int size() |
484 |
{ |
485 |
return size; |
486 |
} |
487 |
|
488 |
public Iterator iterator() |
489 |
{ |
490 |
return new TreeIterator(KEYS); |
491 |
} |
492 |
|
493 |
public void clear() |
494 |
{ |
495 |
TreeMap.this.clear(); |
496 |
} |
497 |
|
498 |
public boolean contains(Object o) |
499 |
{ |
500 |
return containsKey(o); |
501 |
} |
502 |
|
503 |
public boolean remove(Object key) |
504 |
{ |
505 |
Node n = getNode(key); |
506 |
if (n == nil) |
507 |
return false; |
508 |
removeNode(n); |
509 |
return true; |
510 |
} |
511 |
}; |
512 |
return keys; |
513 |
} |
514 |
|
515 |
/** |
516 |
* Returns the last (highest) key in the map. |
517 |
* |
518 |
* @return the last key |
519 |
* @throws NoSuchElementException if the map is empty |
520 |
*/ |
521 |
public Object lastKey() |
522 |
{ |
523 |
if (root == nil) |
524 |
throw new NoSuchElementException("empty"); |
525 |
return lastNode().key; |
526 |
} |
527 |
|
528 |
/** |
529 |
* Puts the supplied value into the Map, mapped by the supplied key. |
530 |
* The value may be retrieved by any object which <code>equals()</code> |
531 |
* this key. NOTE: Since the prior value could also be null, you must |
532 |
* first use containsKey if you want to see if you are replacing the |
533 |
* key's mapping. |
534 |
* |
535 |
* @param key the key used to locate the value |
536 |
* @param value the value to be stored in the HashMap |
537 |
* @return the prior mapping of the key, or null if there was none |
538 |
* @throws ClassCastException if key is not comparable to current map keys |
539 |
* @throws NullPointerException if key is null, but the comparator does |
540 |
* not tolerate nulls |
541 |
* @see #get(Object) |
542 |
* @see Object#equals(Object) |
543 |
*/ |
544 |
public Object put(Object key, Object value) |
545 |
{ |
546 |
Node current = root; |
547 |
Node parent = nil; |
548 |
int comparison = 0; |
549 |
|
550 |
// Find new node's parent. |
551 |
while (current != nil) |
552 |
{ |
553 |
parent = current; |
554 |
comparison = compare(key, current.key); |
555 |
if (comparison > 0) |
556 |
current = current.right; |
557 |
else if (comparison < 0) |
558 |
current = current.left; |
559 |
else // Key already in tree. |
560 |
return current.setValue(value); |
561 |
} |
562 |
|
563 |
// Set up new node. |
564 |
Node n = new Node(key, value, RED); |
565 |
n.parent = parent; |
566 |
|
567 |
// Insert node in tree. |
568 |
modCount++; |
569 |
size++; |
570 |
if (parent == nil) |
571 |
{ |
572 |
// Special case inserting into an empty tree. |
573 |
root = n; |
574 |
return null; |
575 |
} |
576 |
if (comparison > 0) |
577 |
parent.right = n; |
578 |
else |
579 |
parent.left = n; |
580 |
|
581 |
// Rebalance after insert. |
582 |
insertFixup(n); |
583 |
return null; |
584 |
} |
585 |
|
586 |
/** |
587 |
* Copies all elements of the given map into this hashtable. If this table |
588 |
* already has a mapping for a key, the new mapping replaces the current |
589 |
* one. |
590 |
* |
591 |
* @param m the map to be hashed into this |
592 |
* @throws ClassCastException if a key in m is not comparable with keys |
593 |
* in the map |
594 |
* @throws NullPointerException if a key in m is null, and the comparator |
595 |
* does not tolerate nulls |
596 |
*/ |
597 |
public void putAll(Map m) |
598 |
{ |
599 |
Iterator itr = m.entrySet().iterator(); |
600 |
int pos = m.size(); |
601 |
while (--pos >= 0) |
602 |
{ |
603 |
Map.Entry e = (Map.Entry) itr.next(); |
604 |
put(e.getKey(), e.getValue()); |
605 |
} |
606 |
} |
607 |
|
608 |
/** |
609 |
* Removes from the TreeMap and returns the value which is mapped by the |
610 |
* supplied key. If the key maps to nothing, then the TreeMap remains |
611 |
* unchanged, and <code>null</code> is returned. NOTE: Since the value |
612 |
* could also be null, you must use containsKey to see if you are |
613 |
* actually removing a mapping. |
614 |
* |
615 |
* @param key the key used to locate the value to remove |
616 |
* @return whatever the key mapped to, if present |
617 |
* @throws ClassCastException if key is not comparable to current map keys |
618 |
* @throws NullPointerException if key is null, but the comparator does |
619 |
* not tolerate nulls |
620 |
*/ |
621 |
public Object remove(Object key) |
622 |
{ |
623 |
Node n = getNode(key); |
624 |
if (n == nil) |
625 |
return null; |
626 |
// Note: removeNode can alter the contents of n, so save value now. |
627 |
Object result = n.value; |
628 |
removeNode(n); |
629 |
return result; |
630 |
} |
631 |
|
632 |
/** |
633 |
* Returns the number of key-value mappings currently in this Map. |
634 |
* |
635 |
* @return the size |
636 |
*/ |
637 |
public int size() |
638 |
{ |
639 |
return size; |
640 |
} |
641 |
|
642 |
/** |
643 |
* Returns a view of this Map including all entries with keys greater or |
644 |
* equal to <code>fromKey</code> and less than <code>toKey</code> (a |
645 |
* half-open interval). The returned map is backed by the original, so |
646 |
* changes in one appear in the other. The submap will throw an |
647 |
* {@link IllegalArgumentException} for any attempt to access or add an |
648 |
* element beyond the specified cutoffs. The returned map includes the low |
649 |
* endpoint but not the high; if you want to reverse this behavior on |
650 |
* either end, pass in the successor element. |
651 |
* |
652 |
* @param fromKey the (inclusive) low cutoff point |
653 |
* @param toKey the (exclusive) high cutoff point |
654 |
* @return a view of the map between the cutoffs |
655 |
* @throws ClassCastException if either cutoff is not compatible with |
656 |
* the comparator (or is not Comparable, for natural ordering) |
657 |
* @throws NullPointerException if fromKey or toKey is null, but the |
658 |
* comparator does not tolerate null elements |
659 |
* @throws IllegalArgumentException if fromKey is greater than toKey |
660 |
*/ |
661 |
public SortedMap subMap(Object fromKey, Object toKey) |
662 |
{ |
663 |
return new SubMap(fromKey, toKey); |
664 |
} |
665 |
|
666 |
/** |
667 |
* Returns a view of this Map including all entries with keys greater or |
668 |
* equal to <code>fromKey</code>. The returned map is backed by the |
669 |
* original, so changes in one appear in the other. The submap will throw an |
670 |
* {@link IllegalArgumentException} for any attempt to access or add an |
671 |
* element beyond the specified cutoff. The returned map includes the |
672 |
* endpoint; if you want to exclude it, pass in the successor element. |
673 |
* |
674 |
* @param fromKey the (inclusive) low cutoff point |
675 |
* @return a view of the map above the cutoff |
676 |
* @throws ClassCastException if <code>fromKey</code> is not compatible with |
677 |
* the comparator (or is not Comparable, for natural ordering) |
678 |
* @throws NullPointerException if fromKey is null, but the comparator |
679 |
* does not tolerate null elements |
680 |
*/ |
681 |
public SortedMap tailMap(Object fromKey) |
682 |
{ |
683 |
return new SubMap(fromKey, nil); |
684 |
} |
685 |
|
686 |
/** |
687 |
* Returns a "collection view" (or "bag view") of this TreeMap's values. |
688 |
* The collection is backed by the TreeMap, so changes in one show up |
689 |
* in the other. The collection supports element removal, but not element |
690 |
* addition. |
691 |
* |
692 |
* @return a bag view of the values |
693 |
* @see #keySet() |
694 |
* @see #entrySet() |
695 |
*/ |
696 |
public Collection values() |
697 |
{ |
698 |
if (values == null) |
699 |
// We don't bother overriding many of the optional methods, as doing so |
700 |
// wouldn't provide any significant performance advantage. |
701 |
values = new AbstractCollection() |
702 |
{ |
703 |
public int size() |
704 |
{ |
705 |
return size; |
706 |
} |
707 |
|
708 |
public Iterator iterator() |
709 |
{ |
710 |
return new TreeIterator(VALUES); |
711 |
} |
712 |
|
713 |
public void clear() |
714 |
{ |
715 |
TreeMap.this.clear(); |
716 |
} |
717 |
}; |
718 |
return values; |
719 |
} |
720 |
|
721 |
/** |
722 |
* Compares two elements by the set comparator, or by natural ordering. |
723 |
* Package visible for use by nested classes. |
724 |
* |
725 |
* @param o1 the first object |
726 |
* @param o2 the second object |
727 |
* @throws ClassCastException if o1 and o2 are not mutually comparable, |
728 |
* or are not Comparable with natural ordering |
729 |
* @throws NullPointerException if o1 or o2 is null with natural ordering |
730 |
*/ |
731 |
final int compare(Object o1, Object o2) |
732 |
{ |
733 |
return (comparator == null |
734 |
? ((Comparable) o1).compareTo(o2) |
735 |
: comparator.compare(o1, o2)); |
736 |
} |
737 |
|
738 |
/** |
739 |
* Maintain red-black balance after deleting a node. |
740 |
* |
741 |
* @param node the child of the node just deleted, possibly nil |
742 |
* @param parent the parent of the node just deleted, never nil |
743 |
*/ |
744 |
private void deleteFixup(Node node, Node parent) |
745 |
{ |
746 |
// if (parent == nil) |
747 |
// throw new InternalError(); |
748 |
// If a black node has been removed, we need to rebalance to avoid |
749 |
// violating the "same number of black nodes on any path" rule. If |
750 |
// node is red, we can simply recolor it black and all is well. |
751 |
while (node != root && node.color == BLACK) |
752 |
{ |
753 |
if (node == parent.left) |
754 |
{ |
755 |
// Rebalance left side. |
756 |
Node sibling = parent.right; |
757 |
// if (sibling == nil) |
758 |
// throw new InternalError(); |
759 |
if (sibling.color == RED) |
760 |
{ |
761 |
// Case 1: Sibling is red. |
762 |
// Recolor sibling and parent, and rotate parent left. |
763 |
sibling.color = BLACK; |
764 |
parent.color = RED; |
765 |
rotateLeft(parent); |
766 |
sibling = parent.right; |
767 |
} |
768 |
|
769 |
if (sibling.left.color == BLACK && sibling.right.color == BLACK) |
770 |
{ |
771 |
// Case 2: Sibling has no red children. |
772 |
// Recolor sibling, and move to parent. |
773 |
sibling.color = RED; |
774 |
node = parent; |
775 |
parent = parent.parent; |
776 |
} |
777 |
else |
778 |
{ |
779 |
if (sibling.right.color == BLACK) |
780 |
{ |
781 |
// Case 3: Sibling has red left child. |
782 |
// Recolor sibling and left child, rotate sibling right. |
783 |
sibling.left.color = BLACK; |
784 |
sibling.color = RED; |
785 |
rotateRight(sibling); |
786 |
sibling = parent.right; |
787 |
} |
788 |
// Case 4: Sibling has red right child. Recolor sibling, |
789 |
// right child, and parent, and rotate parent left. |
790 |
sibling.color = parent.color; |
791 |
parent.color = BLACK; |
792 |
sibling.right.color = BLACK; |
793 |
rotateLeft(parent); |
794 |
node = root; // Finished. |
795 |
} |
796 |
} |
797 |
else |
798 |
{ |
799 |
// Symmetric "mirror" of left-side case. |
800 |
Node sibling = parent.left; |
801 |
// if (sibling == nil) |
802 |
// throw new InternalError(); |
803 |
if (sibling.color == RED) |
804 |
{ |
805 |
// Case 1: Sibling is red. |
806 |
// Recolor sibling and parent, and rotate parent right. |
807 |
sibling.color = BLACK; |
808 |
parent.color = RED; |
809 |
rotateRight(parent); |
810 |
sibling = parent.left; |
811 |
} |
812 |
|
813 |
if (sibling.right.color == BLACK && sibling.left.color == BLACK) |
814 |
{ |
815 |
// Case 2: Sibling has no red children. |
816 |
// Recolor sibling, and move to parent. |
817 |
sibling.color = RED; |
818 |
node = parent; |
819 |
parent = parent.parent; |
820 |
} |
821 |
else |
822 |
{ |
823 |
if (sibling.left.color == BLACK) |
824 |
{ |
825 |
// Case 3: Sibling has red right child. |
826 |
// Recolor sibling and right child, rotate sibling left. |
827 |
sibling.right.color = BLACK; |
828 |
sibling.color = RED; |
829 |
rotateLeft(sibling); |
830 |
sibling = parent.left; |
831 |
} |
832 |
// Case 4: Sibling has red left child. Recolor sibling, |
833 |
// left child, and parent, and rotate parent right. |
834 |
sibling.color = parent.color; |
835 |
parent.color = BLACK; |
836 |
sibling.left.color = BLACK; |
837 |
rotateRight(parent); |
838 |
node = root; // Finished. |
839 |
} |
840 |
} |
841 |
} |
842 |
node.color = BLACK; |
843 |
} |
844 |
|
845 |
/** |
846 |
* Construct a perfectly balanced tree consisting of n "blank" nodes. This |
847 |
* permits a tree to be generated from pre-sorted input in linear time. |
848 |
* |
849 |
* @param count the number of blank nodes, non-negative |
850 |
*/ |
851 |
private void fabricateTree(final int count) |
852 |
{ |
853 |
if (count == 0) |
854 |
return; |
855 |
|
856 |
// We color every row of nodes black, except for the overflow nodes. |
857 |
// I believe that this is the optimal arrangement. We construct the tree |
858 |
// in place by temporarily linking each node to the next node in the row, |
859 |
// then updating those links to the children when working on the next row. |
860 |
|
861 |
// Make the root node. |
862 |
root = new Node(null, null, BLACK); |
863 |
size = count; |
864 |
Node row = root; |
865 |
int rowsize; |
866 |
|
867 |
// Fill each row that is completely full of nodes. |
868 |
for (rowsize = 2; rowsize + rowsize <= count; rowsize <<= 1) |
869 |
{ |
870 |
Node parent = row; |
871 |
Node last = null; |
872 |
for (int i = 0; i < rowsize; i += 2) |
873 |
{ |
874 |
Node left = new Node(null, null, BLACK); |
875 |
Node right = new Node(null, null, BLACK); |
876 |
left.parent = parent; |
877 |
left.right = right; |
878 |
right.parent = parent; |
879 |
parent.left = left; |
880 |
Node next = parent.right; |
881 |
parent.right = right; |
882 |
parent = next; |
883 |
if (last != null) |
884 |
last.right = left; |
885 |
last = right; |
886 |
} |
887 |
row = row.left; |
888 |
} |
889 |
|
890 |
// Now do the partial final row in red. |
891 |
int overflow = count - rowsize; |
892 |
Node parent = row; |
893 |
int i; |
894 |
for (i = 0; i < overflow; i += 2) |
895 |
{ |
896 |
Node left = new Node(null, null, RED); |
897 |
Node right = new Node(null, null, RED); |
898 |
left.parent = parent; |
899 |
right.parent = parent; |
900 |
parent.left = left; |
901 |
Node next = parent.right; |
902 |
parent.right = right; |
903 |
parent = next; |
904 |
} |
905 |
// Add a lone left node if necessary. |
906 |
if (i - overflow == 0) |
907 |
{ |
908 |
Node left = new Node(null, null, RED); |
909 |
left.parent = parent; |
910 |
parent.left = left; |
911 |
parent = parent.right; |
912 |
left.parent.right = nil; |
913 |
} |
914 |
// Unlink the remaining nodes of the previous row. |
915 |
while (parent != nil) |
916 |
{ |
917 |
Node next = parent.right; |
918 |
parent.right = nil; |
919 |
parent = next; |
920 |
} |
921 |
} |
922 |
|
923 |
/** |
924 |
* Returns the first sorted node in the map, or nil if empty. Package |
925 |
* visible for use by nested classes. |
926 |
* |
927 |
* @return the first node |
928 |
*/ |
929 |
final Node firstNode() |
930 |
{ |
931 |
// Exploit fact that nil.left == nil. |
932 |
Node node = root; |
933 |
while (node.left != nil) |
934 |
node = node.left; |
935 |
return node; |
936 |
} |
937 |
|
938 |
/** |
939 |
* Return the TreeMap.Node associated with key, or the nil node if no such |
940 |
* node exists in the tree. Package visible for use by nested classes. |
941 |
* |
942 |
* @param key the key to search for |
943 |
* @return the node where the key is found, or nil |
944 |
*/ |
945 |
final Node getNode(Object key) |
946 |
{ |
947 |
Node current = root; |
948 |
while (current != nil) |
949 |
{ |
950 |
int comparison = compare(key, current.key); |
951 |
if (comparison > 0) |
952 |
current = current.right; |
953 |
else if (comparison < 0) |
954 |
current = current.left; |
955 |
else |
956 |
return current; |
957 |
} |
958 |
return current; |
959 |
} |
960 |
|
961 |
/** |
962 |
* Find the "highest" node which is < key. If key is nil, return last |
963 |
* node. Package visible for use by nested classes. |
964 |
* |
965 |
* @param key the upper bound, exclusive |
966 |
* @return the previous node |
967 |
*/ |
968 |
final Node highestLessThan(Object key) |
969 |
{ |
970 |
if (key == nil) |
971 |
return lastNode(); |
972 |
|
973 |
Node last = nil; |
974 |
Node current = root; |
975 |
int comparison = 0; |
976 |
|
977 |
while (current != nil) |
978 |
{ |
979 |
last = current; |
980 |
comparison = compare(key, current.key); |
981 |
if (comparison > 0) |
982 |
current = current.right; |
983 |
else if (comparison < 0) |
984 |
current = current.left; |
985 |
else // Exact match. |
986 |
return predecessor(last); |
987 |
} |
988 |
return comparison <= 0 ? predecessor(last) : last; |
989 |
} |
990 |
|
991 |
/** |
992 |
* Maintain red-black balance after inserting a new node. |
993 |
* |
994 |
* @param n the newly inserted node |
995 |
*/ |
996 |
private void insertFixup(Node n) |
997 |
{ |
998 |
// Only need to rebalance when parent is a RED node, and while at least |
999 |
// 2 levels deep into the tree (ie: node has a grandparent). Remember |
1000 |
// that nil.color == BLACK. |
1001 |
while (n.parent.color == RED && n.parent.parent != nil) |
1002 |
{ |
1003 |
if (n.parent == n.parent.parent.left) |
1004 |
{ |
1005 |
Node uncle = n.parent.parent.right; |
1006 |
// Uncle may be nil, in which case it is BLACK. |
1007 |
if (uncle.color == RED) |
1008 |
{ |
1009 |
// Case 1. Uncle is RED: Change colors of parent, uncle, |
1010 |
// and grandparent, and move n to grandparent. |
1011 |
n.parent.color = BLACK; |
1012 |
uncle.color = BLACK; |
1013 |
uncle.parent.color = RED; |
1014 |
n = uncle.parent; |
1015 |
} |
1016 |
else |
1017 |
{ |
1018 |
if (n == n.parent.right) |
1019 |
{ |
1020 |
// Case 2. Uncle is BLACK and x is right child. |
1021 |
// Move n to parent, and rotate n left. |
1022 |
n = n.parent; |
1023 |
rotateLeft(n); |
1024 |
} |
1025 |
// Case 3. Uncle is BLACK and x is left child. |
1026 |
// Recolor parent, grandparent, and rotate grandparent right. |
1027 |
n.parent.color = BLACK; |
1028 |
n.parent.parent.color = RED; |
1029 |
rotateRight(n.parent.parent); |
1030 |
} |
1031 |
} |
1032 |
else |
1033 |
{ |
1034 |
// Mirror image of above code. |
1035 |
Node uncle = n.parent.parent.left; |
1036 |
// Uncle may be nil, in which case it is BLACK. |
1037 |
if (uncle.color == RED) |
1038 |
{ |
1039 |
// Case 1. Uncle is RED: Change colors of parent, uncle, |
1040 |
// and grandparent, and move n to grandparent. |
1041 |
n.parent.color = BLACK; |
1042 |
uncle.color = BLACK; |
1043 |
uncle.parent.color = RED; |
1044 |
n = uncle.parent; |
1045 |
} |
1046 |
else |
1047 |
{ |
1048 |
if (n == n.parent.left) |
1049 |
{ |
1050 |
// Case 2. Uncle is BLACK and x is left child. |
1051 |
// Move n to parent, and rotate n right. |
1052 |
n = n.parent; |
1053 |
rotateRight(n); |
1054 |
} |
1055 |
// Case 3. Uncle is BLACK and x is right child. |
1056 |
// Recolor parent, grandparent, and rotate grandparent left. |
1057 |
n.parent.color = BLACK; |
1058 |
n.parent.parent.color = RED; |
1059 |
rotateLeft(n.parent.parent); |
1060 |
} |
1061 |
} |
1062 |
} |
1063 |
root.color = BLACK; |
1064 |
} |
1065 |
|
1066 |
/** |
1067 |
* Returns the last sorted node in the map, or nil if empty. |
1068 |
* |
1069 |
* @return the last node |
1070 |
*/ |
1071 |
private Node lastNode() |
1072 |
{ |
1073 |
// Exploit fact that nil.right == nil. |
1074 |
Node node = root; |
1075 |
while (node.right != nil) |
1076 |
node = node.right; |
1077 |
return node; |
1078 |
} |
1079 |
|
1080 |
/** |
1081 |
* Find the "lowest" node which is >= key. If key is nil, return either |
1082 |
* nil or the first node, depending on the parameter first. |
1083 |
* Package visible for use by nested classes. |
1084 |
* |
1085 |
* @param key the lower bound, inclusive |
1086 |
* @param first true to return the first element instead of nil for nil key |
1087 |
* @return the next node |
1088 |
*/ |
1089 |
final Node lowestGreaterThan(Object key, boolean first) |
1090 |
{ |
1091 |
if (key == nil) |
1092 |
return first ? firstNode() : nil; |
1093 |
|
1094 |
Node last = nil; |
1095 |
Node current = root; |
1096 |
int comparison = 0; |
1097 |
|
1098 |
while (current != nil) |
1099 |
{ |
1100 |
last = current; |
1101 |
comparison = compare(key, current.key); |
1102 |
if (comparison > 0) |
1103 |
current = current.right; |
1104 |
else if (comparison < 0) |
1105 |
current = current.left; |
1106 |
else |
1107 |
return current; |
1108 |
} |
1109 |
return comparison > 0 ? successor(last) : last; |
1110 |
} |
1111 |
|
1112 |
/** |
1113 |
* Return the node preceding the given one, or nil if there isn't one. |
1114 |
* |
1115 |
* @param node the current node, not nil |
1116 |
* @return the prior node in sorted order |
1117 |
*/ |
1118 |
private Node predecessor(Node node) |
1119 |
{ |
1120 |
if (node.left != nil) |
1121 |
{ |
1122 |
node = node.left; |
1123 |
while (node.right != nil) |
1124 |
node = node.right; |
1125 |
return node; |
1126 |
} |
1127 |
|
1128 |
Node parent = node.parent; |
1129 |
// Exploit fact that nil.left == nil and node is non-nil. |
1130 |
while (node == parent.left) |
1131 |
{ |
1132 |
node = parent; |
1133 |
parent = node.parent; |
1134 |
} |
1135 |
return parent; |
1136 |
} |
1137 |
|
1138 |
/** |
1139 |
* Construct a tree from sorted keys in linear time. Package visible for |
1140 |
* use by TreeSet. |
1141 |
* |
1142 |
* @param s the stream to read from |
1143 |
* @param count the number of keys to read |
1144 |
* @param readValue true to read values, false to insert "" as the value |
1145 |
* @throws ClassNotFoundException if the underlying stream fails |
1146 |
* @throws IOException if the underlying stream fails |
1147 |
* @see #readObject(ObjectInputStream) |
1148 |
* @see TreeSet#readObject(ObjectInputStream) |
1149 |
*/ |
1150 |
final void putFromObjStream(ObjectInputStream s, int count, |
1151 |
boolean readValues) |
1152 |
throws IOException, ClassNotFoundException |
1153 |
{ |
1154 |
fabricateTree(count); |
1155 |
Node node = firstNode(); |
1156 |
|
1157 |
while (--count >= 0) |
1158 |
{ |
1159 |
node.key = s.readObject(); |
1160 |
node.value = readValues ? s.readObject() : ""; |
1161 |
node = successor(node); |
1162 |
} |
1163 |
} |
1164 |
|
1165 |
/** |
1166 |
* Construct a tree from sorted keys in linear time, with values of "". |
1167 |
* Package visible for use by TreeSet. |
1168 |
* |
1169 |
* @param keys the iterator over the sorted keys |
1170 |
* @param count the number of nodes to insert |
1171 |
* @see TreeSet#TreeSet(SortedSet) |
1172 |
*/ |
1173 |
final void putKeysLinear(Iterator keys, int count) |
1174 |
{ |
1175 |
fabricateTree(count); |
1176 |
Node node = firstNode(); |
1177 |
|
1178 |
while (--count >= 0) |
1179 |
{ |
1180 |
node.key = keys.next(); |
1181 |
node.value = ""; |
1182 |
node = successor(node); |
1183 |
} |
1184 |
} |
1185 |
|
1186 |
/** |
1187 |
* Deserializes this object from the given stream. |
1188 |
* |
1189 |
* @param s the stream to read from |
1190 |
* @throws ClassNotFoundException if the underlying stream fails |
1191 |
* @throws IOException if the underlying stream fails |
1192 |
* @serialData the <i>size</i> (int), followed by key (Object) and value |
1193 |
* (Object) pairs in sorted order |
1194 |
*/ |
1195 |
private void readObject(ObjectInputStream s) |
1196 |
throws IOException, ClassNotFoundException |
1197 |
{ |
1198 |
s.defaultReadObject(); |
1199 |
int size = s.readInt(); |
1200 |
putFromObjStream(s, size, true); |
1201 |
} |
1202 |
|
1203 |
/** |
1204 |
* Remove node from tree. This will increment modCount and decrement size. |
1205 |
* Node must exist in the tree. Package visible for use by nested classes. |
1206 |
* |
1207 |
* @param node the node to remove |
1208 |
*/ |
1209 |
final void removeNode(Node node) |
1210 |
{ |
1211 |
Node splice; |
1212 |
Node child; |
1213 |
|
1214 |
modCount++; |
1215 |
size--; |
1216 |
|
1217 |
// Find splice, the node at the position to actually remove from the tree. |
1218 |
if (node.left == nil) |
1219 |
{ |
1220 |
// Node to be deleted has 0 or 1 children. |
1221 |
splice = node; |
1222 |
child = node.right; |
1223 |
} |
1224 |
else if (node.right == nil) |
1225 |
{ |
1226 |
// Node to be deleted has 1 child. |
1227 |
splice = node; |
1228 |
child = node.left; |
1229 |
} |
1230 |
else |
1231 |
{ |
1232 |
// Node has 2 children. Splice is node's predecessor, and we swap |
1233 |
// its contents into node. |
1234 |
splice = node.left; |
1235 |
while (splice.right != nil) |
1236 |
splice = splice.right; |
1237 |
child = splice.left; |
1238 |
node.key = splice.key; |
1239 |
node.value = splice.value; |
1240 |
} |
1241 |
|
1242 |
// Unlink splice from the tree. |
1243 |
Node parent = splice.parent; |
1244 |
if (child != nil) |
1245 |
child.parent = parent; |
1246 |
if (parent == nil) |
1247 |
{ |
1248 |
// Special case for 0 or 1 node remaining. |
1249 |
root = child; |
1250 |
return; |
1251 |
} |
1252 |
if (splice == parent.left) |
1253 |
parent.left = child; |
1254 |
else |
1255 |
parent.right = child; |
1256 |
|
1257 |
if (splice.color == BLACK) |
1258 |
deleteFixup(child, parent); |
1259 |
} |
1260 |
|
1261 |
/** |
1262 |
* Rotate node n to the left. |
1263 |
* |
1264 |
* @param node the node to rotate |
1265 |
*/ |
1266 |
private void rotateLeft(Node node) |
1267 |
{ |
1268 |
Node child = node.right; |
1269 |
// if (node == nil || child == nil) |
1270 |
// throw new InternalError(); |
1271 |
|
1272 |
// Establish node.right link. |
1273 |
node.right = child.left; |
1274 |
if (child.left != nil) |
1275 |
child.left.parent = node; |
1276 |
|
1277 |
// Establish child->parent link. |
1278 |
child.parent = node.parent; |
1279 |
if (node.parent != nil) |
1280 |
{ |
1281 |
if (node == node.parent.left) |
1282 |
node.parent.left = child; |
1283 |
else |
1284 |
node.parent.right = child; |
1285 |
} |
1286 |
else |
1287 |
root = child; |
1288 |
|
1289 |
// Link n and child. |
1290 |
child.left = node; |
1291 |
node.parent = child; |
1292 |
} |
1293 |
|
1294 |
/** |
1295 |
* Rotate node n to the right. |
1296 |
* |
1297 |
* @param node the node to rotate |
1298 |
*/ |
1299 |
private void rotateRight(Node node) |
1300 |
{ |
1301 |
Node child = node.left; |
1302 |
// if (node == nil || child == nil) |
1303 |
// throw new InternalError(); |
1304 |
|
1305 |
// Establish node.left link. |
1306 |
node.left = child.right; |
1307 |
if (child.right != nil) |
1308 |
child.right.parent = node; |
1309 |
|
1310 |
// Establish child->parent link. |
1311 |
child.parent = node.parent; |
1312 |
if (node.parent != nil) |
1313 |
{ |
1314 |
if (node == node.parent.right) |
1315 |
node.parent.right = child; |
1316 |
else |
1317 |
node.parent.left = child; |
1318 |
} |
1319 |
else |
1320 |
root = child; |
1321 |
|
1322 |
// Link n and child. |
1323 |
child.right = node; |
1324 |
node.parent = child; |
1325 |
} |
1326 |
|
1327 |
/** |
1328 |
* Return the node following the given one, or nil if there isn't one. |
1329 |
* Package visible for use by nested classes. |
1330 |
* |
1331 |
* @param node the current node, not nil |
1332 |
* @return the next node in sorted order |
1333 |
*/ |
1334 |
final Node successor(Node node) |
1335 |
{ |
1336 |
if (node.right != nil) |
1337 |
{ |
1338 |
node = node.right; |
1339 |
while (node.left != nil) |
1340 |
node = node.left; |
1341 |
return node; |
1342 |
} |
1343 |
|
1344 |
Node parent = node.parent; |
1345 |
// Exploit fact that nil.right == nil and node is non-nil. |
1346 |
while (node == parent.right) |
1347 |
{ |
1348 |
node = parent; |
1349 |
parent = parent.parent; |
1350 |
} |
1351 |
return parent; |
1352 |
} |
1353 |
|
1354 |
/** |
1355 |
* Serializes this object to the given stream. |
1356 |
* |
1357 |
* @param s the stream to write to |
1358 |
* @throws IOException if the underlying stream fails |
1359 |
* @serialData the <i>size</i> (int), followed by key (Object) and value |
1360 |
* (Object) pairs in sorted order |
1361 |
*/ |
1362 |
private void writeObject(ObjectOutputStream s) throws IOException |
1363 |
{ |
1364 |
s.defaultWriteObject(); |
1365 |
|
1366 |
Node node = firstNode(); |
1367 |
s.writeInt(size); |
1368 |
while (node != nil) |
1369 |
{ |
1370 |
s.writeObject(node.key); |
1371 |
s.writeObject(node.value); |
1372 |
node = successor(node); |
1373 |
} |
1374 |
} |
1375 |
|
1376 |
/** |
1377 |
* Iterate over HashMap's entries. This implementation is parameterized |
1378 |
* to give a sequential view of keys, values, or entries. |
1379 |
* |
1380 |
* @author Eric Blake <ebb9@email.byu.edu> |
1381 |
*/ |
1382 |
private final class TreeIterator implements Iterator |
1383 |
{ |
1384 |
/** |
1385 |
* The type of this Iterator: {@link #KEYS}, {@link #VALUES}, |
1386 |
* or {@link #ENTRIES}. |
1387 |
*/ |
1388 |
private final int type; |
1389 |
/** The number of modifications to the backing Map that we know about. */ |
1390 |
private int knownMod = modCount; |
1391 |
/** The last Entry returned by a next() call. */ |
1392 |
private Node last; |
1393 |
/** The next entry that should be returned by next(). */ |
1394 |
private Node next; |
1395 |
/** |
1396 |
* The last node visible to this iterator. This is used when iterating |
1397 |
* on a SubMap. |
1398 |
*/ |
1399 |
private final Node max; |
1400 |
|
1401 |
/** |
1402 |
* Construct a new TreeIterator with the supplied type. |
1403 |
* @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} |
1404 |
*/ |
1405 |
TreeIterator(int type) |
1406 |
{ |
1407 |
// FIXME gcj cannot handle this. Bug java/4695 |
1408 |
// this(type, firstNode(), nil); |
1409 |
this.type = type; |
1410 |
this.next = firstNode(); |
1411 |
this.max = nil; |
1412 |
} |
1413 |
|
1414 |
/** |
1415 |
* Construct a new TreeIterator with the supplied type. Iteration will |
1416 |
* be from "first" (inclusive) to "max" (exclusive). |
1417 |
* |
1418 |
* @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} |
1419 |
* @param first where to start iteration, nil for empty iterator |
1420 |
* @param max the cutoff for iteration, nil for all remaining nodes |
1421 |
*/ |
1422 |
TreeIterator(int type, Node first, Node max) |
1423 |
{ |
1424 |
this.type = type; |
1425 |
this.next = first; |
1426 |
this.max = max; |
1427 |
} |
1428 |
|
1429 |
/** |
1430 |
* Returns true if the Iterator has more elements. |
1431 |
* @return true if there are more elements |
1432 |
* @throws ConcurrentModificationException if the TreeMap was modified |
1433 |
*/ |
1434 |
public boolean hasNext() |
1435 |
{ |
1436 |
if (knownMod != modCount) |
1437 |
throw new ConcurrentModificationException(); |
1438 |
return next != max; |
1439 |
} |
1440 |
|
1441 |
/** |
1442 |
* Returns the next element in the Iterator's sequential view. |
1443 |
* @return the next element |
1444 |
* @throws ConcurrentModificationException if the TreeMap was modified |
1445 |
* @throws NoSuchElementException if there is none |
1446 |
*/ |
1447 |
public Object next() |
1448 |
{ |
1449 |
if (knownMod != modCount) |
1450 |
throw new ConcurrentModificationException(); |
1451 |
if (next == max) |
1452 |
throw new NoSuchElementException(); |
1453 |
last = next; |
1454 |
next = successor(last); |
1455 |
|
1456 |
if (type == VALUES) |
1457 |
return last.value; |
1458 |
else if (type == KEYS) |
1459 |
return last.key; |
1460 |
return last; |
1461 |
} |
1462 |
|
1463 |
/** |
1464 |
* Removes from the backing TreeMap the last element which was fetched |
1465 |
* with the <code>next()</code> method. |
1466 |
* @throws ConcurrentModificationException if the TreeMap was modified |
1467 |
* @throws IllegalStateException if called when there is no last element |
1468 |
*/ |
1469 |
public void remove() |
1470 |
{ |
1471 |
if (last == null) |
1472 |
throw new IllegalStateException(); |
1473 |
if (knownMod != modCount) |
1474 |
throw new ConcurrentModificationException(); |
1475 |
|
1476 |
removeNode(last); |
1477 |
last = null; |
1478 |
knownMod++; |
1479 |
} |
1480 |
} // class TreeIterator |
1481 |
|
1482 |
/** |
1483 |
* Implementation of {@link #subMap(Object, Object)} and other map |
1484 |
* ranges. This class provides a view of a portion of the original backing |
1485 |
* map, and throws {@link IllegalArgumentException} for attempts to |
1486 |
* access beyond that range. |
1487 |
* |
1488 |
* @author Eric Blake <ebb9@email.byu.edu> |
1489 |
*/ |
1490 |
private final class SubMap extends AbstractMap implements SortedMap |
1491 |
{ |
1492 |
/** |
1493 |
* The lower range of this view, inclusive, or nil for unbounded. |
1494 |
* Package visible for use by nested classes. |
1495 |
*/ |
1496 |
final Object minKey; |
1497 |
|
1498 |
/** |
1499 |
* The upper range of this view, exclusive, or nil for unbounded. |
1500 |
* Package visible for use by nested classes. |
1501 |
*/ |
1502 |
final Object maxKey; |
1503 |
|
1504 |
/** |
1505 |
* The cache for {@link #entrySet()}. |
1506 |
*/ |
1507 |
private Set entries; |
1508 |
|
1509 |
/** |
1510 |
* Create a SubMap representing the elements between minKey (inclusive) |
1511 |
* and maxKey (exclusive). If minKey is nil, SubMap has no lower bound |
1512 |
* (headMap). If maxKey is nil, the SubMap has no upper bound (tailMap). |
1513 |
* |
1514 |
* @param minKey the lower bound |
1515 |
* @param maxKey the upper bound |
1516 |
* @throws IllegalArgumentException if minKey > maxKey |
1517 |
*/ |
1518 |
SubMap(Object minKey, Object maxKey) |
1519 |
{ |
1520 |
if (minKey != nil && maxKey != nil && compare(minKey, maxKey) > 0) |
1521 |
throw new IllegalArgumentException("fromKey > toKey"); |
1522 |
this.minKey = minKey; |
1523 |
this.maxKey = maxKey; |
1524 |
} |
1525 |
|
1526 |
/** |
1527 |
* Check if "key" is in within the range bounds for this SubMap. The |
1528 |
* lower ("from") SubMap range is inclusive, and the upper ("to") bound |
1529 |
* is exclusive. Package visible for use by nested classes. |
1530 |
* |
1531 |
* @param key the key to check |
1532 |
* @return true if the key is in range |
1533 |
*/ |
1534 |
final boolean keyInRange(Object key) |
1535 |
{ |
1536 |
return ((minKey == nil || compare(key, minKey) >= 0) |
1537 |
&& (maxKey == nil || compare(key, maxKey) < 0)); |
1538 |
} |
1539 |
|
1540 |
public void clear() |
1541 |
{ |
1542 |
Node next = lowestGreaterThan(minKey, true); |
1543 |
Node max = lowestGreaterThan(maxKey, false); |
1544 |
while (next != max) |
1545 |
{ |
1546 |
Node current = next; |
1547 |
next = successor(current); |
1548 |
removeNode(current); |
1549 |
} |
1550 |
} |
1551 |
|
1552 |
public Comparator comparator() |
1553 |
{ |
1554 |
return comparator; |
1555 |
} |
1556 |
|
1557 |
public boolean containsKey(Object key) |
1558 |
{ |
1559 |
return keyInRange(key) && TreeMap.this.containsKey(key); |
1560 |
} |
1561 |
|
1562 |
public boolean containsValue(Object value) |
1563 |
{ |
1564 |
Node node = lowestGreaterThan(minKey, true); |
1565 |
Node max = lowestGreaterThan(maxKey, false); |
1566 |
while (node != max) |
1567 |
{ |
1568 |
if (equals(value, node.getValue())) |
1569 |
return true; |
1570 |
node = successor(node); |
1571 |
} |
1572 |
return false; |
1573 |
} |
1574 |
|
1575 |
public Set entrySet() |
1576 |
{ |
1577 |
if (entries == null) |
1578 |
// Create an AbstractSet with custom implementations of those methods |
1579 |
// that can be overriden easily and efficiently. |
1580 |
entries = new AbstractSet() |
1581 |
{ |
1582 |
public int size() |
1583 |
{ |
1584 |
return SubMap.this.size(); |
1585 |
} |
1586 |
|
1587 |
public Iterator iterator() |
1588 |
{ |
1589 |
Node first = lowestGreaterThan(minKey, true); |
1590 |
Node max = lowestGreaterThan(maxKey, false); |
1591 |
return new TreeIterator(ENTRIES, first, max); |
1592 |
} |
1593 |
|
1594 |
public void clear() |
1595 |
{ |
1596 |
SubMap.this.clear(); |
1597 |
} |
1598 |
|
1599 |
public boolean contains(Object o) |
1600 |
{ |
1601 |
if (! (o instanceof Map.Entry)) |
1602 |
return false; |
1603 |
Map.Entry me = (Map.Entry) o; |
1604 |
Object key = me.getKey(); |
1605 |
if (! keyInRange(key)) |
1606 |
return false; |
1607 |
Node n = getNode(key); |
1608 |
return n != nil && AbstractSet.equals(me.getValue(), n.value); |
1609 |
} |
1610 |
|
1611 |
public boolean remove(Object o) |
1612 |
{ |
1613 |
if (! (o instanceof Map.Entry)) |
1614 |
return false; |
1615 |
Map.Entry me = (Map.Entry) o; |
1616 |
Object key = me.getKey(); |
1617 |
if (! keyInRange(key)) |
1618 |
return false; |
1619 |
Node n = getNode(key); |
1620 |
if (n != nil && AbstractSet.equals(me.getValue(), n.value)) |
1621 |
{ |
1622 |
removeNode(n); |
1623 |
return true; |
1624 |
} |
1625 |
return false; |
1626 |
} |
1627 |
}; |
1628 |
return entries; |
1629 |
} |
1630 |
|
1631 |
public Object firstKey() |
1632 |
{ |
1633 |
Node node = lowestGreaterThan(minKey, true); |
1634 |
if (node == nil || ! keyInRange(node.key)) |
1635 |
throw new NoSuchElementException(); |
1636 |
return node.key; |
1637 |
} |
1638 |
|
1639 |
public Object get(Object key) |
1640 |
{ |
1641 |
if (keyInRange(key)) |
1642 |
return TreeMap.this.get(key); |
1643 |
return null; |
1644 |
} |
1645 |
|
1646 |
public SortedMap headMap(Object toKey) |
1647 |
{ |
1648 |
if (! keyInRange(toKey)) |
1649 |
throw new IllegalArgumentException("key outside range"); |
1650 |
return new SubMap(minKey, toKey); |
1651 |
} |
1652 |
|
1653 |
public Set keySet() |
1654 |
{ |
1655 |
if (this.keys == null) |
1656 |
// Create an AbstractSet with custom implementations of those methods |
1657 |
// that can be overriden easily and efficiently. |
1658 |
this.keys = new AbstractSet() |
1659 |
{ |
1660 |
public int size() |
1661 |
{ |
1662 |
return SubMap.this.size(); |
1663 |
} |
1664 |
|
1665 |
public Iterator iterator() |
1666 |
{ |
1667 |
Node first = lowestGreaterThan(minKey, true); |
1668 |
Node max = lowestGreaterThan(maxKey, false); |
1669 |
return new TreeIterator(KEYS, first, max); |
1670 |
} |
1671 |
|
1672 |
public void clear() |
1673 |
{ |
1674 |
SubMap.this.clear(); |
1675 |
} |
1676 |
|
1677 |
public boolean contains(Object o) |
1678 |
{ |
1679 |
if (! keyInRange(o)) |
1680 |
return false; |
1681 |
return getNode(o) != nil; |
1682 |
} |
1683 |
|
1684 |
public boolean remove(Object o) |
1685 |
{ |
1686 |
if (! keyInRange(o)) |
1687 |
return false; |
1688 |
Node n = getNode(o); |
1689 |
if (n != nil) |
1690 |
{ |
1691 |
removeNode(n); |
1692 |
return true; |
1693 |
} |
1694 |
return false; |
1695 |
} |
1696 |
}; |
1697 |
return this.keys; |
1698 |
} |
1699 |
|
1700 |
public Object lastKey() |
1701 |
{ |
1702 |
Node node = highestLessThan(maxKey); |
1703 |
if (node == nil || ! keyInRange(node.key)) |
1704 |
throw new NoSuchElementException(); |
1705 |
return node.key; |
1706 |
} |
1707 |
|
1708 |
public Object put(Object key, Object value) |
1709 |
{ |
1710 |
if (! keyInRange(key)) |
1711 |
throw new IllegalArgumentException("Key outside range"); |
1712 |
return TreeMap.this.put(key, value); |
1713 |
} |
1714 |
|
1715 |
public Object remove(Object key) |
1716 |
{ |
1717 |
if (keyInRange(key)) |
1718 |
return TreeMap.this.remove(key); |
1719 |
return null; |
1720 |
} |
1721 |
|
1722 |
public int size() |
1723 |
{ |
1724 |
Node node = lowestGreaterThan(minKey, true); |
1725 |
Node max = lowestGreaterThan(maxKey, false); |
1726 |
int count = 0; |
1727 |
while (node != max) |
1728 |
{ |
1729 |
count++; |
1730 |
node = successor(node); |
1731 |
} |
1732 |
return count; |
1733 |
} |
1734 |
|
1735 |
public SortedMap subMap(Object fromKey, Object toKey) |
1736 |
{ |
1737 |
if (! keyInRange(fromKey) || ! keyInRange(toKey)) |
1738 |
throw new IllegalArgumentException("key outside range"); |
1739 |
return new SubMap(fromKey, toKey); |
1740 |
} |
1741 |
|
1742 |
public SortedMap tailMap(Object fromKey) |
1743 |
{ |
1744 |
if (! keyInRange(fromKey)) |
1745 |
throw new IllegalArgumentException("key outside range"); |
1746 |
return new SubMap(fromKey, maxKey); |
1747 |
} |
1748 |
|
1749 |
public Collection values() |
1750 |
{ |
1751 |
if (this.values == null) |
1752 |
// Create an AbstractCollection with custom implementations of those |
1753 |
// methods that can be overriden easily and efficiently. |
1754 |
this.values = new AbstractCollection() |
1755 |
{ |
1756 |
public int size() |
1757 |
{ |
1758 |
return SubMap.this.size(); |
1759 |
} |
1760 |
|
1761 |
public Iterator iterator() |
1762 |
{ |
1763 |
Node first = lowestGreaterThan(minKey, true); |
1764 |
Node max = lowestGreaterThan(maxKey, false); |
1765 |
return new TreeIterator(VALUES, first, max); |
1766 |
} |
1767 |
|
1768 |
public void clear() |
1769 |
{ |
1770 |
SubMap.this.clear(); |
1771 |
} |
1772 |
}; |
1773 |
return this.values; |
1774 |
} |
1775 |
} // class SubMap |
1776 |
} // class TreeMap |