0001 /*
0002 * Copyright 1997-2007 Sun Microsystems, Inc. All Rights Reserved.
0003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0004 *
0005 * This code is free software; you can redistribute it and/or modify it
0006 * under the terms of the GNU General Public License version 2 only, as
0007 * published by the Free Software Foundation. Sun designates this
0008 * particular file as subject to the "Classpath" exception as provided
0009 * by Sun in the LICENSE file that accompanied this code.
0010 *
0011 * This code is distributed in the hope that it will be useful, but WITHOUT
0012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0013 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0014 * version 2 for more details (a copy is included in the LICENSE file that
0015 * accompanied this code).
0016 *
0017 * You should have received a copy of the GNU General Public License version
0018 * 2 along with this work; if not, write to the Free Software Foundation,
0019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0020 *
0021 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
0022 * CA 95054 USA or visit www.sun.com if you need additional information or
0023 * have any questions.
0024 */
0025
0026 package java.util;
0027
0028 /**
0029 * A Red-Black tree based {@link NavigableMap} implementation.
0030 * The map is sorted according to the {@linkplain Comparable natural
0031 * ordering} of its keys, or by a {@link Comparator} provided at map
0032 * creation time, depending on which constructor is used.
0033 *
0034 * <p>This implementation provides guaranteed log(n) time cost for the
0035 * <tt>containsKey</tt>, <tt>get</tt>, <tt>put</tt> and <tt>remove</tt>
0036 * operations. Algorithms are adaptations of those in Cormen, Leiserson, and
0037 * Rivest's <I>Introduction to Algorithms</I>.
0038 *
0039 * <p>Note that the ordering maintained by a sorted map (whether or not an
0040 * explicit comparator is provided) must be <i>consistent with equals</i> if
0041 * this sorted map is to correctly implement the <tt>Map</tt> interface. (See
0042 * <tt>Comparable</tt> or <tt>Comparator</tt> for a precise definition of
0043 * <i>consistent with equals</i>.) This is so because the <tt>Map</tt>
0044 * interface is defined in terms of the equals operation, but a map performs
0045 * all key comparisons using its <tt>compareTo</tt> (or <tt>compare</tt>)
0046 * method, so two keys that are deemed equal by this method are, from the
0047 * standpoint of the sorted map, equal. The behavior of a sorted map
0048 * <i>is</i> well-defined even if its ordering is inconsistent with equals; it
0049 * just fails to obey the general contract of the <tt>Map</tt> interface.
0050 *
0051 * <p><strong>Note that this implementation is not synchronized.</strong>
0052 * If multiple threads access a map concurrently, and at least one of the
0053 * threads modifies the map structurally, it <i>must</i> be synchronized
0054 * externally. (A structural modification is any operation that adds or
0055 * deletes one or more mappings; merely changing the value associated
0056 * with an existing key is not a structural modification.) This is
0057 * typically accomplished by synchronizing on some object that naturally
0058 * encapsulates the map.
0059 * If no such object exists, the map should be "wrapped" using the
0060 * {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap}
0061 * method. This is best done at creation time, to prevent accidental
0062 * unsynchronized access to the map: <pre>
0063 * SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre>
0064 *
0065 * <p>The iterators returned by the <tt>iterator</tt> method of the collections
0066 * returned by all of this class's "collection view methods" are
0067 * <i>fail-fast</i>: if the map is structurally modified at any time after the
0068 * iterator is created, in any way except through the iterator's own
0069 * <tt>remove</tt> method, the iterator will throw a {@link
0070 * ConcurrentModificationException}. Thus, in the face of concurrent
0071 * modification, the iterator fails quickly and cleanly, rather than risking
0072 * arbitrary, non-deterministic behavior at an undetermined time in the future.
0073 *
0074 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
0075 * as it is, generally speaking, impossible to make any hard guarantees in the
0076 * presence of unsynchronized concurrent modification. Fail-fast iterators
0077 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
0078 * Therefore, it would be wrong to write a program that depended on this
0079 * exception for its correctness: <i>the fail-fast behavior of iterators
0080 * should be used only to detect bugs.</i>
0081 *
0082 * <p>All <tt>Map.Entry</tt> pairs returned by methods in this class
0083 * and its views represent snapshots of mappings at the time they were
0084 * produced. They do <em>not</em> support the <tt>Entry.setValue</tt>
0085 * method. (Note however that it is possible to change mappings in the
0086 * associated map using <tt>put</tt>.)
0087 *
0088 * <p>This class is a member of the
0089 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
0090 * Java Collections Framework</a>.
0091 *
0092 * @param <K> the type of keys maintained by this map
0093 * @param <V> the type of mapped values
0094 *
0095 * @author Josh Bloch and Doug Lea
0096 * @version 1.73, 05/10/06
0097 * @see Map
0098 * @see HashMap
0099 * @see Hashtable
0100 * @see Comparable
0101 * @see Comparator
0102 * @see Collection
0103 * @since 1.2
0104 */
0105
0106 public class TreeMap<K, V> extends AbstractMap<K, V> implements
0107 NavigableMap<K, V>, Cloneable, java.io.Serializable {
0108 /**
0109 * The comparator used to maintain order in this tree map, or
0110 * null if it uses the natural ordering of its keys.
0111 *
0112 * @serial
0113 */
0114 private final Comparator<? super K> comparator;
0115
0116 private transient Entry<K, V> root = null;
0117
0118 /**
0119 * The number of entries in the tree
0120 */
0121 private transient int size = 0;
0122
0123 /**
0124 * The number of structural modifications to the tree.
0125 */
0126 private transient int modCount = 0;
0127
0128 /**
0129 * Constructs a new, empty tree map, using the natural ordering of its
0130 * keys. All keys inserted into the map must implement the {@link
0131 * Comparable} interface. Furthermore, all such keys must be
0132 * <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw
0133 * a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
0134 * <tt>k2</tt> in the map. If the user attempts to put a key into the
0135 * map that violates this constraint (for example, the user attempts to
0136 * put a string key into a map whose keys are integers), the
0137 * <tt>put(Object key, Object value)</tt> call will throw a
0138 * <tt>ClassCastException</tt>.
0139 */
0140 public TreeMap() {
0141 comparator = null;
0142 }
0143
0144 /**
0145 * Constructs a new, empty tree map, ordered according to the given
0146 * comparator. All keys inserted into the map must be <i>mutually
0147 * comparable</i> by the given comparator: <tt>comparator.compare(k1,
0148 * k2)</tt> must not throw a <tt>ClassCastException</tt> for any keys
0149 * <tt>k1</tt> and <tt>k2</tt> in the map. If the user attempts to put
0150 * a key into the map that violates this constraint, the <tt>put(Object
0151 * key, Object value)</tt> call will throw a
0152 * <tt>ClassCastException</tt>.
0153 *
0154 * @param comparator the comparator that will be used to order this map.
0155 * If <tt>null</tt>, the {@linkplain Comparable natural
0156 * ordering} of the keys will be used.
0157 */
0158 public TreeMap(Comparator<? super K> comparator) {
0159 this .comparator = comparator;
0160 }
0161
0162 /**
0163 * Constructs a new tree map containing the same mappings as the given
0164 * map, ordered according to the <i>natural ordering</i> of its keys.
0165 * All keys inserted into the new map must implement the {@link
0166 * Comparable} interface. Furthermore, all such keys must be
0167 * <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw
0168 * a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
0169 * <tt>k2</tt> in the map. This method runs in n*log(n) time.
0170 *
0171 * @param m the map whose mappings are to be placed in this map
0172 * @throws ClassCastException if the keys in m are not {@link Comparable},
0173 * or are not mutually comparable
0174 * @throws NullPointerException if the specified map is null
0175 */
0176 public TreeMap(Map<? extends K, ? extends V> m) {
0177 comparator = null;
0178 putAll(m);
0179 }
0180
0181 /**
0182 * Constructs a new tree map containing the same mappings and
0183 * using the same ordering as the specified sorted map. This
0184 * method runs in linear time.
0185 *
0186 * @param m the sorted map whose mappings are to be placed in this map,
0187 * and whose comparator is to be used to sort this map
0188 * @throws NullPointerException if the specified map is null
0189 */
0190 public TreeMap(SortedMap<K, ? extends V> m) {
0191 comparator = m.comparator();
0192 try {
0193 buildFromSorted(m.size(), m.entrySet().iterator(), null,
0194 null);
0195 } catch (java.io.IOException cannotHappen) {
0196 } catch (ClassNotFoundException cannotHappen) {
0197 }
0198 }
0199
0200 // Query Operations
0201
0202 /**
0203 * Returns the number of key-value mappings in this map.
0204 *
0205 * @return the number of key-value mappings in this map
0206 */
0207 public int size() {
0208 return size;
0209 }
0210
0211 /**
0212 * Returns <tt>true</tt> if this map contains a mapping for the specified
0213 * key.
0214 *
0215 * @param key key whose presence in this map is to be tested
0216 * @return <tt>true</tt> if this map contains a mapping for the
0217 * specified key
0218 * @throws ClassCastException if the specified key cannot be compared
0219 * with the keys currently in the map
0220 * @throws NullPointerException if the specified key is null
0221 * and this map uses natural ordering, or its comparator
0222 * does not permit null keys
0223 */
0224 public boolean containsKey(Object key) {
0225 return getEntry(key) != null;
0226 }
0227
0228 /**
0229 * Returns <tt>true</tt> if this map maps one or more keys to the
0230 * specified value. More formally, returns <tt>true</tt> if and only if
0231 * this map contains at least one mapping to a value <tt>v</tt> such
0232 * that <tt>(value==null ? v==null : value.equals(v))</tt>. This
0233 * operation will probably require time linear in the map size for
0234 * most implementations.
0235 *
0236 * @param value value whose presence in this map is to be tested
0237 * @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
0238 * <tt>false</tt> otherwise
0239 * @since 1.2
0240 */
0241 public boolean containsValue(Object value) {
0242 for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e))
0243 if (valEquals(value, e.value))
0244 return true;
0245 return false;
0246 }
0247
0248 /**
0249 * Returns the value to which the specified key is mapped,
0250 * or {@code null} if this map contains no mapping for the key.
0251 *
0252 * <p>More formally, if this map contains a mapping from a key
0253 * {@code k} to a value {@code v} such that {@code key} compares
0254 * equal to {@code k} according to the map's ordering, then this
0255 * method returns {@code v}; otherwise it returns {@code null}.
0256 * (There can be at most one such mapping.)
0257 *
0258 * <p>A return value of {@code null} does not <i>necessarily</i>
0259 * indicate that the map contains no mapping for the key; it's also
0260 * possible that the map explicitly maps the key to {@code null}.
0261 * The {@link #containsKey containsKey} operation may be used to
0262 * distinguish these two cases.
0263 *
0264 * @throws ClassCastException if the specified key cannot be compared
0265 * with the keys currently in the map
0266 * @throws NullPointerException if the specified key is null
0267 * and this map uses natural ordering, or its comparator
0268 * does not permit null keys
0269 */
0270 public V get(Object key) {
0271 Entry<K, V> p = getEntry(key);
0272 return (p == null ? null : p.value);
0273 }
0274
0275 public Comparator<? super K> comparator() {
0276 return comparator;
0277 }
0278
0279 /**
0280 * @throws NoSuchElementException {@inheritDoc}
0281 */
0282 public K firstKey() {
0283 return key(getFirstEntry());
0284 }
0285
0286 /**
0287 * @throws NoSuchElementException {@inheritDoc}
0288 */
0289 public K lastKey() {
0290 return key(getLastEntry());
0291 }
0292
0293 /**
0294 * Copies all of the mappings from the specified map to this map.
0295 * These mappings replace any mappings that this map had for any
0296 * of the keys currently in the specified map.
0297 *
0298 * @param map mappings to be stored in this map
0299 * @throws ClassCastException if the class of a key or value in
0300 * the specified map prevents it from being stored in this map
0301 * @throws NullPointerException if the specified map is null or
0302 * the specified map contains a null key and this map does not
0303 * permit null keys
0304 */
0305 public void putAll(Map<? extends K, ? extends V> map) {
0306 int mapSize = map.size();
0307 if (size == 0 && mapSize != 0 && map instanceof SortedMap) {
0308 Comparator c = ((SortedMap) map).comparator();
0309 if (c == comparator || (c != null && c.equals(comparator))) {
0310 ++modCount;
0311 try {
0312 buildFromSorted(mapSize, map.entrySet().iterator(),
0313 null, null);
0314 } catch (java.io.IOException cannotHappen) {
0315 } catch (ClassNotFoundException cannotHappen) {
0316 }
0317 return;
0318 }
0319 }
0320 super .putAll(map);
0321 }
0322
0323 /**
0324 * Returns this map's entry for the given key, or <tt>null</tt> if the map
0325 * does not contain an entry for the key.
0326 *
0327 * @return this map's entry for the given key, or <tt>null</tt> if the map
0328 * does not contain an entry for the key
0329 * @throws ClassCastException if the specified key cannot be compared
0330 * with the keys currently in the map
0331 * @throws NullPointerException if the specified key is null
0332 * and this map uses natural ordering, or its comparator
0333 * does not permit null keys
0334 */
0335 final Entry<K, V> getEntry(Object key) {
0336 // Offload comparator-based version for sake of performance
0337 if (comparator != null)
0338 return getEntryUsingComparator(key);
0339 if (key == null)
0340 throw new NullPointerException();
0341 Comparable<? super K> k = (Comparable<? super K>) key;
0342 Entry<K, V> p = root;
0343 while (p != null) {
0344 int cmp = k.compareTo(p.key);
0345 if (cmp < 0)
0346 p = p.left;
0347 else if (cmp > 0)
0348 p = p.right;
0349 else
0350 return p;
0351 }
0352 return null;
0353 }
0354
0355 /**
0356 * Version of getEntry using comparator. Split off from getEntry
0357 * for performance. (This is not worth doing for most methods,
0358 * that are less dependent on comparator performance, but is
0359 * worthwhile here.)
0360 */
0361 final Entry<K, V> getEntryUsingComparator(Object key) {
0362 K k = (K) key;
0363 Comparator<? super K> cpr = comparator;
0364 if (cpr != null) {
0365 Entry<K, V> p = root;
0366 while (p != null) {
0367 int cmp = cpr.compare(k, p.key);
0368 if (cmp < 0)
0369 p = p.left;
0370 else if (cmp > 0)
0371 p = p.right;
0372 else
0373 return p;
0374 }
0375 }
0376 return null;
0377 }
0378
0379 /**
0380 * Gets the entry corresponding to the specified key; if no such entry
0381 * exists, returns the entry for the least key greater than the specified
0382 * key; if no such entry exists (i.e., the greatest key in the Tree is less
0383 * than the specified key), returns <tt>null</tt>.
0384 */
0385 final Entry<K, V> getCeilingEntry(K key) {
0386 Entry<K, V> p = root;
0387 while (p != null) {
0388 int cmp = compare(key, p.key);
0389 if (cmp < 0) {
0390 if (p.left != null)
0391 p = p.left;
0392 else
0393 return p;
0394 } else if (cmp > 0) {
0395 if (p.right != null) {
0396 p = p.right;
0397 } else {
0398 Entry<K, V> parent = p.parent;
0399 Entry<K, V> ch = p;
0400 while (parent != null && ch == parent.right) {
0401 ch = parent;
0402 parent = parent.parent;
0403 }
0404 return parent;
0405 }
0406 } else
0407 return p;
0408 }
0409 return null;
0410 }
0411
0412 /**
0413 * Gets the entry corresponding to the specified key; if no such entry
0414 * exists, returns the entry for the greatest key less than the specified
0415 * key; if no such entry exists, returns <tt>null</tt>.
0416 */
0417 final Entry<K, V> getFloorEntry(K key) {
0418 Entry<K, V> p = root;
0419 while (p != null) {
0420 int cmp = compare(key, p.key);
0421 if (cmp > 0) {
0422 if (p.right != null)
0423 p = p.right;
0424 else
0425 return p;
0426 } else if (cmp < 0) {
0427 if (p.left != null) {
0428 p = p.left;
0429 } else {
0430 Entry<K, V> parent = p.parent;
0431 Entry<K, V> ch = p;
0432 while (parent != null && ch == parent.left) {
0433 ch = parent;
0434 parent = parent.parent;
0435 }
0436 return parent;
0437 }
0438 } else
0439 return p;
0440
0441 }
0442 return null;
0443 }
0444
0445 /**
0446 * Gets the entry for the least key greater than the specified
0447 * key; if no such entry exists, returns the entry for the least
0448 * key greater than the specified key; if no such entry exists
0449 * returns <tt>null</tt>.
0450 */
0451 final Entry<K, V> getHigherEntry(K key) {
0452 Entry<K, V> p = root;
0453 while (p != null) {
0454 int cmp = compare(key, p.key);
0455 if (cmp < 0) {
0456 if (p.left != null)
0457 p = p.left;
0458 else
0459 return p;
0460 } else {
0461 if (p.right != null) {
0462 p = p.right;
0463 } else {
0464 Entry<K, V> parent = p.parent;
0465 Entry<K, V> ch = p;
0466 while (parent != null && ch == parent.right) {
0467 ch = parent;
0468 parent = parent.parent;
0469 }
0470 return parent;
0471 }
0472 }
0473 }
0474 return null;
0475 }
0476
0477 /**
0478 * Returns the entry for the greatest key less than the specified key; if
0479 * no such entry exists (i.e., the least key in the Tree is greater than
0480 * the specified key), returns <tt>null</tt>.
0481 */
0482 final Entry<K, V> getLowerEntry(K key) {
0483 Entry<K, V> p = root;
0484 while (p != null) {
0485 int cmp = compare(key, p.key);
0486 if (cmp > 0) {
0487 if (p.right != null)
0488 p = p.right;
0489 else
0490 return p;
0491 } else {
0492 if (p.left != null) {
0493 p = p.left;
0494 } else {
0495 Entry<K, V> parent = p.parent;
0496 Entry<K, V> ch = p;
0497 while (parent != null && ch == parent.left) {
0498 ch = parent;
0499 parent = parent.parent;
0500 }
0501 return parent;
0502 }
0503 }
0504 }
0505 return null;
0506 }
0507
0508 /**
0509 * Associates the specified value with the specified key in this map.
0510 * If the map previously contained a mapping for the key, the old
0511 * value is replaced.
0512 *
0513 * @param key key with which the specified value is to be associated
0514 * @param value value to be associated with the specified key
0515 *
0516 * @return the previous value associated with <tt>key</tt>, or
0517 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
0518 * (A <tt>null</tt> return can also indicate that the map
0519 * previously associated <tt>null</tt> with <tt>key</tt>.)
0520 * @throws ClassCastException if the specified key cannot be compared
0521 * with the keys currently in the map
0522 * @throws NullPointerException if the specified key is null
0523 * and this map uses natural ordering, or its comparator
0524 * does not permit null keys
0525 */
0526 public V put(K key, V value) {
0527 Entry<K, V> t = root;
0528 if (t == null) {
0529 // TBD:
0530 // 5045147: (coll) Adding null to an empty TreeSet should
0531 // throw NullPointerException
0532 //
0533 // compare(key, key); // type check
0534 root = new Entry<K, V>(key, value, null);
0535 size = 1;
0536 modCount++;
0537 return null;
0538 }
0539 int cmp;
0540 Entry<K, V> parent;
0541 // split comparator and comparable paths
0542 Comparator<? super K> cpr = comparator;
0543 if (cpr != null) {
0544 do {
0545 parent = t;
0546 cmp = cpr.compare(key, t.key);
0547 if (cmp < 0)
0548 t = t.left;
0549 else if (cmp > 0)
0550 t = t.right;
0551 else
0552 return t.setValue(value);
0553 } while (t != null);
0554 } else {
0555 if (key == null)
0556 throw new NullPointerException();
0557 Comparable<? super K> k = (Comparable<? super K>) key;
0558 do {
0559 parent = t;
0560 cmp = k.compareTo(t.key);
0561 if (cmp < 0)
0562 t = t.left;
0563 else if (cmp > 0)
0564 t = t.right;
0565 else
0566 return t.setValue(value);
0567 } while (t != null);
0568 }
0569 Entry<K, V> e = new Entry<K, V>(key, value, parent);
0570 if (cmp < 0)
0571 parent.left = e;
0572 else
0573 parent.right = e;
0574 fixAfterInsertion(e);
0575 size++;
0576 modCount++;
0577 return null;
0578 }
0579
0580 /**
0581 * Removes the mapping for this key from this TreeMap if present.
0582 *
0583 * @param key key for which mapping should be removed
0584 * @return the previous value associated with <tt>key</tt>, or
0585 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
0586 * (A <tt>null</tt> return can also indicate that the map
0587 * previously associated <tt>null</tt> with <tt>key</tt>.)
0588 * @throws ClassCastException if the specified key cannot be compared
0589 * with the keys currently in the map
0590 * @throws NullPointerException if the specified key is null
0591 * and this map uses natural ordering, or its comparator
0592 * does not permit null keys
0593 */
0594 public V remove(Object key) {
0595 Entry<K, V> p = getEntry(key);
0596 if (p == null)
0597 return null;
0598
0599 V oldValue = p.value;
0600 deleteEntry(p);
0601 return oldValue;
0602 }
0603
0604 /**
0605 * Removes all of the mappings from this map.
0606 * The map will be empty after this call returns.
0607 */
0608 public void clear() {
0609 modCount++;
0610 size = 0;
0611 root = null;
0612 }
0613
0614 /**
0615 * Returns a shallow copy of this <tt>TreeMap</tt> instance. (The keys and
0616 * values themselves are not cloned.)
0617 *
0618 * @return a shallow copy of this map
0619 */
0620 public Object clone() {
0621 TreeMap<K, V> clone = null;
0622 try {
0623 clone = (TreeMap<K, V>) super .clone();
0624 } catch (CloneNotSupportedException e) {
0625 throw new InternalError();
0626 }
0627
0628 // Put clone into "virgin" state (except for comparator)
0629 clone.root = null;
0630 clone.size = 0;
0631 clone.modCount = 0;
0632 clone.entrySet = null;
0633 clone.navigableKeySet = null;
0634 clone.descendingMap = null;
0635
0636 // Initialize clone with our mappings
0637 try {
0638 clone.buildFromSorted(size, entrySet().iterator(), null,
0639 null);
0640 } catch (java.io.IOException cannotHappen) {
0641 } catch (ClassNotFoundException cannotHappen) {
0642 }
0643
0644 return clone;
0645 }
0646
0647 // NavigableMap API methods
0648
0649 /**
0650 * @since 1.6
0651 */
0652 public Map.Entry<K, V> firstEntry() {
0653 return exportEntry(getFirstEntry());
0654 }
0655
0656 /**
0657 * @since 1.6
0658 */
0659 public Map.Entry<K, V> lastEntry() {
0660 return exportEntry(getLastEntry());
0661 }
0662
0663 /**
0664 * @since 1.6
0665 */
0666 public Map.Entry<K, V> pollFirstEntry() {
0667 Entry<K, V> p = getFirstEntry();
0668 Map.Entry<K, V> result = exportEntry(p);
0669 if (p != null)
0670 deleteEntry(p);
0671 return result;
0672 }
0673
0674 /**
0675 * @since 1.6
0676 */
0677 public Map.Entry<K, V> pollLastEntry() {
0678 Entry<K, V> p = getLastEntry();
0679 Map.Entry<K, V> result = exportEntry(p);
0680 if (p != null)
0681 deleteEntry(p);
0682 return result;
0683 }
0684
0685 /**
0686 * @throws ClassCastException {@inheritDoc}
0687 * @throws NullPointerException if the specified key is null
0688 * and this map uses natural ordering, or its comparator
0689 * does not permit null keys
0690 * @since 1.6
0691 */
0692 public Map.Entry<K, V> lowerEntry(K key) {
0693 return exportEntry(getLowerEntry(key));
0694 }
0695
0696 /**
0697 * @throws ClassCastException {@inheritDoc}
0698 * @throws NullPointerException if the specified key is null
0699 * and this map uses natural ordering, or its comparator
0700 * does not permit null keys
0701 * @since 1.6
0702 */
0703 public K lowerKey(K key) {
0704 return keyOrNull(getLowerEntry(key));
0705 }
0706
0707 /**
0708 * @throws ClassCastException {@inheritDoc}
0709 * @throws NullPointerException if the specified key is null
0710 * and this map uses natural ordering, or its comparator
0711 * does not permit null keys
0712 * @since 1.6
0713 */
0714 public Map.Entry<K, V> floorEntry(K key) {
0715 return exportEntry(getFloorEntry(key));
0716 }
0717
0718 /**
0719 * @throws ClassCastException {@inheritDoc}
0720 * @throws NullPointerException if the specified key is null
0721 * and this map uses natural ordering, or its comparator
0722 * does not permit null keys
0723 * @since 1.6
0724 */
0725 public K floorKey(K key) {
0726 return keyOrNull(getFloorEntry(key));
0727 }
0728
0729 /**
0730 * @throws ClassCastException {@inheritDoc}
0731 * @throws NullPointerException if the specified key is null
0732 * and this map uses natural ordering, or its comparator
0733 * does not permit null keys
0734 * @since 1.6
0735 */
0736 public Map.Entry<K, V> ceilingEntry(K key) {
0737 return exportEntry(getCeilingEntry(key));
0738 }
0739
0740 /**
0741 * @throws ClassCastException {@inheritDoc}
0742 * @throws NullPointerException if the specified key is null
0743 * and this map uses natural ordering, or its comparator
0744 * does not permit null keys
0745 * @since 1.6
0746 */
0747 public K ceilingKey(K key) {
0748 return keyOrNull(getCeilingEntry(key));
0749 }
0750
0751 /**
0752 * @throws ClassCastException {@inheritDoc}
0753 * @throws NullPointerException if the specified key is null
0754 * and this map uses natural ordering, or its comparator
0755 * does not permit null keys
0756 * @since 1.6
0757 */
0758 public Map.Entry<K, V> higherEntry(K key) {
0759 return exportEntry(getHigherEntry(key));
0760 }
0761
0762 /**
0763 * @throws ClassCastException {@inheritDoc}
0764 * @throws NullPointerException if the specified key is null
0765 * and this map uses natural ordering, or its comparator
0766 * does not permit null keys
0767 * @since 1.6
0768 */
0769 public K higherKey(K key) {
0770 return keyOrNull(getHigherEntry(key));
0771 }
0772
0773 // Views
0774
0775 /**
0776 * Fields initialized to contain an instance of the entry set view
0777 * the first time this view is requested. Views are stateless, so
0778 * there's no reason to create more than one.
0779 */
0780 private transient EntrySet entrySet = null;
0781 private transient KeySet<K> navigableKeySet = null;
0782 private transient NavigableMap<K, V> descendingMap = null;
0783
0784 /**
0785 * Returns a {@link Set} view of the keys contained in this map.
0786 * The set's iterator returns the keys in ascending order.
0787 * The set is backed by the map, so changes to the map are
0788 * reflected in the set, and vice-versa. If the map is modified
0789 * while an iteration over the set is in progress (except through
0790 * the iterator's own <tt>remove</tt> operation), the results of
0791 * the iteration are undefined. The set supports element removal,
0792 * which removes the corresponding mapping from the map, via the
0793 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
0794 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
0795 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
0796 * operations.
0797 */
0798 public Set<K> keySet() {
0799 return navigableKeySet();
0800 }
0801
0802 /**
0803 * @since 1.6
0804 */
0805 public NavigableSet<K> navigableKeySet() {
0806 KeySet<K> nks = navigableKeySet;
0807 return (nks != null) ? nks
0808 : (navigableKeySet = new KeySet(this ));
0809 }
0810
0811 /**
0812 * @since 1.6
0813 */
0814 public NavigableSet<K> descendingKeySet() {
0815 return descendingMap().navigableKeySet();
0816 }
0817
0818 /**
0819 * Returns a {@link Collection} view of the values contained in this map.
0820 * The collection's iterator returns the values in ascending order
0821 * of the corresponding keys.
0822 * The collection is backed by the map, so changes to the map are
0823 * reflected in the collection, and vice-versa. If the map is
0824 * modified while an iteration over the collection is in progress
0825 * (except through the iterator's own <tt>remove</tt> operation),
0826 * the results of the iteration are undefined. The collection
0827 * supports element removal, which removes the corresponding
0828 * mapping from the map, via the <tt>Iterator.remove</tt>,
0829 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
0830 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
0831 * support the <tt>add</tt> or <tt>addAll</tt> operations.
0832 */
0833 public Collection<V> values() {
0834 Collection<V> vs = values;
0835 return (vs != null) ? vs : (values = new Values());
0836 }
0837
0838 /**
0839 * Returns a {@link Set} view of the mappings contained in this map.
0840 * The set's iterator returns the entries in ascending key order.
0841 * The set is backed by the map, so changes to the map are
0842 * reflected in the set, and vice-versa. If the map is modified
0843 * while an iteration over the set is in progress (except through
0844 * the iterator's own <tt>remove</tt> operation, or through the
0845 * <tt>setValue</tt> operation on a map entry returned by the
0846 * iterator) the results of the iteration are undefined. The set
0847 * supports element removal, which removes the corresponding
0848 * mapping from the map, via the <tt>Iterator.remove</tt>,
0849 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
0850 * <tt>clear</tt> operations. It does not support the
0851 * <tt>add</tt> or <tt>addAll</tt> operations.
0852 */
0853 public Set<Map.Entry<K, V>> entrySet() {
0854 EntrySet es = entrySet;
0855 return (es != null) ? es : (entrySet = new EntrySet());
0856 }
0857
0858 /**
0859 * @since 1.6
0860 */
0861 public NavigableMap<K, V> descendingMap() {
0862 NavigableMap<K, V> km = descendingMap;
0863 return (km != null) ? km
0864 : (descendingMap = new DescendingSubMap(this , true,
0865 null, true, true, null, true));
0866 }
0867
0868 /**
0869 * @throws ClassCastException {@inheritDoc}
0870 * @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
0871 * null and this map uses natural ordering, or its comparator
0872 * does not permit null keys
0873 * @throws IllegalArgumentException {@inheritDoc}
0874 * @since 1.6
0875 */
0876 public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive,
0877 K toKey, boolean toInclusive) {
0878 return new AscendingSubMap(this , false, fromKey, fromInclusive,
0879 false, toKey, toInclusive);
0880 }
0881
0882 /**
0883 * @throws ClassCastException {@inheritDoc}
0884 * @throws NullPointerException if <tt>toKey</tt> is null
0885 * and this map uses natural ordering, or its comparator
0886 * does not permit null keys
0887 * @throws IllegalArgumentException {@inheritDoc}
0888 * @since 1.6
0889 */
0890 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
0891 return new AscendingSubMap(this , true, null, true, false,
0892 toKey, inclusive);
0893 }
0894
0895 /**
0896 * @throws ClassCastException {@inheritDoc}
0897 * @throws NullPointerException if <tt>fromKey</tt> is null
0898 * and this map uses natural ordering, or its comparator
0899 * does not permit null keys
0900 * @throws IllegalArgumentException {@inheritDoc}
0901 * @since 1.6
0902 */
0903 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
0904 return new AscendingSubMap(this , false, fromKey, inclusive,
0905 true, null, true);
0906 }
0907
0908 /**
0909 * @throws ClassCastException {@inheritDoc}
0910 * @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
0911 * null and this map uses natural ordering, or its comparator
0912 * does not permit null keys
0913 * @throws IllegalArgumentException {@inheritDoc}
0914 */
0915 public SortedMap<K, V> subMap(K fromKey, K toKey) {
0916 return subMap(fromKey, true, toKey, false);
0917 }
0918
0919 /**
0920 * @throws ClassCastException {@inheritDoc}
0921 * @throws NullPointerException if <tt>toKey</tt> is null
0922 * and this map uses natural ordering, or its comparator
0923 * does not permit null keys
0924 * @throws IllegalArgumentException {@inheritDoc}
0925 */
0926 public SortedMap<K, V> headMap(K toKey) {
0927 return headMap(toKey, false);
0928 }
0929
0930 /**
0931 * @throws ClassCastException {@inheritDoc}
0932 * @throws NullPointerException if <tt>fromKey</tt> is null
0933 * and this map uses natural ordering, or its comparator
0934 * does not permit null keys
0935 * @throws IllegalArgumentException {@inheritDoc}
0936 */
0937 public SortedMap<K, V> tailMap(K fromKey) {
0938 return tailMap(fromKey, true);
0939 }
0940
0941 // View class support
0942
0943 class Values extends AbstractCollection<V> {
0944 public Iterator<V> iterator() {
0945 return new ValueIterator(getFirstEntry());
0946 }
0947
0948 public int size() {
0949 return TreeMap.this .size();
0950 }
0951
0952 public boolean contains(Object o) {
0953 return TreeMap.this .containsValue(o);
0954 }
0955
0956 public boolean remove(Object o) {
0957 for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
0958 if (valEquals(e.getValue(), o)) {
0959 deleteEntry(e);
0960 return true;
0961 }
0962 }
0963 return false;
0964 }
0965
0966 public void clear() {
0967 TreeMap.this .clear();
0968 }
0969 }
0970
0971 class EntrySet extends AbstractSet<Map.Entry<K, V>> {
0972 public Iterator<Map.Entry<K, V>> iterator() {
0973 return new EntryIterator(getFirstEntry());
0974 }
0975
0976 public boolean contains(Object o) {
0977 if (!(o instanceof Map.Entry))
0978 return false;
0979 Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
0980 V value = entry.getValue();
0981 Entry<K, V> p = getEntry(entry.getKey());
0982 return p != null && valEquals(p.getValue(), value);
0983 }
0984
0985 public boolean remove(Object o) {
0986 if (!(o instanceof Map.Entry))
0987 return false;
0988 Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
0989 V value = entry.getValue();
0990 Entry<K, V> p = getEntry(entry.getKey());
0991 if (p != null && valEquals(p.getValue(), value)) {
0992 deleteEntry(p);
0993 return true;
0994 }
0995 return false;
0996 }
0997
0998 public int size() {
0999 return TreeMap.this .size();
1000 }
1001
1002 public void clear() {
1003 TreeMap.this .clear();
1004 }
1005 }
1006
1007 /*
1008 * Unlike Values and EntrySet, the KeySet class is static,
1009 * delegating to a NavigableMap to allow use by SubMaps, which
1010 * outweighs the ugliness of needing type-tests for the following
1011 * Iterator methods that are defined appropriately in main versus
1012 * submap classes.
1013 */
1014
1015 Iterator<K> keyIterator() {
1016 return new KeyIterator(getFirstEntry());
1017 }
1018
1019 Iterator<K> descendingKeyIterator() {
1020 return new DescendingKeyIterator(getFirstEntry());
1021 }
1022
1023 static final class KeySet<E> extends AbstractSet<E> implements
1024 NavigableSet<E> {
1025 private final NavigableMap<E, Object> m;
1026
1027 KeySet(NavigableMap<E, Object> map) {
1028 m = map;
1029 }
1030
1031 public Iterator<E> iterator() {
1032 if (m instanceof TreeMap)
1033 return ((TreeMap<E, Object>) m).keyIterator();
1034 else
1035 return (Iterator<E>) (((TreeMap.NavigableSubMap) m)
1036 .keyIterator());
1037 }
1038
1039 public Iterator<E> descendingIterator() {
1040 if (m instanceof TreeMap)
1041 return ((TreeMap<E, Object>) m).descendingKeyIterator();
1042 else
1043 return (Iterator<E>) (((TreeMap.NavigableSubMap) m)
1044 .descendingKeyIterator());
1045 }
1046
1047 public int size() {
1048 return m.size();
1049 }
1050
1051 public boolean isEmpty() {
1052 return m.isEmpty();
1053 }
1054
1055 public boolean contains(Object o) {
1056 return m.containsKey(o);
1057 }
1058
1059 public void clear() {
1060 m.clear();
1061 }
1062
1063 public E lower(E e) {
1064 return m.lowerKey(e);
1065 }
1066
1067 public E floor(E e) {
1068 return m.floorKey(e);
1069 }
1070
1071 public E ceiling(E e) {
1072 return m.ceilingKey(e);
1073 }
1074
1075 public E higher(E e) {
1076 return m.higherKey(e);
1077 }
1078
1079 public E first() {
1080 return m.firstKey();
1081 }
1082
1083 public E last() {
1084 return m.lastKey();
1085 }
1086
1087 public Comparator<? super E> comparator() {
1088 return m.comparator();
1089 }
1090
1091 public E pollFirst() {
1092 Map.Entry<E, Object> e = m.pollFirstEntry();
1093 return e == null ? null : e.getKey();
1094 }
1095
1096 public E pollLast() {
1097 Map.Entry<E, Object> e = m.pollLastEntry();
1098 return e == null ? null : e.getKey();
1099 }
1100
1101 public boolean remove(Object o) {
1102 int oldSize = size();
1103 m.remove(o);
1104 return size() != oldSize;
1105 }
1106
1107 public NavigableSet<E> subSet(E fromElement,
1108 boolean fromInclusive, E toElement, boolean toInclusive) {
1109 return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
1110 toElement, toInclusive));
1111 }
1112
1113 public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1114 return new TreeSet<E>(m.headMap(toElement, inclusive));
1115 }
1116
1117 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1118 return new TreeSet<E>(m.tailMap(fromElement, inclusive));
1119 }
1120
1121 public SortedSet<E> subSet(E fromElement, E toElement) {
1122 return subSet(fromElement, true, toElement, false);
1123 }
1124
1125 public SortedSet<E> headSet(E toElement) {
1126 return headSet(toElement, false);
1127 }
1128
1129 public SortedSet<E> tailSet(E fromElement) {
1130 return tailSet(fromElement, true);
1131 }
1132
1133 public NavigableSet<E> descendingSet() {
1134 return new TreeSet(m.descendingMap());
1135 }
1136 }
1137
1138 /**
1139 * Base class for TreeMap Iterators
1140 */
1141 abstract class PrivateEntryIterator<T> implements Iterator<T> {
1142 Entry<K, V> next;
1143 Entry<K, V> lastReturned;
1144 int expectedModCount;
1145
1146 PrivateEntryIterator(Entry<K, V> first) {
1147 expectedModCount = modCount;
1148 lastReturned = null;
1149 next = first;
1150 }
1151
1152 public final boolean hasNext() {
1153 return next != null;
1154 }
1155
1156 final Entry<K, V> nextEntry() {
1157 Entry<K, V> e = next;
1158 if (e == null)
1159 throw new NoSuchElementException();
1160 if (modCount != expectedModCount)
1161 throw new ConcurrentModificationException();
1162 next = successor(e);
1163 lastReturned = e;
1164 return e;
1165 }
1166
1167 final Entry<K, V> prevEntry() {
1168 Entry<K, V> e = next;
1169 if (e == null)
1170 throw new NoSuchElementException();
1171 if (modCount != expectedModCount)
1172 throw new ConcurrentModificationException();
1173 next = predecessor(e);
1174 lastReturned = e;
1175 return e;
1176 }
1177
1178 public void remove() {
1179 if (lastReturned == null)
1180 throw new IllegalStateException();
1181 if (modCount != expectedModCount)
1182 throw new ConcurrentModificationException();
1183 // deleted entries are replaced by their successors
1184 if (lastReturned.left != null && lastReturned.right != null)
1185 next = lastReturned;
1186 deleteEntry(lastReturned);
1187 expectedModCount = modCount;
1188 lastReturned = null;
1189 }
1190 }
1191
1192 final class EntryIterator extends
1193 PrivateEntryIterator<Map.Entry<K, V>> {
1194 EntryIterator(Entry<K, V> first) {
1195 super (first);
1196 }
1197
1198 public Map.Entry<K, V> next() {
1199 return nextEntry();
1200 }
1201 }
1202
1203 final class ValueIterator extends PrivateEntryIterator<V> {
1204 ValueIterator(Entry<K, V> first) {
1205 super (first);
1206 }
1207
1208 public V next() {
1209 return nextEntry().value;
1210 }
1211 }
1212
1213 final class KeyIterator extends PrivateEntryIterator<K> {
1214 KeyIterator(Entry<K, V> first) {
1215 super (first);
1216 }
1217
1218 public K next() {
1219 return nextEntry().key;
1220 }
1221 }
1222
1223 final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1224 DescendingKeyIterator(Entry<K, V> first) {
1225 super (first);
1226 }
1227
1228 public K next() {
1229 return prevEntry().key;
1230 }
1231 }
1232
1233 // Little utilities
1234
1235 /**
1236 * Compares two keys using the correct comparison method for this TreeMap.
1237 */
1238 final int compare(Object k1, Object k2) {
1239 return comparator == null ? ((Comparable<? super K>) k1)
1240 .compareTo((K) k2) : comparator.compare((K) k1, (K) k2);
1241 }
1242
1243 /**
1244 * Test two values for equality. Differs from o1.equals(o2) only in
1245 * that it copes with <tt>null</tt> o1 properly.
1246 */
1247 final static boolean valEquals(Object o1, Object o2) {
1248 return (o1 == null ? o2 == null : o1.equals(o2));
1249 }
1250
1251 /**
1252 * Return SimpleImmutableEntry for entry, or null if null
1253 */
1254 static <K, V> Map.Entry<K, V> exportEntry(TreeMap.Entry<K, V> e) {
1255 return e == null ? null
1256 : new AbstractMap.SimpleImmutableEntry<K, V>(e);
1257 }
1258
1259 /**
1260 * Return key for entry, or null if null
1261 */
1262 static <K, V> K keyOrNull(TreeMap.Entry<K, V> e) {
1263 return e == null ? null : e.key;
1264 }
1265
1266 /**
1267 * Returns the key corresponding to the specified Entry.
1268 * @throws NoSuchElementException if the Entry is null
1269 */
1270 static <K> K key(Entry<K, ?> e) {
1271 if (e == null)
1272 throw new NoSuchElementException();
1273 return e.key;
1274 }
1275
1276 // SubMaps
1277
1278 /**
1279 * Dummy value serving as unmatchable fence key for unbounded
1280 * SubMapIterators
1281 */
1282 private static final Object UNBOUNDED = new Object();
1283
1284 /**
1285 * @serial include
1286 */
1287 static abstract class NavigableSubMap<K, V> extends
1288 AbstractMap<K, V> implements NavigableMap<K, V>,
1289 java.io.Serializable {
1290 /**
1291 * The backing map.
1292 */
1293 final TreeMap<K, V> m;
1294
1295 /**
1296 * Endpoints are represented as triples (fromStart, lo,
1297 * loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1298 * true, then the low (absolute) bound is the start of the
1299 * backing map, and the other values are ignored. Otherwise,
1300 * if loInclusive is true, lo is the inclusive bound, else lo
1301 * is the exclusive bound. Similarly for the upper bound.
1302 */
1303 final K lo, hi;
1304 final boolean fromStart, toEnd;
1305 final boolean loInclusive, hiInclusive;
1306
1307 NavigableSubMap(TreeMap<K, V> m, boolean fromStart, K lo,
1308 boolean loInclusive, boolean toEnd, K hi,
1309 boolean hiInclusive) {
1310 if (!fromStart && !toEnd) {
1311 if (m.compare(lo, hi) > 0)
1312 throw new IllegalArgumentException(
1313 "fromKey > toKey");
1314 } else {
1315 if (!fromStart) // type check
1316 m.compare(lo, lo);
1317 if (!toEnd)
1318 m.compare(hi, hi);
1319 }
1320
1321 this .m = m;
1322 this .fromStart = fromStart;
1323 this .lo = lo;
1324 this .loInclusive = loInclusive;
1325 this .toEnd = toEnd;
1326 this .hi = hi;
1327 this .hiInclusive = hiInclusive;
1328 }
1329
1330 // internal utilities
1331
1332 final boolean tooLow(Object key) {
1333 if (!fromStart) {
1334 int c = m.compare(key, lo);
1335 if (c < 0 || (c == 0 && !loInclusive))
1336 return true;
1337 }
1338 return false;
1339 }
1340
1341 final boolean tooHigh(Object key) {
1342 if (!toEnd) {
1343 int c = m.compare(key, hi);
1344 if (c > 0 || (c == 0 && !hiInclusive))
1345 return true;
1346 }
1347 return false;
1348 }
1349
1350 final boolean inRange(Object key) {
1351 return !tooLow(key) && !tooHigh(key);
1352 }
1353
1354 final boolean inClosedRange(Object key) {
1355 return (fromStart || m.compare(key, lo) >= 0)
1356 && (toEnd || m.compare(hi, key) >= 0);
1357 }
1358
1359 final boolean inRange(Object key, boolean inclusive) {
1360 return inclusive ? inRange(key) : inClosedRange(key);
1361 }
1362
1363 /*
1364 * Absolute versions of relation operations.
1365 * Subclasses map to these using like-named "sub"
1366 * versions that invert senses for descending maps
1367 */
1368
1369 final TreeMap.Entry<K, V> absLowest() {
1370 TreeMap.Entry<K, V> e = (fromStart ? m.getFirstEntry()
1371 : (loInclusive ? m.getCeilingEntry(lo) : m
1372 .getHigherEntry(lo)));
1373 return (e == null || tooHigh(e.key)) ? null : e;
1374 }
1375
1376 final TreeMap.Entry<K, V> absHighest() {
1377 TreeMap.Entry<K, V> e = (toEnd ? m.getLastEntry()
1378 : (hiInclusive ? m.getFloorEntry(hi) : m
1379 .getLowerEntry(hi)));
1380 return (e == null || tooLow(e.key)) ? null : e;
1381 }
1382
1383 final TreeMap.Entry<K, V> absCeiling(K key) {
1384 if (tooLow(key))
1385 return absLowest();
1386 TreeMap.Entry<K, V> e = m.getCeilingEntry(key);
1387 return (e == null || tooHigh(e.key)) ? null : e;
1388 }
1389
1390 final TreeMap.Entry<K, V> absHigher(K key) {
1391 if (tooLow(key))
1392 return absLowest();
1393 TreeMap.Entry<K, V> e = m.getHigherEntry(key);
1394 return (e == null || tooHigh(e.key)) ? null : e;
1395 }
1396
1397 final TreeMap.Entry<K, V> absFloor(K key) {
1398 if (tooHigh(key))
1399 return absHighest();
1400 TreeMap.Entry<K, V> e = m.getFloorEntry(key);
1401 return (e == null || tooLow(e.key)) ? null : e;
1402 }
1403
1404 final TreeMap.Entry<K, V> absLower(K key) {
1405 if (tooHigh(key))
1406 return absHighest();
1407 TreeMap.Entry<K, V> e = m.getLowerEntry(key);
1408 return (e == null || tooLow(e.key)) ? null : e;
1409 }
1410
1411 /** Returns the absolute high fence for ascending traversal */
1412 final TreeMap.Entry<K, V> absHighFence() {
1413 return (toEnd ? null : (hiInclusive ? m.getHigherEntry(hi)
1414 : m.getCeilingEntry(hi)));
1415 }
1416
1417 /** Return the absolute low fence for descending traversal */
1418 final TreeMap.Entry<K, V> absLowFence() {
1419 return (fromStart ? null : (loInclusive ? m
1420 .getLowerEntry(lo) : m.getFloorEntry(lo)));
1421 }
1422
1423 // Abstract methods defined in ascending vs descending classes
1424 // These relay to the appropriate absolute versions
1425
1426 abstract TreeMap.Entry<K, V> subLowest();
1427
1428 abstract TreeMap.Entry<K, V> subHighest();
1429
1430 abstract TreeMap.Entry<K, V> subCeiling(K key);
1431
1432 abstract TreeMap.Entry<K, V> subHigher(K key);
1433
1434 abstract TreeMap.Entry<K, V> subFloor(K key);
1435
1436 abstract TreeMap.Entry<K, V> subLower(K key);
1437
1438 /** Returns ascending iterator from the perspective of this submap */
1439 abstract Iterator<K> keyIterator();
1440
1441 /** Returns descending iterator from the perspective of this submap */
1442 abstract Iterator<K> descendingKeyIterator();
1443
1444 // public methods
1445
1446 public boolean isEmpty() {
1447 return (fromStart && toEnd) ? m.isEmpty() : entrySet()
1448 .isEmpty();
1449 }
1450
1451 public int size() {
1452 return (fromStart && toEnd) ? m.size() : entrySet().size();
1453 }
1454
1455 public final boolean containsKey(Object key) {
1456 return inRange(key) && m.containsKey(key);
1457 }
1458
1459 public final V put(K key, V value) {
1460 if (!inRange(key))
1461 throw new IllegalArgumentException("key out of range");
1462 return m.put(key, value);
1463 }
1464
1465 public final V get(Object key) {
1466 return !inRange(key) ? null : m.get(key);
1467 }
1468
1469 public final V remove(Object key) {
1470 return !inRange(key) ? null : m.remove(key);
1471 }
1472
1473 public final Map.Entry<K, V> ceilingEntry(K key) {
1474 return exportEntry(subCeiling(key));
1475 }
1476
1477 public final K ceilingKey(K key) {
1478 return keyOrNull(subCeiling(key));
1479 }
1480
1481 public final Map.Entry<K, V> higherEntry(K key) {
1482 return exportEntry(subHigher(key));
1483 }
1484
1485 public final K higherKey(K key) {
1486 return keyOrNull(subHigher(key));
1487 }
1488
1489 public final Map.Entry<K, V> floorEntry(K key) {
1490 return exportEntry(subFloor(key));
1491 }
1492
1493 public final K floorKey(K key) {
1494 return keyOrNull(subFloor(key));
1495 }
1496
1497 public final Map.Entry<K, V> lowerEntry(K key) {
1498 return exportEntry(subLower(key));
1499 }
1500
1501 public final K lowerKey(K key) {
1502 return keyOrNull(subLower(key));
1503 }
1504
1505 public final K firstKey() {
1506 return key(subLowest());
1507 }
1508
1509 public final K lastKey() {
1510 return key(subHighest());
1511 }
1512
1513 public final Map.Entry<K, V> firstEntry() {
1514 return exportEntry(subLowest());
1515 }
1516
1517 public final Map.Entry<K, V> lastEntry() {
1518 return exportEntry(subHighest());
1519 }
1520
1521 public final Map.Entry<K, V> pollFirstEntry() {
1522 TreeMap.Entry<K, V> e = subLowest();
1523 Map.Entry<K, V> result = exportEntry(e);
1524 if (e != null)
1525 m.deleteEntry(e);
1526 return result;
1527 }
1528
1529 public final Map.Entry<K, V> pollLastEntry() {
1530 TreeMap.Entry<K, V> e = subHighest();
1531 Map.Entry<K, V> result = exportEntry(e);
1532 if (e != null)
1533 m.deleteEntry(e);
1534 return result;
1535 }
1536
1537 // Views
1538 transient NavigableMap<K, V> descendingMapView = null;
1539 transient EntrySetView entrySetView = null;
1540 transient KeySet<K> navigableKeySetView = null;
1541
1542 public final NavigableSet<K> navigableKeySet() {
1543 KeySet<K> nksv = navigableKeySetView;
1544 return (nksv != null) ? nksv
1545 : (navigableKeySetView = new TreeMap.KeySet(this ));
1546 }
1547
1548 public final Set<K> keySet() {
1549 return navigableKeySet();
1550 }
1551
1552 public NavigableSet<K> descendingKeySet() {
1553 return descendingMap().navigableKeySet();
1554 }
1555
1556 public final SortedMap<K, V> subMap(K fromKey, K toKey) {
1557 return subMap(fromKey, true, toKey, false);
1558 }
1559
1560 public final SortedMap<K, V> headMap(K toKey) {
1561 return headMap(toKey, false);
1562 }
1563
1564 public final SortedMap<K, V> tailMap(K fromKey) {
1565 return tailMap(fromKey, true);
1566 }
1567
1568 // View classes
1569
1570 abstract class EntrySetView extends
1571 AbstractSet<Map.Entry<K, V>> {
1572 private transient int size = -1, sizeModCount;
1573
1574 public int size() {
1575 if (fromStart && toEnd)
1576 return m.size();
1577 if (size == -1 || sizeModCount != m.modCount) {
1578 sizeModCount = m.modCount;
1579 size = 0;
1580 Iterator i = iterator();
1581 while (i.hasNext()) {
1582 size++;
1583 i.next();
1584 }
1585 }
1586 return size;
1587 }
1588
1589 public boolean isEmpty() {
1590 TreeMap.Entry<K, V> n = absLowest();
1591 return n == null || tooHigh(n.key);
1592 }
1593
1594 public boolean contains(Object o) {
1595 if (!(o instanceof Map.Entry))
1596 return false;
1597 Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
1598 K key = entry.getKey();
1599 if (!inRange(key))
1600 return false;
1601 TreeMap.Entry node = m.getEntry(key);
1602 return node != null
1603 && valEquals(node.getValue(), entry.getValue());
1604 }
1605
1606 public boolean remove(Object o) {
1607 if (!(o instanceof Map.Entry))
1608 return false;
1609 Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
1610 K key = entry.getKey();
1611 if (!inRange(key))
1612 return false;
1613 TreeMap.Entry<K, V> node = m.getEntry(key);
1614 if (node != null
1615 && valEquals(node.getValue(), entry.getValue())) {
1616 m.deleteEntry(node);
1617 return true;
1618 }
1619 return false;
1620 }
1621 }
1622
1623 /**
1624 * Iterators for SubMaps
1625 */
1626 abstract class SubMapIterator<T> implements Iterator<T> {
1627 TreeMap.Entry<K, V> lastReturned;
1628 TreeMap.Entry<K, V> next;
1629 final Object fenceKey;
1630 int expectedModCount;
1631
1632 SubMapIterator(TreeMap.Entry<K, V> first,
1633 TreeMap.Entry<K, V> fence) {
1634 expectedModCount = m.modCount;
1635 lastReturned = null;
1636 next = first;
1637 fenceKey = fence == null ? UNBOUNDED : fence.key;
1638 }
1639
1640 public final boolean hasNext() {
1641 return next != null && next.key != fenceKey;
1642 }
1643
1644 final TreeMap.Entry<K, V> nextEntry() {
1645 TreeMap.Entry<K, V> e = next;
1646 if (e == null || e.key == fenceKey)
1647 throw new NoSuchElementException();
1648 if (m.modCount != expectedModCount)
1649 throw new ConcurrentModificationException();
1650 next = successor(e);
1651 lastReturned = e;
1652 return e;
1653 }
1654
1655 final TreeMap.Entry<K, V> prevEntry() {
1656 TreeMap.Entry<K, V> e = next;
1657 if (e == null || e.key == fenceKey)
1658 throw new NoSuchElementException();
1659 if (m.modCount != expectedModCount)
1660 throw new ConcurrentModificationException();
1661 next = predecessor(e);
1662 lastReturned = e;
1663 return e;
1664 }
1665
1666 final void removeAscending() {
1667 if (lastReturned == null)
1668 throw new IllegalStateException();
1669 if (m.modCount != expectedModCount)
1670 throw new ConcurrentModificationException();
1671 // deleted entries are replaced by their successors
1672 if (lastReturned.left != null
1673 && lastReturned.right != null)
1674 next = lastReturned;
1675 m.deleteEntry(lastReturned);
1676 lastReturned = null;
1677 expectedModCount = m.modCount;
1678 }
1679
1680 final void removeDescending() {
1681 if (lastReturned == null)
1682 throw new IllegalStateException();
1683 if (m.modCount != expectedModCount)
1684 throw new ConcurrentModificationException();
1685 m.deleteEntry(lastReturned);
1686 lastReturned = null;
1687 expectedModCount = m.modCount;
1688 }
1689
1690 }
1691
1692 final class SubMapEntryIterator extends
1693 SubMapIterator<Map.Entry<K, V>> {
1694 SubMapEntryIterator(TreeMap.Entry<K, V> first,
1695 TreeMap.Entry<K, V> fence) {
1696 super (first, fence);
1697 }
1698
1699 public Map.Entry<K, V> next() {
1700 return nextEntry();
1701 }
1702
1703 public void remove() {
1704 removeAscending();
1705 }
1706 }
1707
1708 final class SubMapKeyIterator extends SubMapIterator<K> {
1709 SubMapKeyIterator(TreeMap.Entry<K, V> first,
1710 TreeMap.Entry<K, V> fence) {
1711 super (first, fence);
1712 }
1713
1714 public K next() {
1715 return nextEntry().key;
1716 }
1717
1718 public void remove() {
1719 removeAscending();
1720 }
1721 }
1722
1723 final class DescendingSubMapEntryIterator extends
1724 SubMapIterator<Map.Entry<K, V>> {
1725 DescendingSubMapEntryIterator(TreeMap.Entry<K, V> last,
1726 TreeMap.Entry<K, V> fence) {
1727 super (last, fence);
1728 }
1729
1730 public Map.Entry<K, V> next() {
1731 return prevEntry();
1732 }
1733
1734 public void remove() {
1735 removeDescending();
1736 }
1737 }
1738
1739 final class DescendingSubMapKeyIterator extends
1740 SubMapIterator<K> {
1741 DescendingSubMapKeyIterator(TreeMap.Entry<K, V> last,
1742 TreeMap.Entry<K, V> fence) {
1743 super (last, fence);
1744 }
1745
1746 public K next() {
1747 return prevEntry().key;
1748 }
1749
1750 public void remove() {
1751 removeDescending();
1752 }
1753 }
1754 }
1755
1756 /**
1757 * @serial include
1758 */
1759 static final class AscendingSubMap<K, V> extends
1760 NavigableSubMap<K, V> {
1761 private static final long serialVersionUID = 912986545866124060L;
1762
1763 AscendingSubMap(TreeMap<K, V> m, boolean fromStart, K lo,
1764 boolean loInclusive, boolean toEnd, K hi,
1765 boolean hiInclusive) {
1766 super (m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1767 }
1768
1769 public Comparator<? super K> comparator() {
1770 return m.comparator();
1771 }
1772
1773 public NavigableMap<K, V> subMap(K fromKey,
1774 boolean fromInclusive, K toKey, boolean toInclusive) {
1775 if (!inRange(fromKey, fromInclusive))
1776 throw new IllegalArgumentException(
1777 "fromKey out of range");
1778 if (!inRange(toKey, toInclusive))
1779 throw new IllegalArgumentException("toKey out of range");
1780 return new AscendingSubMap(m, false, fromKey,
1781 fromInclusive, false, toKey, toInclusive);
1782 }
1783
1784 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
1785 if (!inRange(toKey, inclusive))
1786 throw new IllegalArgumentException("toKey out of range");
1787 return new AscendingSubMap(m, fromStart, lo, loInclusive,
1788 false, toKey, inclusive);
1789 }
1790
1791 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
1792 if (!inRange(fromKey, inclusive))
1793 throw new IllegalArgumentException(
1794 "fromKey out of range");
1795 return new AscendingSubMap(m, false, fromKey, inclusive,
1796 toEnd, hi, hiInclusive);
1797 }
1798
1799 public NavigableMap<K, V> descendingMap() {
1800 NavigableMap<K, V> mv = descendingMapView;
1801 return (mv != null) ? mv
1802 : (descendingMapView = new DescendingSubMap(m,
1803 fromStart, lo, loInclusive, toEnd, hi,
1804 hiInclusive));
1805 }
1806
1807 Iterator<K> keyIterator() {
1808 return new SubMapKeyIterator(absLowest(), absHighFence());
1809 }
1810
1811 Iterator<K> descendingKeyIterator() {
1812 return new DescendingSubMapKeyIterator(absHighest(),
1813 absLowFence());
1814 }
1815
1816 final class AscendingEntrySetView extends EntrySetView {
1817 public Iterator<Map.Entry<K, V>> iterator() {
1818 return new SubMapEntryIterator(absLowest(),
1819 absHighFence());
1820 }
1821 }
1822
1823 public Set<Map.Entry<K, V>> entrySet() {
1824 EntrySetView es = entrySetView;
1825 return (es != null) ? es : new AscendingEntrySetView();
1826 }
1827
1828 TreeMap.Entry<K, V> subLowest() {
1829 return absLowest();
1830 }
1831
1832 TreeMap.Entry<K, V> subHighest() {
1833 return absHighest();
1834 }
1835
1836 TreeMap.Entry<K, V> subCeiling(K key) {
1837 return absCeiling(key);
1838 }
1839
1840 TreeMap.Entry<K, V> subHigher(K key) {
1841 return absHigher(key);
1842 }
1843
1844 TreeMap.Entry<K, V> subFloor(K key) {
1845 return absFloor(key);
1846 }
1847
1848 TreeMap.Entry<K, V> subLower(K key) {
1849 return absLower(key);
1850 }
1851 }
1852
1853 /**
1854 * @serial include
1855 */
1856 static final class DescendingSubMap<K, V> extends
1857 NavigableSubMap<K, V> {
1858 private static final long serialVersionUID = 912986545866120460L;
1859
1860 DescendingSubMap(TreeMap<K, V> m, boolean fromStart, K lo,
1861 boolean loInclusive, boolean toEnd, K hi,
1862 boolean hiInclusive) {
1863 super (m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1864 }
1865
1866 private final Comparator<? super K> reverseComparator = Collections
1867 .reverseOrder(m.comparator);
1868
1869 public Comparator<? super K> comparator() {
1870 return reverseComparator;
1871 }
1872
1873 public NavigableMap<K, V> subMap(K fromKey,
1874 boolean fromInclusive, K toKey, boolean toInclusive) {
1875 if (!inRange(fromKey, fromInclusive))
1876 throw new IllegalArgumentException(
1877 "fromKey out of range");
1878 if (!inRange(toKey, toInclusive))
1879 throw new IllegalArgumentException("toKey out of range");
1880 return new DescendingSubMap(m, false, toKey, toInclusive,
1881 false, fromKey, fromInclusive);
1882 }
1883
1884 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
1885 if (!inRange(toKey, inclusive))
1886 throw new IllegalArgumentException("toKey out of range");
1887 return new DescendingSubMap(m, false, toKey, inclusive,
1888 toEnd, hi, hiInclusive);
1889 }
1890
1891 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
1892 if (!inRange(fromKey, inclusive))
1893 throw new IllegalArgumentException(
1894 "fromKey out of range");
1895 return new DescendingSubMap(m, fromStart, lo, loInclusive,
1896 false, fromKey, inclusive);
1897 }
1898
1899 public NavigableMap<K, V> descendingMap() {
1900 NavigableMap<K, V> mv = descendingMapView;
1901 return (mv != null) ? mv
1902 : (descendingMapView = new AscendingSubMap(m,
1903 fromStart, lo, loInclusive, toEnd, hi,
1904 hiInclusive));
1905 }
1906
1907 Iterator<K> keyIterator() {
1908 return new DescendingSubMapKeyIterator(absHighest(),
1909 absLowFence());
1910 }
1911
1912 Iterator<K> descendingKeyIterator() {
1913 return new SubMapKeyIterator(absLowest(), absHighFence());
1914 }
1915
1916 final class DescendingEntrySetView extends EntrySetView {
1917 public Iterator<Map.Entry<K, V>> iterator() {
1918 return new DescendingSubMapEntryIterator(absHighest(),
1919 absLowFence());
1920 }
1921 }
1922
1923 public Set<Map.Entry<K, V>> entrySet() {
1924 EntrySetView es = entrySetView;
1925 return (es != null) ? es : new DescendingEntrySetView();
1926 }
1927
1928 TreeMap.Entry<K, V> subLowest() {
1929 return absHighest();
1930 }
1931
1932 TreeMap.Entry<K, V> subHighest() {
1933 return absLowest();
1934 }
1935
1936 TreeMap.Entry<K, V> subCeiling(K key) {
1937 return absFloor(key);
1938 }
1939
1940 TreeMap.Entry<K, V> subHigher(K key) {
1941 return absLower(key);
1942 }
1943
1944 TreeMap.Entry<K, V> subFloor(K key) {
1945 return absCeiling(key);
1946 }
1947
1948 TreeMap.Entry<K, V> subLower(K key) {
1949 return absHigher(key);
1950 }
1951 }
1952
1953 /**
1954 * This class exists solely for the sake of serialization
1955 * compatibility with previous releases of TreeMap that did not
1956 * support NavigableMap. It translates an old-version SubMap into
1957 * a new-version AscendingSubMap. This class is never otherwise
1958 * used.
1959 *
1960 * @serial include
1961 */
1962 private class SubMap extends AbstractMap<K, V> implements
1963 SortedMap<K, V>, java.io.Serializable {
1964 private static final long serialVersionUID = -6520786458950516097L;
1965 private boolean fromStart = false, toEnd = false;
1966 private K fromKey, toKey;
1967
1968 private Object readResolve() {
1969 return new AscendingSubMap(TreeMap.this , fromStart,
1970 fromKey, true, toEnd, toKey, false);
1971 }
1972
1973 public Set<Map.Entry<K, V>> entrySet() {
1974 throw new InternalError();
1975 }
1976
1977 public K lastKey() {
1978 throw new InternalError();
1979 }
1980
1981 public K firstKey() {
1982 throw new InternalError();
1983 }
1984
1985 public SortedMap<K, V> subMap(K fromKey, K toKey) {
1986 throw new InternalError();
1987 }
1988
1989 public SortedMap<K, V> headMap(K toKey) {
1990 throw new InternalError();
1991 }
1992
1993 public SortedMap<K, V> tailMap(K fromKey) {
1994 throw new InternalError();
1995 }
1996
1997 public Comparator<? super K> comparator() {
1998 throw new InternalError();
1999 }
2000 }
2001
2002 // Red-black mechanics
2003
2004 private static final boolean RED = false;
2005 private static final boolean BLACK = true;
2006
2007 /**
2008 * Node in the Tree. Doubles as a means to pass key-value pairs back to
2009 * user (see Map.Entry).
2010 */
2011
2012 static final class Entry<K, V> implements Map.Entry<K, V> {
2013 K key;
2014 V value;
2015 Entry<K, V> left = null;
2016 Entry<K, V> right = null;
2017 Entry<K, V> parent;
2018 boolean color = BLACK;
2019
2020 /**
2021 * Make a new cell with given key, value, and parent, and with
2022 * <tt>null</tt> child links, and BLACK color.
2023 */
2024 Entry(K key, V value, Entry<K, V> parent) {
2025 this .key = key;
2026 this .value = value;
2027 this .parent = parent;
2028 }
2029
2030 /**
2031 * Returns the key.
2032 *
2033 * @return the key
2034 */
2035 public K getKey() {
2036 return key;
2037 }
2038
2039 /**
2040 * Returns the value associated with the key.
2041 *
2042 * @return the value associated with the key
2043 */
2044 public V getValue() {
2045 return value;
2046 }
2047
2048 /**
2049 * Replaces the value currently associated with the key with the given
2050 * value.
2051 *
2052 * @return the value associated with the key before this method was
2053 * called
2054 */
2055 public V setValue(V value) {
2056 V oldValue = this .value;
2057 this .value = value;
2058 return oldValue;
2059 }
2060
2061 public boolean equals(Object o) {
2062 if (!(o instanceof Map.Entry))
2063 return false;
2064 Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
2065
2066 return valEquals(key, e.getKey())
2067 && valEquals(value, e.getValue());
2068 }
2069
2070 public int hashCode() {
2071 int keyHash = (key == null ? 0 : key.hashCode());
2072 int valueHash = (value == null ? 0 : value.hashCode());
2073 return keyHash ^ valueHash;
2074 }
2075
2076 public String toString() {
2077 return key + "=" + value;
2078 }
2079 }
2080
2081 /**
2082 * Returns the first Entry in the TreeMap (according to the TreeMap's
2083 * key-sort function). Returns null if the TreeMap is empty.
2084 */
2085 final Entry<K, V> getFirstEntry() {
2086 Entry<K, V> p = root;
2087 if (p != null)
2088 while (p.left != null)
2089 p = p.left;
2090 return p;
2091 }
2092
2093 /**
2094 * Returns the last Entry in the TreeMap (according to the TreeMap's
2095 * key-sort function). Returns null if the TreeMap is empty.
2096 */
2097 final Entry<K, V> getLastEntry() {
2098 Entry<K, V> p = root;
2099 if (p != null)
2100 while (p.right != null)
2101 p = p.right;
2102 return p;
2103 }
2104
2105 /**
2106 * Returns the successor of the specified Entry, or null if no such.
2107 */
2108 static <K, V> TreeMap.Entry<K, V> successor(Entry<K, V> t) {
2109 if (t == null)
2110 return null;
2111 else if (t.right != null) {
2112 Entry<K, V> p = t.right;
2113 while (p.left != null)
2114 p = p.left;
2115 return p;
2116 } else {
2117 Entry<K, V> p = t.parent;
2118 Entry<K, V> ch = t;
2119 while (p != null && ch == p.right) {
2120 ch = p;
2121 p = p.parent;
2122 }
2123 return p;
2124 }
2125 }
2126
2127 /**
2128 * Returns the predecessor of the specified Entry, or null if no such.
2129 */
2130 static <K, V> Entry<K, V> predecessor(Entry<K, V> t) {
2131 if (t == null)
2132 return null;
2133 else if (t.left != null) {
2134 Entry<K, V> p = t.left;
2135 while (p.right != null)
2136 p = p.right;
2137 return p;
2138 } else {
2139 Entry<K, V> p = t.parent;
2140 Entry<K, V> ch = t;
2141 while (p != null && ch == p.left) {
2142 ch = p;
2143 p = p.parent;
2144 }
2145 return p;
2146 }
2147 }
2148
2149 /**
2150 * Balancing operations.
2151 *
2152 * Implementations of rebalancings during insertion and deletion are
2153 * slightly different than the CLR version. Rather than using dummy
2154 * nilnodes, we use a set of accessors that deal properly with null. They
2155 * are used to avoid messiness surrounding nullness checks in the main
2156 * algorithms.
2157 */
2158
2159 private static <K, V> boolean colorOf(Entry<K, V> p) {
2160 return (p == null ? BLACK : p.color);
2161 }
2162
2163 private static <K, V> Entry<K, V> parentOf(Entry<K, V> p) {
2164 return (p == null ? null : p.parent);
2165 }
2166
2167 private static <K, V> void setColor(Entry<K, V> p, boolean c) {
2168 if (p != null)
2169 p.color = c;
2170 }
2171
2172 private static <K, V> Entry<K, V> leftOf(Entry<K, V> p) {
2173 return (p == null) ? null : p.left;
2174 }
2175
2176 private static <K, V> Entry<K, V> rightOf(Entry<K, V> p) {
2177 return (p == null) ? null : p.right;
2178 }
2179
2180 /** From CLR */
2181 private void rotateLeft(Entry<K, V> p) {
2182 if (p != null) {
2183 Entry<K, V> r = p.right;
2184 p.right = r.left;
2185 if (r.left != null)
2186 r.left.parent = p;
2187 r.parent = p.parent;
2188 if (p.parent == null)
2189 root = r;
2190 else if (p.parent.left == p)
2191 p.parent.left = r;
2192 else
2193 p.parent.right = r;
2194 r.left = p;
2195 p.parent = r;
2196 }
2197 }
2198
2199 /** From CLR */
2200 private void rotateRight(Entry<K, V> p) {
2201 if (p != null) {
2202 Entry<K, V> l = p.left;
2203 p.left = l.right;
2204 if (l.right != null)
2205 l.right.parent = p;
2206 l.parent = p.parent;
2207 if (p.parent == null)
2208 root = l;
2209 else if (p.parent.right == p)
2210 p.parent.right = l;
2211 else
2212 p.parent.left = l;
2213 l.right = p;
2214 p.parent = l;
2215 }
2216 }
2217
2218 /** From CLR */
2219 private void fixAfterInsertion(Entry<K, V> x) {
2220 x.color = RED;
2221
2222 while (x != null && x != root && x.parent.color == RED) {
2223 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
2224 Entry<K, V> y = rightOf(parentOf(parentOf(x)));
2225 if (colorOf(y) == RED) {
2226 setColor(parentOf(x), BLACK);
2227 setColor(y, BLACK);
2228 setColor(parentOf(parentOf(x)), RED);
2229 x = parentOf(parentOf(x));
2230 } else {
2231 if (x == rightOf(parentOf(x))) {
2232 x = parentOf(x);
2233 rotateLeft(x);
2234 }
2235 setColor(parentOf(x), BLACK);
2236 setColor(parentOf(parentOf(x)), RED);
2237 rotateRight(parentOf(parentOf(x)));
2238 }
2239 } else {
2240 Entry<K, V> y = leftOf(parentOf(parentOf(x)));
2241 if (colorOf(y) == RED) {
2242 setColor(parentOf(x), BLACK);
2243 setColor(y, BLACK);
2244 setColor(parentOf(parentOf(x)), RED);
2245 x = parentOf(parentOf(x));
2246 } else {
2247 if (x == leftOf(parentOf(x))) {
2248 x = parentOf(x);
2249 rotateRight(x);
2250 }
2251 setColor(parentOf(x), BLACK);
2252 setColor(parentOf(parentOf(x)), RED);
2253 rotateLeft(parentOf(parentOf(x)));
2254 }
2255 }
2256 }
2257 root.color = BLACK;
2258 }
2259
2260 /**
2261 * Delete node p, and then rebalance the tree.
2262 */
2263 private void deleteEntry(Entry<K, V> p) {
2264 modCount++;
2265 size--;
2266
2267 // If strictly internal, copy successor's element to p and then make p
2268 // point to successor.
2269 if (p.left != null && p.right != null) {
2270 Entry<K, V> s = successor(p);
2271 p.key = s.key;
2272 p.value = s.value;
2273 p = s;
2274 } // p has 2 children
2275
2276 // Start fixup at replacement node, if it exists.
2277 Entry<K, V> replacement = (p.left != null ? p.left : p.right);
2278
2279 if (replacement != null) {
2280 // Link replacement to parent
2281 replacement.parent = p.parent;
2282 if (p.parent == null)
2283 root = replacement;
2284 else if (p == p.parent.left)
2285 p.parent.left = replacement;
2286 else
2287 p.parent.right = replacement;
2288
2289 // Null out links so they are OK to use by fixAfterDeletion.
2290 p.left = p.right = p.parent = null;
2291
2292 // Fix replacement
2293 if (p.color == BLACK)
2294 fixAfterDeletion(replacement);
2295 } else if (p.parent == null) { // return if we are the only node.
2296 root = null;
2297 } else { // No children. Use self as phantom replacement and unlink.
2298 if (p.color == BLACK)
2299 fixAfterDeletion(p);
2300
2301 if (p.parent != null) {
2302 if (p == p.parent.left)
2303 p.parent.left = null;
2304 else if (p == p.parent.right)
2305 p.parent.right = null;
2306 p.parent = null;
2307 }
2308 }
2309 }
2310
2311 /** From CLR */
2312 private void fixAfterDeletion(Entry<K, V> x) {
2313 while (x != root && colorOf(x) == BLACK) {
2314 if (x == leftOf(parentOf(x))) {
2315 Entry<K, V> sib = rightOf(parentOf(x));
2316
2317 if (colorOf(sib) == RED) {
2318 setColor(sib, BLACK);
2319 setColor(parentOf(x), RED);
2320 rotateLeft(parentOf(x));
2321 sib = rightOf(parentOf(x));
2322 }
2323
2324 if (colorOf(leftOf(sib)) == BLACK
2325 && colorOf(rightOf(sib)) == BLACK) {
2326 setColor(sib, RED);
2327 x = parentOf(x);
2328 } else {
2329 if (colorOf(rightOf(sib)) == BLACK) {
2330 setColor(leftOf(sib), BLACK);
2331 setColor(sib, RED);
2332 rotateRight(sib);
2333 sib = rightOf(parentOf(x));
2334 }
2335 setColor(sib, colorOf(parentOf(x)));
2336 setColor(parentOf(x), BLACK);
2337 setColor(rightOf(sib), BLACK);
2338 rotateLeft(parentOf(x));
2339 x = root;
2340 }
2341 } else { // symmetric
2342 Entry<K, V> sib = leftOf(parentOf(x));
2343
2344 if (colorOf(sib) == RED) {
2345 setColor(sib, BLACK);
2346 setColor(parentOf(x), RED);
2347 rotateRight(parentOf(x));
2348 sib = leftOf(parentOf(x));
2349 }
2350
2351 if (colorOf(rightOf(sib)) == BLACK
2352 && colorOf(leftOf(sib)) == BLACK) {
2353 setColor(sib, RED);
2354 x = parentOf(x);
2355 } else {
2356 if (colorOf(leftOf(sib)) == BLACK) {
2357 setColor(rightOf(sib), BLACK);
2358 setColor(sib, RED);
2359 rotateLeft(sib);
2360 sib = leftOf(parentOf(x));
2361 }
2362 setColor(sib, colorOf(parentOf(x)));
2363 setColor(parentOf(x), BLACK);
2364 setColor(leftOf(sib), BLACK);
2365 rotateRight(parentOf(x));
2366 x = root;
2367 }
2368 }
2369 }
2370
2371 setColor(x, BLACK);
2372 }
2373
2374 private static final long serialVersionUID = 919286545866124006L;
2375
2376 /**
2377 * Save the state of the <tt>TreeMap</tt> instance to a stream (i.e.,
2378 * serialize it).
2379 *
2380 * @serialData The <i>size</i> of the TreeMap (the number of key-value
2381 * mappings) is emitted (int), followed by the key (Object)
2382 * and value (Object) for each key-value mapping represented
2383 * by the TreeMap. The key-value mappings are emitted in
2384 * key-order (as determined by the TreeMap's Comparator,
2385 * or by the keys' natural ordering if the TreeMap has no
2386 * Comparator).
2387 */
2388 private void writeObject(java.io.ObjectOutputStream s)
2389 throws java.io.IOException {
2390 // Write out the Comparator and any hidden stuff
2391 s.defaultWriteObject();
2392
2393 // Write out size (number of Mappings)
2394 s.writeInt(size);
2395
2396 // Write out keys and values (alternating)
2397 for (Iterator<Map.Entry<K, V>> i = entrySet().iterator(); i
2398 .hasNext();) {
2399 Map.Entry<K, V> e = i.next();
2400 s.writeObject(e.getKey());
2401 s.writeObject(e.getValue());
2402 }
2403 }
2404
2405 /**
2406 * Reconstitute the <tt>TreeMap</tt> instance from a stream (i.e.,
2407 * deserialize it).
2408 */
2409 private void readObject(final java.io.ObjectInputStream s)
2410 throws java.io.IOException, ClassNotFoundException {
2411 // Read in the Comparator and any hidden stuff
2412 s.defaultReadObject();
2413
2414 // Read in size
2415 int size = s.readInt();
2416
2417 buildFromSorted(size, null, s, null);
2418 }
2419
2420 /** Intended to be called only from TreeSet.readObject */
2421 void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2422 throws java.io.IOException, ClassNotFoundException {
2423 buildFromSorted(size, null, s, defaultVal);
2424 }
2425
2426 /** Intended to be called only from TreeSet.addAll */
2427 void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2428 try {
2429 buildFromSorted(set.size(), set.iterator(), null,
2430 defaultVal);
2431 } catch (java.io.IOException cannotHappen) {
2432 } catch (ClassNotFoundException cannotHappen) {
2433 }
2434 }
2435
2436 /**
2437 * Linear time tree building algorithm from sorted data. Can accept keys
2438 * and/or values from iterator or stream. This leads to too many
2439 * parameters, but seems better than alternatives. The four formats
2440 * that this method accepts are:
2441 *
2442 * 1) An iterator of Map.Entries. (it != null, defaultVal == null).
2443 * 2) An iterator of keys. (it != null, defaultVal != null).
2444 * 3) A stream of alternating serialized keys and values.
2445 * (it == null, defaultVal == null).
2446 * 4) A stream of serialized keys. (it == null, defaultVal != null).
2447 *
2448 * It is assumed that the comparator of the TreeMap is already set prior
2449 * to calling this method.
2450 *
2451 * @param size the number of keys (or key-value pairs) to be read from
2452 * the iterator or stream
2453 * @param it If non-null, new entries are created from entries
2454 * or keys read from this iterator.
2455 * @param str If non-null, new entries are created from keys and
2456 * possibly values read from this stream in serialized form.
2457 * Exactly one of it and str should be non-null.
2458 * @param defaultVal if non-null, this default value is used for
2459 * each value in the map. If null, each value is read from
2460 * iterator or stream, as described above.
2461 * @throws IOException propagated from stream reads. This cannot
2462 * occur if str is null.
2463 * @throws ClassNotFoundException propagated from readObject.
2464 * This cannot occur if str is null.
2465 */
2466 private void buildFromSorted(int size, Iterator it,
2467 java.io.ObjectInputStream str, V defaultVal)
2468 throws java.io.IOException, ClassNotFoundException {
2469 this .size = size;
2470 root = buildFromSorted(0, 0, size - 1, computeRedLevel(size),
2471 it, str, defaultVal);
2472 }
2473
2474 /**
2475 * Recursive "helper method" that does the real work of the
2476 * previous method. Identically named parameters have
2477 * identical definitions. Additional parameters are documented below.
2478 * It is assumed that the comparator and size fields of the TreeMap are
2479 * already set prior to calling this method. (It ignores both fields.)
2480 *
2481 * @param level the current level of tree. Initial call should be 0.
2482 * @param lo the first element index of this subtree. Initial should be 0.
2483 * @param hi the last element index of this subtree. Initial should be
2484 * size-1.
2485 * @param redLevel the level at which nodes should be red.
2486 * Must be equal to computeRedLevel for tree of this size.
2487 */
2488 private final Entry<K, V> buildFromSorted(int level, int lo,
2489 int hi, int redLevel, Iterator it,
2490 java.io.ObjectInputStream str, V defaultVal)
2491 throws java.io.IOException, ClassNotFoundException {
2492 /*
2493 * Strategy: The root is the middlemost element. To get to it, we
2494 * have to first recursively construct the entire left subtree,
2495 * so as to grab all of its elements. We can then proceed with right
2496 * subtree.
2497 *
2498 * The lo and hi arguments are the minimum and maximum
2499 * indices to pull out of the iterator or stream for current subtree.
2500 * They are not actually indexed, we just proceed sequentially,
2501 * ensuring that items are extracted in corresponding order.
2502 */
2503
2504 if (hi < lo)
2505 return null;
2506
2507 int mid = (lo + hi) >>> 1;
2508
2509 Entry<K, V> left = null;
2510 if (lo < mid)
2511 left = buildFromSorted(level + 1, lo, mid - 1, redLevel,
2512 it, str, defaultVal);
2513
2514 // extract key and/or value from iterator or stream
2515 K key;
2516 V value;
2517 if (it != null) {
2518 if (defaultVal == null) {
2519 Map.Entry<K, V> entry = (Map.Entry<K, V>) it.next();
2520 key = entry.getKey();
2521 value = entry.getValue();
2522 } else {
2523 key = (K) it.next();
2524 value = defaultVal;
2525 }
2526 } else { // use stream
2527 key = (K) str.readObject();
2528 value = (defaultVal != null ? defaultVal : (V) str
2529 .readObject());
2530 }
2531
2532 Entry<K, V> middle = new Entry<K, V>(key, value, null);
2533
2534 // color nodes in non-full bottommost level red
2535 if (level == redLevel)
2536 middle.color = RED;
2537
2538 if (left != null) {
2539 middle.left = left;
2540 left.parent = middle;
2541 }
2542
2543 if (mid < hi) {
2544 Entry<K, V> right = buildFromSorted(level + 1, mid + 1, hi,
2545 redLevel, it, str, defaultVal);
2546 middle.right = right;
2547 right.parent = middle;
2548 }
2549
2550 return middle;
2551 }
2552
2553 /**
2554 * Find the level down to which to assign all nodes BLACK. This is the
2555 * last `full' level of the complete binary tree produced by
2556 * buildTree. The remaining nodes are colored RED. (This makes a `nice'
2557 * set of color assignments wrt future insertions.) This level number is
2558 * computed by finding the number of splits needed to reach the zeroeth
2559 * node. (The answer is ~lg(N), but in any case must be computed by same
2560 * quick O(lg(N)) loop.)
2561 */
2562 private static int computeRedLevel(int sz) {
2563 int level = 0;
2564 for (int m = sz - 1; m >= 0; m = m / 2 - 1)
2565 level++;
2566 return level;
2567 }
2568 }
|