Print this page
Split |
Close |
Expand all |
Collapse all |
--- old/src/share/classes/java/util/TreeMap.java
+++ new/src/share/classes/java/util/TreeMap.java
1 1 /*
2 2 * Copyright (c) 1997, 2008, Oracle and/or its affiliates. All rights reserved.
3 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 4 *
5 5 * This code is free software; you can redistribute it and/or modify it
6 6 * under the terms of the GNU General Public License version 2 only, as
7 7 * published by the Free Software Foundation. Oracle designates this
8 8 * particular file as subject to the "Classpath" exception as provided
9 9 * by Oracle in the LICENSE file that accompanied this code.
10 10 *
11 11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 14 * version 2 for more details (a copy is included in the LICENSE file that
15 15 * accompanied this code).
16 16 *
17 17 * You should have received a copy of the GNU General Public License version
18 18 * 2 along with this work; if not, write to the Free Software Foundation,
19 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 20 *
21 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 22 * or visit www.oracle.com if you need additional information or have any
23 23 * questions.
24 24 */
25 25
26 26 package java.util;
27 27
28 28 /**
29 29 * A Red-Black tree based {@link NavigableMap} implementation.
30 30 * The map is sorted according to the {@linkplain Comparable natural
31 31 * ordering} of its keys, or by a {@link Comparator} provided at map
32 32 * creation time, depending on which constructor is used.
33 33 *
34 34 * <p>This implementation provides guaranteed log(n) time cost for the
35 35 * {@code containsKey}, {@code get}, {@code put} and {@code remove}
36 36 * operations. Algorithms are adaptations of those in Cormen, Leiserson, and
37 37 * Rivest's <em>Introduction to Algorithms</em>.
38 38 *
39 39 * <p>Note that the ordering maintained by a tree map, like any sorted map, and
40 40 * whether or not an explicit comparator is provided, must be <em>consistent
41 41 * with {@code equals}</em> if this sorted map is to correctly implement the
42 42 * {@code Map} interface. (See {@code Comparable} or {@code Comparator} for a
43 43 * precise definition of <em>consistent with equals</em>.) This is so because
44 44 * the {@code Map} interface is defined in terms of the {@code equals}
45 45 * operation, but a sorted map performs all key comparisons using its {@code
46 46 * compareTo} (or {@code compare}) method, so two keys that are deemed equal by
47 47 * this method are, from the standpoint of the sorted map, equal. The behavior
48 48 * of a sorted map <em>is</em> well-defined even if its ordering is
49 49 * inconsistent with {@code equals}; it just fails to obey the general contract
50 50 * of the {@code Map} interface.
51 51 *
52 52 * <p><strong>Note that this implementation is not synchronized.</strong>
53 53 * If multiple threads access a map concurrently, and at least one of the
54 54 * threads modifies the map structurally, it <em>must</em> be synchronized
55 55 * externally. (A structural modification is any operation that adds or
56 56 * deletes one or more mappings; merely changing the value associated
57 57 * with an existing key is not a structural modification.) This is
58 58 * typically accomplished by synchronizing on some object that naturally
59 59 * encapsulates the map.
60 60 * If no such object exists, the map should be "wrapped" using the
61 61 * {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap}
62 62 * method. This is best done at creation time, to prevent accidental
63 63 * unsynchronized access to the map: <pre>
64 64 * SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre>
65 65 *
66 66 * <p>The iterators returned by the {@code iterator} method of the collections
67 67 * returned by all of this class's "collection view methods" are
68 68 * <em>fail-fast</em>: if the map is structurally modified at any time after
69 69 * the iterator is created, in any way except through the iterator's own
70 70 * {@code remove} method, the iterator will throw a {@link
71 71 * ConcurrentModificationException}. Thus, in the face of concurrent
72 72 * modification, the iterator fails quickly and cleanly, rather than risking
73 73 * arbitrary, non-deterministic behavior at an undetermined time in the future.
74 74 *
75 75 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
76 76 * as it is, generally speaking, impossible to make any hard guarantees in the
77 77 * presence of unsynchronized concurrent modification. Fail-fast iterators
78 78 * throw {@code ConcurrentModificationException} on a best-effort basis.
79 79 * Therefore, it would be wrong to write a program that depended on this
80 80 * exception for its correctness: <em>the fail-fast behavior of iterators
81 81 * should be used only to detect bugs.</em>
82 82 *
83 83 * <p>All {@code Map.Entry} pairs returned by methods in this class
84 84 * and its views represent snapshots of mappings at the time they were
85 85 * produced. They do <strong>not</strong> support the {@code Entry.setValue}
86 86 * method. (Note however that it is possible to change mappings in the
87 87 * associated map using {@code put}.)
88 88 *
89 89 * <p>This class is a member of the
90 90 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
91 91 * Java Collections Framework</a>.
92 92 *
93 93 * @param <K> the type of keys maintained by this map
94 94 * @param <V> the type of mapped values
95 95 *
96 96 * @author Josh Bloch and Doug Lea
97 97 * @see Map
98 98 * @see HashMap
99 99 * @see Hashtable
100 100 * @see Comparable
101 101 * @see Comparator
102 102 * @see Collection
103 103 * @since 1.2
104 104 */
105 105
106 106 public class TreeMap<K,V>
107 107 extends AbstractMap<K,V>
108 108 implements NavigableMap<K,V>, Cloneable, java.io.Serializable
109 109 {
110 110 /**
111 111 * The comparator used to maintain order in this tree map, or
112 112 * null if it uses the natural ordering of its keys.
113 113 *
114 114 * @serial
115 115 */
116 116 private final Comparator<? super K> comparator;
117 117
118 118 private transient Entry<K,V> root = null;
119 119
120 120 /**
121 121 * The number of entries in the tree
122 122 */
123 123 private transient int size = 0;
124 124
125 125 /**
126 126 * The number of structural modifications to the tree.
127 127 */
128 128 private transient int modCount = 0;
129 129
130 130 /**
131 131 * Constructs a new, empty tree map, using the natural ordering of its
132 132 * keys. All keys inserted into the map must implement the {@link
133 133 * Comparable} interface. Furthermore, all such keys must be
134 134 * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
135 135 * a {@code ClassCastException} for any keys {@code k1} and
136 136 * {@code k2} in the map. If the user attempts to put a key into the
137 137 * map that violates this constraint (for example, the user attempts to
138 138 * put a string key into a map whose keys are integers), the
139 139 * {@code put(Object key, Object value)} call will throw a
140 140 * {@code ClassCastException}.
141 141 */
142 142 public TreeMap() {
143 143 comparator = null;
144 144 }
145 145
146 146 /**
147 147 * Constructs a new, empty tree map, ordered according to the given
148 148 * comparator. All keys inserted into the map must be <em>mutually
149 149 * comparable</em> by the given comparator: {@code comparator.compare(k1,
150 150 * k2)} must not throw a {@code ClassCastException} for any keys
151 151 * {@code k1} and {@code k2} in the map. If the user attempts to put
152 152 * a key into the map that violates this constraint, the {@code put(Object
153 153 * key, Object value)} call will throw a
154 154 * {@code ClassCastException}.
155 155 *
156 156 * @param comparator the comparator that will be used to order this map.
157 157 * If {@code null}, the {@linkplain Comparable natural
158 158 * ordering} of the keys will be used.
159 159 */
160 160 public TreeMap(Comparator<? super K> comparator) {
161 161 this.comparator = comparator;
162 162 }
163 163
164 164 /**
165 165 * Constructs a new tree map containing the same mappings as the given
166 166 * map, ordered according to the <em>natural ordering</em> of its keys.
167 167 * All keys inserted into the new map must implement the {@link
168 168 * Comparable} interface. Furthermore, all such keys must be
169 169 * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
170 170 * a {@code ClassCastException} for any keys {@code k1} and
171 171 * {@code k2} in the map. This method runs in n*log(n) time.
172 172 *
173 173 * @param m the map whose mappings are to be placed in this map
174 174 * @throws ClassCastException if the keys in m are not {@link Comparable},
175 175 * or are not mutually comparable
176 176 * @throws NullPointerException if the specified map is null
177 177 */
178 178 public TreeMap(Map<? extends K, ? extends V> m) {
179 179 comparator = null;
180 180 putAll(m);
181 181 }
182 182
183 183 /**
184 184 * Constructs a new tree map containing the same mappings and
185 185 * using the same ordering as the specified sorted map. This
186 186 * method runs in linear time.
187 187 *
188 188 * @param m the sorted map whose mappings are to be placed in this map,
189 189 * and whose comparator is to be used to sort this map
190 190 * @throws NullPointerException if the specified map is null
191 191 */
192 192 public TreeMap(SortedMap<K, ? extends V> m) {
193 193 comparator = m.comparator();
194 194 try {
195 195 buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
196 196 } catch (java.io.IOException cannotHappen) {
197 197 } catch (ClassNotFoundException cannotHappen) {
198 198 }
199 199 }
200 200
201 201
202 202 // Query Operations
203 203
204 204 /**
205 205 * Returns the number of key-value mappings in this map.
206 206 *
207 207 * @return the number of key-value mappings in this map
208 208 */
209 209 public int size() {
210 210 return size;
211 211 }
212 212
213 213 /**
214 214 * Returns {@code true} if this map contains a mapping for the specified
215 215 * key.
216 216 *
217 217 * @param key key whose presence in this map is to be tested
218 218 * @return {@code true} if this map contains a mapping for the
219 219 * specified key
220 220 * @throws ClassCastException if the specified key cannot be compared
221 221 * with the keys currently in the map
222 222 * @throws NullPointerException if the specified key is null
223 223 * and this map uses natural ordering, or its comparator
224 224 * does not permit null keys
225 225 */
226 226 public boolean containsKey(Object key) {
227 227 return getEntry(key) != null;
228 228 }
229 229
230 230 /**
231 231 * Returns {@code true} if this map maps one or more keys to the
232 232 * specified value. More formally, returns {@code true} if and only if
233 233 * this map contains at least one mapping to a value {@code v} such
234 234 * that {@code (value==null ? v==null : value.equals(v))}. This
235 235 * operation will probably require time linear in the map size for
236 236 * most implementations.
237 237 *
238 238 * @param value value whose presence in this map is to be tested
239 239 * @return {@code true} if a mapping to {@code value} exists;
240 240 * {@code false} otherwise
241 241 * @since 1.2
242 242 */
243 243 public boolean containsValue(Object value) {
244 244 for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
245 245 if (valEquals(value, e.value))
246 246 return true;
247 247 return false;
248 248 }
249 249
250 250 /**
251 251 * Returns the value to which the specified key is mapped,
252 252 * or {@code null} if this map contains no mapping for the key.
253 253 *
254 254 * <p>More formally, if this map contains a mapping from a key
255 255 * {@code k} to a value {@code v} such that {@code key} compares
256 256 * equal to {@code k} according to the map's ordering, then this
257 257 * method returns {@code v}; otherwise it returns {@code null}.
258 258 * (There can be at most one such mapping.)
259 259 *
260 260 * <p>A return value of {@code null} does not <em>necessarily</em>
261 261 * indicate that the map contains no mapping for the key; it's also
262 262 * possible that the map explicitly maps the key to {@code null}.
263 263 * The {@link #containsKey containsKey} operation may be used to
264 264 * distinguish these two cases.
265 265 *
266 266 * @throws ClassCastException if the specified key cannot be compared
267 267 * with the keys currently in the map
268 268 * @throws NullPointerException if the specified key is null
269 269 * and this map uses natural ordering, or its comparator
270 270 * does not permit null keys
271 271 */
272 272 public V get(Object key) {
273 273 Entry<K,V> p = getEntry(key);
274 274 return (p==null ? null : p.value);
275 275 }
276 276
277 277 public Comparator<? super K> comparator() {
278 278 return comparator;
279 279 }
280 280
281 281 /**
282 282 * @throws NoSuchElementException {@inheritDoc}
283 283 */
284 284 public K firstKey() {
285 285 return key(getFirstEntry());
286 286 }
287 287
288 288 /**
289 289 * @throws NoSuchElementException {@inheritDoc}
290 290 */
291 291 public K lastKey() {
292 292 return key(getLastEntry());
293 293 }
294 294
295 295 /**
296 296 * Copies all of the mappings from the specified map to this map.
297 297 * These mappings replace any mappings that this map had for any
298 298 * of the keys currently in the specified map.
299 299 *
300 300 * @param map mappings to be stored in this map
301 301 * @throws ClassCastException if the class of a key or value in
302 302 * the specified map prevents it from being stored in this map
303 303 * @throws NullPointerException if the specified map is null or
304 304 * the specified map contains a null key and this map does not
305 305 * permit null keys
306 306 */
307 307 public void putAll(Map<? extends K, ? extends V> map) {
308 308 int mapSize = map.size();
309 309 if (size==0 && mapSize!=0 && map instanceof SortedMap) {
310 310 Comparator c = ((SortedMap)map).comparator();
311 311 if (c == comparator || (c != null && c.equals(comparator))) {
312 312 ++modCount;
313 313 try {
314 314 buildFromSorted(mapSize, map.entrySet().iterator(),
315 315 null, null);
316 316 } catch (java.io.IOException cannotHappen) {
317 317 } catch (ClassNotFoundException cannotHappen) {
318 318 }
319 319 return;
320 320 }
321 321 }
322 322 super.putAll(map);
323 323 }
324 324
325 325 /**
326 326 * Returns this map's entry for the given key, or {@code null} if the map
327 327 * does not contain an entry for the key.
328 328 *
329 329 * @return this map's entry for the given key, or {@code null} if the map
330 330 * does not contain an entry for the key
331 331 * @throws ClassCastException if the specified key cannot be compared
332 332 * with the keys currently in the map
333 333 * @throws NullPointerException if the specified key is null
334 334 * and this map uses natural ordering, or its comparator
335 335 * does not permit null keys
336 336 */
337 337 final Entry<K,V> getEntry(Object key) {
338 338 // Offload comparator-based version for sake of performance
339 339 if (comparator != null)
340 340 return getEntryUsingComparator(key);
341 341 if (key == null)
342 342 throw new NullPointerException();
343 343 Comparable<? super K> k = (Comparable<? super K>) key;
344 344 Entry<K,V> p = root;
345 345 while (p != null) {
346 346 int cmp = k.compareTo(p.key);
347 347 if (cmp < 0)
348 348 p = p.left;
349 349 else if (cmp > 0)
350 350 p = p.right;
351 351 else
352 352 return p;
353 353 }
354 354 return null;
355 355 }
356 356
357 357 /**
358 358 * Version of getEntry using comparator. Split off from getEntry
359 359 * for performance. (This is not worth doing for most methods,
360 360 * that are less dependent on comparator performance, but is
361 361 * worthwhile here.)
362 362 */
363 363 final Entry<K,V> getEntryUsingComparator(Object key) {
364 364 K k = (K) key;
365 365 Comparator<? super K> cpr = comparator;
366 366 if (cpr != null) {
367 367 Entry<K,V> p = root;
368 368 while (p != null) {
369 369 int cmp = cpr.compare(k, p.key);
370 370 if (cmp < 0)
371 371 p = p.left;
372 372 else if (cmp > 0)
373 373 p = p.right;
374 374 else
375 375 return p;
376 376 }
377 377 }
378 378 return null;
379 379 }
380 380
381 381 /**
382 382 * Gets the entry corresponding to the specified key; if no such entry
383 383 * exists, returns the entry for the least key greater than the specified
384 384 * key; if no such entry exists (i.e., the greatest key in the Tree is less
385 385 * than the specified key), returns {@code null}.
386 386 */
387 387 final Entry<K,V> getCeilingEntry(K key) {
388 388 Entry<K,V> p = root;
389 389 while (p != null) {
390 390 int cmp = compare(key, p.key);
391 391 if (cmp < 0) {
392 392 if (p.left != null)
393 393 p = p.left;
394 394 else
395 395 return p;
396 396 } else if (cmp > 0) {
397 397 if (p.right != null) {
398 398 p = p.right;
399 399 } else {
400 400 Entry<K,V> parent = p.parent;
401 401 Entry<K,V> ch = p;
402 402 while (parent != null && ch == parent.right) {
403 403 ch = parent;
404 404 parent = parent.parent;
405 405 }
406 406 return parent;
407 407 }
408 408 } else
409 409 return p;
410 410 }
411 411 return null;
412 412 }
413 413
414 414 /**
415 415 * Gets the entry corresponding to the specified key; if no such entry
416 416 * exists, returns the entry for the greatest key less than the specified
417 417 * key; if no such entry exists, returns {@code null}.
418 418 */
419 419 final Entry<K,V> getFloorEntry(K key) {
420 420 Entry<K,V> p = root;
421 421 while (p != null) {
422 422 int cmp = compare(key, p.key);
423 423 if (cmp > 0) {
424 424 if (p.right != null)
425 425 p = p.right;
426 426 else
427 427 return p;
428 428 } else if (cmp < 0) {
429 429 if (p.left != null) {
430 430 p = p.left;
431 431 } else {
432 432 Entry<K,V> parent = p.parent;
433 433 Entry<K,V> ch = p;
434 434 while (parent != null && ch == parent.left) {
435 435 ch = parent;
436 436 parent = parent.parent;
437 437 }
438 438 return parent;
439 439 }
440 440 } else
441 441 return p;
442 442
443 443 }
444 444 return null;
445 445 }
446 446
447 447 /**
448 448 * Gets the entry for the least key greater than the specified
449 449 * key; if no such entry exists, returns the entry for the least
450 450 * key greater than the specified key; if no such entry exists
451 451 * returns {@code null}.
452 452 */
453 453 final Entry<K,V> getHigherEntry(K key) {
454 454 Entry<K,V> p = root;
455 455 while (p != null) {
456 456 int cmp = compare(key, p.key);
457 457 if (cmp < 0) {
458 458 if (p.left != null)
459 459 p = p.left;
460 460 else
461 461 return p;
462 462 } else {
463 463 if (p.right != null) {
464 464 p = p.right;
465 465 } else {
466 466 Entry<K,V> parent = p.parent;
467 467 Entry<K,V> ch = p;
468 468 while (parent != null && ch == parent.right) {
469 469 ch = parent;
470 470 parent = parent.parent;
471 471 }
472 472 return parent;
473 473 }
474 474 }
475 475 }
476 476 return null;
477 477 }
478 478
479 479 /**
480 480 * Returns the entry for the greatest key less than the specified key; if
481 481 * no such entry exists (i.e., the least key in the Tree is greater than
482 482 * the specified key), returns {@code null}.
483 483 */
484 484 final Entry<K,V> getLowerEntry(K key) {
485 485 Entry<K,V> p = root;
486 486 while (p != null) {
487 487 int cmp = compare(key, p.key);
488 488 if (cmp > 0) {
489 489 if (p.right != null)
490 490 p = p.right;
491 491 else
492 492 return p;
493 493 } else {
494 494 if (p.left != null) {
495 495 p = p.left;
496 496 } else {
497 497 Entry<K,V> parent = p.parent;
498 498 Entry<K,V> ch = p;
499 499 while (parent != null && ch == parent.left) {
500 500 ch = parent;
501 501 parent = parent.parent;
502 502 }
503 503 return parent;
504 504 }
505 505 }
506 506 }
507 507 return null;
508 508 }
509 509
510 510 /**
511 511 * Associates the specified value with the specified key in this map.
512 512 * If the map previously contained a mapping for the key, the old
513 513 * value is replaced.
514 514 *
515 515 * @param key key with which the specified value is to be associated
516 516 * @param value value to be associated with the specified key
517 517 *
518 518 * @return the previous value associated with {@code key}, or
519 519 * {@code null} if there was no mapping for {@code key}.
520 520 * (A {@code null} return can also indicate that the map
521 521 * previously associated {@code null} with {@code key}.)
522 522 * @throws ClassCastException if the specified key cannot be compared
523 523 * with the keys currently in the map
524 524 * @throws NullPointerException if the specified key is null
525 525 * and this map uses natural ordering, or its comparator
526 526 * does not permit null keys
527 527 */
528 528 public V put(K key, V value) {
529 529 Entry<K,V> t = root;
530 530 if (t == null) {
531 531 // TBD:
532 532 // 5045147: (coll) Adding null to an empty TreeSet should
533 533 // throw NullPointerException
534 534 //
535 535 // compare(key, key); // type check
536 536 root = new Entry<K,V>(key, value, null);
537 537 size = 1;
538 538 modCount++;
539 539 return null;
540 540 }
541 541 int cmp;
542 542 Entry<K,V> parent;
543 543 // split comparator and comparable paths
544 544 Comparator<? super K> cpr = comparator;
545 545 if (cpr != null) {
546 546 do {
547 547 parent = t;
548 548 cmp = cpr.compare(key, t.key);
549 549 if (cmp < 0)
550 550 t = t.left;
551 551 else if (cmp > 0)
552 552 t = t.right;
553 553 else
554 554 return t.setValue(value);
555 555 } while (t != null);
556 556 }
557 557 else {
558 558 if (key == null)
559 559 throw new NullPointerException();
560 560 Comparable<? super K> k = (Comparable<? super K>) key;
561 561 do {
562 562 parent = t;
563 563 cmp = k.compareTo(t.key);
564 564 if (cmp < 0)
565 565 t = t.left;
566 566 else if (cmp > 0)
567 567 t = t.right;
568 568 else
569 569 return t.setValue(value);
570 570 } while (t != null);
571 571 }
572 572 Entry<K,V> e = new Entry<K,V>(key, value, parent);
573 573 if (cmp < 0)
574 574 parent.left = e;
575 575 else
576 576 parent.right = e;
577 577 fixAfterInsertion(e);
578 578 size++;
579 579 modCount++;
580 580 return null;
581 581 }
582 582
583 583 /**
584 584 * Removes the mapping for this key from this TreeMap if present.
585 585 *
586 586 * @param key key for which mapping should be removed
587 587 * @return the previous value associated with {@code key}, or
588 588 * {@code null} if there was no mapping for {@code key}.
589 589 * (A {@code null} return can also indicate that the map
590 590 * previously associated {@code null} with {@code key}.)
591 591 * @throws ClassCastException if the specified key cannot be compared
592 592 * with the keys currently in the map
593 593 * @throws NullPointerException if the specified key is null
594 594 * and this map uses natural ordering, or its comparator
595 595 * does not permit null keys
596 596 */
597 597 public V remove(Object key) {
598 598 Entry<K,V> p = getEntry(key);
599 599 if (p == null)
600 600 return null;
601 601
602 602 V oldValue = p.value;
603 603 deleteEntry(p);
604 604 return oldValue;
605 605 }
606 606
607 607 /**
608 608 * Removes all of the mappings from this map.
609 609 * The map will be empty after this call returns.
610 610 */
611 611 public void clear() {
612 612 modCount++;
613 613 size = 0;
614 614 root = null;
615 615 }
616 616
617 617 /**
618 618 * Returns a shallow copy of this {@code TreeMap} instance. (The keys and
619 619 * values themselves are not cloned.)
620 620 *
621 621 * @return a shallow copy of this map
622 622 */
623 623 public Object clone() {
624 624 TreeMap<K,V> clone = null;
625 625 try {
626 626 clone = (TreeMap<K,V>) super.clone();
627 627 } catch (CloneNotSupportedException e) {
628 628 throw new InternalError();
629 629 }
630 630
631 631 // Put clone into "virgin" state (except for comparator)
632 632 clone.root = null;
633 633 clone.size = 0;
634 634 clone.modCount = 0;
635 635 clone.entrySet = null;
636 636 clone.navigableKeySet = null;
637 637 clone.descendingMap = null;
638 638
639 639 // Initialize clone with our mappings
640 640 try {
641 641 clone.buildFromSorted(size, entrySet().iterator(), null, null);
642 642 } catch (java.io.IOException cannotHappen) {
643 643 } catch (ClassNotFoundException cannotHappen) {
644 644 }
645 645
646 646 return clone;
647 647 }
648 648
649 649 // NavigableMap API methods
650 650
651 651 /**
652 652 * @since 1.6
653 653 */
654 654 public Map.Entry<K,V> firstEntry() {
655 655 return exportEntry(getFirstEntry());
656 656 }
657 657
658 658 /**
659 659 * @since 1.6
660 660 */
661 661 public Map.Entry<K,V> lastEntry() {
662 662 return exportEntry(getLastEntry());
663 663 }
664 664
665 665 /**
666 666 * @since 1.6
667 667 */
668 668 public Map.Entry<K,V> pollFirstEntry() {
669 669 Entry<K,V> p = getFirstEntry();
670 670 Map.Entry<K,V> result = exportEntry(p);
671 671 if (p != null)
672 672 deleteEntry(p);
673 673 return result;
674 674 }
675 675
676 676 /**
677 677 * @since 1.6
678 678 */
679 679 public Map.Entry<K,V> pollLastEntry() {
680 680 Entry<K,V> p = getLastEntry();
681 681 Map.Entry<K,V> result = exportEntry(p);
682 682 if (p != null)
683 683 deleteEntry(p);
684 684 return result;
685 685 }
686 686
687 687 /**
688 688 * @throws ClassCastException {@inheritDoc}
689 689 * @throws NullPointerException if the specified key is null
690 690 * and this map uses natural ordering, or its comparator
691 691 * does not permit null keys
692 692 * @since 1.6
693 693 */
694 694 public Map.Entry<K,V> lowerEntry(K key) {
695 695 return exportEntry(getLowerEntry(key));
696 696 }
697 697
698 698 /**
699 699 * @throws ClassCastException {@inheritDoc}
700 700 * @throws NullPointerException if the specified key is null
701 701 * and this map uses natural ordering, or its comparator
702 702 * does not permit null keys
703 703 * @since 1.6
704 704 */
705 705 public K lowerKey(K key) {
706 706 return keyOrNull(getLowerEntry(key));
707 707 }
708 708
709 709 /**
710 710 * @throws ClassCastException {@inheritDoc}
711 711 * @throws NullPointerException if the specified key is null
712 712 * and this map uses natural ordering, or its comparator
713 713 * does not permit null keys
714 714 * @since 1.6
715 715 */
716 716 public Map.Entry<K,V> floorEntry(K key) {
717 717 return exportEntry(getFloorEntry(key));
718 718 }
719 719
720 720 /**
721 721 * @throws ClassCastException {@inheritDoc}
722 722 * @throws NullPointerException if the specified key is null
723 723 * and this map uses natural ordering, or its comparator
724 724 * does not permit null keys
725 725 * @since 1.6
726 726 */
727 727 public K floorKey(K key) {
728 728 return keyOrNull(getFloorEntry(key));
729 729 }
730 730
731 731 /**
732 732 * @throws ClassCastException {@inheritDoc}
733 733 * @throws NullPointerException if the specified key is null
734 734 * and this map uses natural ordering, or its comparator
735 735 * does not permit null keys
736 736 * @since 1.6
737 737 */
738 738 public Map.Entry<K,V> ceilingEntry(K key) {
739 739 return exportEntry(getCeilingEntry(key));
740 740 }
741 741
742 742 /**
743 743 * @throws ClassCastException {@inheritDoc}
744 744 * @throws NullPointerException if the specified key is null
745 745 * and this map uses natural ordering, or its comparator
746 746 * does not permit null keys
747 747 * @since 1.6
748 748 */
749 749 public K ceilingKey(K key) {
750 750 return keyOrNull(getCeilingEntry(key));
751 751 }
752 752
753 753 /**
754 754 * @throws ClassCastException {@inheritDoc}
755 755 * @throws NullPointerException if the specified key is null
756 756 * and this map uses natural ordering, or its comparator
757 757 * does not permit null keys
758 758 * @since 1.6
759 759 */
760 760 public Map.Entry<K,V> higherEntry(K key) {
761 761 return exportEntry(getHigherEntry(key));
762 762 }
763 763
764 764 /**
765 765 * @throws ClassCastException {@inheritDoc}
766 766 * @throws NullPointerException if the specified key is null
767 767 * and this map uses natural ordering, or its comparator
768 768 * does not permit null keys
769 769 * @since 1.6
770 770 */
771 771 public K higherKey(K key) {
772 772 return keyOrNull(getHigherEntry(key));
773 773 }
774 774
775 775 // Views
776 776
777 777 /**
778 778 * Fields initialized to contain an instance of the entry set view
779 779 * the first time this view is requested. Views are stateless, so
780 780 * there's no reason to create more than one.
781 781 */
782 782 private transient EntrySet entrySet = null;
783 783 private transient KeySet<K> navigableKeySet = null;
784 784 private transient NavigableMap<K,V> descendingMap = null;
785 785
786 786 /**
787 787 * Returns a {@link Set} view of the keys contained in this map.
788 788 * The set's iterator returns the keys in ascending order.
789 789 * The set is backed by the map, so changes to the map are
790 790 * reflected in the set, and vice-versa. If the map is modified
791 791 * while an iteration over the set is in progress (except through
792 792 * the iterator's own {@code remove} operation), the results of
793 793 * the iteration are undefined. The set supports element removal,
794 794 * which removes the corresponding mapping from the map, via the
795 795 * {@code Iterator.remove}, {@code Set.remove},
796 796 * {@code removeAll}, {@code retainAll}, and {@code clear}
797 797 * operations. It does not support the {@code add} or {@code addAll}
798 798 * operations.
799 799 */
800 800 public Set<K> keySet() {
801 801 return navigableKeySet();
802 802 }
803 803
804 804 /**
805 805 * @since 1.6
806 806 */
807 807 public NavigableSet<K> navigableKeySet() {
808 808 KeySet<K> nks = navigableKeySet;
809 809 return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
810 810 }
811 811
812 812 /**
813 813 * @since 1.6
814 814 */
815 815 public NavigableSet<K> descendingKeySet() {
816 816 return descendingMap().navigableKeySet();
817 817 }
818 818
819 819 /**
820 820 * Returns a {@link Collection} view of the values contained in this map.
821 821 * The collection's iterator returns the values in ascending order
822 822 * of the corresponding keys.
823 823 * The collection is backed by the map, so changes to the map are
824 824 * reflected in the collection, and vice-versa. If the map is
825 825 * modified while an iteration over the collection is in progress
826 826 * (except through the iterator's own {@code remove} operation),
827 827 * the results of the iteration are undefined. The collection
828 828 * supports element removal, which removes the corresponding
829 829 * mapping from the map, via the {@code Iterator.remove},
830 830 * {@code Collection.remove}, {@code removeAll},
831 831 * {@code retainAll} and {@code clear} operations. It does not
832 832 * support the {@code add} or {@code addAll} operations.
833 833 */
834 834 public Collection<V> values() {
835 835 Collection<V> vs = values;
836 836 return (vs != null) ? vs : (values = new Values());
837 837 }
838 838
839 839 /**
840 840 * Returns a {@link Set} view of the mappings contained in this map.
841 841 * The set's iterator returns the entries in ascending key order.
842 842 * The set is backed by the map, so changes to the map are
843 843 * reflected in the set, and vice-versa. If the map is modified
844 844 * while an iteration over the set is in progress (except through
845 845 * the iterator's own {@code remove} operation, or through the
846 846 * {@code setValue} operation on a map entry returned by the
847 847 * iterator) the results of the iteration are undefined. The set
848 848 * supports element removal, which removes the corresponding
849 849 * mapping from the map, via the {@code Iterator.remove},
850 850 * {@code Set.remove}, {@code removeAll}, {@code retainAll} and
851 851 * {@code clear} operations. It does not support the
852 852 * {@code add} or {@code addAll} operations.
853 853 */
854 854 public Set<Map.Entry<K,V>> entrySet() {
855 855 EntrySet es = entrySet;
856 856 return (es != null) ? es : (entrySet = new EntrySet());
857 857 }
858 858
859 859 /**
860 860 * @since 1.6
861 861 */
862 862 public NavigableMap<K, V> descendingMap() {
863 863 NavigableMap<K, V> km = descendingMap;
864 864 return (km != null) ? km :
865 865 (descendingMap = new DescendingSubMap(this,
866 866 true, null, true,
867 867 true, null, true));
868 868 }
869 869
870 870 /**
871 871 * @throws ClassCastException {@inheritDoc}
872 872 * @throws NullPointerException if {@code fromKey} or {@code toKey} is
873 873 * null and this map uses natural ordering, or its comparator
874 874 * does not permit null keys
875 875 * @throws IllegalArgumentException {@inheritDoc}
876 876 * @since 1.6
877 877 */
878 878 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
879 879 K toKey, boolean toInclusive) {
880 880 return new AscendingSubMap(this,
881 881 false, fromKey, fromInclusive,
882 882 false, toKey, toInclusive);
883 883 }
884 884
885 885 /**
886 886 * @throws ClassCastException {@inheritDoc}
887 887 * @throws NullPointerException if {@code toKey} is null
888 888 * and this map uses natural ordering, or its comparator
889 889 * does not permit null keys
890 890 * @throws IllegalArgumentException {@inheritDoc}
891 891 * @since 1.6
892 892 */
893 893 public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
894 894 return new AscendingSubMap(this,
895 895 true, null, true,
896 896 false, toKey, inclusive);
897 897 }
898 898
899 899 /**
900 900 * @throws ClassCastException {@inheritDoc}
901 901 * @throws NullPointerException if {@code fromKey} is null
902 902 * and this map uses natural ordering, or its comparator
903 903 * does not permit null keys
904 904 * @throws IllegalArgumentException {@inheritDoc}
905 905 * @since 1.6
906 906 */
907 907 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
908 908 return new AscendingSubMap(this,
909 909 false, fromKey, inclusive,
910 910 true, null, true);
911 911 }
912 912
913 913 /**
914 914 * @throws ClassCastException {@inheritDoc}
915 915 * @throws NullPointerException if {@code fromKey} or {@code toKey} is
916 916 * null and this map uses natural ordering, or its comparator
917 917 * does not permit null keys
918 918 * @throws IllegalArgumentException {@inheritDoc}
919 919 */
920 920 public SortedMap<K,V> subMap(K fromKey, K toKey) {
921 921 return subMap(fromKey, true, toKey, false);
922 922 }
923 923
924 924 /**
925 925 * @throws ClassCastException {@inheritDoc}
926 926 * @throws NullPointerException if {@code toKey} is null
927 927 * and this map uses natural ordering, or its comparator
928 928 * does not permit null keys
929 929 * @throws IllegalArgumentException {@inheritDoc}
930 930 */
931 931 public SortedMap<K,V> headMap(K toKey) {
932 932 return headMap(toKey, false);
933 933 }
934 934
935 935 /**
936 936 * @throws ClassCastException {@inheritDoc}
937 937 * @throws NullPointerException if {@code fromKey} is null
938 938 * and this map uses natural ordering, or its comparator
939 939 * does not permit null keys
940 940 * @throws IllegalArgumentException {@inheritDoc}
941 941 */
942 942 public SortedMap<K,V> tailMap(K fromKey) {
943 943 return tailMap(fromKey, true);
944 944 }
945 945
946 946 // View class support
947 947
948 948 class Values extends AbstractCollection<V> {
949 949 public Iterator<V> iterator() {
950 950 return new ValueIterator(getFirstEntry());
951 951 }
952 952
953 953 public int size() {
954 954 return TreeMap.this.size();
955 955 }
956 956
957 957 public boolean contains(Object o) {
958 958 return TreeMap.this.containsValue(o);
959 959 }
960 960
961 961 public boolean remove(Object o) {
962 962 for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
963 963 if (valEquals(e.getValue(), o)) {
964 964 deleteEntry(e);
965 965 return true;
966 966 }
967 967 }
968 968 return false;
969 969 }
970 970
971 971 public void clear() {
972 972 TreeMap.this.clear();
973 973 }
974 974 }
975 975
976 976 class EntrySet extends AbstractSet<Map.Entry<K,V>> {
977 977 public Iterator<Map.Entry<K,V>> iterator() {
978 978 return new EntryIterator(getFirstEntry());
979 979 }
980 980
981 981 public boolean contains(Object o) {
982 982 if (!(o instanceof Map.Entry))
983 983 return false;
984 984 Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
985 985 V value = entry.getValue();
986 986 Entry<K,V> p = getEntry(entry.getKey());
987 987 return p != null && valEquals(p.getValue(), value);
988 988 }
989 989
990 990 public boolean remove(Object o) {
991 991 if (!(o instanceof Map.Entry))
992 992 return false;
993 993 Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
994 994 V value = entry.getValue();
995 995 Entry<K,V> p = getEntry(entry.getKey());
996 996 if (p != null && valEquals(p.getValue(), value)) {
997 997 deleteEntry(p);
998 998 return true;
999 999 }
1000 1000 return false;
1001 1001 }
1002 1002
1003 1003 public int size() {
1004 1004 return TreeMap.this.size();
1005 1005 }
1006 1006
1007 1007 public void clear() {
1008 1008 TreeMap.this.clear();
1009 1009 }
1010 1010 }
1011 1011
1012 1012 /*
1013 1013 * Unlike Values and EntrySet, the KeySet class is static,
1014 1014 * delegating to a NavigableMap to allow use by SubMaps, which
1015 1015 * outweighs the ugliness of needing type-tests for the following
1016 1016 * Iterator methods that are defined appropriately in main versus
1017 1017 * submap classes.
1018 1018 */
1019 1019
1020 1020 Iterator<K> keyIterator() {
1021 1021 return new KeyIterator(getFirstEntry());
1022 1022 }
1023 1023
1024 1024 Iterator<K> descendingKeyIterator() {
1025 1025 return new DescendingKeyIterator(getLastEntry());
1026 1026 }
1027 1027
1028 1028 static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
1029 1029 private final NavigableMap<E, Object> m;
1030 1030 KeySet(NavigableMap<E,Object> map) { m = map; }
1031 1031
1032 1032 public Iterator<E> iterator() {
1033 1033 if (m instanceof TreeMap)
1034 1034 return ((TreeMap<E,Object>)m).keyIterator();
1035 1035 else
1036 1036 return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());
1037 1037 }
1038 1038
1039 1039 public Iterator<E> descendingIterator() {
1040 1040 if (m instanceof TreeMap)
1041 1041 return ((TreeMap<E,Object>)m).descendingKeyIterator();
1042 1042 else
1043 1043 return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
1044 1044 }
1045 1045
1046 1046 public int size() { return m.size(); }
1047 1047 public boolean isEmpty() { return m.isEmpty(); }
1048 1048 public boolean contains(Object o) { return m.containsKey(o); }
↓ open down ↓ |
1048 lines elided |
↑ open up ↑ |
1049 1049 public void clear() { m.clear(); }
1050 1050 public E lower(E e) { return m.lowerKey(e); }
1051 1051 public E floor(E e) { return m.floorKey(e); }
1052 1052 public E ceiling(E e) { return m.ceilingKey(e); }
1053 1053 public E higher(E e) { return m.higherKey(e); }
1054 1054 public E first() { return m.firstKey(); }
1055 1055 public E last() { return m.lastKey(); }
1056 1056 public Comparator<? super E> comparator() { return m.comparator(); }
1057 1057 public E pollFirst() {
1058 1058 Map.Entry<E,Object> e = m.pollFirstEntry();
1059 - return e == null? null : e.getKey();
1059 + return (e == null) ? null : e.getKey();
1060 1060 }
1061 1061 public E pollLast() {
1062 1062 Map.Entry<E,Object> e = m.pollLastEntry();
1063 - return e == null? null : e.getKey();
1063 + return (e == null) ? null : e.getKey();
1064 1064 }
1065 1065 public boolean remove(Object o) {
1066 1066 int oldSize = size();
1067 1067 m.remove(o);
1068 1068 return size() != oldSize;
1069 1069 }
1070 1070 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1071 1071 E toElement, boolean toInclusive) {
1072 1072 return new KeySet<E>(m.subMap(fromElement, fromInclusive,
1073 1073 toElement, toInclusive));
1074 1074 }
1075 1075 public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1076 1076 return new KeySet<E>(m.headMap(toElement, inclusive));
1077 1077 }
1078 1078 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1079 1079 return new KeySet<E>(m.tailMap(fromElement, inclusive));
1080 1080 }
1081 1081 public SortedSet<E> subSet(E fromElement, E toElement) {
1082 1082 return subSet(fromElement, true, toElement, false);
1083 1083 }
1084 1084 public SortedSet<E> headSet(E toElement) {
1085 1085 return headSet(toElement, false);
1086 1086 }
1087 1087 public SortedSet<E> tailSet(E fromElement) {
1088 1088 return tailSet(fromElement, true);
1089 1089 }
1090 1090 public NavigableSet<E> descendingSet() {
1091 1091 return new KeySet(m.descendingMap());
1092 1092 }
1093 1093 }
1094 1094
1095 1095 /**
1096 1096 * Base class for TreeMap Iterators
1097 1097 */
1098 1098 abstract class PrivateEntryIterator<T> implements Iterator<T> {
1099 1099 Entry<K,V> next;
1100 1100 Entry<K,V> lastReturned;
1101 1101 int expectedModCount;
1102 1102
1103 1103 PrivateEntryIterator(Entry<K,V> first) {
1104 1104 expectedModCount = modCount;
1105 1105 lastReturned = null;
1106 1106 next = first;
1107 1107 }
1108 1108
1109 1109 public final boolean hasNext() {
1110 1110 return next != null;
1111 1111 }
1112 1112
1113 1113 final Entry<K,V> nextEntry() {
1114 1114 Entry<K,V> e = next;
1115 1115 if (e == null)
1116 1116 throw new NoSuchElementException();
1117 1117 if (modCount != expectedModCount)
1118 1118 throw new ConcurrentModificationException();
1119 1119 next = successor(e);
1120 1120 lastReturned = e;
1121 1121 return e;
1122 1122 }
1123 1123
1124 1124 final Entry<K,V> prevEntry() {
1125 1125 Entry<K,V> e = next;
1126 1126 if (e == null)
1127 1127 throw new NoSuchElementException();
1128 1128 if (modCount != expectedModCount)
1129 1129 throw new ConcurrentModificationException();
1130 1130 next = predecessor(e);
1131 1131 lastReturned = e;
1132 1132 return e;
1133 1133 }
1134 1134
1135 1135 public void remove() {
1136 1136 if (lastReturned == null)
1137 1137 throw new IllegalStateException();
1138 1138 if (modCount != expectedModCount)
1139 1139 throw new ConcurrentModificationException();
1140 1140 // deleted entries are replaced by their successors
1141 1141 if (lastReturned.left != null && lastReturned.right != null)
1142 1142 next = lastReturned;
1143 1143 deleteEntry(lastReturned);
1144 1144 expectedModCount = modCount;
1145 1145 lastReturned = null;
1146 1146 }
1147 1147 }
1148 1148
1149 1149 final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1150 1150 EntryIterator(Entry<K,V> first) {
1151 1151 super(first);
1152 1152 }
1153 1153 public Map.Entry<K,V> next() {
1154 1154 return nextEntry();
1155 1155 }
1156 1156 }
1157 1157
1158 1158 final class ValueIterator extends PrivateEntryIterator<V> {
1159 1159 ValueIterator(Entry<K,V> first) {
1160 1160 super(first);
1161 1161 }
1162 1162 public V next() {
1163 1163 return nextEntry().value;
1164 1164 }
1165 1165 }
1166 1166
1167 1167 final class KeyIterator extends PrivateEntryIterator<K> {
1168 1168 KeyIterator(Entry<K,V> first) {
1169 1169 super(first);
1170 1170 }
1171 1171 public K next() {
1172 1172 return nextEntry().key;
1173 1173 }
1174 1174 }
1175 1175
1176 1176 final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1177 1177 DescendingKeyIterator(Entry<K,V> first) {
1178 1178 super(first);
1179 1179 }
1180 1180 public K next() {
1181 1181 return prevEntry().key;
1182 1182 }
1183 1183 }
1184 1184
1185 1185 // Little utilities
1186 1186
1187 1187 /**
1188 1188 * Compares two keys using the correct comparison method for this TreeMap.
↓ open down ↓ |
115 lines elided |
↑ open up ↑ |
1189 1189 */
1190 1190 final int compare(Object k1, Object k2) {
1191 1191 return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1192 1192 : comparator.compare((K)k1, (K)k2);
1193 1193 }
1194 1194
1195 1195 /**
1196 1196 * Test two values for equality. Differs from o1.equals(o2) only in
1197 1197 * that it copes with {@code null} o1 properly.
1198 1198 */
1199 - final static boolean valEquals(Object o1, Object o2) {
1199 + static final boolean valEquals(Object o1, Object o2) {
1200 1200 return (o1==null ? o2==null : o1.equals(o2));
1201 1201 }
1202 1202
1203 1203 /**
1204 1204 * Return SimpleImmutableEntry for entry, or null if null
1205 1205 */
1206 1206 static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1207 - return e == null? null :
1207 + return (e == null) ? null :
1208 1208 new AbstractMap.SimpleImmutableEntry<K,V>(e);
1209 1209 }
1210 1210
1211 1211 /**
1212 1212 * Return key for entry, or null if null
1213 1213 */
1214 1214 static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1215 - return e == null? null : e.key;
1215 + return (e == null) ? null : e.key;
1216 1216 }
1217 1217
1218 1218 /**
1219 1219 * Returns the key corresponding to the specified Entry.
1220 1220 * @throws NoSuchElementException if the Entry is null
1221 1221 */
1222 1222 static <K> K key(Entry<K,?> e) {
1223 1223 if (e==null)
1224 1224 throw new NoSuchElementException();
1225 1225 return e.key;
1226 1226 }
1227 1227
1228 1228
1229 1229 // SubMaps
↓ open down ↓ |
4 lines elided |
↑ open up ↑ |
1230 1230
1231 1231 /**
1232 1232 * Dummy value serving as unmatchable fence key for unbounded
1233 1233 * SubMapIterators
1234 1234 */
1235 1235 private static final Object UNBOUNDED = new Object();
1236 1236
1237 1237 /**
1238 1238 * @serial include
1239 1239 */
1240 - static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
1240 + abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V>
1241 1241 implements NavigableMap<K,V>, java.io.Serializable {
1242 1242 /**
1243 1243 * The backing map.
1244 1244 */
1245 1245 final TreeMap<K,V> m;
1246 1246
1247 1247 /**
1248 1248 * Endpoints are represented as triples (fromStart, lo,
1249 1249 * loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1250 1250 * true, then the low (absolute) bound is the start of the
1251 1251 * backing map, and the other values are ignored. Otherwise,
1252 1252 * if loInclusive is true, lo is the inclusive bound, else lo
1253 1253 * is the exclusive bound. Similarly for the upper bound.
1254 1254 */
1255 1255 final K lo, hi;
1256 1256 final boolean fromStart, toEnd;
1257 1257 final boolean loInclusive, hiInclusive;
1258 1258
1259 1259 NavigableSubMap(TreeMap<K,V> m,
1260 1260 boolean fromStart, K lo, boolean loInclusive,
1261 1261 boolean toEnd, K hi, boolean hiInclusive) {
1262 1262 if (!fromStart && !toEnd) {
1263 1263 if (m.compare(lo, hi) > 0)
1264 1264 throw new IllegalArgumentException("fromKey > toKey");
1265 1265 } else {
1266 1266 if (!fromStart) // type check
1267 1267 m.compare(lo, lo);
1268 1268 if (!toEnd)
1269 1269 m.compare(hi, hi);
1270 1270 }
1271 1271
1272 1272 this.m = m;
1273 1273 this.fromStart = fromStart;
1274 1274 this.lo = lo;
1275 1275 this.loInclusive = loInclusive;
1276 1276 this.toEnd = toEnd;
1277 1277 this.hi = hi;
1278 1278 this.hiInclusive = hiInclusive;
1279 1279 }
1280 1280
1281 1281 // internal utilities
1282 1282
1283 1283 final boolean tooLow(Object key) {
1284 1284 if (!fromStart) {
1285 1285 int c = m.compare(key, lo);
1286 1286 if (c < 0 || (c == 0 && !loInclusive))
1287 1287 return true;
1288 1288 }
1289 1289 return false;
1290 1290 }
1291 1291
1292 1292 final boolean tooHigh(Object key) {
1293 1293 if (!toEnd) {
1294 1294 int c = m.compare(key, hi);
1295 1295 if (c > 0 || (c == 0 && !hiInclusive))
1296 1296 return true;
1297 1297 }
1298 1298 return false;
1299 1299 }
1300 1300
1301 1301 final boolean inRange(Object key) {
1302 1302 return !tooLow(key) && !tooHigh(key);
1303 1303 }
1304 1304
1305 1305 final boolean inClosedRange(Object key) {
1306 1306 return (fromStart || m.compare(key, lo) >= 0)
1307 1307 && (toEnd || m.compare(hi, key) >= 0);
1308 1308 }
1309 1309
1310 1310 final boolean inRange(Object key, boolean inclusive) {
1311 1311 return inclusive ? inRange(key) : inClosedRange(key);
1312 1312 }
1313 1313
1314 1314 /*
1315 1315 * Absolute versions of relation operations.
1316 1316 * Subclasses map to these using like-named "sub"
1317 1317 * versions that invert senses for descending maps
1318 1318 */
1319 1319
1320 1320 final TreeMap.Entry<K,V> absLowest() {
1321 1321 TreeMap.Entry<K,V> e =
1322 1322 (fromStart ? m.getFirstEntry() :
1323 1323 (loInclusive ? m.getCeilingEntry(lo) :
1324 1324 m.getHigherEntry(lo)));
1325 1325 return (e == null || tooHigh(e.key)) ? null : e;
1326 1326 }
1327 1327
1328 1328 final TreeMap.Entry<K,V> absHighest() {
1329 1329 TreeMap.Entry<K,V> e =
1330 1330 (toEnd ? m.getLastEntry() :
1331 1331 (hiInclusive ? m.getFloorEntry(hi) :
1332 1332 m.getLowerEntry(hi)));
1333 1333 return (e == null || tooLow(e.key)) ? null : e;
1334 1334 }
1335 1335
1336 1336 final TreeMap.Entry<K,V> absCeiling(K key) {
1337 1337 if (tooLow(key))
1338 1338 return absLowest();
1339 1339 TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1340 1340 return (e == null || tooHigh(e.key)) ? null : e;
1341 1341 }
1342 1342
1343 1343 final TreeMap.Entry<K,V> absHigher(K key) {
1344 1344 if (tooLow(key))
1345 1345 return absLowest();
1346 1346 TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1347 1347 return (e == null || tooHigh(e.key)) ? null : e;
1348 1348 }
1349 1349
1350 1350 final TreeMap.Entry<K,V> absFloor(K key) {
1351 1351 if (tooHigh(key))
1352 1352 return absHighest();
1353 1353 TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1354 1354 return (e == null || tooLow(e.key)) ? null : e;
1355 1355 }
1356 1356
1357 1357 final TreeMap.Entry<K,V> absLower(K key) {
1358 1358 if (tooHigh(key))
1359 1359 return absHighest();
1360 1360 TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1361 1361 return (e == null || tooLow(e.key)) ? null : e;
1362 1362 }
1363 1363
1364 1364 /** Returns the absolute high fence for ascending traversal */
1365 1365 final TreeMap.Entry<K,V> absHighFence() {
1366 1366 return (toEnd ? null : (hiInclusive ?
1367 1367 m.getHigherEntry(hi) :
1368 1368 m.getCeilingEntry(hi)));
1369 1369 }
1370 1370
1371 1371 /** Return the absolute low fence for descending traversal */
1372 1372 final TreeMap.Entry<K,V> absLowFence() {
1373 1373 return (fromStart ? null : (loInclusive ?
1374 1374 m.getLowerEntry(lo) :
1375 1375 m.getFloorEntry(lo)));
1376 1376 }
1377 1377
1378 1378 // Abstract methods defined in ascending vs descending classes
1379 1379 // These relay to the appropriate absolute versions
1380 1380
1381 1381 abstract TreeMap.Entry<K,V> subLowest();
1382 1382 abstract TreeMap.Entry<K,V> subHighest();
1383 1383 abstract TreeMap.Entry<K,V> subCeiling(K key);
1384 1384 abstract TreeMap.Entry<K,V> subHigher(K key);
1385 1385 abstract TreeMap.Entry<K,V> subFloor(K key);
1386 1386 abstract TreeMap.Entry<K,V> subLower(K key);
1387 1387
1388 1388 /** Returns ascending iterator from the perspective of this submap */
1389 1389 abstract Iterator<K> keyIterator();
1390 1390
1391 1391 /** Returns descending iterator from the perspective of this submap */
1392 1392 abstract Iterator<K> descendingKeyIterator();
1393 1393
1394 1394 // public methods
1395 1395
1396 1396 public boolean isEmpty() {
1397 1397 return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1398 1398 }
1399 1399
1400 1400 public int size() {
1401 1401 return (fromStart && toEnd) ? m.size() : entrySet().size();
1402 1402 }
1403 1403
1404 1404 public final boolean containsKey(Object key) {
↓ open down ↓ |
154 lines elided |
↑ open up ↑ |
1405 1405 return inRange(key) && m.containsKey(key);
1406 1406 }
1407 1407
1408 1408 public final V put(K key, V value) {
1409 1409 if (!inRange(key))
1410 1410 throw new IllegalArgumentException("key out of range");
1411 1411 return m.put(key, value);
1412 1412 }
1413 1413
1414 1414 public final V get(Object key) {
1415 - return !inRange(key)? null : m.get(key);
1415 + return !inRange(key) ? null : m.get(key);
1416 1416 }
1417 1417
1418 1418 public final V remove(Object key) {
1419 - return !inRange(key)? null : m.remove(key);
1419 + return !inRange(key) ? null : m.remove(key);
1420 1420 }
1421 1421
1422 1422 public final Map.Entry<K,V> ceilingEntry(K key) {
1423 1423 return exportEntry(subCeiling(key));
1424 1424 }
1425 1425
1426 1426 public final K ceilingKey(K key) {
1427 1427 return keyOrNull(subCeiling(key));
1428 1428 }
1429 1429
1430 1430 public final Map.Entry<K,V> higherEntry(K key) {
1431 1431 return exportEntry(subHigher(key));
1432 1432 }
1433 1433
1434 1434 public final K higherKey(K key) {
1435 1435 return keyOrNull(subHigher(key));
1436 1436 }
1437 1437
1438 1438 public final Map.Entry<K,V> floorEntry(K key) {
1439 1439 return exportEntry(subFloor(key));
1440 1440 }
1441 1441
1442 1442 public final K floorKey(K key) {
1443 1443 return keyOrNull(subFloor(key));
1444 1444 }
1445 1445
1446 1446 public final Map.Entry<K,V> lowerEntry(K key) {
1447 1447 return exportEntry(subLower(key));
1448 1448 }
1449 1449
1450 1450 public final K lowerKey(K key) {
1451 1451 return keyOrNull(subLower(key));
1452 1452 }
1453 1453
1454 1454 public final K firstKey() {
1455 1455 return key(subLowest());
1456 1456 }
1457 1457
1458 1458 public final K lastKey() {
1459 1459 return key(subHighest());
1460 1460 }
1461 1461
1462 1462 public final Map.Entry<K,V> firstEntry() {
1463 1463 return exportEntry(subLowest());
1464 1464 }
1465 1465
1466 1466 public final Map.Entry<K,V> lastEntry() {
1467 1467 return exportEntry(subHighest());
1468 1468 }
1469 1469
1470 1470 public final Map.Entry<K,V> pollFirstEntry() {
1471 1471 TreeMap.Entry<K,V> e = subLowest();
1472 1472 Map.Entry<K,V> result = exportEntry(e);
1473 1473 if (e != null)
1474 1474 m.deleteEntry(e);
1475 1475 return result;
1476 1476 }
1477 1477
1478 1478 public final Map.Entry<K,V> pollLastEntry() {
1479 1479 TreeMap.Entry<K,V> e = subHighest();
1480 1480 Map.Entry<K,V> result = exportEntry(e);
1481 1481 if (e != null)
1482 1482 m.deleteEntry(e);
1483 1483 return result;
1484 1484 }
1485 1485
1486 1486 // Views
1487 1487 transient NavigableMap<K,V> descendingMapView = null;
1488 1488 transient EntrySetView entrySetView = null;
1489 1489 transient KeySet<K> navigableKeySetView = null;
1490 1490
1491 1491 public final NavigableSet<K> navigableKeySet() {
1492 1492 KeySet<K> nksv = navigableKeySetView;
1493 1493 return (nksv != null) ? nksv :
1494 1494 (navigableKeySetView = new TreeMap.KeySet(this));
1495 1495 }
1496 1496
1497 1497 public final Set<K> keySet() {
1498 1498 return navigableKeySet();
1499 1499 }
1500 1500
1501 1501 public NavigableSet<K> descendingKeySet() {
1502 1502 return descendingMap().navigableKeySet();
1503 1503 }
1504 1504
1505 1505 public final SortedMap<K,V> subMap(K fromKey, K toKey) {
1506 1506 return subMap(fromKey, true, toKey, false);
1507 1507 }
1508 1508
1509 1509 public final SortedMap<K,V> headMap(K toKey) {
1510 1510 return headMap(toKey, false);
1511 1511 }
1512 1512
1513 1513 public final SortedMap<K,V> tailMap(K fromKey) {
1514 1514 return tailMap(fromKey, true);
1515 1515 }
1516 1516
1517 1517 // View classes
1518 1518
1519 1519 abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1520 1520 private transient int size = -1, sizeModCount;
1521 1521
1522 1522 public int size() {
1523 1523 if (fromStart && toEnd)
1524 1524 return m.size();
1525 1525 if (size == -1 || sizeModCount != m.modCount) {
1526 1526 sizeModCount = m.modCount;
1527 1527 size = 0;
1528 1528 Iterator i = iterator();
1529 1529 while (i.hasNext()) {
1530 1530 size++;
1531 1531 i.next();
1532 1532 }
1533 1533 }
1534 1534 return size;
1535 1535 }
1536 1536
1537 1537 public boolean isEmpty() {
1538 1538 TreeMap.Entry<K,V> n = absLowest();
1539 1539 return n == null || tooHigh(n.key);
1540 1540 }
1541 1541
1542 1542 public boolean contains(Object o) {
1543 1543 if (!(o instanceof Map.Entry))
1544 1544 return false;
1545 1545 Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1546 1546 K key = entry.getKey();
1547 1547 if (!inRange(key))
1548 1548 return false;
1549 1549 TreeMap.Entry node = m.getEntry(key);
1550 1550 return node != null &&
1551 1551 valEquals(node.getValue(), entry.getValue());
↓ open down ↓ |
122 lines elided |
↑ open up ↑ |
1552 1552 }
1553 1553
1554 1554 public boolean remove(Object o) {
1555 1555 if (!(o instanceof Map.Entry))
1556 1556 return false;
1557 1557 Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
1558 1558 K key = entry.getKey();
1559 1559 if (!inRange(key))
1560 1560 return false;
1561 1561 TreeMap.Entry<K,V> node = m.getEntry(key);
1562 - if (node!=null && valEquals(node.getValue(),entry.getValue())){
1562 + if (node!=null && valEquals(node.getValue(),
1563 + entry.getValue())) {
1563 1564 m.deleteEntry(node);
1564 1565 return true;
1565 1566 }
1566 1567 return false;
1567 1568 }
1568 1569 }
1569 1570
1570 1571 /**
1571 1572 * Iterators for SubMaps
1572 1573 */
1573 1574 abstract class SubMapIterator<T> implements Iterator<T> {
1574 1575 TreeMap.Entry<K,V> lastReturned;
1575 1576 TreeMap.Entry<K,V> next;
1576 1577 final Object fenceKey;
1577 1578 int expectedModCount;
1578 1579
1579 1580 SubMapIterator(TreeMap.Entry<K,V> first,
1580 1581 TreeMap.Entry<K,V> fence) {
1581 1582 expectedModCount = m.modCount;
1582 1583 lastReturned = null;
1583 1584 next = first;
1584 1585 fenceKey = fence == null ? UNBOUNDED : fence.key;
1585 1586 }
1586 1587
1587 1588 public final boolean hasNext() {
1588 1589 return next != null && next.key != fenceKey;
1589 1590 }
1590 1591
1591 1592 final TreeMap.Entry<K,V> nextEntry() {
1592 1593 TreeMap.Entry<K,V> e = next;
1593 1594 if (e == null || e.key == fenceKey)
1594 1595 throw new NoSuchElementException();
1595 1596 if (m.modCount != expectedModCount)
1596 1597 throw new ConcurrentModificationException();
1597 1598 next = successor(e);
1598 1599 lastReturned = e;
1599 1600 return e;
1600 1601 }
1601 1602
1602 1603 final TreeMap.Entry<K,V> prevEntry() {
1603 1604 TreeMap.Entry<K,V> e = next;
1604 1605 if (e == null || e.key == fenceKey)
1605 1606 throw new NoSuchElementException();
1606 1607 if (m.modCount != expectedModCount)
1607 1608 throw new ConcurrentModificationException();
1608 1609 next = predecessor(e);
1609 1610 lastReturned = e;
1610 1611 return e;
1611 1612 }
1612 1613
1613 1614 final void removeAscending() {
1614 1615 if (lastReturned == null)
1615 1616 throw new IllegalStateException();
1616 1617 if (m.modCount != expectedModCount)
1617 1618 throw new ConcurrentModificationException();
1618 1619 // deleted entries are replaced by their successors
1619 1620 if (lastReturned.left != null && lastReturned.right != null)
1620 1621 next = lastReturned;
1621 1622 m.deleteEntry(lastReturned);
1622 1623 lastReturned = null;
1623 1624 expectedModCount = m.modCount;
1624 1625 }
1625 1626
1626 1627 final void removeDescending() {
1627 1628 if (lastReturned == null)
1628 1629 throw new IllegalStateException();
1629 1630 if (m.modCount != expectedModCount)
1630 1631 throw new ConcurrentModificationException();
1631 1632 m.deleteEntry(lastReturned);
1632 1633 lastReturned = null;
1633 1634 expectedModCount = m.modCount;
1634 1635 }
1635 1636
1636 1637 }
1637 1638
1638 1639 final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1639 1640 SubMapEntryIterator(TreeMap.Entry<K,V> first,
1640 1641 TreeMap.Entry<K,V> fence) {
1641 1642 super(first, fence);
1642 1643 }
1643 1644 public Map.Entry<K,V> next() {
1644 1645 return nextEntry();
1645 1646 }
1646 1647 public void remove() {
1647 1648 removeAscending();
1648 1649 }
1649 1650 }
1650 1651
1651 1652 final class SubMapKeyIterator extends SubMapIterator<K> {
1652 1653 SubMapKeyIterator(TreeMap.Entry<K,V> first,
1653 1654 TreeMap.Entry<K,V> fence) {
1654 1655 super(first, fence);
1655 1656 }
1656 1657 public K next() {
1657 1658 return nextEntry().key;
1658 1659 }
1659 1660 public void remove() {
1660 1661 removeAscending();
1661 1662 }
1662 1663 }
1663 1664
1664 1665 final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1665 1666 DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1666 1667 TreeMap.Entry<K,V> fence) {
1667 1668 super(last, fence);
1668 1669 }
1669 1670
1670 1671 public Map.Entry<K,V> next() {
1671 1672 return prevEntry();
1672 1673 }
1673 1674 public void remove() {
1674 1675 removeDescending();
1675 1676 }
1676 1677 }
1677 1678
1678 1679 final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1679 1680 DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1680 1681 TreeMap.Entry<K,V> fence) {
1681 1682 super(last, fence);
1682 1683 }
1683 1684 public K next() {
1684 1685 return prevEntry().key;
1685 1686 }
1686 1687 public void remove() {
1687 1688 removeDescending();
1688 1689 }
1689 1690 }
1690 1691 }
1691 1692
1692 1693 /**
1693 1694 * @serial include
1694 1695 */
1695 1696 static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1696 1697 private static final long serialVersionUID = 912986545866124060L;
1697 1698
1698 1699 AscendingSubMap(TreeMap<K,V> m,
1699 1700 boolean fromStart, K lo, boolean loInclusive,
1700 1701 boolean toEnd, K hi, boolean hiInclusive) {
1701 1702 super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1702 1703 }
1703 1704
1704 1705 public Comparator<? super K> comparator() {
1705 1706 return m.comparator();
1706 1707 }
1707 1708
1708 1709 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1709 1710 K toKey, boolean toInclusive) {
1710 1711 if (!inRange(fromKey, fromInclusive))
1711 1712 throw new IllegalArgumentException("fromKey out of range");
1712 1713 if (!inRange(toKey, toInclusive))
1713 1714 throw new IllegalArgumentException("toKey out of range");
1714 1715 return new AscendingSubMap(m,
1715 1716 false, fromKey, fromInclusive,
1716 1717 false, toKey, toInclusive);
↓ open down ↓ |
144 lines elided |
↑ open up ↑ |
1717 1718 }
1718 1719
1719 1720 public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1720 1721 if (!inRange(toKey, inclusive))
1721 1722 throw new IllegalArgumentException("toKey out of range");
1722 1723 return new AscendingSubMap(m,
1723 1724 fromStart, lo, loInclusive,
1724 1725 false, toKey, inclusive);
1725 1726 }
1726 1727
1727 - public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1728 + public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
1728 1729 if (!inRange(fromKey, inclusive))
1729 1730 throw new IllegalArgumentException("fromKey out of range");
1730 1731 return new AscendingSubMap(m,
1731 1732 false, fromKey, inclusive,
1732 1733 toEnd, hi, hiInclusive);
1733 1734 }
1734 1735
1735 1736 public NavigableMap<K,V> descendingMap() {
1736 1737 NavigableMap<K,V> mv = descendingMapView;
1737 1738 return (mv != null) ? mv :
1738 1739 (descendingMapView =
1739 1740 new DescendingSubMap(m,
1740 1741 fromStart, lo, loInclusive,
1741 1742 toEnd, hi, hiInclusive));
1742 1743 }
1743 1744
1744 1745 Iterator<K> keyIterator() {
1745 1746 return new SubMapKeyIterator(absLowest(), absHighFence());
1746 1747 }
1747 1748
1748 1749 Iterator<K> descendingKeyIterator() {
1749 1750 return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1750 1751 }
1751 1752
1752 1753 final class AscendingEntrySetView extends EntrySetView {
1753 1754 public Iterator<Map.Entry<K,V>> iterator() {
1754 1755 return new SubMapEntryIterator(absLowest(), absHighFence());
1755 1756 }
1756 1757 }
1757 1758
1758 1759 public Set<Map.Entry<K,V>> entrySet() {
1759 1760 EntrySetView es = entrySetView;
1760 1761 return (es != null) ? es : new AscendingEntrySetView();
1761 1762 }
1762 1763
1763 1764 TreeMap.Entry<K,V> subLowest() { return absLowest(); }
1764 1765 TreeMap.Entry<K,V> subHighest() { return absHighest(); }
1765 1766 TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1766 1767 TreeMap.Entry<K,V> subHigher(K key) { return absHigher(key); }
1767 1768 TreeMap.Entry<K,V> subFloor(K key) { return absFloor(key); }
1768 1769 TreeMap.Entry<K,V> subLower(K key) { return absLower(key); }
1769 1770 }
1770 1771
1771 1772 /**
1772 1773 * @serial include
1773 1774 */
1774 1775 static final class DescendingSubMap<K,V> extends NavigableSubMap<K,V> {
1775 1776 private static final long serialVersionUID = 912986545866120460L;
1776 1777 DescendingSubMap(TreeMap<K,V> m,
1777 1778 boolean fromStart, K lo, boolean loInclusive,
1778 1779 boolean toEnd, K hi, boolean hiInclusive) {
1779 1780 super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1780 1781 }
1781 1782
1782 1783 private final Comparator<? super K> reverseComparator =
1783 1784 Collections.reverseOrder(m.comparator);
1784 1785
1785 1786 public Comparator<? super K> comparator() {
1786 1787 return reverseComparator;
1787 1788 }
1788 1789
1789 1790 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1790 1791 K toKey, boolean toInclusive) {
1791 1792 if (!inRange(fromKey, fromInclusive))
1792 1793 throw new IllegalArgumentException("fromKey out of range");
1793 1794 if (!inRange(toKey, toInclusive))
1794 1795 throw new IllegalArgumentException("toKey out of range");
1795 1796 return new DescendingSubMap(m,
1796 1797 false, toKey, toInclusive,
1797 1798 false, fromKey, fromInclusive);
↓ open down ↓ |
60 lines elided |
↑ open up ↑ |
1798 1799 }
1799 1800
1800 1801 public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1801 1802 if (!inRange(toKey, inclusive))
1802 1803 throw new IllegalArgumentException("toKey out of range");
1803 1804 return new DescendingSubMap(m,
1804 1805 false, toKey, inclusive,
1805 1806 toEnd, hi, hiInclusive);
1806 1807 }
1807 1808
1808 - public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1809 + public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
1809 1810 if (!inRange(fromKey, inclusive))
1810 1811 throw new IllegalArgumentException("fromKey out of range");
1811 1812 return new DescendingSubMap(m,
1812 1813 fromStart, lo, loInclusive,
1813 1814 false, fromKey, inclusive);
1814 1815 }
1815 1816
1816 1817 public NavigableMap<K,V> descendingMap() {
1817 1818 NavigableMap<K,V> mv = descendingMapView;
1818 1819 return (mv != null) ? mv :
1819 1820 (descendingMapView =
1820 1821 new AscendingSubMap(m,
1821 1822 fromStart, lo, loInclusive,
1822 1823 toEnd, hi, hiInclusive));
1823 1824 }
1824 1825
1825 1826 Iterator<K> keyIterator() {
1826 1827 return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1827 1828 }
1828 1829
1829 1830 Iterator<K> descendingKeyIterator() {
1830 1831 return new SubMapKeyIterator(absLowest(), absHighFence());
1831 1832 }
1832 1833
1833 1834 final class DescendingEntrySetView extends EntrySetView {
1834 1835 public Iterator<Map.Entry<K,V>> iterator() {
1835 1836 return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
1836 1837 }
1837 1838 }
1838 1839
1839 1840 public Set<Map.Entry<K,V>> entrySet() {
1840 1841 EntrySetView es = entrySetView;
1841 1842 return (es != null) ? es : new DescendingEntrySetView();
1842 1843 }
1843 1844
1844 1845 TreeMap.Entry<K,V> subLowest() { return absHighest(); }
1845 1846 TreeMap.Entry<K,V> subHighest() { return absLowest(); }
1846 1847 TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
1847 1848 TreeMap.Entry<K,V> subHigher(K key) { return absLower(key); }
1848 1849 TreeMap.Entry<K,V> subFloor(K key) { return absCeiling(key); }
1849 1850 TreeMap.Entry<K,V> subLower(K key) { return absHigher(key); }
1850 1851 }
1851 1852
1852 1853 /**
1853 1854 * This class exists solely for the sake of serialization
1854 1855 * compatibility with previous releases of TreeMap that did not
1855 1856 * support NavigableMap. It translates an old-version SubMap into
1856 1857 * a new-version AscendingSubMap. This class is never otherwise
1857 1858 * used.
1858 1859 *
1859 1860 * @serial include
1860 1861 */
1861 1862 private class SubMap extends AbstractMap<K,V>
1862 1863 implements SortedMap<K,V>, java.io.Serializable {
1863 1864 private static final long serialVersionUID = -6520786458950516097L;
1864 1865 private boolean fromStart = false, toEnd = false;
1865 1866 private K fromKey, toKey;
1866 1867 private Object readResolve() {
1867 1868 return new AscendingSubMap(TreeMap.this,
1868 1869 fromStart, fromKey, true,
1869 1870 toEnd, toKey, false);
1870 1871 }
1871 1872 public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
1872 1873 public K lastKey() { throw new InternalError(); }
1873 1874 public K firstKey() { throw new InternalError(); }
1874 1875 public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
1875 1876 public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
1876 1877 public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
1877 1878 public Comparator<? super K> comparator() { throw new InternalError(); }
1878 1879 }
1879 1880
1880 1881
1881 1882 // Red-black mechanics
1882 1883
1883 1884 private static final boolean RED = false;
1884 1885 private static final boolean BLACK = true;
1885 1886
1886 1887 /**
1887 1888 * Node in the Tree. Doubles as a means to pass key-value pairs back to
1888 1889 * user (see Map.Entry).
1889 1890 */
1890 1891
1891 1892 static final class Entry<K,V> implements Map.Entry<K,V> {
1892 1893 K key;
1893 1894 V value;
1894 1895 Entry<K,V> left = null;
1895 1896 Entry<K,V> right = null;
1896 1897 Entry<K,V> parent;
1897 1898 boolean color = BLACK;
1898 1899
1899 1900 /**
1900 1901 * Make a new cell with given key, value, and parent, and with
1901 1902 * {@code null} child links, and BLACK color.
1902 1903 */
1903 1904 Entry(K key, V value, Entry<K,V> parent) {
1904 1905 this.key = key;
1905 1906 this.value = value;
1906 1907 this.parent = parent;
1907 1908 }
1908 1909
1909 1910 /**
1910 1911 * Returns the key.
1911 1912 *
1912 1913 * @return the key
1913 1914 */
1914 1915 public K getKey() {
1915 1916 return key;
1916 1917 }
1917 1918
1918 1919 /**
1919 1920 * Returns the value associated with the key.
1920 1921 *
1921 1922 * @return the value associated with the key
1922 1923 */
1923 1924 public V getValue() {
1924 1925 return value;
1925 1926 }
1926 1927
1927 1928 /**
1928 1929 * Replaces the value currently associated with the key with the given
1929 1930 * value.
1930 1931 *
1931 1932 * @return the value associated with the key before this method was
1932 1933 * called
1933 1934 */
1934 1935 public V setValue(V value) {
1935 1936 V oldValue = this.value;
1936 1937 this.value = value;
1937 1938 return oldValue;
1938 1939 }
1939 1940
1940 1941 public boolean equals(Object o) {
1941 1942 if (!(o instanceof Map.Entry))
1942 1943 return false;
1943 1944 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1944 1945
1945 1946 return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
1946 1947 }
1947 1948
1948 1949 public int hashCode() {
1949 1950 int keyHash = (key==null ? 0 : key.hashCode());
1950 1951 int valueHash = (value==null ? 0 : value.hashCode());
1951 1952 return keyHash ^ valueHash;
1952 1953 }
1953 1954
1954 1955 public String toString() {
1955 1956 return key + "=" + value;
1956 1957 }
1957 1958 }
1958 1959
1959 1960 /**
1960 1961 * Returns the first Entry in the TreeMap (according to the TreeMap's
1961 1962 * key-sort function). Returns null if the TreeMap is empty.
1962 1963 */
1963 1964 final Entry<K,V> getFirstEntry() {
1964 1965 Entry<K,V> p = root;
1965 1966 if (p != null)
1966 1967 while (p.left != null)
1967 1968 p = p.left;
1968 1969 return p;
1969 1970 }
1970 1971
1971 1972 /**
1972 1973 * Returns the last Entry in the TreeMap (according to the TreeMap's
1973 1974 * key-sort function). Returns null if the TreeMap is empty.
1974 1975 */
1975 1976 final Entry<K,V> getLastEntry() {
1976 1977 Entry<K,V> p = root;
1977 1978 if (p != null)
1978 1979 while (p.right != null)
1979 1980 p = p.right;
1980 1981 return p;
1981 1982 }
1982 1983
1983 1984 /**
1984 1985 * Returns the successor of the specified Entry, or null if no such.
1985 1986 */
1986 1987 static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
1987 1988 if (t == null)
1988 1989 return null;
1989 1990 else if (t.right != null) {
1990 1991 Entry<K,V> p = t.right;
1991 1992 while (p.left != null)
1992 1993 p = p.left;
1993 1994 return p;
1994 1995 } else {
1995 1996 Entry<K,V> p = t.parent;
1996 1997 Entry<K,V> ch = t;
1997 1998 while (p != null && ch == p.right) {
1998 1999 ch = p;
1999 2000 p = p.parent;
2000 2001 }
2001 2002 return p;
2002 2003 }
2003 2004 }
2004 2005
2005 2006 /**
2006 2007 * Returns the predecessor of the specified Entry, or null if no such.
2007 2008 */
2008 2009 static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
2009 2010 if (t == null)
2010 2011 return null;
2011 2012 else if (t.left != null) {
2012 2013 Entry<K,V> p = t.left;
2013 2014 while (p.right != null)
2014 2015 p = p.right;
2015 2016 return p;
2016 2017 } else {
2017 2018 Entry<K,V> p = t.parent;
2018 2019 Entry<K,V> ch = t;
2019 2020 while (p != null && ch == p.left) {
2020 2021 ch = p;
2021 2022 p = p.parent;
2022 2023 }
2023 2024 return p;
2024 2025 }
2025 2026 }
2026 2027
2027 2028 /**
2028 2029 * Balancing operations.
2029 2030 *
2030 2031 * Implementations of rebalancings during insertion and deletion are
2031 2032 * slightly different than the CLR version. Rather than using dummy
2032 2033 * nilnodes, we use a set of accessors that deal properly with null. They
2033 2034 * are used to avoid messiness surrounding nullness checks in the main
2034 2035 * algorithms.
2035 2036 */
2036 2037
2037 2038 private static <K,V> boolean colorOf(Entry<K,V> p) {
2038 2039 return (p == null ? BLACK : p.color);
2039 2040 }
2040 2041
2041 2042 private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {
2042 2043 return (p == null ? null: p.parent);
2043 2044 }
2044 2045
2045 2046 private static <K,V> void setColor(Entry<K,V> p, boolean c) {
2046 2047 if (p != null)
2047 2048 p.color = c;
2048 2049 }
2049 2050
2050 2051 private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
2051 2052 return (p == null) ? null: p.left;
2052 2053 }
2053 2054
2054 2055 private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {
2055 2056 return (p == null) ? null: p.right;
2056 2057 }
2057 2058
2058 2059 /** From CLR */
2059 2060 private void rotateLeft(Entry<K,V> p) {
2060 2061 if (p != null) {
2061 2062 Entry<K,V> r = p.right;
2062 2063 p.right = r.left;
2063 2064 if (r.left != null)
2064 2065 r.left.parent = p;
2065 2066 r.parent = p.parent;
2066 2067 if (p.parent == null)
2067 2068 root = r;
2068 2069 else if (p.parent.left == p)
2069 2070 p.parent.left = r;
2070 2071 else
2071 2072 p.parent.right = r;
2072 2073 r.left = p;
2073 2074 p.parent = r;
2074 2075 }
2075 2076 }
2076 2077
2077 2078 /** From CLR */
2078 2079 private void rotateRight(Entry<K,V> p) {
2079 2080 if (p != null) {
2080 2081 Entry<K,V> l = p.left;
2081 2082 p.left = l.right;
2082 2083 if (l.right != null) l.right.parent = p;
2083 2084 l.parent = p.parent;
2084 2085 if (p.parent == null)
2085 2086 root = l;
2086 2087 else if (p.parent.right == p)
2087 2088 p.parent.right = l;
2088 2089 else p.parent.left = l;
2089 2090 l.right = p;
2090 2091 p.parent = l;
2091 2092 }
2092 2093 }
2093 2094
2094 2095 /** From CLR */
2095 2096 private void fixAfterInsertion(Entry<K,V> x) {
2096 2097 x.color = RED;
2097 2098
2098 2099 while (x != null && x != root && x.parent.color == RED) {
2099 2100 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
2100 2101 Entry<K,V> y = rightOf(parentOf(parentOf(x)));
2101 2102 if (colorOf(y) == RED) {
2102 2103 setColor(parentOf(x), BLACK);
2103 2104 setColor(y, BLACK);
2104 2105 setColor(parentOf(parentOf(x)), RED);
2105 2106 x = parentOf(parentOf(x));
2106 2107 } else {
2107 2108 if (x == rightOf(parentOf(x))) {
2108 2109 x = parentOf(x);
2109 2110 rotateLeft(x);
2110 2111 }
2111 2112 setColor(parentOf(x), BLACK);
2112 2113 setColor(parentOf(parentOf(x)), RED);
2113 2114 rotateRight(parentOf(parentOf(x)));
2114 2115 }
2115 2116 } else {
2116 2117 Entry<K,V> y = leftOf(parentOf(parentOf(x)));
2117 2118 if (colorOf(y) == RED) {
2118 2119 setColor(parentOf(x), BLACK);
2119 2120 setColor(y, BLACK);
2120 2121 setColor(parentOf(parentOf(x)), RED);
2121 2122 x = parentOf(parentOf(x));
2122 2123 } else {
2123 2124 if (x == leftOf(parentOf(x))) {
2124 2125 x = parentOf(x);
2125 2126 rotateRight(x);
2126 2127 }
2127 2128 setColor(parentOf(x), BLACK);
2128 2129 setColor(parentOf(parentOf(x)), RED);
2129 2130 rotateLeft(parentOf(parentOf(x)));
2130 2131 }
2131 2132 }
2132 2133 }
2133 2134 root.color = BLACK;
2134 2135 }
2135 2136
↓ open down ↓ |
317 lines elided |
↑ open up ↑ |
2136 2137 /**
2137 2138 * Delete node p, and then rebalance the tree.
2138 2139 */
2139 2140 private void deleteEntry(Entry<K,V> p) {
2140 2141 modCount++;
2141 2142 size--;
2142 2143
2143 2144 // If strictly internal, copy successor's element to p and then make p
2144 2145 // point to successor.
2145 2146 if (p.left != null && p.right != null) {
2146 - Entry<K,V> s = successor (p);
2147 + Entry<K,V> s = successor(p);
2147 2148 p.key = s.key;
2148 2149 p.value = s.value;
2149 2150 p = s;
2150 2151 } // p has 2 children
2151 2152
2152 2153 // Start fixup at replacement node, if it exists.
2153 2154 Entry<K,V> replacement = (p.left != null ? p.left : p.right);
2154 2155
2155 2156 if (replacement != null) {
2156 2157 // Link replacement to parent
2157 2158 replacement.parent = p.parent;
2158 2159 if (p.parent == null)
2159 2160 root = replacement;
2160 2161 else if (p == p.parent.left)
2161 2162 p.parent.left = replacement;
2162 2163 else
2163 2164 p.parent.right = replacement;
2164 2165
2165 2166 // Null out links so they are OK to use by fixAfterDeletion.
2166 2167 p.left = p.right = p.parent = null;
2167 2168
2168 2169 // Fix replacement
2169 2170 if (p.color == BLACK)
2170 2171 fixAfterDeletion(replacement);
2171 2172 } else if (p.parent == null) { // return if we are the only node.
2172 2173 root = null;
2173 2174 } else { // No children. Use self as phantom replacement and unlink.
2174 2175 if (p.color == BLACK)
2175 2176 fixAfterDeletion(p);
2176 2177
2177 2178 if (p.parent != null) {
2178 2179 if (p == p.parent.left)
2179 2180 p.parent.left = null;
2180 2181 else if (p == p.parent.right)
2181 2182 p.parent.right = null;
2182 2183 p.parent = null;
2183 2184 }
2184 2185 }
2185 2186 }
2186 2187
2187 2188 /** From CLR */
2188 2189 private void fixAfterDeletion(Entry<K,V> x) {
2189 2190 while (x != root && colorOf(x) == BLACK) {
2190 2191 if (x == leftOf(parentOf(x))) {
2191 2192 Entry<K,V> sib = rightOf(parentOf(x));
2192 2193
2193 2194 if (colorOf(sib) == RED) {
2194 2195 setColor(sib, BLACK);
2195 2196 setColor(parentOf(x), RED);
2196 2197 rotateLeft(parentOf(x));
2197 2198 sib = rightOf(parentOf(x));
2198 2199 }
2199 2200
2200 2201 if (colorOf(leftOf(sib)) == BLACK &&
2201 2202 colorOf(rightOf(sib)) == BLACK) {
2202 2203 setColor(sib, RED);
2203 2204 x = parentOf(x);
2204 2205 } else {
2205 2206 if (colorOf(rightOf(sib)) == BLACK) {
2206 2207 setColor(leftOf(sib), BLACK);
2207 2208 setColor(sib, RED);
2208 2209 rotateRight(sib);
2209 2210 sib = rightOf(parentOf(x));
2210 2211 }
2211 2212 setColor(sib, colorOf(parentOf(x)));
2212 2213 setColor(parentOf(x), BLACK);
2213 2214 setColor(rightOf(sib), BLACK);
2214 2215 rotateLeft(parentOf(x));
2215 2216 x = root;
2216 2217 }
2217 2218 } else { // symmetric
2218 2219 Entry<K,V> sib = leftOf(parentOf(x));
2219 2220
2220 2221 if (colorOf(sib) == RED) {
2221 2222 setColor(sib, BLACK);
2222 2223 setColor(parentOf(x), RED);
2223 2224 rotateRight(parentOf(x));
2224 2225 sib = leftOf(parentOf(x));
2225 2226 }
2226 2227
2227 2228 if (colorOf(rightOf(sib)) == BLACK &&
2228 2229 colorOf(leftOf(sib)) == BLACK) {
2229 2230 setColor(sib, RED);
2230 2231 x = parentOf(x);
2231 2232 } else {
2232 2233 if (colorOf(leftOf(sib)) == BLACK) {
2233 2234 setColor(rightOf(sib), BLACK);
2234 2235 setColor(sib, RED);
2235 2236 rotateLeft(sib);
2236 2237 sib = leftOf(parentOf(x));
2237 2238 }
2238 2239 setColor(sib, colorOf(parentOf(x)));
2239 2240 setColor(parentOf(x), BLACK);
2240 2241 setColor(leftOf(sib), BLACK);
2241 2242 rotateRight(parentOf(x));
2242 2243 x = root;
2243 2244 }
2244 2245 }
2245 2246 }
2246 2247
2247 2248 setColor(x, BLACK);
2248 2249 }
2249 2250
2250 2251 private static final long serialVersionUID = 919286545866124006L;
2251 2252
2252 2253 /**
2253 2254 * Save the state of the {@code TreeMap} instance to a stream (i.e.,
2254 2255 * serialize it).
2255 2256 *
2256 2257 * @serialData The <em>size</em> of the TreeMap (the number of key-value
2257 2258 * mappings) is emitted (int), followed by the key (Object)
2258 2259 * and value (Object) for each key-value mapping represented
2259 2260 * by the TreeMap. The key-value mappings are emitted in
2260 2261 * key-order (as determined by the TreeMap's Comparator,
2261 2262 * or by the keys' natural ordering if the TreeMap has no
2262 2263 * Comparator).
2263 2264 */
2264 2265 private void writeObject(java.io.ObjectOutputStream s)
2265 2266 throws java.io.IOException {
2266 2267 // Write out the Comparator and any hidden stuff
2267 2268 s.defaultWriteObject();
2268 2269
2269 2270 // Write out size (number of Mappings)
2270 2271 s.writeInt(size);
2271 2272
2272 2273 // Write out keys and values (alternating)
2273 2274 for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {
2274 2275 Map.Entry<K,V> e = i.next();
2275 2276 s.writeObject(e.getKey());
2276 2277 s.writeObject(e.getValue());
2277 2278 }
2278 2279 }
2279 2280
2280 2281 /**
2281 2282 * Reconstitute the {@code TreeMap} instance from a stream (i.e.,
2282 2283 * deserialize it).
2283 2284 */
2284 2285 private void readObject(final java.io.ObjectInputStream s)
2285 2286 throws java.io.IOException, ClassNotFoundException {
2286 2287 // Read in the Comparator and any hidden stuff
2287 2288 s.defaultReadObject();
2288 2289
2289 2290 // Read in size
2290 2291 int size = s.readInt();
2291 2292
2292 2293 buildFromSorted(size, null, s, null);
2293 2294 }
2294 2295
2295 2296 /** Intended to be called only from TreeSet.readObject */
2296 2297 void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2297 2298 throws java.io.IOException, ClassNotFoundException {
2298 2299 buildFromSorted(size, null, s, defaultVal);
2299 2300 }
2300 2301
2301 2302 /** Intended to be called only from TreeSet.addAll */
2302 2303 void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2303 2304 try {
2304 2305 buildFromSorted(set.size(), set.iterator(), null, defaultVal);
2305 2306 } catch (java.io.IOException cannotHappen) {
2306 2307 } catch (ClassNotFoundException cannotHappen) {
2307 2308 }
2308 2309 }
2309 2310
2310 2311
2311 2312 /**
2312 2313 * Linear time tree building algorithm from sorted data. Can accept keys
2313 2314 * and/or values from iterator or stream. This leads to too many
2314 2315 * parameters, but seems better than alternatives. The four formats
2315 2316 * that this method accepts are:
2316 2317 *
2317 2318 * 1) An iterator of Map.Entries. (it != null, defaultVal == null).
2318 2319 * 2) An iterator of keys. (it != null, defaultVal != null).
2319 2320 * 3) A stream of alternating serialized keys and values.
2320 2321 * (it == null, defaultVal == null).
2321 2322 * 4) A stream of serialized keys. (it == null, defaultVal != null).
2322 2323 *
2323 2324 * It is assumed that the comparator of the TreeMap is already set prior
2324 2325 * to calling this method.
2325 2326 *
2326 2327 * @param size the number of keys (or key-value pairs) to be read from
2327 2328 * the iterator or stream
2328 2329 * @param it If non-null, new entries are created from entries
2329 2330 * or keys read from this iterator.
2330 2331 * @param str If non-null, new entries are created from keys and
2331 2332 * possibly values read from this stream in serialized form.
2332 2333 * Exactly one of it and str should be non-null.
2333 2334 * @param defaultVal if non-null, this default value is used for
2334 2335 * each value in the map. If null, each value is read from
2335 2336 * iterator or stream, as described above.
2336 2337 * @throws IOException propagated from stream reads. This cannot
2337 2338 * occur if str is null.
2338 2339 * @throws ClassNotFoundException propagated from readObject.
2339 2340 * This cannot occur if str is null.
2340 2341 */
2341 2342 private void buildFromSorted(int size, Iterator it,
2342 2343 java.io.ObjectInputStream str,
2343 2344 V defaultVal)
2344 2345 throws java.io.IOException, ClassNotFoundException {
2345 2346 this.size = size;
2346 2347 root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
2347 2348 it, str, defaultVal);
2348 2349 }
2349 2350
2350 2351 /**
2351 2352 * Recursive "helper method" that does the real work of the
2352 2353 * previous method. Identically named parameters have
2353 2354 * identical definitions. Additional parameters are documented below.
2354 2355 * It is assumed that the comparator and size fields of the TreeMap are
2355 2356 * already set prior to calling this method. (It ignores both fields.)
2356 2357 *
2357 2358 * @param level the current level of tree. Initial call should be 0.
2358 2359 * @param lo the first element index of this subtree. Initial should be 0.
2359 2360 * @param hi the last element index of this subtree. Initial should be
2360 2361 * size-1.
2361 2362 * @param redLevel the level at which nodes should be red.
2362 2363 * Must be equal to computeRedLevel for tree of this size.
2363 2364 */
2364 2365 private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
2365 2366 int redLevel,
2366 2367 Iterator it,
2367 2368 java.io.ObjectInputStream str,
2368 2369 V defaultVal)
2369 2370 throws java.io.IOException, ClassNotFoundException {
2370 2371 /*
2371 2372 * Strategy: The root is the middlemost element. To get to it, we
2372 2373 * have to first recursively construct the entire left subtree,
2373 2374 * so as to grab all of its elements. We can then proceed with right
2374 2375 * subtree.
2375 2376 *
2376 2377 * The lo and hi arguments are the minimum and maximum
2377 2378 * indices to pull out of the iterator or stream for current subtree.
2378 2379 * They are not actually indexed, we just proceed sequentially,
2379 2380 * ensuring that items are extracted in corresponding order.
2380 2381 */
2381 2382
2382 2383 if (hi < lo) return null;
2383 2384
2384 2385 int mid = (lo + hi) >>> 1;
2385 2386
2386 2387 Entry<K,V> left = null;
2387 2388 if (lo < mid)
2388 2389 left = buildFromSorted(level+1, lo, mid - 1, redLevel,
2389 2390 it, str, defaultVal);
2390 2391
2391 2392 // extract key and/or value from iterator or stream
2392 2393 K key;
2393 2394 V value;
2394 2395 if (it != null) {
2395 2396 if (defaultVal==null) {
2396 2397 Map.Entry<K,V> entry = (Map.Entry<K,V>)it.next();
2397 2398 key = entry.getKey();
2398 2399 value = entry.getValue();
2399 2400 } else {
2400 2401 key = (K)it.next();
2401 2402 value = defaultVal;
2402 2403 }
2403 2404 } else { // use stream
2404 2405 key = (K) str.readObject();
2405 2406 value = (defaultVal != null ? defaultVal : (V) str.readObject());
2406 2407 }
2407 2408
2408 2409 Entry<K,V> middle = new Entry<K,V>(key, value, null);
2409 2410
2410 2411 // color nodes in non-full bottommost level red
2411 2412 if (level == redLevel)
2412 2413 middle.color = RED;
2413 2414
2414 2415 if (left != null) {
2415 2416 middle.left = left;
2416 2417 left.parent = middle;
2417 2418 }
2418 2419
2419 2420 if (mid < hi) {
2420 2421 Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
2421 2422 it, str, defaultVal);
2422 2423 middle.right = right;
2423 2424 right.parent = middle;
2424 2425 }
2425 2426
2426 2427 return middle;
2427 2428 }
2428 2429
2429 2430 /**
2430 2431 * Find the level down to which to assign all nodes BLACK. This is the
2431 2432 * last `full' level of the complete binary tree produced by
2432 2433 * buildTree. The remaining nodes are colored RED. (This makes a `nice'
2433 2434 * set of color assignments wrt future insertions.) This level number is
2434 2435 * computed by finding the number of splits needed to reach the zeroeth
2435 2436 * node. (The answer is ~lg(N), but in any case must be computed by same
2436 2437 * quick O(lg(N)) loop.)
2437 2438 */
2438 2439 private static int computeRedLevel(int sz) {
2439 2440 int level = 0;
2440 2441 for (int m = sz - 1; m >= 0; m = m / 2 - 1)
2441 2442 level++;
2442 2443 return level;
2443 2444 }
2444 2445 }
↓ open down ↓ |
288 lines elided |
↑ open up ↑ |
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX