2 * Copyright (C) 2014 The Android Open Source Project
3 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
6 * This code is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License version 2 only, as
8 * published by the Free Software Foundation. Oracle designates this
9 * particular file as subject to the "Classpath" exception as provided
10 * by Oracle in the LICENSE file that accompanied this code.
12 * This code is distributed in the hope that it will be useful, but WITHOUT
13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 * version 2 for more details (a copy is included in the LICENSE file that
16 * accompanied this code).
18 * You should have received a copy of the GNU General Public License version
19 * 2 along with this work; if not, write to the Free Software Foundation,
20 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
22 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
23 * or visit www.oracle.com if you need additional information or have any
29 import java
.io
.Serializable
;
30 import java
.util
.function
.BiConsumer
;
31 import java
.util
.function
.BiFunction
;
32 import java
.util
.function
.Consumer
;
35 * A Red-Black tree based {@link NavigableMap} implementation.
36 * The map is sorted according to the {@linkplain Comparable natural
37 * ordering} of its keys, or by a {@link Comparator} provided at map
38 * creation time, depending on which constructor is used.
40 * <p>This implementation provides guaranteed log(n) time cost for the
41 * {@code containsKey}, {@code get}, {@code put} and {@code remove}
42 * operations. Algorithms are adaptations of those in Cormen, Leiserson, and
43 * Rivest's <em>Introduction to Algorithms</em>.
45 * <p>Note that the ordering maintained by a tree map, like any sorted map, and
46 * whether or not an explicit comparator is provided, must be <em>consistent
47 * with {@code equals}</em> if this sorted map is to correctly implement the
48 * {@code Map} interface. (See {@code Comparable} or {@code Comparator} for a
49 * precise definition of <em>consistent with equals</em>.) This is so because
50 * the {@code Map} interface is defined in terms of the {@code equals}
51 * operation, but a sorted map performs all key comparisons using its {@code
52 * compareTo} (or {@code compare}) method, so two keys that are deemed equal by
53 * this method are, from the standpoint of the sorted map, equal. The behavior
54 * of a sorted map <em>is</em> well-defined even if its ordering is
55 * inconsistent with {@code equals}; it just fails to obey the general contract
56 * of the {@code Map} interface.
58 * <p><strong>Note that this implementation is not synchronized.</strong>
59 * If multiple threads access a map concurrently, and at least one of the
60 * threads modifies the map structurally, it <em>must</em> be synchronized
61 * externally. (A structural modification is any operation that adds or
62 * deletes one or more mappings; merely changing the value associated
63 * with an existing key is not a structural modification.) This is
64 * typically accomplished by synchronizing on some object that naturally
65 * encapsulates the map.
66 * If no such object exists, the map should be "wrapped" using the
67 * {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap}
68 * method. This is best done at creation time, to prevent accidental
69 * unsynchronized access to the map: <pre>
70 * SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre>
72 * <p>The iterators returned by the {@code iterator} method of the collections
73 * returned by all of this class's "collection view methods" are
74 * <em>fail-fast</em>: if the map is structurally modified at any time after
75 * the iterator is created, in any way except through the iterator's own
76 * {@code remove} method, the iterator will throw a {@link
77 * ConcurrentModificationException}. Thus, in the face of concurrent
78 * modification, the iterator fails quickly and cleanly, rather than risking
79 * arbitrary, non-deterministic behavior at an undetermined time in the future.
81 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
82 * as it is, generally speaking, impossible to make any hard guarantees in the
83 * presence of unsynchronized concurrent modification. Fail-fast iterators
84 * throw {@code ConcurrentModificationException} on a best-effort basis.
85 * Therefore, it would be wrong to write a program that depended on this
86 * exception for its correctness: <em>the fail-fast behavior of iterators
87 * should be used only to detect bugs.</em>
89 * <p>All {@code Map.Entry} pairs returned by methods in this class
90 * and its views represent snapshots of mappings at the time they were
91 * produced. They do <strong>not</strong> support the {@code Entry.setValue}
92 * method. (Note however that it is possible to change mappings in the
93 * associated map using {@code put}.)
95 * <p>This class is a member of the
96 * <a href="{@docRoot}openjdk-redirect.html?v=8&path=/technotes/guides/collections/index.html">
97 * Java Collections Framework</a>.
99 * @param <K> the type of keys maintained by this map
100 * @param <V> the type of mapped values
102 * @author Josh Bloch and Doug Lea
112 public class TreeMap
<K
,V
>
113 extends AbstractMap
<K
,V
>
114 implements NavigableMap
<K
,V
>, Cloneable
, java
.io
.Serializable
117 * The comparator used to maintain order in this tree map, or
118 * null if it uses the natural ordering of its keys.
122 private final Comparator
<?
super K
> comparator
;
124 private transient TreeMapEntry
<K
,V
> root
= null;
127 * The number of entries in the tree
129 private transient int size
= 0;
132 * The number of structural modifications to the tree.
134 private transient int modCount
= 0;
137 * Constructs a new, empty tree map, using the natural ordering of its
138 * keys. All keys inserted into the map must implement the {@link
139 * Comparable} interface. Furthermore, all such keys must be
140 * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
141 * a {@code ClassCastException} for any keys {@code k1} and
142 * {@code k2} in the map. If the user attempts to put a key into the
143 * map that violates this constraint (for example, the user attempts to
144 * put a string key into a map whose keys are integers), the
145 * {@code put(Object key, Object value)} call will throw a
146 * {@code ClassCastException}.
153 * Constructs a new, empty tree map, ordered according to the given
154 * comparator. All keys inserted into the map must be <em>mutually
155 * comparable</em> by the given comparator: {@code comparator.compare(k1,
156 * k2)} must not throw a {@code ClassCastException} for any keys
157 * {@code k1} and {@code k2} in the map. If the user attempts to put
158 * a key into the map that violates this constraint, the {@code put(Object
159 * key, Object value)} call will throw a
160 * {@code ClassCastException}.
162 * @param comparator the comparator that will be used to order this map.
163 * If {@code null}, the {@linkplain Comparable natural
164 * ordering} of the keys will be used.
166 public TreeMap(Comparator
<?
super K
> comparator
) {
167 this.comparator
= comparator
;
171 * Constructs a new tree map containing the same mappings as the given
172 * map, ordered according to the <em>natural ordering</em> of its keys.
173 * All keys inserted into the new map must implement the {@link
174 * Comparable} interface. Furthermore, all such keys must be
175 * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
176 * a {@code ClassCastException} for any keys {@code k1} and
177 * {@code k2} in the map. This method runs in n*log(n) time.
179 * @param m the map whose mappings are to be placed in this map
180 * @throws ClassCastException if the keys in m are not {@link Comparable},
181 * or are not mutually comparable
182 * @throws NullPointerException if the specified map is null
184 public TreeMap(Map
<?
extends K
, ?
extends V
> m
) {
190 * Constructs a new tree map containing the same mappings and
191 * using the same ordering as the specified sorted map. This
192 * method runs in linear time.
194 * @param m the sorted map whose mappings are to be placed in this map,
195 * and whose comparator is to be used to sort this map
196 * @throws NullPointerException if the specified map is null
198 public TreeMap(SortedMap
<K
, ?
extends V
> m
) {
199 comparator
= m
.comparator();
201 buildFromSorted(m
.size(), m
.entrySet().iterator(), null, null);
202 } catch (java
.io
.IOException cannotHappen
) {
203 } catch (ClassNotFoundException cannotHappen
) {
211 * Returns the number of key-value mappings in this map.
213 * @return the number of key-value mappings in this map
220 * Returns {@code true} if this map contains a mapping for the specified
223 * @param key key whose presence in this map is to be tested
224 * @return {@code true} if this map contains a mapping for the
226 * @throws ClassCastException if the specified key cannot be compared
227 * with the keys currently in the map
228 * @throws NullPointerException if the specified key is null
229 * and this map uses natural ordering, or its comparator
230 * does not permit null keys
232 public boolean containsKey(Object key
) {
233 return getEntry(key
) != null;
237 * Returns {@code true} if this map maps one or more keys to the
238 * specified value. More formally, returns {@code true} if and only if
239 * this map contains at least one mapping to a value {@code v} such
240 * that {@code (value==null ? v==null : value.equals(v))}. This
241 * operation will probably require time linear in the map size for
242 * most implementations.
244 * @param value value whose presence in this map is to be tested
245 * @return {@code true} if a mapping to {@code value} exists;
246 * {@code false} otherwise
249 public boolean containsValue(Object value
) {
250 for (TreeMapEntry
<K
,V
> e
= getFirstEntry(); e
!= null; e
= successor(e
))
251 if (valEquals(value
, e
.value
))
257 * Returns the value to which the specified key is mapped,
258 * or {@code null} if this map contains no mapping for the key.
260 * <p>More formally, if this map contains a mapping from a key
261 * {@code k} to a value {@code v} such that {@code key} compares
262 * equal to {@code k} according to the map's ordering, then this
263 * method returns {@code v}; otherwise it returns {@code null}.
264 * (There can be at most one such mapping.)
266 * <p>A return value of {@code null} does not <em>necessarily</em>
267 * indicate that the map contains no mapping for the key; it's also
268 * possible that the map explicitly maps the key to {@code null}.
269 * The {@link #containsKey containsKey} operation may be used to
270 * distinguish these two cases.
272 * @throws ClassCastException if the specified key cannot be compared
273 * with the keys currently in the map
274 * @throws NullPointerException if the specified key is null
275 * and this map uses natural ordering, or its comparator
276 * does not permit null keys
278 public V
get(Object key
) {
279 TreeMapEntry
<K
,V
> p
= getEntry(key
);
280 return (p
==null ?
null : p
.value
);
283 public Comparator
<?
super K
> comparator() {
288 * @throws NoSuchElementException {@inheritDoc}
290 public K
firstKey() {
291 return key(getFirstEntry());
295 * @throws NoSuchElementException {@inheritDoc}
298 return key(getLastEntry());
302 * Copies all of the mappings from the specified map to this map.
303 * These mappings replace any mappings that this map had for any
304 * of the keys currently in the specified map.
306 * @param map mappings to be stored in this map
307 * @throws ClassCastException if the class of a key or value in
308 * the specified map prevents it from being stored in this map
309 * @throws NullPointerException if the specified map is null or
310 * the specified map contains a null key and this map does not
313 public void putAll(Map
<?
extends K
, ?
extends V
> map
) {
314 int mapSize
= map
.size();
315 if (size
==0 && mapSize
!=0 && map
instanceof SortedMap
) {
316 Comparator
<?
> c
= ((SortedMap
<?
,?
>)map
).comparator();
317 if (c
== comparator
|| (c
!= null && c
.equals(comparator
))) {
320 buildFromSorted(mapSize
, map
.entrySet().iterator(),
322 } catch (java
.io
.IOException cannotHappen
) {
323 } catch (ClassNotFoundException cannotHappen
) {
332 * Returns this map's entry for the given key, or {@code null} if the map
333 * does not contain an entry for the key.
335 * @return this map's entry for the given key, or {@code null} if the map
336 * does not contain an entry for the key
337 * @throws ClassCastException if the specified key cannot be compared
338 * with the keys currently in the map
339 * @throws NullPointerException if the specified key is null
340 * and this map uses natural ordering, or its comparator
341 * does not permit null keys
343 final TreeMapEntry
<K
,V
> getEntry(Object key
) {
344 // Offload comparator-based version for sake of performance
345 if (comparator
!= null)
346 return getEntryUsingComparator(key
);
348 throw new NullPointerException();
349 @SuppressWarnings("unchecked")
350 Comparable
<?
super K
> k
= (Comparable
<?
super K
>) key
;
351 TreeMapEntry
<K
,V
> p
= root
;
353 int cmp
= k
.compareTo(p
.key
);
365 * Version of getEntry using comparator. Split off from getEntry
366 * for performance. (This is not worth doing for most methods,
367 * that are less dependent on comparator performance, but is
370 final TreeMapEntry
<K
,V
> getEntryUsingComparator(Object key
) {
371 @SuppressWarnings("unchecked")
373 Comparator
<?
super K
> cpr
= comparator
;
375 TreeMapEntry
<K
,V
> p
= root
;
377 int cmp
= cpr
.compare(k
, p
.key
);
390 * Gets the entry corresponding to the specified key; if no such entry
391 * exists, returns the entry for the least key greater than the specified
392 * key; if no such entry exists (i.e., the greatest key in the Tree is less
393 * than the specified key), returns {@code null}.
395 final TreeMapEntry
<K
,V
> getCeilingEntry(K key
) {
396 TreeMapEntry
<K
,V
> p
= root
;
398 int cmp
= compare(key
, p
.key
);
404 } else if (cmp
> 0) {
405 if (p
.right
!= null) {
408 TreeMapEntry
<K
,V
> parent
= p
.parent
;
409 TreeMapEntry
<K
,V
> ch
= p
;
410 while (parent
!= null && ch
== parent
.right
) {
412 parent
= parent
.parent
;
423 * Gets the entry corresponding to the specified key; if no such entry
424 * exists, returns the entry for the greatest key less than the specified
425 * key; if no such entry exists, returns {@code null}.
427 final TreeMapEntry
<K
,V
> getFloorEntry(K key
) {
428 TreeMapEntry
<K
,V
> p
= root
;
430 int cmp
= compare(key
, p
.key
);
436 } else if (cmp
< 0) {
437 if (p
.left
!= null) {
440 TreeMapEntry
<K
,V
> parent
= p
.parent
;
441 TreeMapEntry
<K
,V
> ch
= p
;
442 while (parent
!= null && ch
== parent
.left
) {
444 parent
= parent
.parent
;
456 * Gets the entry for the least key greater than the specified
457 * key; if no such entry exists, returns the entry for the least
458 * key greater than the specified key; if no such entry exists
459 * returns {@code null}.
461 final TreeMapEntry
<K
,V
> getHigherEntry(K key
) {
462 TreeMapEntry
<K
,V
> p
= root
;
464 int cmp
= compare(key
, p
.key
);
471 if (p
.right
!= null) {
474 TreeMapEntry
<K
,V
> parent
= p
.parent
;
475 TreeMapEntry
<K
,V
> ch
= p
;
476 while (parent
!= null && ch
== parent
.right
) {
478 parent
= parent
.parent
;
488 * Returns the entry for the greatest key less than the specified key; if
489 * no such entry exists (i.e., the least key in the Tree is greater than
490 * the specified key), returns {@code null}.
492 final TreeMapEntry
<K
,V
> getLowerEntry(K key
) {
493 TreeMapEntry
<K
,V
> p
= root
;
495 int cmp
= compare(key
, p
.key
);
502 if (p
.left
!= null) {
505 TreeMapEntry
<K
,V
> parent
= p
.parent
;
506 TreeMapEntry
<K
,V
> ch
= p
;
507 while (parent
!= null && ch
== parent
.left
) {
509 parent
= parent
.parent
;
519 * Associates the specified value with the specified key in this map.
520 * If the map previously contained a mapping for the key, the old
523 * @param key key with which the specified value is to be associated
524 * @param value value to be associated with the specified key
526 * @return the previous value associated with {@code key}, or
527 * {@code null} if there was no mapping for {@code key}.
528 * (A {@code null} return can also indicate that the map
529 * previously associated {@code null} with {@code key}.)
530 * @throws ClassCastException if the specified key cannot be compared
531 * with the keys currently in the map
532 * @throws NullPointerException if the specified key is null
533 * and this map uses natural ordering, or its comparator
534 * does not permit null keys
536 public V
put(K key
, V value
) {
537 TreeMapEntry
<K
,V
> t
= root
;
539 // We could just call compare(key, key) for its side effect of checking the type and
540 // nullness of the input key. However, several applications seem to have written comparators
541 // that only expect to be called on elements that aren't equal to each other (after
542 // making assumptions about the domain of the map). Clearly, such comparators are bogus
543 // because get() would never work, but TreeSets are frequently used for sorting a set
544 // of distinct elements.
546 // As a temporary work around, we perform the null & instanceof checks by hand so that
547 // we can guarantee that elements are never compared against themselves.
549 // compare(key, key);
551 // **** THIS CHANGE WILL BE REVERTED IN A FUTURE ANDROID RELEASE ****
552 if (comparator
!= null) {
554 comparator
.compare(key
, key
);
558 throw new NullPointerException("key == null");
559 } else if (!(key
instanceof Comparable
)) {
560 throw new ClassCastException(
561 "Cannot cast" + key
.getClass().getName() + " to Comparable.");
565 root
= new TreeMapEntry
<>(key
, value
, null);
571 TreeMapEntry
<K
,V
> parent
;
572 // split comparator and comparable paths
573 Comparator
<?
super K
> cpr
= comparator
;
577 cmp
= cpr
.compare(key
, t
.key
);
583 return t
.setValue(value
);
588 throw new NullPointerException();
589 @SuppressWarnings("unchecked")
590 Comparable
<?
super K
> k
= (Comparable
<?
super K
>) key
;
593 cmp
= k
.compareTo(t
.key
);
599 return t
.setValue(value
);
602 TreeMapEntry
<K
,V
> e
= new TreeMapEntry
<>(key
, value
, parent
);
607 fixAfterInsertion(e
);
614 * Removes the mapping for this key from this TreeMap if present.
616 * @param key key for which mapping should be removed
617 * @return the previous value associated with {@code key}, or
618 * {@code null} if there was no mapping for {@code key}.
619 * (A {@code null} return can also indicate that the map
620 * previously associated {@code null} with {@code key}.)
621 * @throws ClassCastException if the specified key cannot be compared
622 * with the keys currently in the map
623 * @throws NullPointerException if the specified key is null
624 * and this map uses natural ordering, or its comparator
625 * does not permit null keys
627 public V
remove(Object key
) {
628 TreeMapEntry
<K
,V
> p
= getEntry(key
);
632 V oldValue
= p
.value
;
638 * Removes all of the mappings from this map.
639 * The map will be empty after this call returns.
641 public void clear() {
648 * Returns a shallow copy of this {@code TreeMap} instance. (The keys and
649 * values themselves are not cloned.)
651 * @return a shallow copy of this map
653 public Object
clone() {
656 clone
= (TreeMap
<?
,?
>) super.clone();
657 } catch (CloneNotSupportedException e
) {
658 throw new InternalError(e
);
661 // Put clone into "virgin" state (except for comparator)
665 clone
.entrySet
= null;
666 clone
.navigableKeySet
= null;
667 clone
.descendingMap
= null;
669 // Initialize clone with our mappings
671 clone
.buildFromSorted(size
, entrySet().iterator(), null, null);
672 } catch (java
.io
.IOException cannotHappen
) {
673 } catch (ClassNotFoundException cannotHappen
) {
679 // NavigableMap API methods
684 public Map
.Entry
<K
,V
> firstEntry() {
685 return exportEntry(getFirstEntry());
691 public Map
.Entry
<K
,V
> lastEntry() {
692 return exportEntry(getLastEntry());
698 public Map
.Entry
<K
,V
> pollFirstEntry() {
699 TreeMapEntry
<K
,V
> p
= getFirstEntry();
700 Map
.Entry
<K
,V
> result
= exportEntry(p
);
709 public Map
.Entry
<K
,V
> pollLastEntry() {
710 TreeMapEntry
<K
,V
> p
= getLastEntry();
711 Map
.Entry
<K
,V
> result
= exportEntry(p
);
718 * @throws ClassCastException {@inheritDoc}
719 * @throws NullPointerException if the specified key is null
720 * and this map uses natural ordering, or its comparator
721 * does not permit null keys
724 public Map
.Entry
<K
,V
> lowerEntry(K key
) {
725 return exportEntry(getLowerEntry(key
));
729 * @throws ClassCastException {@inheritDoc}
730 * @throws NullPointerException if the specified key is null
731 * and this map uses natural ordering, or its comparator
732 * does not permit null keys
735 public K
lowerKey(K key
) {
736 return keyOrNull(getLowerEntry(key
));
740 * @throws ClassCastException {@inheritDoc}
741 * @throws NullPointerException if the specified key is null
742 * and this map uses natural ordering, or its comparator
743 * does not permit null keys
746 public Map
.Entry
<K
,V
> floorEntry(K key
) {
747 return exportEntry(getFloorEntry(key
));
751 * @throws ClassCastException {@inheritDoc}
752 * @throws NullPointerException if the specified key is null
753 * and this map uses natural ordering, or its comparator
754 * does not permit null keys
757 public K
floorKey(K key
) {
758 return keyOrNull(getFloorEntry(key
));
762 * @throws ClassCastException {@inheritDoc}
763 * @throws NullPointerException if the specified key is null
764 * and this map uses natural ordering, or its comparator
765 * does not permit null keys
768 public Map
.Entry
<K
,V
> ceilingEntry(K key
) {
769 return exportEntry(getCeilingEntry(key
));
773 * @throws ClassCastException {@inheritDoc}
774 * @throws NullPointerException if the specified key is null
775 * and this map uses natural ordering, or its comparator
776 * does not permit null keys
779 public K
ceilingKey(K key
) {
780 return keyOrNull(getCeilingEntry(key
));
784 * @throws ClassCastException {@inheritDoc}
785 * @throws NullPointerException if the specified key is null
786 * and this map uses natural ordering, or its comparator
787 * does not permit null keys
790 public Map
.Entry
<K
,V
> higherEntry(K key
) {
791 return exportEntry(getHigherEntry(key
));
795 * @throws ClassCastException {@inheritDoc}
796 * @throws NullPointerException if the specified key is null
797 * and this map uses natural ordering, or its comparator
798 * does not permit null keys
801 public K
higherKey(K key
) {
802 return keyOrNull(getHigherEntry(key
));
808 * Fields initialized to contain an instance of the entry set view
809 * the first time this view is requested. Views are stateless, so
810 * there's no reason to create more than one.
812 private transient EntrySet entrySet
= null;
813 private transient KeySet
<K
> navigableKeySet
= null;
814 private transient NavigableMap
<K
,V
> descendingMap
= null;
817 * Returns a {@link Set} view of the keys contained in this map.
819 * <p>The set's iterator returns the keys in ascending order.
820 * The set's spliterator is
821 * <em><a href="Spliterator.html#binding">late-binding</a></em>,
822 * <em>fail-fast</em>, and additionally reports {@link Spliterator#SORTED}
823 * and {@link Spliterator#ORDERED} with an encounter order that is ascending
824 * key order. The spliterator's comparator (see
825 * {@link java.util.Spliterator#getComparator()}) is {@code null} if
826 * the tree map's comparator (see {@link #comparator()}) is {@code null}.
827 * Otherwise, the spliterator's comparator is the same as or imposes the
828 * same total ordering as the tree map's comparator.
830 * <p>The set is backed by the map, so changes to the map are
831 * reflected in the set, and vice-versa. If the map is modified
832 * while an iteration over the set is in progress (except through
833 * the iterator's own {@code remove} operation), the results of
834 * the iteration are undefined. The set supports element removal,
835 * which removes the corresponding mapping from the map, via the
836 * {@code Iterator.remove}, {@code Set.remove},
837 * {@code removeAll}, {@code retainAll}, and {@code clear}
838 * operations. It does not support the {@code add} or {@code addAll}
841 public Set
<K
> keySet() {
842 return navigableKeySet();
848 public NavigableSet
<K
> navigableKeySet() {
849 KeySet
<K
> nks
= navigableKeySet
;
850 return (nks
!= null) ? nks
: (navigableKeySet
= new KeySet
<>(this));
856 public NavigableSet
<K
> descendingKeySet() {
857 return descendingMap().navigableKeySet();
861 * Returns a {@link Collection} view of the values contained in this map.
863 * <p>The collection's iterator returns the values in ascending order
864 * of the corresponding keys. The collection's spliterator is
865 * <em><a href="Spliterator.html#binding">late-binding</a></em>,
866 * <em>fail-fast</em>, and additionally reports {@link Spliterator#ORDERED}
867 * with an encounter order that is ascending order of the corresponding
870 * <p>The collection is backed by the map, so changes to the map are
871 * reflected in the collection, and vice-versa. If the map is
872 * modified while an iteration over the collection is in progress
873 * (except through the iterator's own {@code remove} operation),
874 * the results of the iteration are undefined. The collection
875 * supports element removal, which removes the corresponding
876 * mapping from the map, via the {@code Iterator.remove},
877 * {@code Collection.remove}, {@code removeAll},
878 * {@code retainAll} and {@code clear} operations. It does not
879 * support the {@code add} or {@code addAll} operations.
881 public Collection
<V
> values() {
882 Collection
<V
> vs
= values
;
883 return (vs
!= null) ? vs
: (values
= new Values());
887 * Returns a {@link Set} view of the mappings contained in this map.
889 * <p>The set's iterator returns the entries in ascending key order. The
890 * sets's spliterator is
891 * <em><a href="Spliterator.html#binding">late-binding</a></em>,
892 * <em>fail-fast</em>, and additionally reports {@link Spliterator#SORTED} and
893 * {@link Spliterator#ORDERED} with an encounter order that is ascending key
896 * <p>The set is backed by the map, so changes to the map are
897 * reflected in the set, and vice-versa. If the map is modified
898 * while an iteration over the set is in progress (except through
899 * the iterator's own {@code remove} operation, or through the
900 * {@code setValue} operation on a map entry returned by the
901 * iterator) the results of the iteration are undefined. The set
902 * supports element removal, which removes the corresponding
903 * mapping from the map, via the {@code Iterator.remove},
904 * {@code Set.remove}, {@code removeAll}, {@code retainAll} and
905 * {@code clear} operations. It does not support the
906 * {@code add} or {@code addAll} operations.
908 public Set
<Map
.Entry
<K
,V
>> entrySet() {
909 EntrySet es
= entrySet
;
910 return (es
!= null) ? es
: (entrySet
= new EntrySet());
916 public NavigableMap
<K
, V
> descendingMap() {
917 NavigableMap
<K
, V
> km
= descendingMap
;
918 return (km
!= null) ? km
:
919 (descendingMap
= new DescendingSubMap
<>(this,
925 * @throws ClassCastException {@inheritDoc}
926 * @throws NullPointerException if {@code fromKey} or {@code toKey} is
927 * null and this map uses natural ordering, or its comparator
928 * does not permit null keys
929 * @throws IllegalArgumentException {@inheritDoc}
932 public NavigableMap
<K
,V
> subMap(K fromKey
, boolean fromInclusive
,
933 K toKey
, boolean toInclusive
) {
934 return new AscendingSubMap
<>(this,
935 false, fromKey
, fromInclusive
,
936 false, toKey
, toInclusive
);
940 * @throws ClassCastException {@inheritDoc}
941 * @throws NullPointerException if {@code toKey} is null
942 * and this map uses natural ordering, or its comparator
943 * does not permit null keys
944 * @throws IllegalArgumentException {@inheritDoc}
947 public NavigableMap
<K
,V
> headMap(K toKey
, boolean inclusive
) {
948 return new AscendingSubMap
<>(this,
950 false, toKey
, inclusive
);
954 * @throws ClassCastException {@inheritDoc}
955 * @throws NullPointerException if {@code fromKey} is null
956 * and this map uses natural ordering, or its comparator
957 * does not permit null keys
958 * @throws IllegalArgumentException {@inheritDoc}
961 public NavigableMap
<K
,V
> tailMap(K fromKey
, boolean inclusive
) {
962 return new AscendingSubMap
<>(this,
963 false, fromKey
, inclusive
,
968 * @throws ClassCastException {@inheritDoc}
969 * @throws NullPointerException if {@code fromKey} or {@code toKey} is
970 * null and this map uses natural ordering, or its comparator
971 * does not permit null keys
972 * @throws IllegalArgumentException {@inheritDoc}
974 public SortedMap
<K
,V
> subMap(K fromKey
, K toKey
) {
975 return subMap(fromKey
, true, toKey
, false);
979 * @throws ClassCastException {@inheritDoc}
980 * @throws NullPointerException if {@code toKey} is null
981 * and this map uses natural ordering, or its comparator
982 * does not permit null keys
983 * @throws IllegalArgumentException {@inheritDoc}
985 public SortedMap
<K
,V
> headMap(K toKey
) {
986 return headMap(toKey
, false);
990 * @throws ClassCastException {@inheritDoc}
991 * @throws NullPointerException if {@code fromKey} is null
992 * and this map uses natural ordering, or its comparator
993 * does not permit null keys
994 * @throws IllegalArgumentException {@inheritDoc}
996 public SortedMap
<K
,V
> tailMap(K fromKey
) {
997 return tailMap(fromKey
, true);
1001 public boolean replace(K key
, V oldValue
, V newValue
) {
1002 TreeMapEntry
<K
,V
> p
= getEntry(key
);
1003 if (p
!=null && Objects
.equals(oldValue
, p
.value
)) {
1011 public V
replace(K key
, V value
) {
1012 TreeMapEntry
<K
,V
> p
= getEntry(key
);
1014 V oldValue
= p
.value
;
1022 public void forEach(BiConsumer
<?
super K
, ?
super V
> action
) {
1023 Objects
.requireNonNull(action
);
1024 int expectedModCount
= modCount
;
1025 for (TreeMapEntry
<K
, V
> e
= getFirstEntry(); e
!= null; e
= successor(e
)) {
1026 action
.accept(e
.key
, e
.value
);
1028 if (expectedModCount
!= modCount
) {
1029 throw new ConcurrentModificationException();
1035 public void replaceAll(BiFunction
<?
super K
, ?
super V
, ?
extends V
> function
) {
1036 Objects
.requireNonNull(function
);
1037 int expectedModCount
= modCount
;
1039 for (TreeMapEntry
<K
, V
> e
= getFirstEntry(); e
!= null; e
= successor(e
)) {
1040 e
.value
= function
.apply(e
.key
, e
.value
);
1042 if (expectedModCount
!= modCount
) {
1043 throw new ConcurrentModificationException();
1048 // View class support
1050 class Values
extends AbstractCollection
<V
> {
1051 public Iterator
<V
> iterator() {
1052 return new ValueIterator(getFirstEntry());
1056 return TreeMap
.this.size();
1059 public boolean contains(Object o
) {
1060 return TreeMap
.this.containsValue(o
);
1063 public boolean remove(Object o
) {
1064 for (TreeMapEntry
<K
,V
> e
= getFirstEntry(); e
!= null; e
= successor(e
)) {
1065 if (valEquals(e
.getValue(), o
)) {
1073 public void clear() {
1074 TreeMap
.this.clear();
1077 public Spliterator
<V
> spliterator() {
1078 return new ValueSpliterator
<K
,V
>(TreeMap
.this, null, null, 0, -1, 0);
1082 class EntrySet
extends AbstractSet
<Map
.Entry
<K
,V
>> {
1083 public Iterator
<Map
.Entry
<K
,V
>> iterator() {
1084 return new EntryIterator(getFirstEntry());
1087 public boolean contains(Object o
) {
1088 if (!(o
instanceof Map
.Entry
))
1090 Map
.Entry
<K
,V
> entry
= (Map
.Entry
<K
,V
>) o
;
1091 V value
= entry
.getValue();
1092 TreeMapEntry
<K
,V
> p
= getEntry(entry
.getKey());
1093 return p
!= null && valEquals(p
.getValue(), value
);
1096 public boolean remove(Object o
) {
1097 if (!(o
instanceof Map
.Entry
))
1099 Map
.Entry
<K
,V
> entry
= (Map
.Entry
<K
,V
>) o
;
1100 V value
= entry
.getValue();
1101 TreeMapEntry
<K
,V
> p
= getEntry(entry
.getKey());
1102 if (p
!= null && valEquals(p
.getValue(), value
)) {
1110 return TreeMap
.this.size();
1113 public void clear() {
1114 TreeMap
.this.clear();
1117 public Spliterator
<Map
.Entry
<K
,V
>> spliterator() {
1118 return new EntrySpliterator
<K
,V
>(TreeMap
.this, null, null, 0, -1, 0);
1123 * Unlike Values and EntrySet, the KeySet class is static,
1124 * delegating to a NavigableMap to allow use by SubMaps, which
1125 * outweighs the ugliness of needing type-tests for the following
1126 * Iterator methods that are defined appropriately in main versus
1130 Iterator
<K
> keyIterator() {
1131 return new KeyIterator(getFirstEntry());
1134 Iterator
<K
> descendingKeyIterator() {
1135 return new DescendingKeyIterator(getLastEntry());
1138 static final class KeySet
<E
> extends AbstractSet
<E
> implements NavigableSet
<E
> {
1139 private final NavigableMap
<E
, ?
> m
;
1140 KeySet(NavigableMap
<E
,?
> map
) { m
= map
; }
1142 public Iterator
<E
> iterator() {
1143 if (m
instanceof TreeMap
)
1144 return ((TreeMap
<E
,?
>)m
).keyIterator();
1146 return ((TreeMap
.NavigableSubMap
<E
,?
>)m
).keyIterator();
1149 public Iterator
<E
> descendingIterator() {
1150 if (m
instanceof TreeMap
)
1151 return ((TreeMap
<E
,?
>)m
).descendingKeyIterator();
1153 return ((TreeMap
.NavigableSubMap
<E
,?
>)m
).descendingKeyIterator();
1156 public int size() { return m
.size(); }
1157 public boolean isEmpty() { return m
.isEmpty(); }
1158 public boolean contains(Object o
) { return m
.containsKey(o
); }
1159 public void clear() { m
.clear(); }
1160 public E
lower(E e
) { return m
.lowerKey(e
); }
1161 public E
floor(E e
) { return m
.floorKey(e
); }
1162 public E
ceiling(E e
) { return m
.ceilingKey(e
); }
1163 public E
higher(E e
) { return m
.higherKey(e
); }
1164 public E
first() { return m
.firstKey(); }
1165 public E
last() { return m
.lastKey(); }
1166 public Comparator
<?
super E
> comparator() { return m
.comparator(); }
1167 public E
pollFirst() {
1168 Map
.Entry
<E
,?
> e
= m
.pollFirstEntry();
1169 return (e
== null) ?
null : e
.getKey();
1171 public E
pollLast() {
1172 Map
.Entry
<E
,?
> e
= m
.pollLastEntry();
1173 return (e
== null) ?
null : e
.getKey();
1175 public boolean remove(Object o
) {
1176 int oldSize
= size();
1178 return size() != oldSize
;
1180 public NavigableSet
<E
> subSet(E fromElement
, boolean fromInclusive
,
1181 E toElement
, boolean toInclusive
) {
1182 return new KeySet
<>(m
.subMap(fromElement
, fromInclusive
,
1183 toElement
, toInclusive
));
1185 public NavigableSet
<E
> headSet(E toElement
, boolean inclusive
) {
1186 return new KeySet
<>(m
.headMap(toElement
, inclusive
));
1188 public NavigableSet
<E
> tailSet(E fromElement
, boolean inclusive
) {
1189 return new KeySet
<>(m
.tailMap(fromElement
, inclusive
));
1191 public SortedSet
<E
> subSet(E fromElement
, E toElement
) {
1192 return subSet(fromElement
, true, toElement
, false);
1194 public SortedSet
<E
> headSet(E toElement
) {
1195 return headSet(toElement
, false);
1197 public SortedSet
<E
> tailSet(E fromElement
) {
1198 return tailSet(fromElement
, true);
1200 public NavigableSet
<E
> descendingSet() {
1201 return new KeySet
<>(m
.descendingMap());
1204 public Spliterator
<E
> spliterator() {
1205 return keySpliteratorFor(m
);
1210 * Base class for TreeMap Iterators
1212 abstract class PrivateEntryIterator
<T
> implements Iterator
<T
> {
1213 TreeMapEntry
<K
,V
> next
;
1214 TreeMapEntry
<K
,V
> lastReturned
;
1215 int expectedModCount
;
1217 PrivateEntryIterator(TreeMapEntry
<K
,V
> first
) {
1218 expectedModCount
= modCount
;
1219 lastReturned
= null;
1223 public final boolean hasNext() {
1224 return next
!= null;
1227 final TreeMapEntry
<K
,V
> nextEntry() {
1228 TreeMapEntry
<K
,V
> e
= next
;
1230 throw new NoSuchElementException();
1231 if (modCount
!= expectedModCount
)
1232 throw new ConcurrentModificationException();
1233 next
= successor(e
);
1238 final TreeMapEntry
<K
,V
> prevEntry() {
1239 TreeMapEntry
<K
,V
> e
= next
;
1241 throw new NoSuchElementException();
1242 if (modCount
!= expectedModCount
)
1243 throw new ConcurrentModificationException();
1244 next
= predecessor(e
);
1249 public void remove() {
1250 if (lastReturned
== null)
1251 throw new IllegalStateException();
1252 if (modCount
!= expectedModCount
)
1253 throw new ConcurrentModificationException();
1254 // deleted entries are replaced by their successors
1255 if (lastReturned
.left
!= null && lastReturned
.right
!= null)
1256 next
= lastReturned
;
1257 deleteEntry(lastReturned
);
1258 expectedModCount
= modCount
;
1259 lastReturned
= null;
1263 final class EntryIterator
extends PrivateEntryIterator
<Map
.Entry
<K
,V
>> {
1264 EntryIterator(TreeMapEntry
<K
,V
> first
) {
1267 public Map
.Entry
<K
,V
> next() {
1272 final class ValueIterator
extends PrivateEntryIterator
<V
> {
1273 ValueIterator(TreeMapEntry
<K
,V
> first
) {
1277 return nextEntry().value
;
1281 final class KeyIterator
extends PrivateEntryIterator
<K
> {
1282 KeyIterator(TreeMapEntry
<K
,V
> first
) {
1286 return nextEntry().key
;
1290 final class DescendingKeyIterator
extends PrivateEntryIterator
<K
> {
1291 DescendingKeyIterator(TreeMapEntry
<K
,V
> first
) {
1295 return prevEntry().key
;
1297 public void remove() {
1298 if (lastReturned
== null)
1299 throw new IllegalStateException();
1300 if (modCount
!= expectedModCount
)
1301 throw new ConcurrentModificationException();
1302 deleteEntry(lastReturned
);
1303 lastReturned
= null;
1304 expectedModCount
= modCount
;
1311 * Compares two keys using the correct comparison method for this TreeMap.
1313 @SuppressWarnings("unchecked")
1314 final int compare(Object k1
, Object k2
) {
1315 return comparator
==null ?
((Comparable
<?
super K
>)k1
).compareTo((K
)k2
)
1316 : comparator
.compare((K
)k1
, (K
)k2
);
1320 * Test two values for equality. Differs from o1.equals(o2) only in
1321 * that it copes with {@code null} o1 properly.
1323 static final boolean valEquals(Object o1
, Object o2
) {
1324 return (o1
==null ? o2
==null : o1
.equals(o2
));
1328 * Return SimpleImmutableEntry for entry, or null if null
1330 static <K
,V
> Map
.Entry
<K
,V
> exportEntry(TreeMapEntry
<K
,V
> e
) {
1331 return (e
== null) ?
null :
1332 new AbstractMap
.SimpleImmutableEntry
<>(e
);
1336 * Return key for entry, or null if null
1338 static <K
,V
> K
keyOrNull(TreeMapEntry
<K
,V
> e
) {
1339 return (e
== null) ?
null : e
.key
;
1343 * Returns the key corresponding to the specified Entry.
1344 * @throws NoSuchElementException if the Entry is null
1346 static <K
> K
key(TreeMapEntry
<K
,?
> e
) {
1348 throw new NoSuchElementException();
1356 * Dummy value serving as unmatchable fence key for unbounded
1359 private static final Object UNBOUNDED
= new Object();
1364 abstract static class NavigableSubMap
<K
,V
> extends AbstractMap
<K
,V
>
1365 implements NavigableMap
<K
,V
>, java
.io
.Serializable
{
1366 // Android-changed: Explicitly add a serialVersionUID so that we're serialization
1367 // compatible with the Java-7 version of this class. Several new methods were added
1368 // in Java-8 but none of them have any bearing on the serialized format of the class
1369 // or require any additional state to be preserved.
1370 private static final long serialVersionUID
= 2765629423043303731L;
1375 final TreeMap
<K
,V
> m
;
1378 * Endpoints are represented as triples (fromStart, lo,
1379 * loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1380 * true, then the low (absolute) bound is the start of the
1381 * backing map, and the other values are ignored. Otherwise,
1382 * if loInclusive is true, lo is the inclusive bound, else lo
1383 * is the exclusive bound. Similarly for the upper bound.
1386 final boolean fromStart
, toEnd
;
1387 final boolean loInclusive
, hiInclusive
;
1389 NavigableSubMap(TreeMap
<K
,V
> m
,
1390 boolean fromStart
, K lo
, boolean loInclusive
,
1391 boolean toEnd
, K hi
, boolean hiInclusive
) {
1392 if (!fromStart
&& !toEnd
) {
1393 if (m
.compare(lo
, hi
) > 0)
1394 throw new IllegalArgumentException("fromKey > toKey");
1396 if (!fromStart
) // type check
1403 this.fromStart
= fromStart
;
1405 this.loInclusive
= loInclusive
;
1408 this.hiInclusive
= hiInclusive
;
1411 // internal utilities
1413 final boolean tooLow(Object key
) {
1415 int c
= m
.compare(key
, lo
);
1416 if (c
< 0 || (c
== 0 && !loInclusive
))
1422 final boolean tooHigh(Object key
) {
1424 int c
= m
.compare(key
, hi
);
1425 if (c
> 0 || (c
== 0 && !hiInclusive
))
1431 final boolean inRange(Object key
) {
1432 return !tooLow(key
) && !tooHigh(key
);
1435 final boolean inClosedRange(Object key
) {
1436 return (fromStart
|| m
.compare(key
, lo
) >= 0)
1437 && (toEnd
|| m
.compare(hi
, key
) >= 0);
1440 final boolean inRange(Object key
, boolean inclusive
) {
1441 return inclusive ?
inRange(key
) : inClosedRange(key
);
1445 * Absolute versions of relation operations.
1446 * Subclasses map to these using like-named "sub"
1447 * versions that invert senses for descending maps
1450 final TreeMapEntry
<K
,V
> absLowest() {
1451 TreeMapEntry
<K
,V
> e
=
1452 (fromStart ? m
.getFirstEntry() :
1453 (loInclusive ? m
.getCeilingEntry(lo
) :
1454 m
.getHigherEntry(lo
)));
1455 return (e
== null || tooHigh(e
.key
)) ?
null : e
;
1458 final TreeMapEntry
<K
,V
> absHighest() {
1459 TreeMapEntry
<K
,V
> e
=
1460 (toEnd ? m
.getLastEntry() :
1461 (hiInclusive ? m
.getFloorEntry(hi
) :
1462 m
.getLowerEntry(hi
)));
1463 return (e
== null || tooLow(e
.key
)) ?
null : e
;
1466 final TreeMapEntry
<K
,V
> absCeiling(K key
) {
1469 TreeMapEntry
<K
,V
> e
= m
.getCeilingEntry(key
);
1470 return (e
== null || tooHigh(e
.key
)) ?
null : e
;
1473 final TreeMapEntry
<K
,V
> absHigher(K key
) {
1476 TreeMapEntry
<K
,V
> e
= m
.getHigherEntry(key
);
1477 return (e
== null || tooHigh(e
.key
)) ?
null : e
;
1480 final TreeMapEntry
<K
,V
> absFloor(K key
) {
1482 return absHighest();
1483 TreeMapEntry
<K
,V
> e
= m
.getFloorEntry(key
);
1484 return (e
== null || tooLow(e
.key
)) ?
null : e
;
1487 final TreeMapEntry
<K
,V
> absLower(K key
) {
1489 return absHighest();
1490 TreeMapEntry
<K
,V
> e
= m
.getLowerEntry(key
);
1491 return (e
== null || tooLow(e
.key
)) ?
null : e
;
1494 /** Returns the absolute high fence for ascending traversal */
1495 final TreeMapEntry
<K
,V
> absHighFence() {
1496 return (toEnd ?
null : (hiInclusive ?
1497 m
.getHigherEntry(hi
) :
1498 m
.getCeilingEntry(hi
)));
1501 /** Return the absolute low fence for descending traversal */
1502 final TreeMapEntry
<K
,V
> absLowFence() {
1503 return (fromStart ?
null : (loInclusive ?
1504 m
.getLowerEntry(lo
) :
1505 m
.getFloorEntry(lo
)));
1508 // Abstract methods defined in ascending vs descending classes
1509 // These relay to the appropriate absolute versions
1511 abstract TreeMapEntry
<K
,V
> subLowest();
1512 abstract TreeMapEntry
<K
,V
> subHighest();
1513 abstract TreeMapEntry
<K
,V
> subCeiling(K key
);
1514 abstract TreeMapEntry
<K
,V
> subHigher(K key
);
1515 abstract TreeMapEntry
<K
,V
> subFloor(K key
);
1516 abstract TreeMapEntry
<K
,V
> subLower(K key
);
1518 /** Returns ascending iterator from the perspective of this submap */
1519 abstract Iterator
<K
> keyIterator();
1521 abstract Spliterator
<K
> keySpliterator();
1523 /** Returns descending iterator from the perspective of this submap */
1524 abstract Iterator
<K
> descendingKeyIterator();
1528 public boolean isEmpty() {
1529 return (fromStart
&& toEnd
) ? m
.isEmpty() : entrySet().isEmpty();
1533 return (fromStart
&& toEnd
) ? m
.size() : entrySet().size();
1536 public final boolean containsKey(Object key
) {
1537 return inRange(key
) && m
.containsKey(key
);
1540 public final V
put(K key
, V value
) {
1542 throw new IllegalArgumentException("key out of range");
1543 return m
.put(key
, value
);
1546 public final V
get(Object key
) {
1547 return !inRange(key
) ?
null : m
.get(key
);
1550 public final V
remove(Object key
) {
1551 return !inRange(key
) ?
null : m
.remove(key
);
1554 public final Map
.Entry
<K
,V
> ceilingEntry(K key
) {
1555 return exportEntry(subCeiling(key
));
1558 public final K
ceilingKey(K key
) {
1559 return keyOrNull(subCeiling(key
));
1562 public final Map
.Entry
<K
,V
> higherEntry(K key
) {
1563 return exportEntry(subHigher(key
));
1566 public final K
higherKey(K key
) {
1567 return keyOrNull(subHigher(key
));
1570 public final Map
.Entry
<K
,V
> floorEntry(K key
) {
1571 return exportEntry(subFloor(key
));
1574 public final K
floorKey(K key
) {
1575 return keyOrNull(subFloor(key
));
1578 public final Map
.Entry
<K
,V
> lowerEntry(K key
) {
1579 return exportEntry(subLower(key
));
1582 public final K
lowerKey(K key
) {
1583 return keyOrNull(subLower(key
));
1586 public final K
firstKey() {
1587 return key(subLowest());
1590 public final K
lastKey() {
1591 return key(subHighest());
1594 public final Map
.Entry
<K
,V
> firstEntry() {
1595 return exportEntry(subLowest());
1598 public final Map
.Entry
<K
,V
> lastEntry() {
1599 return exportEntry(subHighest());
1602 public final Map
.Entry
<K
,V
> pollFirstEntry() {
1603 TreeMapEntry
<K
,V
> e
= subLowest();
1604 Map
.Entry
<K
,V
> result
= exportEntry(e
);
1610 public final Map
.Entry
<K
,V
> pollLastEntry() {
1611 TreeMapEntry
<K
,V
> e
= subHighest();
1612 Map
.Entry
<K
,V
> result
= exportEntry(e
);
1619 transient NavigableMap
<K
,V
> descendingMapView
= null;
1620 transient EntrySetView entrySetView
= null;
1621 transient KeySet
<K
> navigableKeySetView
= null;
1623 public final NavigableSet
<K
> navigableKeySet() {
1624 KeySet
<K
> nksv
= navigableKeySetView
;
1625 return (nksv
!= null) ? nksv
:
1626 (navigableKeySetView
= new TreeMap
.KeySet
<>(this));
1629 public final Set
<K
> keySet() {
1630 return navigableKeySet();
1633 public NavigableSet
<K
> descendingKeySet() {
1634 return descendingMap().navigableKeySet();
1637 public final SortedMap
<K
,V
> subMap(K fromKey
, K toKey
) {
1638 return subMap(fromKey
, true, toKey
, false);
1641 public final SortedMap
<K
,V
> headMap(K toKey
) {
1642 return headMap(toKey
, false);
1645 public final SortedMap
<K
,V
> tailMap(K fromKey
) {
1646 return tailMap(fromKey
, true);
1651 abstract class EntrySetView
extends AbstractSet
<Map
.Entry
<K
,V
>> {
1652 private transient int size
= -1, sizeModCount
;
1655 if (fromStart
&& toEnd
)
1657 if (size
== -1 || sizeModCount
!= m
.modCount
) {
1658 sizeModCount
= m
.modCount
;
1660 Iterator
<?
> i
= iterator();
1661 while (i
.hasNext()) {
1669 public boolean isEmpty() {
1670 TreeMapEntry
<K
,V
> n
= absLowest();
1671 return n
== null || tooHigh(n
.key
);
1674 public boolean contains(Object o
) {
1675 if (!(o
instanceof Map
.Entry
))
1677 Map
.Entry
<?
,?
> entry
= (Map
.Entry
<?
,?
>) o
;
1678 Object key
= entry
.getKey();
1681 TreeMapEntry
<?
, ?
> node
= m
.getEntry(key
);
1682 return node
!= null &&
1683 valEquals(node
.getValue(), entry
.getValue());
1686 public boolean remove(Object o
) {
1687 if (!(o
instanceof Map
.Entry
))
1689 Map
.Entry
<?
,?
> entry
= (Map
.Entry
<?
,?
>) o
;
1690 Object key
= entry
.getKey();
1693 TreeMapEntry
<K
,V
> node
= m
.getEntry(key
);
1694 if (node
!=null && valEquals(node
.getValue(),
1695 entry
.getValue())) {
1696 m
.deleteEntry(node
);
1704 * Iterators for SubMaps
1706 abstract class SubMapIterator
<T
> implements Iterator
<T
> {
1707 TreeMapEntry
<K
,V
> lastReturned
;
1708 TreeMapEntry
<K
,V
> next
;
1709 final Object fenceKey
;
1710 int expectedModCount
;
1712 SubMapIterator(TreeMapEntry
<K
,V
> first
,
1713 TreeMapEntry
<K
,V
> fence
) {
1714 expectedModCount
= m
.modCount
;
1715 lastReturned
= null;
1717 fenceKey
= fence
== null ? UNBOUNDED
: fence
.key
;
1720 public final boolean hasNext() {
1721 return next
!= null && next
.key
!= fenceKey
;
1724 final TreeMapEntry
<K
,V
> nextEntry() {
1725 TreeMapEntry
<K
,V
> e
= next
;
1726 if (e
== null || e
.key
== fenceKey
)
1727 throw new NoSuchElementException();
1728 if (m
.modCount
!= expectedModCount
)
1729 throw new ConcurrentModificationException();
1730 next
= successor(e
);
1735 final TreeMapEntry
<K
,V
> prevEntry() {
1736 TreeMapEntry
<K
,V
> e
= next
;
1737 if (e
== null || e
.key
== fenceKey
)
1738 throw new NoSuchElementException();
1739 if (m
.modCount
!= expectedModCount
)
1740 throw new ConcurrentModificationException();
1741 next
= predecessor(e
);
1746 final void removeAscending() {
1747 if (lastReturned
== null)
1748 throw new IllegalStateException();
1749 if (m
.modCount
!= expectedModCount
)
1750 throw new ConcurrentModificationException();
1751 // deleted entries are replaced by their successors
1752 if (lastReturned
.left
!= null && lastReturned
.right
!= null)
1753 next
= lastReturned
;
1754 m
.deleteEntry(lastReturned
);
1755 lastReturned
= null;
1756 expectedModCount
= m
.modCount
;
1759 final void removeDescending() {
1760 if (lastReturned
== null)
1761 throw new IllegalStateException();
1762 if (m
.modCount
!= expectedModCount
)
1763 throw new ConcurrentModificationException();
1764 m
.deleteEntry(lastReturned
);
1765 lastReturned
= null;
1766 expectedModCount
= m
.modCount
;
1771 final class SubMapEntryIterator
extends SubMapIterator
<Map
.Entry
<K
,V
>> {
1772 SubMapEntryIterator(TreeMapEntry
<K
,V
> first
,
1773 TreeMapEntry
<K
,V
> fence
) {
1774 super(first
, fence
);
1776 public Map
.Entry
<K
,V
> next() {
1779 public void remove() {
1784 final class DescendingSubMapEntryIterator
extends SubMapIterator
<Map
.Entry
<K
,V
>> {
1785 DescendingSubMapEntryIterator(TreeMapEntry
<K
,V
> last
,
1786 TreeMapEntry
<K
,V
> fence
) {
1790 public Map
.Entry
<K
,V
> next() {
1793 public void remove() {
1798 // Implement minimal Spliterator as KeySpliterator backup
1799 final class SubMapKeyIterator
extends SubMapIterator
<K
>
1800 implements Spliterator
<K
> {
1801 SubMapKeyIterator(TreeMapEntry
<K
,V
> first
,
1802 TreeMapEntry
<K
,V
> fence
) {
1803 super(first
, fence
);
1806 return nextEntry().key
;
1808 public void remove() {
1811 public Spliterator
<K
> trySplit() {
1814 public void forEachRemaining(Consumer
<?
super K
> action
) {
1816 action
.accept(next());
1818 public boolean tryAdvance(Consumer
<?
super K
> action
) {
1820 action
.accept(next());
1825 public long estimateSize() {
1826 return Long
.MAX_VALUE
;
1828 public int characteristics() {
1829 return Spliterator
.DISTINCT
| Spliterator
.ORDERED
|
1832 public final Comparator
<?
super K
> getComparator() {
1833 return NavigableSubMap
.this.comparator();
1837 final class DescendingSubMapKeyIterator
extends SubMapIterator
<K
>
1838 implements Spliterator
<K
> {
1839 DescendingSubMapKeyIterator(TreeMapEntry
<K
,V
> last
,
1840 TreeMapEntry
<K
,V
> fence
) {
1844 return prevEntry().key
;
1846 public void remove() {
1849 public Spliterator
<K
> trySplit() {
1852 public void forEachRemaining(Consumer
<?
super K
> action
) {
1854 action
.accept(next());
1856 public boolean tryAdvance(Consumer
<?
super K
> action
) {
1858 action
.accept(next());
1863 public long estimateSize() {
1864 return Long
.MAX_VALUE
;
1866 public int characteristics() {
1867 return Spliterator
.DISTINCT
| Spliterator
.ORDERED
;
1875 static final class AscendingSubMap
<K
,V
> extends NavigableSubMap
<K
,V
> {
1876 private static final long serialVersionUID
= 912986545866124060L;
1878 AscendingSubMap(TreeMap
<K
,V
> m
,
1879 boolean fromStart
, K lo
, boolean loInclusive
,
1880 boolean toEnd
, K hi
, boolean hiInclusive
) {
1881 super(m
, fromStart
, lo
, loInclusive
, toEnd
, hi
, hiInclusive
);
1884 public Comparator
<?
super K
> comparator() {
1885 return m
.comparator();
1888 public NavigableMap
<K
,V
> subMap(K fromKey
, boolean fromInclusive
,
1889 K toKey
, boolean toInclusive
) {
1890 if (!inRange(fromKey
, fromInclusive
))
1891 throw new IllegalArgumentException("fromKey out of range");
1892 if (!inRange(toKey
, toInclusive
))
1893 throw new IllegalArgumentException("toKey out of range");
1894 return new AscendingSubMap
<>(m
,
1895 false, fromKey
, fromInclusive
,
1896 false, toKey
, toInclusive
);
1899 public NavigableMap
<K
,V
> headMap(K toKey
, boolean inclusive
) {
1900 /* ----- BEGIN android -----
1902 if (!inRange(toKey, inclusive)) */
1903 if (!inRange(toKey
) && !(!toEnd
&& m
.compare(toKey
, hi
) == 0 &&
1904 !hiInclusive
&& !inclusive
))
1905 // ----- END android -----
1906 throw new IllegalArgumentException("toKey out of range");
1907 return new AscendingSubMap
<>(m
,
1908 fromStart
, lo
, loInclusive
,
1909 false, toKey
, inclusive
);
1912 public NavigableMap
<K
,V
> tailMap(K fromKey
, boolean inclusive
) {
1913 /* ----- BEGIN android -----
1915 if (!inRange(fromKey, inclusive)) */
1916 if (!inRange(fromKey
) && !(!fromStart
&& m
.compare(fromKey
, lo
) == 0 &&
1917 !loInclusive
&& !inclusive
))
1918 // ----- END android -----
1919 throw new IllegalArgumentException("fromKey out of range");
1920 return new AscendingSubMap
<>(m
,
1921 false, fromKey
, inclusive
,
1922 toEnd
, hi
, hiInclusive
);
1925 public NavigableMap
<K
,V
> descendingMap() {
1926 NavigableMap
<K
,V
> mv
= descendingMapView
;
1927 return (mv
!= null) ? mv
:
1928 (descendingMapView
=
1929 new DescendingSubMap
<>(m
,
1930 fromStart
, lo
, loInclusive
,
1931 toEnd
, hi
, hiInclusive
));
1934 Iterator
<K
> keyIterator() {
1935 return new SubMapKeyIterator(absLowest(), absHighFence());
1938 Spliterator
<K
> keySpliterator() {
1939 return new SubMapKeyIterator(absLowest(), absHighFence());
1942 Iterator
<K
> descendingKeyIterator() {
1943 return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1946 final class AscendingEntrySetView
extends EntrySetView
{
1947 public Iterator
<Map
.Entry
<K
,V
>> iterator() {
1948 return new SubMapEntryIterator(absLowest(), absHighFence());
1952 public Set
<Map
.Entry
<K
,V
>> entrySet() {
1953 EntrySetView es
= entrySetView
;
1954 return (es
!= null) ? es
: new AscendingEntrySetView();
1957 TreeMapEntry
<K
,V
> subLowest() { return absLowest(); }
1958 TreeMapEntry
<K
,V
> subHighest() { return absHighest(); }
1959 TreeMapEntry
<K
,V
> subCeiling(K key
) { return absCeiling(key
); }
1960 TreeMapEntry
<K
,V
> subHigher(K key
) { return absHigher(key
); }
1961 TreeMapEntry
<K
,V
> subFloor(K key
) { return absFloor(key
); }
1962 TreeMapEntry
<K
,V
> subLower(K key
) { return absLower(key
); }
1968 static final class DescendingSubMap
<K
,V
> extends NavigableSubMap
<K
,V
> {
1969 private static final long serialVersionUID
= 912986545866120460L;
1970 DescendingSubMap(TreeMap
<K
,V
> m
,
1971 boolean fromStart
, K lo
, boolean loInclusive
,
1972 boolean toEnd
, K hi
, boolean hiInclusive
) {
1973 super(m
, fromStart
, lo
, loInclusive
, toEnd
, hi
, hiInclusive
);
1976 private final Comparator
<?
super K
> reverseComparator
=
1977 Collections
.reverseOrder(m
.comparator
);
1979 public Comparator
<?
super K
> comparator() {
1980 return reverseComparator
;
1983 public NavigableMap
<K
,V
> subMap(K fromKey
, boolean fromInclusive
,
1984 K toKey
, boolean toInclusive
) {
1985 if (!inRange(fromKey
, fromInclusive
))
1986 throw new IllegalArgumentException("fromKey out of range");
1987 if (!inRange(toKey
, toInclusive
))
1988 throw new IllegalArgumentException("toKey out of range");
1989 return new DescendingSubMap
<>(m
,
1990 false, toKey
, toInclusive
,
1991 false, fromKey
, fromInclusive
);
1994 public NavigableMap
<K
,V
> headMap(K toKey
, boolean inclusive
) {
1995 /* ----- BEGIN android -----
1997 if (!inRange(toKey, inclusive)) */
1998 if (!inRange(toKey
) && !(!fromStart
&& m
.compare(toKey
, lo
) == 0 &&
1999 !loInclusive
&& !inclusive
))
2000 // ----- END android -----
2001 throw new IllegalArgumentException("toKey out of range");
2002 return new DescendingSubMap
<>(m
,
2003 false, toKey
, inclusive
,
2004 toEnd
, hi
, hiInclusive
);
2007 public NavigableMap
<K
,V
> tailMap(K fromKey
, boolean inclusive
) {
2008 /* ----- BEGIN android -----
2010 if (!inRange(fromKey, inclusive)) */
2011 if (!inRange(fromKey
) && !(!toEnd
&& m
.compare(fromKey
, hi
) == 0 &&
2012 !hiInclusive
&& !inclusive
))
2013 // ----- END android -----
2014 throw new IllegalArgumentException("fromKey out of range");
2015 return new DescendingSubMap
<>(m
,
2016 fromStart
, lo
, loInclusive
,
2017 false, fromKey
, inclusive
);
2020 public NavigableMap
<K
,V
> descendingMap() {
2021 NavigableMap
<K
,V
> mv
= descendingMapView
;
2022 return (mv
!= null) ? mv
:
2023 (descendingMapView
=
2024 new AscendingSubMap
<>(m
,
2025 fromStart
, lo
, loInclusive
,
2026 toEnd
, hi
, hiInclusive
));
2029 Iterator
<K
> keyIterator() {
2030 return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
2033 Spliterator
<K
> keySpliterator() {
2034 return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
2037 Iterator
<K
> descendingKeyIterator() {
2038 return new SubMapKeyIterator(absLowest(), absHighFence());
2041 final class DescendingEntrySetView
extends EntrySetView
{
2042 public Iterator
<Map
.Entry
<K
,V
>> iterator() {
2043 return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
2047 public Set
<Map
.Entry
<K
,V
>> entrySet() {
2048 EntrySetView es
= entrySetView
;
2049 return (es
!= null) ? es
: (entrySetView
= new DescendingEntrySetView());
2052 TreeMapEntry
<K
,V
> subLowest() { return absHighest(); }
2053 TreeMapEntry
<K
,V
> subHighest() { return absLowest(); }
2054 TreeMapEntry
<K
,V
> subCeiling(K key
) { return absFloor(key
); }
2055 TreeMapEntry
<K
,V
> subHigher(K key
) { return absLower(key
); }
2056 TreeMapEntry
<K
,V
> subFloor(K key
) { return absCeiling(key
); }
2057 TreeMapEntry
<K
,V
> subLower(K key
) { return absHigher(key
); }
2061 * This class exists solely for the sake of serialization
2062 * compatibility with previous releases of TreeMap that did not
2063 * support NavigableMap. It translates an old-version SubMap into
2064 * a new-version AscendingSubMap. This class is never otherwise
2069 private class SubMap
extends AbstractMap
<K
,V
>
2070 implements SortedMap
<K
,V
>, java
.io
.Serializable
{
2071 private static final long serialVersionUID
= -6520786458950516097L;
2072 private boolean fromStart
= false, toEnd
= false;
2073 private K fromKey
, toKey
;
2074 private Object
readResolve() {
2075 return new AscendingSubMap
<>(TreeMap
.this,
2076 fromStart
, fromKey
, true,
2077 toEnd
, toKey
, false);
2079 public Set
<Map
.Entry
<K
,V
>> entrySet() { throw new InternalError(); }
2080 public K
lastKey() { throw new InternalError(); }
2081 public K
firstKey() { throw new InternalError(); }
2082 public SortedMap
<K
,V
> subMap(K fromKey
, K toKey
) { throw new InternalError(); }
2083 public SortedMap
<K
,V
> headMap(K toKey
) { throw new InternalError(); }
2084 public SortedMap
<K
,V
> tailMap(K fromKey
) { throw new InternalError(); }
2085 public Comparator
<?
super K
> comparator() { throw new InternalError(); }
2089 // Red-black mechanics
2091 private static final boolean RED
= false;
2092 private static final boolean BLACK
= true;
2095 * Node in the Tree. Doubles as a means to pass key-value pairs back to
2096 * user (see Map.Entry).
2099 static final class TreeMapEntry
<K
,V
> implements Map
.Entry
<K
,V
> {
2102 TreeMapEntry
<K
,V
> left
= null;
2103 TreeMapEntry
<K
,V
> right
= null;
2104 TreeMapEntry
<K
,V
> parent
;
2105 boolean color
= BLACK
;
2108 * Make a new cell with given key, value, and parent, and with
2109 * {@code null} child links, and BLACK color.
2111 TreeMapEntry(K key
, V value
, TreeMapEntry
<K
,V
> parent
) {
2114 this.parent
= parent
;
2127 * Returns the value associated with the key.
2129 * @return the value associated with the key
2131 public V
getValue() {
2136 * Replaces the value currently associated with the key with the given
2139 * @return the value associated with the key before this method was
2142 public V
setValue(V value
) {
2143 V oldValue
= this.value
;
2148 public boolean equals(Object o
) {
2149 if (!(o
instanceof Map
.Entry
))
2151 Map
.Entry
<?
,?
> e
= (Map
.Entry
<?
,?
>)o
;
2153 return valEquals(key
,e
.getKey()) && valEquals(value
,e
.getValue());
2156 public int hashCode() {
2157 int keyHash
= (key
==null ?
0 : key
.hashCode());
2158 int valueHash
= (value
==null ?
0 : value
.hashCode());
2159 return keyHash ^ valueHash
;
2162 public String
toString() {
2163 return key
+ "=" + value
;
2168 * Returns the first Entry in the TreeMap (according to the TreeMap's
2169 * key-sort function). Returns null if the TreeMap is empty.
2171 final TreeMapEntry
<K
,V
> getFirstEntry() {
2172 TreeMapEntry
<K
,V
> p
= root
;
2174 while (p
.left
!= null)
2180 * Returns the last Entry in the TreeMap (according to the TreeMap's
2181 * key-sort function). Returns null if the TreeMap is empty.
2183 final TreeMapEntry
<K
,V
> getLastEntry() {
2184 TreeMapEntry
<K
,V
> p
= root
;
2186 while (p
.right
!= null)
2192 * Returns the successor of the specified Entry, or null if no such.
2194 static <K
,V
> TreeMapEntry
<K
,V
> successor(TreeMapEntry
<K
,V
> t
) {
2197 else if (t
.right
!= null) {
2198 TreeMapEntry
<K
,V
> p
= t
.right
;
2199 while (p
.left
!= null)
2203 TreeMapEntry
<K
,V
> p
= t
.parent
;
2204 TreeMapEntry
<K
,V
> ch
= t
;
2205 while (p
!= null && ch
== p
.right
) {
2214 * Returns the predecessor of the specified Entry, or null if no such.
2216 static <K
,V
> TreeMapEntry
<K
,V
> predecessor(TreeMapEntry
<K
,V
> t
) {
2219 else if (t
.left
!= null) {
2220 TreeMapEntry
<K
,V
> p
= t
.left
;
2221 while (p
.right
!= null)
2225 TreeMapEntry
<K
,V
> p
= t
.parent
;
2226 TreeMapEntry
<K
,V
> ch
= t
;
2227 while (p
!= null && ch
== p
.left
) {
2236 * Balancing operations.
2238 * Implementations of rebalancings during insertion and deletion are
2239 * slightly different than the CLR version. Rather than using dummy
2240 * nilnodes, we use a set of accessors that deal properly with null. They
2241 * are used to avoid messiness surrounding nullness checks in the main
2245 private static <K
,V
> boolean colorOf(TreeMapEntry
<K
,V
> p
) {
2246 return (p
== null ? BLACK
: p
.color
);
2249 private static <K
,V
> TreeMapEntry
<K
,V
> parentOf(TreeMapEntry
<K
,V
> p
) {
2250 return (p
== null ?
null: p
.parent
);
2253 private static <K
,V
> void setColor(TreeMapEntry
<K
,V
> p
, boolean c
) {
2258 private static <K
,V
> TreeMapEntry
<K
,V
> leftOf(TreeMapEntry
<K
,V
> p
) {
2259 return (p
== null) ?
null: p
.left
;
2262 private static <K
,V
> TreeMapEntry
<K
,V
> rightOf(TreeMapEntry
<K
,V
> p
) {
2263 return (p
== null) ?
null: p
.right
;
2267 private void rotateLeft(TreeMapEntry
<K
,V
> p
) {
2269 TreeMapEntry
<K
,V
> r
= p
.right
;
2273 r
.parent
= p
.parent
;
2274 if (p
.parent
== null)
2276 else if (p
.parent
.left
== p
)
2286 private void rotateRight(TreeMapEntry
<K
,V
> p
) {
2288 TreeMapEntry
<K
,V
> l
= p
.left
;
2290 if (l
.right
!= null) l
.right
.parent
= p
;
2291 l
.parent
= p
.parent
;
2292 if (p
.parent
== null)
2294 else if (p
.parent
.right
== p
)
2296 else p
.parent
.left
= l
;
2303 private void fixAfterInsertion(TreeMapEntry
<K
,V
> x
) {
2306 while (x
!= null && x
!= root
&& x
.parent
.color
== RED
) {
2307 if (parentOf(x
) == leftOf(parentOf(parentOf(x
)))) {
2308 TreeMapEntry
<K
,V
> y
= rightOf(parentOf(parentOf(x
)));
2309 if (colorOf(y
) == RED
) {
2310 setColor(parentOf(x
), BLACK
);
2312 setColor(parentOf(parentOf(x
)), RED
);
2313 x
= parentOf(parentOf(x
));
2315 if (x
== rightOf(parentOf(x
))) {
2319 setColor(parentOf(x
), BLACK
);
2320 setColor(parentOf(parentOf(x
)), RED
);
2321 rotateRight(parentOf(parentOf(x
)));
2324 TreeMapEntry
<K
,V
> y
= leftOf(parentOf(parentOf(x
)));
2325 if (colorOf(y
) == RED
) {
2326 setColor(parentOf(x
), BLACK
);
2328 setColor(parentOf(parentOf(x
)), RED
);
2329 x
= parentOf(parentOf(x
));
2331 if (x
== leftOf(parentOf(x
))) {
2335 setColor(parentOf(x
), BLACK
);
2336 setColor(parentOf(parentOf(x
)), RED
);
2337 rotateLeft(parentOf(parentOf(x
)));
2345 * Delete node p, and then rebalance the tree.
2347 private void deleteEntry(TreeMapEntry
<K
,V
> p
) {
2351 // If strictly internal, copy successor's element to p and then make p
2352 // point to successor.
2353 if (p
.left
!= null && p
.right
!= null) {
2354 TreeMapEntry
<K
,V
> s
= successor(p
);
2358 } // p has 2 children
2360 // Start fixup at replacement node, if it exists.
2361 TreeMapEntry
<K
,V
> replacement
= (p
.left
!= null ? p
.left
: p
.right
);
2363 if (replacement
!= null) {
2364 // Link replacement to parent
2365 replacement
.parent
= p
.parent
;
2366 if (p
.parent
== null)
2368 else if (p
== p
.parent
.left
)
2369 p
.parent
.left
= replacement
;
2371 p
.parent
.right
= replacement
;
2373 // Null out links so they are OK to use by fixAfterDeletion.
2374 p
.left
= p
.right
= p
.parent
= null;
2377 if (p
.color
== BLACK
)
2378 fixAfterDeletion(replacement
);
2379 } else if (p
.parent
== null) { // return if we are the only node.
2381 } else { // No children. Use self as phantom replacement and unlink.
2382 if (p
.color
== BLACK
)
2383 fixAfterDeletion(p
);
2385 if (p
.parent
!= null) {
2386 if (p
== p
.parent
.left
)
2387 p
.parent
.left
= null;
2388 else if (p
== p
.parent
.right
)
2389 p
.parent
.right
= null;
2396 private void fixAfterDeletion(TreeMapEntry
<K
,V
> x
) {
2397 while (x
!= root
&& colorOf(x
) == BLACK
) {
2398 if (x
== leftOf(parentOf(x
))) {
2399 TreeMapEntry
<K
,V
> sib
= rightOf(parentOf(x
));
2401 if (colorOf(sib
) == RED
) {
2402 setColor(sib
, BLACK
);
2403 setColor(parentOf(x
), RED
);
2404 rotateLeft(parentOf(x
));
2405 sib
= rightOf(parentOf(x
));
2408 if (colorOf(leftOf(sib
)) == BLACK
&&
2409 colorOf(rightOf(sib
)) == BLACK
) {
2413 if (colorOf(rightOf(sib
)) == BLACK
) {
2414 setColor(leftOf(sib
), BLACK
);
2417 sib
= rightOf(parentOf(x
));
2419 setColor(sib
, colorOf(parentOf(x
)));
2420 setColor(parentOf(x
), BLACK
);
2421 setColor(rightOf(sib
), BLACK
);
2422 rotateLeft(parentOf(x
));
2425 } else { // symmetric
2426 TreeMapEntry
<K
,V
> sib
= leftOf(parentOf(x
));
2428 if (colorOf(sib
) == RED
) {
2429 setColor(sib
, BLACK
);
2430 setColor(parentOf(x
), RED
);
2431 rotateRight(parentOf(x
));
2432 sib
= leftOf(parentOf(x
));
2435 if (colorOf(rightOf(sib
)) == BLACK
&&
2436 colorOf(leftOf(sib
)) == BLACK
) {
2440 if (colorOf(leftOf(sib
)) == BLACK
) {
2441 setColor(rightOf(sib
), BLACK
);
2444 sib
= leftOf(parentOf(x
));
2446 setColor(sib
, colorOf(parentOf(x
)));
2447 setColor(parentOf(x
), BLACK
);
2448 setColor(leftOf(sib
), BLACK
);
2449 rotateRight(parentOf(x
));
2458 private static final long serialVersionUID
= 919286545866124006L;
2461 * Save the state of the {@code TreeMap} instance to a stream (i.e.,
2464 * @serialData The <em>size</em> of the TreeMap (the number of key-value
2465 * mappings) is emitted (int), followed by the key (Object)
2466 * and value (Object) for each key-value mapping represented
2467 * by the TreeMap. The key-value mappings are emitted in
2468 * key-order (as determined by the TreeMap's Comparator,
2469 * or by the keys' natural ordering if the TreeMap has no
2472 private void writeObject(java
.io
.ObjectOutputStream s
)
2473 throws java
.io
.IOException
{
2474 // Write out the Comparator and any hidden stuff
2475 s
.defaultWriteObject();
2477 // Write out size (number of Mappings)
2480 // Write out keys and values (alternating)
2481 for (Iterator
<Map
.Entry
<K
,V
>> i
= entrySet().iterator(); i
.hasNext(); ) {
2482 Map
.Entry
<K
,V
> e
= i
.next();
2483 s
.writeObject(e
.getKey());
2484 s
.writeObject(e
.getValue());
2489 * Reconstitute the {@code TreeMap} instance from a stream (i.e.,
2492 private void readObject(final java
.io
.ObjectInputStream s
)
2493 throws java
.io
.IOException
, ClassNotFoundException
{
2494 // Read in the Comparator and any hidden stuff
2495 s
.defaultReadObject();
2498 int size
= s
.readInt();
2500 buildFromSorted(size
, null, s
, null);
2503 /** Intended to be called only from TreeSet.readObject */
2504 void readTreeSet(int size
, java
.io
.ObjectInputStream s
, V defaultVal
)
2505 throws java
.io
.IOException
, ClassNotFoundException
{
2506 buildFromSorted(size
, null, s
, defaultVal
);
2509 /** Intended to be called only from TreeSet.addAll */
2510 void addAllForTreeSet(SortedSet
<?
extends K
> set
, V defaultVal
) {
2512 buildFromSorted(set
.size(), set
.iterator(), null, defaultVal
);
2513 } catch (java
.io
.IOException cannotHappen
) {
2514 } catch (ClassNotFoundException cannotHappen
) {
2520 * Linear time tree building algorithm from sorted data. Can accept keys
2521 * and/or values from iterator or stream. This leads to too many
2522 * parameters, but seems better than alternatives. The four formats
2523 * that this method accepts are:
2525 * 1) An iterator of Map.Entries. (it != null, defaultVal == null).
2526 * 2) An iterator of keys. (it != null, defaultVal != null).
2527 * 3) A stream of alternating serialized keys and values.
2528 * (it == null, defaultVal == null).
2529 * 4) A stream of serialized keys. (it == null, defaultVal != null).
2531 * It is assumed that the comparator of the TreeMap is already set prior
2532 * to calling this method.
2534 * @param size the number of keys (or key-value pairs) to be read from
2535 * the iterator or stream
2536 * @param it If non-null, new entries are created from entries
2537 * or keys read from this iterator.
2538 * @param str If non-null, new entries are created from keys and
2539 * possibly values read from this stream in serialized form.
2540 * Exactly one of it and str should be non-null.
2541 * @param defaultVal if non-null, this default value is used for
2542 * each value in the map. If null, each value is read from
2543 * iterator or stream, as described above.
2544 * @throws java.io.IOException propagated from stream reads. This cannot
2545 * occur if str is null.
2546 * @throws ClassNotFoundException propagated from readObject.
2547 * This cannot occur if str is null.
2549 private void buildFromSorted(int size
, Iterator
<?
> it
,
2550 java
.io
.ObjectInputStream str
,
2552 throws java
.io
.IOException
, ClassNotFoundException
{
2554 root
= buildFromSorted(0, 0, size
-1, computeRedLevel(size
),
2555 it
, str
, defaultVal
);
2559 * Recursive "helper method" that does the real work of the
2560 * previous method. Identically named parameters have
2561 * identical definitions. Additional parameters are documented below.
2562 * It is assumed that the comparator and size fields of the TreeMap are
2563 * already set prior to calling this method. (It ignores both fields.)
2565 * @param level the current level of tree. Initial call should be 0.
2566 * @param lo the first element index of this subtree. Initial should be 0.
2567 * @param hi the last element index of this subtree. Initial should be
2569 * @param redLevel the level at which nodes should be red.
2570 * Must be equal to computeRedLevel for tree of this size.
2572 @SuppressWarnings("unchecked")
2573 private final TreeMapEntry
<K
,V
> buildFromSorted(int level
, int lo
, int hi
,
2576 java
.io
.ObjectInputStream str
,
2578 throws java
.io
.IOException
, ClassNotFoundException
{
2580 * Strategy: The root is the middlemost element. To get to it, we
2581 * have to first recursively construct the entire left subtree,
2582 * so as to grab all of its elements. We can then proceed with right
2585 * The lo and hi arguments are the minimum and maximum
2586 * indices to pull out of the iterator or stream for current subtree.
2587 * They are not actually indexed, we just proceed sequentially,
2588 * ensuring that items are extracted in corresponding order.
2591 if (hi
< lo
) return null;
2593 int mid
= (lo
+ hi
) >>> 1;
2595 TreeMapEntry
<K
,V
> left
= null;
2597 left
= buildFromSorted(level
+1, lo
, mid
- 1, redLevel
,
2598 it
, str
, defaultVal
);
2600 // extract key and/or value from iterator or stream
2604 if (defaultVal
==null) {
2605 Map
.Entry
<K
,V
> entry
= (Map
.Entry
<K
,V
>)it
.next();
2606 key
= entry
.getKey();
2607 value
= entry
.getValue();
2612 } else { // use stream
2613 key
= (K
) str
.readObject();
2614 value
= (defaultVal
!= null ? defaultVal
: (V
) str
.readObject());
2617 TreeMapEntry
<K
,V
> middle
= new TreeMapEntry
<>(key
, value
, null);
2619 // color nodes in non-full bottommost level red
2620 if (level
== redLevel
)
2625 left
.parent
= middle
;
2629 TreeMapEntry
<K
,V
> right
= buildFromSorted(level
+1, mid
+1, hi
, redLevel
,
2630 it
, str
, defaultVal
);
2631 middle
.right
= right
;
2632 right
.parent
= middle
;
2639 * Find the level down to which to assign all nodes BLACK. This is the
2640 * last `full' level of the complete binary tree produced by
2641 * buildTree. The remaining nodes are colored RED. (This makes a `nice'
2642 * set of color assignments wrt future insertions.) This level number is
2643 * computed by finding the number of splits needed to reach the zeroeth
2644 * node. (The answer is ~lg(N), but in any case must be computed by same
2645 * quick O(lg(N)) loop.)
2647 private static int computeRedLevel(int sz
) {
2649 for (int m
= sz
- 1; m
>= 0; m
= m
/ 2 - 1)
2655 * Currently, we support Spliterator-based versions only for the
2656 * full map, in either plain of descending form, otherwise relying
2657 * on defaults because size estimation for submaps would dominate
2658 * costs. The type tests needed to check these for key views are
2659 * not very nice but avoid disrupting existing class
2660 * structures. Callers must use plain default spliterators if this
2663 static <K
> Spliterator
<K
> keySpliteratorFor(NavigableMap
<K
,?
> m
) {
2664 if (m
instanceof TreeMap
) {
2665 @SuppressWarnings("unchecked") TreeMap
<K
,Object
> t
=
2666 (TreeMap
<K
,Object
>) m
;
2667 return t
.keySpliterator();
2669 if (m
instanceof DescendingSubMap
) {
2670 @SuppressWarnings("unchecked") DescendingSubMap
<K
,?
> dm
=
2671 (DescendingSubMap
<K
,?
>) m
;
2672 TreeMap
<K
,?
> tm
= dm
.m
;
2673 if (dm
== tm
.descendingMap
) {
2674 @SuppressWarnings("unchecked") TreeMap
<K
,Object
> t
=
2675 (TreeMap
<K
,Object
>) tm
;
2676 return t
.descendingKeySpliterator();
2679 @SuppressWarnings("unchecked") NavigableSubMap
<K
,?
> sm
=
2680 (NavigableSubMap
<K
,?
>) m
;
2681 return sm
.keySpliterator();
2684 final Spliterator
<K
> keySpliterator() {
2685 return new KeySpliterator
<K
,V
>(this, null, null, 0, -1, 0);
2688 final Spliterator
<K
> descendingKeySpliterator() {
2689 return new DescendingKeySpliterator
<K
,V
>(this, null, null, 0, -2, 0);
2693 * Base class for spliterators. Iteration starts at a given
2694 * origin and continues up to but not including a given fence (or
2695 * null for end). At top-level, for ascending cases, the first
2696 * split uses the root as left-fence/right-origin. From there,
2697 * right-hand splits replace the current fence with its left
2698 * child, also serving as origin for the split-off spliterator.
2699 * Left-hands are symmetric. Descending versions place the origin
2700 * at the end and invert ascending split rules. This base class
2701 * is non-commital about directionality, or whether the top-level
2702 * spliterator covers the whole tree. This means that the actual
2703 * split mechanics are located in subclasses. Some of the subclass
2704 * trySplit methods are identical (except for return types), but
2705 * not nicely factorable.
2707 * Currently, subclass versions exist only for the full map
2708 * (including descending keys via its descendingMap). Others are
2709 * possible but currently not worthwhile because submaps require
2710 * O(n) computations to determine size, which substantially limits
2711 * potential speed-ups of using custom Spliterators versus default
2714 * To boostrap initialization, external constructors use
2715 * negative size estimates: -1 for ascend, -2 for descend.
2717 static class TreeMapSpliterator
<K
,V
> {
2718 final TreeMap
<K
,V
> tree
;
2719 TreeMapEntry
<K
,V
> current
; // traverser; initially first node in range
2720 TreeMapEntry
<K
,V
> fence
; // one past last, or null
2721 int side
; // 0: top, -1: is a left split, +1: right
2722 int est
; // size estimate (exact only for top-level)
2723 int expectedModCount
; // for CME checks
2725 TreeMapSpliterator(TreeMap
<K
,V
> tree
,
2726 TreeMapEntry
<K
,V
> origin
, TreeMapEntry
<K
,V
> fence
,
2727 int side
, int est
, int expectedModCount
) {
2729 this.current
= origin
;
2733 this.expectedModCount
= expectedModCount
;
2736 final int getEstimate() { // force initialization
2737 int s
; TreeMap
<K
,V
> t
;
2738 if ((s
= est
) < 0) {
2739 if ((t
= tree
) != null) {
2740 current
= (s
== -1) ? t
.getFirstEntry() : t
.getLastEntry();
2742 expectedModCount
= t
.modCount
;
2750 public final long estimateSize() {
2751 return (long)getEstimate();
2755 static final class KeySpliterator
<K
,V
>
2756 extends TreeMapSpliterator
<K
,V
>
2757 implements Spliterator
<K
> {
2758 KeySpliterator(TreeMap
<K
,V
> tree
,
2759 TreeMapEntry
<K
,V
> origin
, TreeMapEntry
<K
,V
> fence
,
2760 int side
, int est
, int expectedModCount
) {
2761 super(tree
, origin
, fence
, side
, est
, expectedModCount
);
2764 public KeySpliterator
<K
,V
> trySplit() {
2766 getEstimate(); // force initialization
2768 TreeMapEntry
<K
,V
> e
= current
, f
= fence
,
2769 s
= ((e
== null || e
== f
) ?
null : // empty
2770 (d
== 0) ? tree
.root
: // was top
2771 (d
> 0) ? e
.right
: // was right
2772 (d
< 0 && f
!= null) ? f
.left
: // was left
2774 if (s
!= null && s
!= e
&& s
!= f
&&
2775 tree
.compare(e
.key
, s
.key
) < 0) { // e not already past s
2777 return new KeySpliterator
<>
2778 (tree
, e
, current
= s
, -1, est
>>>= 1, expectedModCount
);
2783 public void forEachRemaining(Consumer
<?
super K
> action
) {
2785 throw new NullPointerException();
2787 getEstimate(); // force initialization
2788 TreeMapEntry
<K
,V
> f
= fence
, e
, p
, pl
;
2789 if ((e
= current
) != null && e
!= f
) {
2790 current
= f
; // exhaust
2792 action
.accept(e
.key
);
2793 if ((p
= e
.right
) != null) {
2794 while ((pl
= p
.left
) != null)
2798 while ((p
= e
.parent
) != null && e
== p
.right
)
2801 } while ((e
= p
) != null && e
!= f
);
2802 if (tree
.modCount
!= expectedModCount
)
2803 throw new ConcurrentModificationException();
2807 public boolean tryAdvance(Consumer
<?
super K
> action
) {
2808 TreeMapEntry
<K
,V
> e
;
2810 throw new NullPointerException();
2812 getEstimate(); // force initialization
2813 if ((e
= current
) == null || e
== fence
)
2815 current
= successor(e
);
2816 action
.accept(e
.key
);
2817 if (tree
.modCount
!= expectedModCount
)
2818 throw new ConcurrentModificationException();
2822 public int characteristics() {
2823 return (side
== 0 ? Spliterator
.SIZED
: 0) |
2824 Spliterator
.DISTINCT
| Spliterator
.SORTED
| Spliterator
.ORDERED
;
2827 public final Comparator
<?
super K
> getComparator() {
2828 return tree
.comparator
;
2833 static final class DescendingKeySpliterator
<K
,V
>
2834 extends TreeMapSpliterator
<K
,V
>
2835 implements Spliterator
<K
> {
2836 DescendingKeySpliterator(TreeMap
<K
,V
> tree
,
2837 TreeMapEntry
<K
,V
> origin
, TreeMapEntry
<K
,V
> fence
,
2838 int side
, int est
, int expectedModCount
) {
2839 super(tree
, origin
, fence
, side
, est
, expectedModCount
);
2842 public DescendingKeySpliterator
<K
,V
> trySplit() {
2844 getEstimate(); // force initialization
2846 TreeMapEntry
<K
,V
> e
= current
, f
= fence
,
2847 s
= ((e
== null || e
== f
) ?
null : // empty
2848 (d
== 0) ? tree
.root
: // was top
2849 (d
< 0) ? e
.left
: // was left
2850 (d
> 0 && f
!= null) ? f
.right
: // was right
2852 if (s
!= null && s
!= e
&& s
!= f
&&
2853 tree
.compare(e
.key
, s
.key
) > 0) { // e not already past s
2855 return new DescendingKeySpliterator
<>
2856 (tree
, e
, current
= s
, -1, est
>>>= 1, expectedModCount
);
2861 public void forEachRemaining(Consumer
<?
super K
> action
) {
2863 throw new NullPointerException();
2865 getEstimate(); // force initialization
2866 TreeMapEntry
<K
,V
> f
= fence
, e
, p
, pr
;
2867 if ((e
= current
) != null && e
!= f
) {
2868 current
= f
; // exhaust
2870 action
.accept(e
.key
);
2871 if ((p
= e
.left
) != null) {
2872 while ((pr
= p
.right
) != null)
2876 while ((p
= e
.parent
) != null && e
== p
.left
)
2879 } while ((e
= p
) != null && e
!= f
);
2880 if (tree
.modCount
!= expectedModCount
)
2881 throw new ConcurrentModificationException();
2885 public boolean tryAdvance(Consumer
<?
super K
> action
) {
2886 TreeMapEntry
<K
,V
> e
;
2888 throw new NullPointerException();
2890 getEstimate(); // force initialization
2891 if ((e
= current
) == null || e
== fence
)
2893 current
= predecessor(e
);
2894 action
.accept(e
.key
);
2895 if (tree
.modCount
!= expectedModCount
)
2896 throw new ConcurrentModificationException();
2900 public int characteristics() {
2901 return (side
== 0 ? Spliterator
.SIZED
: 0) |
2902 Spliterator
.DISTINCT
| Spliterator
.ORDERED
;
2906 static final class ValueSpliterator
<K
,V
>
2907 extends TreeMapSpliterator
<K
,V
>
2908 implements Spliterator
<V
> {
2909 ValueSpliterator(TreeMap
<K
,V
> tree
,
2910 TreeMapEntry
<K
,V
> origin
, TreeMapEntry
<K
,V
> fence
,
2911 int side
, int est
, int expectedModCount
) {
2912 super(tree
, origin
, fence
, side
, est
, expectedModCount
);
2915 public ValueSpliterator
<K
,V
> trySplit() {
2917 getEstimate(); // force initialization
2919 TreeMapEntry
<K
,V
> e
= current
, f
= fence
,
2920 s
= ((e
== null || e
== f
) ?
null : // empty
2921 (d
== 0) ? tree
.root
: // was top
2922 (d
> 0) ? e
.right
: // was right
2923 (d
< 0 && f
!= null) ? f
.left
: // was left
2925 if (s
!= null && s
!= e
&& s
!= f
&&
2926 tree
.compare(e
.key
, s
.key
) < 0) { // e not already past s
2928 return new ValueSpliterator
<>
2929 (tree
, e
, current
= s
, -1, est
>>>= 1, expectedModCount
);
2934 public void forEachRemaining(Consumer
<?
super V
> action
) {
2936 throw new NullPointerException();
2938 getEstimate(); // force initialization
2939 TreeMapEntry
<K
,V
> f
= fence
, e
, p
, pl
;
2940 if ((e
= current
) != null && e
!= f
) {
2941 current
= f
; // exhaust
2943 action
.accept(e
.value
);
2944 if ((p
= e
.right
) != null) {
2945 while ((pl
= p
.left
) != null)
2949 while ((p
= e
.parent
) != null && e
== p
.right
)
2952 } while ((e
= p
) != null && e
!= f
);
2953 if (tree
.modCount
!= expectedModCount
)
2954 throw new ConcurrentModificationException();
2958 public boolean tryAdvance(Consumer
<?
super V
> action
) {
2959 TreeMapEntry
<K
,V
> e
;
2961 throw new NullPointerException();
2963 getEstimate(); // force initialization
2964 if ((e
= current
) == null || e
== fence
)
2966 current
= successor(e
);
2967 action
.accept(e
.value
);
2968 if (tree
.modCount
!= expectedModCount
)
2969 throw new ConcurrentModificationException();
2973 public int characteristics() {
2974 return (side
== 0 ? Spliterator
.SIZED
: 0) | Spliterator
.ORDERED
;
2978 static final class EntrySpliterator
<K
,V
>
2979 extends TreeMapSpliterator
<K
,V
>
2980 implements Spliterator
<Map
.Entry
<K
,V
>> {
2981 EntrySpliterator(TreeMap
<K
,V
> tree
,
2982 TreeMapEntry
<K
,V
> origin
, TreeMapEntry
<K
,V
> fence
,
2983 int side
, int est
, int expectedModCount
) {
2984 super(tree
, origin
, fence
, side
, est
, expectedModCount
);
2987 public EntrySpliterator
<K
,V
> trySplit() {
2989 getEstimate(); // force initialization
2991 TreeMapEntry
<K
,V
> e
= current
, f
= fence
,
2992 s
= ((e
== null || e
== f
) ?
null : // empty
2993 (d
== 0) ? tree
.root
: // was top
2994 (d
> 0) ? e
.right
: // was right
2995 (d
< 0 && f
!= null) ? f
.left
: // was left
2997 if (s
!= null && s
!= e
&& s
!= f
&&
2998 tree
.compare(e
.key
, s
.key
) < 0) { // e not already past s
3000 return new EntrySpliterator
<>
3001 (tree
, e
, current
= s
, -1, est
>>>= 1, expectedModCount
);
3006 public void forEachRemaining(Consumer
<?
super Map
.Entry
<K
, V
>> action
) {
3008 throw new NullPointerException();
3010 getEstimate(); // force initialization
3011 TreeMapEntry
<K
,V
> f
= fence
, e
, p
, pl
;
3012 if ((e
= current
) != null && e
!= f
) {
3013 current
= f
; // exhaust
3016 if ((p
= e
.right
) != null) {
3017 while ((pl
= p
.left
) != null)
3021 while ((p
= e
.parent
) != null && e
== p
.right
)
3024 } while ((e
= p
) != null && e
!= f
);
3025 if (tree
.modCount
!= expectedModCount
)
3026 throw new ConcurrentModificationException();
3030 public boolean tryAdvance(Consumer
<?
super Map
.Entry
<K
,V
>> action
) {
3031 TreeMapEntry
<K
,V
> e
;
3033 throw new NullPointerException();
3035 getEstimate(); // force initialization
3036 if ((e
= current
) == null || e
== fence
)
3038 current
= successor(e
);
3040 if (tree
.modCount
!= expectedModCount
)
3041 throw new ConcurrentModificationException();
3045 public int characteristics() {
3046 return (side
== 0 ? Spliterator
.SIZED
: 0) |
3047 Spliterator
.DISTINCT
| Spliterator
.SORTED
| Spliterator
.ORDERED
;
3051 public Comparator
<Map
.Entry
<K
, V
>> getComparator() {
3052 // Adapt or create a key-based comparator
3053 if (tree
.comparator
!= null) {
3054 return Map
.Entry
.comparingByKey(tree
.comparator
);
3057 return (Comparator
<Map
.Entry
<K
, V
>> & Serializable
) (e1
, e2
) -> {
3058 @SuppressWarnings("unchecked")
3059 Comparable
<?
super K
> k1
= (Comparable
<?
super K
>) e1
.getKey();
3060 return k1
.compareTo(e2
.getKey());