| /* |
| * Copyright (C) 2014 The Android Open Source Project |
| * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. Oracle designates this |
| * particular file as subject to the "Classpath" exception as provided |
| * by Oracle in the LICENSE file that accompanied this code. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| |
| package java.util; |
| |
| import java.util.function.BiConsumer; |
| import java.util.function.Consumer; |
| |
| /** |
| * A Red-Black tree based {@link NavigableMap} implementation. |
| * The map is sorted according to the {@linkplain Comparable natural |
| * ordering} of its keys, or by a {@link Comparator} provided at map |
| * creation time, depending on which constructor is used. |
| * |
| * <p>This implementation provides guaranteed log(n) time cost for the |
| * {@code containsKey}, {@code get}, {@code put} and {@code remove} |
| * operations. Algorithms are adaptations of those in Cormen, Leiserson, and |
| * Rivest's <em>Introduction to Algorithms</em>. |
| * |
| * <p>Note that the ordering maintained by a tree map, like any sorted map, and |
| * whether or not an explicit comparator is provided, must be <em>consistent |
| * with {@code equals}</em> if this sorted map is to correctly implement the |
| * {@code Map} interface. (See {@code Comparable} or {@code Comparator} for a |
| * precise definition of <em>consistent with equals</em>.) This is so because |
| * the {@code Map} interface is defined in terms of the {@code equals} |
| * operation, but a sorted map performs all key comparisons using its {@code |
| * compareTo} (or {@code compare}) method, so two keys that are deemed equal by |
| * this method are, from the standpoint of the sorted map, equal. The behavior |
| * of a sorted map <em>is</em> well-defined even if its ordering is |
| * inconsistent with {@code equals}; it just fails to obey the general contract |
| * of the {@code Map} interface. |
| * |
| * <p><strong>Note that this implementation is not synchronized.</strong> |
| * If multiple threads access a map concurrently, and at least one of the |
| * threads modifies the map structurally, it <em>must</em> be synchronized |
| * externally. (A structural modification is any operation that adds or |
| * deletes one or more mappings; merely changing the value associated |
| * with an existing key is not a structural modification.) This is |
| * typically accomplished by synchronizing on some object that naturally |
| * encapsulates the map. |
| * If no such object exists, the map should be "wrapped" using the |
| * {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap} |
| * method. This is best done at creation time, to prevent accidental |
| * unsynchronized access to the map: <pre> |
| * SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre> |
| * |
| * <p>The iterators returned by the {@code iterator} method of the collections |
| * returned by all of this class's "collection view methods" are |
| * <em>fail-fast</em>: if the map is structurally modified at any time after |
| * the iterator is created, in any way except through the iterator's own |
| * {@code remove} method, the iterator will throw a {@link |
| * ConcurrentModificationException}. Thus, in the face of concurrent |
| * modification, the iterator fails quickly and cleanly, rather than risking |
| * arbitrary, non-deterministic behavior at an undetermined time in the future. |
| * |
| * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed |
| * as it is, generally speaking, impossible to make any hard guarantees in the |
| * presence of unsynchronized concurrent modification. Fail-fast iterators |
| * throw {@code ConcurrentModificationException} on a best-effort basis. |
| * Therefore, it would be wrong to write a program that depended on this |
| * exception for its correctness: <em>the fail-fast behavior of iterators |
| * should be used only to detect bugs.</em> |
| * |
| * <p>All {@code Map.Entry} pairs returned by methods in this class |
| * and its views represent snapshots of mappings at the time they were |
| * produced. They do <strong>not</strong> support the {@code Entry.setValue} |
| * method. (Note however that it is possible to change mappings in the |
| * associated map using {@code put}.) |
| * |
| * <p>This class is a member of the |
| * <a href="{@docRoot}/../technotes/guides/collections/index.html"> |
| * Java Collections Framework</a>. |
| * |
| * @param <K> the type of keys maintained by this map |
| * @param <V> the type of mapped values |
| * |
| * @author Josh Bloch and Doug Lea |
| * @see Map |
| * @see HashMap |
| * @see Hashtable |
| * @see Comparable |
| * @see Comparator |
| * @see Collection |
| * @since 1.2 |
| */ |
| |
| public class TreeMap<K,V> |
| extends AbstractMap<K,V> |
| implements NavigableMap<K,V>, Cloneable, java.io.Serializable |
| { |
| /** |
| * The comparator used to maintain order in this tree map, or |
| * null if it uses the natural ordering of its keys. |
| * |
| * @serial |
| */ |
| private final Comparator<? super K> comparator; |
| |
| private transient TreeMapEntry<K,V> root = null; |
| |
| /** |
| * The number of entries in the tree |
| */ |
| private transient int size = 0; |
| |
| /** |
| * The number of structural modifications to the tree. |
| */ |
| private transient int modCount = 0; |
| |
| /** |
| * Constructs a new, empty tree map, using the natural ordering of its |
| * keys. All keys inserted into the map must implement the {@link |
| * Comparable} interface. Furthermore, all such keys must be |
| * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw |
| * a {@code ClassCastException} for any keys {@code k1} and |
| * {@code k2} in the map. If the user attempts to put a key into the |
| * map that violates this constraint (for example, the user attempts to |
| * put a string key into a map whose keys are integers), the |
| * {@code put(Object key, Object value)} call will throw a |
| * {@code ClassCastException}. |
| */ |
| public TreeMap() { |
| comparator = null; |
| } |
| |
| /** |
| * Constructs a new, empty tree map, ordered according to the given |
| * comparator. All keys inserted into the map must be <em>mutually |
| * comparable</em> by the given comparator: {@code comparator.compare(k1, |
| * k2)} must not throw a {@code ClassCastException} for any keys |
| * {@code k1} and {@code k2} in the map. If the user attempts to put |
| * a key into the map that violates this constraint, the {@code put(Object |
| * key, Object value)} call will throw a |
| * {@code ClassCastException}. |
| * |
| * @param comparator the comparator that will be used to order this map. |
| * If {@code null}, the {@linkplain Comparable natural |
| * ordering} of the keys will be used. |
| */ |
| public TreeMap(Comparator<? super K> comparator) { |
| this.comparator = comparator; |
| } |
| |
| /** |
| * Constructs a new tree map containing the same mappings as the given |
| * map, ordered according to the <em>natural ordering</em> of its keys. |
| * All keys inserted into the new map must implement the {@link |
| * Comparable} interface. Furthermore, all such keys must be |
| * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw |
| * a {@code ClassCastException} for any keys {@code k1} and |
| * {@code k2} in the map. This method runs in n*log(n) time. |
| * |
| * @param m the map whose mappings are to be placed in this map |
| * @throws ClassCastException if the keys in m are not {@link Comparable}, |
| * or are not mutually comparable |
| * @throws NullPointerException if the specified map is null |
| */ |
| public TreeMap(Map<? extends K, ? extends V> m) { |
| comparator = null; |
| putAll(m); |
| } |
| |
| /** |
| * Constructs a new tree map containing the same mappings and |
| * using the same ordering as the specified sorted map. This |
| * method runs in linear time. |
| * |
| * @param m the sorted map whose mappings are to be placed in this map, |
| * and whose comparator is to be used to sort this map |
| * @throws NullPointerException if the specified map is null |
| */ |
| public TreeMap(SortedMap<K, ? extends V> m) { |
| comparator = m.comparator(); |
| try { |
| buildFromSorted(m.size(), m.entrySet().iterator(), null, null); |
| } catch (java.io.IOException cannotHappen) { |
| } catch (ClassNotFoundException cannotHappen) { |
| } |
| } |
| |
| |
| // Query Operations |
| |
| /** |
| * Returns the number of key-value mappings in this map. |
| * |
| * @return the number of key-value mappings in this map |
| */ |
| public int size() { |
| return size; |
| } |
| |
| /** |
| * Returns {@code true} if this map contains a mapping for the specified |
| * key. |
| * |
| * @param key key whose presence in this map is to be tested |
| * @return {@code true} if this map contains a mapping for the |
| * specified key |
| * @throws ClassCastException if the specified key cannot be compared |
| * with the keys currently in the map |
| * @throws NullPointerException if the specified key is null |
| * and this map uses natural ordering, or its comparator |
| * does not permit null keys |
| */ |
| public boolean containsKey(Object key) { |
| return getEntry(key) != null; |
| } |
| |
| /** |
| * Returns {@code true} if this map maps one or more keys to the |
| * specified value. More formally, returns {@code true} if and only if |
| * this map contains at least one mapping to a value {@code v} such |
| * that {@code (value==null ? v==null : value.equals(v))}. This |
| * operation will probably require time linear in the map size for |
| * most implementations. |
| * |
| * @param value value whose presence in this map is to be tested |
| * @return {@code true} if a mapping to {@code value} exists; |
| * {@code false} otherwise |
| * @since 1.2 |
| */ |
| public boolean containsValue(Object value) { |
| for (TreeMapEntry<K,V> e = getFirstEntry(); e != null; e = successor(e)) |
| if (valEquals(value, e.value)) |
| return true; |
| return false; |
| } |
| |
| /** |
| * Returns the value to which the specified key is mapped, |
| * or {@code null} if this map contains no mapping for the key. |
| * |
| * <p>More formally, if this map contains a mapping from a key |
| * {@code k} to a value {@code v} such that {@code key} compares |
| * equal to {@code k} according to the map's ordering, then this |
| * method returns {@code v}; otherwise it returns {@code null}. |
| * (There can be at most one such mapping.) |
| * |
| * <p>A return value of {@code null} does not <em>necessarily</em> |
| * indicate that the map contains no mapping for the key; it's also |
| * possible that the map explicitly maps the key to {@code null}. |
| * The {@link #containsKey containsKey} operation may be used to |
| * distinguish these two cases. |
| * |
| * @throws ClassCastException if the specified key cannot be compared |
| * with the keys currently in the map |
| * @throws NullPointerException if the specified key is null |
| * and this map uses natural ordering, or its comparator |
| * does not permit null keys |
| */ |
| public V get(Object key) { |
| TreeMapEntry<K,V> p = getEntry(key); |
| return (p==null ? null : p.value); |
| } |
| |
| public Comparator<? super K> comparator() { |
| return comparator; |
| } |
| |
| /** |
| * @throws NoSuchElementException {@inheritDoc} |
| */ |
| public K firstKey() { |
| return key(getFirstEntry()); |
| } |
| |
| /** |
| * @throws NoSuchElementException {@inheritDoc} |
| */ |
| public K lastKey() { |
| return key(getLastEntry()); |
| } |
| |
| /** |
| * Copies all of the mappings from the specified map to this map. |
| * These mappings replace any mappings that this map had for any |
| * of the keys currently in the specified map. |
| * |
| * @param map mappings to be stored in this map |
| * @throws ClassCastException if the class of a key or value in |
| * the specified map prevents it from being stored in this map |
| * @throws NullPointerException if the specified map is null or |
| * the specified map contains a null key and this map does not |
| * permit null keys |
| */ |
| public void putAll(Map<? extends K, ? extends V> map) { |
| int mapSize = map.size(); |
| if (size==0 && mapSize!=0 && map instanceof SortedMap) { |
| Comparator c = ((SortedMap)map).comparator(); |
| if (c == comparator || (c != null && c.equals(comparator))) { |
| ++modCount; |
| try { |
| buildFromSorted(mapSize, map.entrySet().iterator(), |
| null, null); |
| } catch (java.io.IOException cannotHappen) { |
| } catch (ClassNotFoundException cannotHappen) { |
| } |
| return; |
| } |
| } |
| super.putAll(map); |
| } |
| |
| /** |
| * Returns this map's entry for the given key, or {@code null} if the map |
| * does not contain an entry for the key. |
| * |
| * @return this map's entry for the given key, or {@code null} if the map |
| * does not contain an entry for the key |
| * @throws ClassCastException if the specified key cannot be compared |
| * with the keys currently in the map |
| * @throws NullPointerException if the specified key is null |
| * and this map uses natural ordering, or its comparator |
| * does not permit null keys |
| */ |
| final TreeMapEntry<K,V> getEntry(Object key) { |
| // Offload comparator-based version for sake of performance |
| if (comparator != null) |
| return getEntryUsingComparator(key); |
| if (key == null) |
| throw new NullPointerException(); |
| Comparable<? super K> k = (Comparable<? super K>) key; |
| TreeMapEntry<K,V> p = root; |
| while (p != null) { |
| int cmp = k.compareTo(p.key); |
| if (cmp < 0) |
| p = p.left; |
| else if (cmp > 0) |
| p = p.right; |
| else |
| return p; |
| } |
| return null; |
| } |
| |
| /** |
| * Version of getEntry using comparator. Split off from getEntry |
| * for performance. (This is not worth doing for most methods, |
| * that are less dependent on comparator performance, but is |
| * worthwhile here.) |
| */ |
| final TreeMapEntry<K,V> getEntryUsingComparator(Object key) { |
| K k = (K) key; |
| Comparator<? super K> cpr = comparator; |
| if (cpr != null) { |
| TreeMapEntry<K,V> p = root; |
| while (p != null) { |
| int cmp = cpr.compare(k, p.key); |
| if (cmp < 0) |
| p = p.left; |
| else if (cmp > 0) |
| p = p.right; |
| else |
| return p; |
| } |
| } |
| return null; |
| } |
| |
| /** |
| * Gets the entry corresponding to the specified key; if no such entry |
| * exists, returns the entry for the least key greater than the specified |
| * key; if no such entry exists (i.e., the greatest key in the Tree is less |
| * than the specified key), returns {@code null}. |
| */ |
| final TreeMapEntry<K,V> getCeilingEntry(K key) { |
| TreeMapEntry<K,V> p = root; |
| while (p != null) { |
| int cmp = compare(key, p.key); |
| if (cmp < 0) { |
| if (p.left != null) |
| p = p.left; |
| else |
| return p; |
| } else if (cmp > 0) { |
| if (p.right != null) { |
| p = p.right; |
| } else { |
| TreeMapEntry<K,V> parent = p.parent; |
| TreeMapEntry<K,V> ch = p; |
| while (parent != null && ch == parent.right) { |
| ch = parent; |
| parent = parent.parent; |
| } |
| return parent; |
| } |
| } else |
| return p; |
| } |
| return null; |
| } |
| |
| /** |
| * Gets the entry corresponding to the specified key; if no such entry |
| * exists, returns the entry for the greatest key less than the specified |
| * key; if no such entry exists, returns {@code null}. |
| */ |
| final TreeMapEntry<K,V> getFloorEntry(K key) { |
| TreeMapEntry<K,V> p = root; |
| while (p != null) { |
| int cmp = compare(key, p.key); |
| if (cmp > 0) { |
| if (p.right != null) |
| p = p.right; |
| else |
| return p; |
| } else if (cmp < 0) { |
| if (p.left != null) { |
| p = p.left; |
| } else { |
| TreeMapEntry<K,V> parent = p.parent; |
| TreeMapEntry<K,V> ch = p; |
| while (parent != null && ch == parent.left) { |
| ch = parent; |
| parent = parent.parent; |
| } |
| return parent; |
| } |
| } else |
| return p; |
| |
| } |
| return null; |
| } |
| |
| /** |
| * Gets the entry for the least key greater than the specified |
| * key; if no such entry exists, returns the entry for the least |
| * key greater than the specified key; if no such entry exists |
| * returns {@code null}. |
| */ |
| final TreeMapEntry<K,V> getHigherEntry(K key) { |
| TreeMapEntry<K,V> p = root; |
| while (p != null) { |
| int cmp = compare(key, p.key); |
| if (cmp < 0) { |
| if (p.left != null) |
| p = p.left; |
| else |
| return p; |
| } else { |
| if (p.right != null) { |
| p = p.right; |
| } else { |
| TreeMapEntry<K,V> parent = p.parent; |
| TreeMapEntry<K,V> ch = p; |
| while (parent != null && ch == parent.right) { |
| ch = parent; |
| parent = parent.parent; |
| } |
| return parent; |
| } |
| } |
| } |
| return null; |
| } |
| |
| /** |
| * Returns the entry for the greatest key less than the specified key; if |
| * no such entry exists (i.e., the least key in the Tree is greater than |
| * the specified key), returns {@code null}. |
| */ |
| final TreeMapEntry<K,V> getLowerEntry(K key) { |
| TreeMapEntry<K,V> p = root; |
| while (p != null) { |
| int cmp = compare(key, p.key); |
| if (cmp > 0) { |
| if (p.right != null) |
| p = p.right; |
| else |
| return p; |
| } else { |
| if (p.left != null) { |
| p = p.left; |
| } else { |
| TreeMapEntry<K,V> parent = p.parent; |
| TreeMapEntry<K,V> ch = p; |
| while (parent != null && ch == parent.left) { |
| ch = parent; |
| parent = parent.parent; |
| } |
| return parent; |
| } |
| } |
| } |
| return null; |
| } |
| |
| /** |
| * Associates the specified value with the specified key in this map. |
| * If the map previously contained a mapping for the key, the old |
| * value is replaced. |
| * |
| * @param key key with which the specified value is to be associated |
| * @param value value to be associated with the specified key |
| * |
| * @return the previous value associated with {@code key}, or |
| * {@code null} if there was no mapping for {@code key}. |
| * (A {@code null} return can also indicate that the map |
| * previously associated {@code null} with {@code key}.) |
| * @throws ClassCastException if the specified key cannot be compared |
| * with the keys currently in the map |
| * @throws NullPointerException if the specified key is null |
| * and this map uses natural ordering, or its comparator |
| * does not permit null keys |
| */ |
| public V put(K key, V value) { |
| TreeMapEntry<K,V> t = root; |
| if (t == null) { |
| // We could just call compare(key, key) for its side effect of checking the type and |
| // nullness of the input key. However, several applications seem to have written comparators |
| // that only expect to be called on elements that aren't equal to each other (after |
| // making assumptions about the domain of the map). Clearly, such comparators are bogus |
| // because get() would never work, but TreeSets are frequently used for sorting a set |
| // of distinct elements. |
| // |
| // As a temporary work around, we perform the null & instanceof checks by hand so that |
| // we can guarantee that elements are never compared against themselves. |
| // |
| // compare(key, key); |
| // |
| // **** THIS CHANGE WILL BE REVERTED IN A FUTURE ANDROID RELEASE **** |
| if (comparator != null) { |
| if (key == null) { |
| comparator.compare(key, key); |
| } |
| } else { |
| if (key == null) { |
| throw new NullPointerException("key == null"); |
| } else if (!(key instanceof Comparable)) { |
| throw new ClassCastException( |
| "Cannot cast" + key.getClass().getName() + " to Comparable."); |
| } |
| } |
| |
| root = new TreeMapEntry<>(key, value, null); |
| size = 1; |
| modCount++; |
| return null; |
| } |
| int cmp; |
| TreeMapEntry<K,V> parent; |
| // split comparator and comparable paths |
| Comparator<? super K> cpr = comparator; |
| if (cpr != null) { |
| do { |
| parent = t; |
| cmp = cpr.compare(key, t.key); |
| if (cmp < 0) |
| t = t.left; |
| else if (cmp > 0) |
| t = t.right; |
| else |
| return t.setValue(value); |
| } while (t != null); |
| } |
| else { |
| if (key == null) |
| throw new NullPointerException(); |
| Comparable<? super K> k = (Comparable<? super K>) key; |
| do { |
| parent = t; |
| cmp = k.compareTo(t.key); |
| if (cmp < 0) |
| t = t.left; |
| else if (cmp > 0) |
| t = t.right; |
| else |
| return t.setValue(value); |
| } while (t != null); |
| } |
| TreeMapEntry<K,V> e = new TreeMapEntry<>(key, value, parent); |
| if (cmp < 0) |
| parent.left = e; |
| else |
| parent.right = e; |
| fixAfterInsertion(e); |
| size++; |
| modCount++; |
| return null; |
| } |
| |
| /** |
| * Removes the mapping for this key from this TreeMap if present. |
| * |
| * @param key key for which mapping should be removed |
| * @return the previous value associated with {@code key}, or |
| * {@code null} if there was no mapping for {@code key}. |
| * (A {@code null} return can also indicate that the map |
| * previously associated {@code null} with {@code key}.) |
| * @throws ClassCastException if the specified key cannot be compared |
| * with the keys currently in the map |
| * @throws NullPointerException if the specified key is null |
| * and this map uses natural ordering, or its comparator |
| * does not permit null keys |
| */ |
| public V remove(Object key) { |
| TreeMapEntry<K,V> p = getEntry(key); |
| if (p == null) |
| return null; |
| |
| V oldValue = p.value; |
| deleteEntry(p); |
| return oldValue; |
| } |
| |
| /** |
| * Removes all of the mappings from this map. |
| * The map will be empty after this call returns. |
| */ |
| public void clear() { |
| modCount++; |
| size = 0; |
| root = null; |
| } |
| |
| /** |
| * Returns a shallow copy of this {@code TreeMap} instance. (The keys and |
| * values themselves are not cloned.) |
| * |
| * @return a shallow copy of this map |
| */ |
| public Object clone() { |
| TreeMap<K,V> clone = null; |
| try { |
| clone = (TreeMap<K,V>) super.clone(); |
| } catch (CloneNotSupportedException e) { |
| throw new InternalError(); |
| } |
| |
| // Put clone into "virgin" state (except for comparator) |
| clone.root = null; |
| clone.size = 0; |
| clone.modCount = 0; |
| clone.entrySet = null; |
| clone.navigableKeySet = null; |
| clone.descendingMap = null; |
| |
| // Initialize clone with our mappings |
| try { |
| clone.buildFromSorted(size, entrySet().iterator(), null, null); |
| } catch (java.io.IOException cannotHappen) { |
| } catch (ClassNotFoundException cannotHappen) { |
| } |
| |
| return clone; |
| } |
| |
| // NavigableMap API methods |
| |
| /** |
| * @since 1.6 |
| */ |
| public Map.Entry<K,V> firstEntry() { |
| return exportEntry(getFirstEntry()); |
| } |
| |
| /** |
| * @since 1.6 |
| */ |
| public Map.Entry<K,V> lastEntry() { |
| return exportEntry(getLastEntry()); |
| } |
| |
| /** |
| * @since 1.6 |
| */ |
| public Map.Entry<K,V> pollFirstEntry() { |
| TreeMapEntry<K,V> p = getFirstEntry(); |
| Map.Entry<K,V> result = exportEntry(p); |
| if (p != null) |
| deleteEntry(p); |
| return result; |
| } |
| |
| /** |
| * @since 1.6 |
| */ |
| public Map.Entry<K,V> pollLastEntry() { |
| TreeMapEntry<K,V> p = getLastEntry(); |
| Map.Entry<K,V> result = exportEntry(p); |
| if (p != null) |
| deleteEntry(p); |
| return result; |
| } |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if the specified key is null |
| * and this map uses natural ordering, or its comparator |
| * does not permit null keys |
| * @since 1.6 |
| */ |
| public Map.Entry<K,V> lowerEntry(K key) { |
| return exportEntry(getLowerEntry(key)); |
| } |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if the specified key is null |
| * and this map uses natural ordering, or its comparator |
| * does not permit null keys |
| * @since 1.6 |
| */ |
| public K lowerKey(K key) { |
| return keyOrNull(getLowerEntry(key)); |
| } |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if the specified key is null |
| * and this map uses natural ordering, or its comparator |
| * does not permit null keys |
| * @since 1.6 |
| */ |
| public Map.Entry<K,V> floorEntry(K key) { |
| return exportEntry(getFloorEntry(key)); |
| } |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if the specified key is null |
| * and this map uses natural ordering, or its comparator |
| * does not permit null keys |
| * @since 1.6 |
| */ |
| public K floorKey(K key) { |
| return keyOrNull(getFloorEntry(key)); |
| } |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if the specified key is null |
| * and this map uses natural ordering, or its comparator |
| * does not permit null keys |
| * @since 1.6 |
| */ |
| public Map.Entry<K,V> ceilingEntry(K key) { |
| return exportEntry(getCeilingEntry(key)); |
| } |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if the specified key is null |
| * and this map uses natural ordering, or its comparator |
| * does not permit null keys |
| * @since 1.6 |
| */ |
| public K ceilingKey(K key) { |
| return keyOrNull(getCeilingEntry(key)); |
| } |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if the specified key is null |
| * and this map uses natural ordering, or its comparator |
| * does not permit null keys |
| * @since 1.6 |
| */ |
| public Map.Entry<K,V> higherEntry(K key) { |
| return exportEntry(getHigherEntry(key)); |
| } |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if the specified key is null |
| * and this map uses natural ordering, or its comparator |
| * does not permit null keys |
| * @since 1.6 |
| */ |
| public K higherKey(K key) { |
| return keyOrNull(getHigherEntry(key)); |
| } |
| |
| // Views |
| |
| /** |
| * Fields initialized to contain an instance of the entry set view |
| * the first time this view is requested. Views are stateless, so |
| * there's no reason to create more than one. |
| */ |
| private transient EntrySet entrySet = null; |
| private transient KeySet<K> navigableKeySet = null; |
| private transient NavigableMap<K,V> descendingMap = null; |
| |
| /** |
| * Returns a {@link Set} view of the keys contained in this map. |
| * The set's iterator returns the keys in ascending order. |
| * The set is backed by the map, so changes to the map are |
| * reflected in the set, and vice-versa. If the map is modified |
| * while an iteration over the set is in progress (except through |
| * the iterator's own {@code remove} operation), the results of |
| * the iteration are undefined. The set supports element removal, |
| * which removes the corresponding mapping from the map, via the |
| * {@code Iterator.remove}, {@code Set.remove}, |
| * {@code removeAll}, {@code retainAll}, and {@code clear} |
| * operations. It does not support the {@code add} or {@code addAll} |
| * operations. |
| */ |
| public Set<K> keySet() { |
| return navigableKeySet(); |
| } |
| |
| /** |
| * @since 1.6 |
| */ |
| public NavigableSet<K> navigableKeySet() { |
| KeySet<K> nks = navigableKeySet; |
| return (nks != null) ? nks : (navigableKeySet = new KeySet(this)); |
| } |
| |
| /** |
| * @since 1.6 |
| */ |
| public NavigableSet<K> descendingKeySet() { |
| return descendingMap().navigableKeySet(); |
| } |
| |
| /** |
| * Returns a {@link Collection} view of the values contained in this map. |
| * The collection's iterator returns the values in ascending order |
| * of the corresponding keys. |
| * The collection is backed by the map, so changes to the map are |
| * reflected in the collection, and vice-versa. If the map is |
| * modified while an iteration over the collection is in progress |
| * (except through the iterator's own {@code remove} operation), |
| * the results of the iteration are undefined. The collection |
| * supports element removal, which removes the corresponding |
| * mapping from the map, via the {@code Iterator.remove}, |
| * {@code Collection.remove}, {@code removeAll}, |
| * {@code retainAll} and {@code clear} operations. It does not |
| * support the {@code add} or {@code addAll} operations. |
| */ |
| public Collection<V> values() { |
| Collection<V> vs = values; |
| return (vs != null) ? vs : (values = new Values()); |
| } |
| |
| /** |
| * Returns a {@link Set} view of the mappings contained in this map. |
| * The set's iterator returns the entries in ascending key order. |
| * The set is backed by the map, so changes to the map are |
| * reflected in the set, and vice-versa. If the map is modified |
| * while an iteration over the set is in progress (except through |
| * the iterator's own {@code remove} operation, or through the |
| * {@code setValue} operation on a map entry returned by the |
| * iterator) the results of the iteration are undefined. The set |
| * supports element removal, which removes the corresponding |
| * mapping from the map, via the {@code Iterator.remove}, |
| * {@code Set.remove}, {@code removeAll}, {@code retainAll} and |
| * {@code clear} operations. It does not support the |
| * {@code add} or {@code addAll} operations. |
| */ |
| public Set<Map.Entry<K,V>> entrySet() { |
| EntrySet es = entrySet; |
| return (es != null) ? es : (entrySet = new EntrySet()); |
| } |
| |
| /** |
| * @since 1.6 |
| */ |
| public NavigableMap<K, V> descendingMap() { |
| NavigableMap<K, V> km = descendingMap; |
| return (km != null) ? km : |
| (descendingMap = new DescendingSubMap(this, |
| true, null, true, |
| true, null, true)); |
| } |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if {@code fromKey} or {@code toKey} is |
| * null and this map uses natural ordering, or its comparator |
| * does not permit null keys |
| * @throws IllegalArgumentException {@inheritDoc} |
| * @since 1.6 |
| */ |
| public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, |
| K toKey, boolean toInclusive) { |
| return new AscendingSubMap(this, |
| false, fromKey, fromInclusive, |
| false, toKey, toInclusive); |
| } |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if {@code toKey} is null |
| * and this map uses natural ordering, or its comparator |
| * does not permit null keys |
| * @throws IllegalArgumentException {@inheritDoc} |
| * @since 1.6 |
| */ |
| public NavigableMap<K,V> headMap(K toKey, boolean inclusive) { |
| return new AscendingSubMap(this, |
| true, null, true, |
| false, toKey, inclusive); |
| } |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if {@code fromKey} is null |
| * and this map uses natural ordering, or its comparator |
| * does not permit null keys |
| * @throws IllegalArgumentException {@inheritDoc} |
| * @since 1.6 |
| */ |
| public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) { |
| return new AscendingSubMap(this, |
| false, fromKey, inclusive, |
| true, null, true); |
| } |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if {@code fromKey} or {@code toKey} is |
| * null and this map uses natural ordering, or its comparator |
| * does not permit null keys |
| * @throws IllegalArgumentException {@inheritDoc} |
| */ |
| public SortedMap<K,V> subMap(K fromKey, K toKey) { |
| return subMap(fromKey, true, toKey, false); |
| } |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if {@code toKey} is null |
| * and this map uses natural ordering, or its comparator |
| * does not permit null keys |
| * @throws IllegalArgumentException {@inheritDoc} |
| */ |
| public SortedMap<K,V> headMap(K toKey) { |
| return headMap(toKey, false); |
| } |
| |
| /** |
| * @throws ClassCastException {@inheritDoc} |
| * @throws NullPointerException if {@code fromKey} is null |
| * and this map uses natural ordering, or its comparator |
| * does not permit null keys |
| * @throws IllegalArgumentException {@inheritDoc} |
| */ |
| public SortedMap<K,V> tailMap(K fromKey) { |
| return tailMap(fromKey, true); |
| } |
| |
| @Override |
| public void forEach(BiConsumer<? super K, ? super V> action) { |
| Objects.requireNonNull(action); |
| int expectedModCount = modCount; |
| for (TreeMapEntry<K, V> e = getFirstEntry(); e != null; e = successor(e)) { |
| action.accept(e.key, e.value); |
| |
| if (expectedModCount != modCount) { |
| throw new ConcurrentModificationException(); |
| } |
| } |
| } |
| |
| // View class support |
| |
| class Values extends AbstractCollection<V> { |
| public Iterator<V> iterator() { |
| return new ValueIterator(getFirstEntry()); |
| } |
| |
| public int size() { |
| return TreeMap.this.size(); |
| } |
| |
| public boolean contains(Object o) { |
| return TreeMap.this.containsValue(o); |
| } |
| |
| public boolean remove(Object o) { |
| for (TreeMapEntry<K,V> e = getFirstEntry(); e != null; e = successor(e)) { |
| if (valEquals(e.getValue(), o)) { |
| deleteEntry(e); |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| public void clear() { |
| TreeMap.this.clear(); |
| } |
| } |
| |
| class EntrySet extends AbstractSet<Map.Entry<K,V>> { |
| public Iterator<Map.Entry<K,V>> iterator() { |
| return new EntryIterator(getFirstEntry()); |
| } |
| |
| public boolean contains(Object o) { |
| if (!(o instanceof Map.Entry)) |
| return false; |
| Map.Entry<K,V> entry = (Map.Entry<K,V>) o; |
| V value = entry.getValue(); |
| TreeMapEntry<K,V> p = getEntry(entry.getKey()); |
| return p != null && valEquals(p.getValue(), value); |
| } |
| |
| public boolean remove(Object o) { |
| if (!(o instanceof Map.Entry)) |
| return false; |
| Map.Entry<K,V> entry = (Map.Entry<K,V>) o; |
| V value = entry.getValue(); |
| TreeMapEntry<K,V> p = getEntry(entry.getKey()); |
| if (p != null && valEquals(p.getValue(), value)) { |
| deleteEntry(p); |
| return true; |
| } |
| return false; |
| } |
| |
| public int size() { |
| return TreeMap.this.size(); |
| } |
| |
| public void clear() { |
| TreeMap.this.clear(); |
| } |
| } |
| |
| /* |
| * Unlike Values and EntrySet, the KeySet class is static, |
| * delegating to a NavigableMap to allow use by SubMaps, which |
| * outweighs the ugliness of needing type-tests for the following |
| * Iterator methods that are defined appropriately in main versus |
| * submap classes. |
| */ |
| |
| Iterator<K> keyIterator() { |
| return new KeyIterator(getFirstEntry()); |
| } |
| |
| Iterator<K> descendingKeyIterator() { |
| return new DescendingKeyIterator(getLastEntry()); |
| } |
| |
| static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> { |
| private final NavigableMap<E, Object> m; |
| KeySet(NavigableMap<E,Object> map) { m = map; } |
| |
| public Iterator<E> iterator() { |
| if (m instanceof TreeMap) |
| return ((TreeMap<E,Object>)m).keyIterator(); |
| else |
| return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator()); |
| } |
| |
| public Iterator<E> descendingIterator() { |
| if (m instanceof TreeMap) |
| return ((TreeMap<E,Object>)m).descendingKeyIterator(); |
| else |
| return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator()); |
| } |
| |
| public int size() { return m.size(); } |
| public boolean isEmpty() { return m.isEmpty(); } |
| public boolean contains(Object o) { return m.containsKey(o); } |
| public void clear() { m.clear(); } |
| public E lower(E e) { return m.lowerKey(e); } |
| public E floor(E e) { return m.floorKey(e); } |
| public E ceiling(E e) { return m.ceilingKey(e); } |
| public E higher(E e) { return m.higherKey(e); } |
| public E first() { return m.firstKey(); } |
| public E last() { return m.lastKey(); } |
| public Comparator<? super E> comparator() { return m.comparator(); } |
| public E pollFirst() { |
| Map.Entry<E,Object> e = m.pollFirstEntry(); |
| return (e == null) ? null : e.getKey(); |
| } |
| public E pollLast() { |
| Map.Entry<E,Object> e = m.pollLastEntry(); |
| return (e == null) ? null : e.getKey(); |
| } |
| public boolean remove(Object o) { |
| int oldSize = size(); |
| m.remove(o); |
| return size() != oldSize; |
| } |
| public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, |
| E toElement, boolean toInclusive) { |
| return new KeySet<>(m.subMap(fromElement, fromInclusive, |
| toElement, toInclusive)); |
| } |
| public NavigableSet<E> headSet(E toElement, boolean inclusive) { |
| return new KeySet<>(m.headMap(toElement, inclusive)); |
| } |
| public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { |
| return new KeySet<>(m.tailMap(fromElement, inclusive)); |
| } |
| public SortedSet<E> subSet(E fromElement, E toElement) { |
| return subSet(fromElement, true, toElement, false); |
| } |
| public SortedSet<E> headSet(E toElement) { |
| return headSet(toElement, false); |
| } |
| public SortedSet<E> tailSet(E fromElement) { |
| return tailSet(fromElement, true); |
| } |
| public NavigableSet<E> descendingSet() { |
| return new KeySet(m.descendingMap()); |
| } |
| } |
| |
| /** |
| * Base class for TreeMap Iterators |
| */ |
| abstract class PrivateEntryIterator<T> implements Iterator<T> { |
| TreeMapEntry<K,V> next; |
| TreeMapEntry<K,V> lastReturned; |
| int expectedModCount; |
| |
| PrivateEntryIterator(TreeMapEntry<K,V> first) { |
| expectedModCount = modCount; |
| lastReturned = null; |
| next = first; |
| } |
| |
| public final boolean hasNext() { |
| return next != null; |
| } |
| |
| final TreeMapEntry<K,V> nextEntry() { |
| TreeMapEntry<K,V> e = next; |
| if (e == null) |
| throw new NoSuchElementException(); |
| if (modCount != expectedModCount) |
| throw new ConcurrentModificationException(); |
| next = successor(e); |
| lastReturned = e; |
| return e; |
| } |
| |
| final TreeMapEntry<K,V> prevEntry() { |
| TreeMapEntry<K,V> e = next; |
| if (e == null) |
| throw new NoSuchElementException(); |
| if (modCount != expectedModCount) |
| throw new ConcurrentModificationException(); |
| next = predecessor(e); |
| lastReturned = e; |
| return e; |
| } |
| |
| public void remove() { |
| if (lastReturned == null) |
| throw new IllegalStateException(); |
| if (modCount != expectedModCount) |
| throw new ConcurrentModificationException(); |
| // deleted entries are replaced by their successors |
| if (lastReturned.left != null && lastReturned.right != null) |
| next = lastReturned; |
| deleteEntry(lastReturned); |
| expectedModCount = modCount; |
| lastReturned = null; |
| } |
| } |
| |
| final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> { |
| EntryIterator(TreeMapEntry<K,V> first) { |
| super(first); |
| } |
| public Map.Entry<K,V> next() { |
| return nextEntry(); |
| } |
| } |
| |
| final class ValueIterator extends PrivateEntryIterator<V> { |
| ValueIterator(TreeMapEntry<K,V> first) { |
| super(first); |
| } |
| public V next() { |
| return nextEntry().value; |
| } |
| } |
| |
| final class KeyIterator extends PrivateEntryIterator<K> { |
| KeyIterator(TreeMapEntry<K,V> first) { |
| super(first); |
| } |
| public K next() { |
| return nextEntry().key; |
| } |
| } |
| |
| final class DescendingKeyIterator extends PrivateEntryIterator<K> { |
| DescendingKeyIterator(TreeMapEntry<K,V> first) { |
| super(first); |
| } |
| public K next() { |
| return prevEntry().key; |
| } |
| } |
| |
| // Little utilities |
| |
| /** |
| * Compares two keys using the correct comparison method for this TreeMap. |
| */ |
| final int compare(Object k1, Object k2) { |
| return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2) |
| : comparator.compare((K)k1, (K)k2); |
| } |
| |
| /** |
| * Test two values for equality. Differs from o1.equals(o2) only in |
| * that it copes with {@code null} o1 properly. |
| */ |
| static final boolean valEquals(Object o1, Object o2) { |
| return (o1==null ? o2==null : o1.equals(o2)); |
| } |
| |
| /** |
| * Return SimpleImmutableEntry for entry, or null if null |
| */ |
| static <K,V> Map.Entry<K,V> exportEntry(TreeMapEntry<K,V> e) { |
| return (e == null) ? null : |
| new AbstractMap.SimpleImmutableEntry<>(e); |
| } |
| |
| /** |
| * Return key for entry, or null if null |
| */ |
| static <K,V> K keyOrNull(TreeMapEntry<K,V> e) { |
| return (e == null) ? null : e.key; |
| } |
| |
| /** |
| * Returns the key corresponding to the specified Entry. |
| * @throws NoSuchElementException if the Entry is null |
| */ |
| static <K> K key(TreeMapEntry<K,?> e) { |
| if (e==null) |
| throw new NoSuchElementException(); |
| return e.key; |
| } |
| |
| |
| // SubMaps |
| |
| /** |
| * Dummy value serving as unmatchable fence key for unbounded |
| * SubMapIterators |
| */ |
| private static final Object UNBOUNDED = new Object(); |
| |
| /** |
| * @serial include |
| */ |
| abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V> |
| implements NavigableMap<K,V>, java.io.Serializable { |
| /** |
| * The backing map. |
| */ |
| final TreeMap<K,V> m; |
| |
| /** |
| * Endpoints are represented as triples (fromStart, lo, |
| * loInclusive) and (toEnd, hi, hiInclusive). If fromStart is |
| * true, then the low (absolute) bound is the start of the |
| * backing map, and the other values are ignored. Otherwise, |
| * if loInclusive is true, lo is the inclusive bound, else lo |
| * is the exclusive bound. Similarly for the upper bound. |
| */ |
| final K lo, hi; |
| final boolean fromStart, toEnd; |
| final boolean loInclusive, hiInclusive; |
| |
| NavigableSubMap(TreeMap<K,V> m, |
| boolean fromStart, K lo, boolean loInclusive, |
| boolean toEnd, K hi, boolean hiInclusive) { |
| if (!fromStart && !toEnd) { |
| if (m.compare(lo, hi) > 0) |
| throw new IllegalArgumentException("fromKey > toKey"); |
| } else { |
| if (!fromStart) // type check |
| m.compare(lo, lo); |
| if (!toEnd) |
| m.compare(hi, hi); |
| } |
| |
| this.m = m; |
| this.fromStart = fromStart; |
| this.lo = lo; |
| this.loInclusive = loInclusive; |
| this.toEnd = toEnd; |
| this.hi = hi; |
| this.hiInclusive = hiInclusive; |
| } |
| |
| // internal utilities |
| |
| final boolean tooLow(Object key) { |
| if (!fromStart) { |
| int c = m.compare(key, lo); |
| if (c < 0 || (c == 0 && !loInclusive)) |
| return true; |
| } |
| return false; |
| } |
| |
| final boolean tooHigh(Object key) { |
| if (!toEnd) { |
| int c = m.compare(key, hi); |
| if (c > 0 || (c == 0 && !hiInclusive)) |
| return true; |
| } |
| return false; |
| } |
| |
| final boolean inRange(Object key) { |
| return !tooLow(key) && !tooHigh(key); |
| } |
| |
| final boolean inClosedRange(Object key) { |
| return (fromStart || m.compare(key, lo) >= 0) |
| && (toEnd || m.compare(hi, key) >= 0); |
| } |
| |
| final boolean inRange(Object key, boolean inclusive) { |
| return inclusive ? inRange(key) : inClosedRange(key); |
| } |
| |
| /* |
| * Absolute versions of relation operations. |
| * Subclasses map to these using like-named "sub" |
| * versions that invert senses for descending maps |
| */ |
| |
| final TreeMapEntry<K,V> absLowest() { |
| TreeMapEntry<K,V> e = |
| (fromStart ? m.getFirstEntry() : |
| (loInclusive ? m.getCeilingEntry(lo) : |
| m.getHigherEntry(lo))); |
| return (e == null || tooHigh(e.key)) ? null : e; |
| } |
| |
| final TreeMapEntry<K,V> absHighest() { |
| TreeMapEntry<K,V> e = |
| (toEnd ? m.getLastEntry() : |
| (hiInclusive ? m.getFloorEntry(hi) : |
| m.getLowerEntry(hi))); |
| return (e == null || tooLow(e.key)) ? null : e; |
| } |
| |
| final TreeMapEntry<K,V> absCeiling(K key) { |
| if (tooLow(key)) |
| return absLowest(); |
| TreeMapEntry<K,V> e = m.getCeilingEntry(key); |
| return (e == null || tooHigh(e.key)) ? null : e; |
| } |
| |
| final TreeMapEntry<K,V> absHigher(K key) { |
| if (tooLow(key)) |
| return absLowest(); |
| TreeMapEntry<K,V> e = m.getHigherEntry(key); |
| return (e == null || tooHigh(e.key)) ? null : e; |
| } |
| |
| final TreeMapEntry<K,V> absFloor(K key) { |
| if (tooHigh(key)) |
| return absHighest(); |
| TreeMapEntry<K,V> e = m.getFloorEntry(key); |
| return (e == null || tooLow(e.key)) ? null : e; |
| } |
| |
| final TreeMapEntry<K,V> absLower(K key) { |
| if (tooHigh(key)) |
| return absHighest(); |
| TreeMapEntry<K,V> e = m.getLowerEntry(key); |
| return (e == null || tooLow(e.key)) ? null : e; |
| } |
| |
| /** Returns the absolute high fence for ascending traversal */ |
| final TreeMapEntry<K,V> absHighFence() { |
| return (toEnd ? null : (hiInclusive ? |
| m.getHigherEntry(hi) : |
| m.getCeilingEntry(hi))); |
| } |
| |
| /** Return the absolute low fence for descending traversal */ |
| final TreeMapEntry<K,V> absLowFence() { |
| return (fromStart ? null : (loInclusive ? |
| m.getLowerEntry(lo) : |
| m.getFloorEntry(lo))); |
| } |
| |
| // Abstract methods defined in ascending vs descending classes |
| // These relay to the appropriate absolute versions |
| |
| abstract TreeMapEntry<K,V> subLowest(); |
| abstract TreeMapEntry<K,V> subHighest(); |
| abstract TreeMapEntry<K,V> subCeiling(K key); |
| abstract TreeMapEntry<K,V> subHigher(K key); |
| abstract TreeMapEntry<K,V> subFloor(K key); |
| abstract TreeMapEntry<K,V> subLower(K key); |
| |
| /** Returns ascending iterator from the perspective of this submap */ |
| abstract Iterator<K> keyIterator(); |
| |
| /** Returns descending iterator from the perspective of this submap */ |
| abstract Iterator<K> descendingKeyIterator(); |
| |
| // public methods |
| |
| public boolean isEmpty() { |
| return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty(); |
| } |
| |
| public int size() { |
| return (fromStart && toEnd) ? m.size() : entrySet().size(); |
| } |
| |
| public final boolean containsKey(Object key) { |
| return inRange(key) && m.containsKey(key); |
| } |
| |
| public final V put(K key, V value) { |
| if (!inRange(key)) |
| throw new IllegalArgumentException("key out of range"); |
| return m.put(key, value); |
| } |
| |
| public final V get(Object key) { |
| return !inRange(key) ? null : m.get(key); |
| } |
| |
| public final V remove(Object key) { |
| return !inRange(key) ? null : m.remove(key); |
| } |
| |
| public final Map.Entry<K,V> ceilingEntry(K key) { |
| return exportEntry(subCeiling(key)); |
| } |
| |
| public final K ceilingKey(K key) { |
| return keyOrNull(subCeiling(key)); |
| } |
| |
| public final Map.Entry<K,V> higherEntry(K key) { |
| return exportEntry(subHigher(key)); |
| } |
| |
| public final K higherKey(K key) { |
| return keyOrNull(subHigher(key)); |
| } |
| |
| public final Map.Entry<K,V> floorEntry(K key) { |
| return exportEntry(subFloor(key)); |
| } |
| |
| public final K floorKey(K key) { |
| return keyOrNull(subFloor(key)); |
| } |
| |
| public final Map.Entry<K,V> lowerEntry(K key) { |
| return exportEntry(subLower(key)); |
| } |
| |
| public final K lowerKey(K key) { |
| return keyOrNull(subLower(key)); |
| } |
| |
| public final K firstKey() { |
| return key(subLowest()); |
| } |
| |
| public final K lastKey() { |
| return key(subHighest()); |
| } |
| |
| public final Map.Entry<K,V> firstEntry() { |
| return exportEntry(subLowest()); |
| } |
| |
| public final Map.Entry<K,V> lastEntry() { |
| return exportEntry(subHighest()); |
| } |
| |
| public final Map.Entry<K,V> pollFirstEntry() { |
| TreeMapEntry<K,V> e = subLowest(); |
| Map.Entry<K,V> result = exportEntry(e); |
| if (e != null) |
| m.deleteEntry(e); |
| return result; |
| } |
| |
| public final Map.Entry<K,V> pollLastEntry() { |
| TreeMapEntry<K,V> e = subHighest(); |
| Map.Entry<K,V> result = exportEntry(e); |
| if (e != null) |
| m.deleteEntry(e); |
| return result; |
| } |
| |
| // Views |
| transient NavigableMap<K,V> descendingMapView = null; |
| transient EntrySetView entrySetView = null; |
| transient KeySet<K> navigableKeySetView = null; |
| |
| public final NavigableSet<K> navigableKeySet() { |
| KeySet<K> nksv = navigableKeySetView; |
| return (nksv != null) ? nksv : |
| (navigableKeySetView = new TreeMap.KeySet(this)); |
| } |
| |
| public final Set<K> keySet() { |
| return navigableKeySet(); |
| } |
| |
| public NavigableSet<K> descendingKeySet() { |
| return descendingMap().navigableKeySet(); |
| } |
| |
| public final SortedMap<K,V> subMap(K fromKey, K toKey) { |
| return subMap(fromKey, true, toKey, false); |
| } |
| |
| public final SortedMap<K,V> headMap(K toKey) { |
| return headMap(toKey, false); |
| } |
| |
| public final SortedMap<K,V> tailMap(K fromKey) { |
| return tailMap(fromKey, true); |
| } |
| |
| // View classes |
| |
| abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> { |
| private transient int size = -1, sizeModCount; |
| |
| public int size() { |
| if (fromStart && toEnd) |
| return m.size(); |
| if (size == -1 || sizeModCount != m.modCount) { |
| sizeModCount = m.modCount; |
| size = 0; |
| Iterator i = iterator(); |
| while (i.hasNext()) { |
| size++; |
| i.next(); |
| } |
| } |
| return size; |
| } |
| |
| public boolean isEmpty() { |
| TreeMapEntry<K,V> n = absLowest(); |
| return n == null || tooHigh(n.key); |
| } |
| |
| public boolean contains(Object o) { |
| if (!(o instanceof Map.Entry)) |
| return false; |
| Map.Entry<K,V> entry = (Map.Entry<K,V>) o; |
| K key = entry.getKey(); |
| if (!inRange(key)) |
| return false; |
| TreeMapEntry node = m.getEntry(key); |
| return node != null && |
| valEquals(node.getValue(), entry.getValue()); |
| } |
| |
| public boolean remove(Object o) { |
| if (!(o instanceof Map.Entry)) |
| return false; |
| Map.Entry<K,V> entry = (Map.Entry<K,V>) o; |
| K key = entry.getKey(); |
| if (!inRange(key)) |
| return false; |
| TreeMapEntry<K,V> node = m.getEntry(key); |
| if (node!=null && valEquals(node.getValue(), |
| entry.getValue())) { |
| m.deleteEntry(node); |
| return true; |
| } |
| return false; |
| } |
| } |
| |
| /** |
| * Iterators for SubMaps |
| */ |
| abstract class SubMapIterator<T> implements Iterator<T> { |
| TreeMapEntry<K,V> lastReturned; |
| TreeMapEntry<K,V> next; |
| final Object fenceKey; |
| int expectedModCount; |
| |
| SubMapIterator(TreeMapEntry<K,V> first, |
| TreeMapEntry<K,V> fence) { |
| expectedModCount = m.modCount; |
| lastReturned = null; |
| next = first; |
| fenceKey = fence == null ? UNBOUNDED : fence.key; |
| } |
| |
| public final boolean hasNext() { |
| return next != null && next.key != fenceKey; |
| } |
| |
| final TreeMapEntry<K,V> nextEntry() { |
| TreeMapEntry<K,V> e = next; |
| if (e == null || e.key == fenceKey) |
| throw new NoSuchElementException(); |
| if (m.modCount != expectedModCount) |
| throw new ConcurrentModificationException(); |
| next = successor(e); |
| lastReturned = e; |
| return e; |
| } |
| |
| final TreeMapEntry<K,V> prevEntry() { |
| TreeMapEntry<K,V> e = next; |
| if (e == null || e.key == fenceKey) |
| throw new NoSuchElementException(); |
| if (m.modCount != expectedModCount) |
| throw new ConcurrentModificationException(); |
| next = predecessor(e); |
| lastReturned = e; |
| return e; |
| } |
| |
| final void removeAscending() { |
| if (lastReturned == null) |
| throw new IllegalStateException(); |
| if (m.modCount != expectedModCount) |
| throw new ConcurrentModificationException(); |
| // deleted entries are replaced by their successors |
| if (lastReturned.left != null && lastReturned.right != null) |
| next = lastReturned; |
| m.deleteEntry(lastReturned); |
| lastReturned = null; |
| expectedModCount = m.modCount; |
| } |
| |
| final void removeDescending() { |
| if (lastReturned == null) |
| throw new IllegalStateException(); |
| if (m.modCount != expectedModCount) |
| throw new ConcurrentModificationException(); |
| m.deleteEntry(lastReturned); |
| lastReturned = null; |
| expectedModCount = m.modCount; |
| } |
| |
| } |
| |
| final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> { |
| SubMapEntryIterator(TreeMapEntry<K,V> first, |
| TreeMapEntry<K,V> fence) { |
| super(first, fence); |
| } |
| public Map.Entry<K,V> next() { |
| return nextEntry(); |
| } |
| public void remove() { |
| removeAscending(); |
| } |
| } |
| |
| final class SubMapKeyIterator extends SubMapIterator<K> { |
| SubMapKeyIterator(TreeMapEntry<K,V> first, |
| TreeMapEntry<K,V> fence) { |
| super(first, fence); |
| } |
| public K next() { |
| return nextEntry().key; |
| } |
| public void remove() { |
| removeAscending(); |
| } |
| } |
| |
| final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> { |
| DescendingSubMapEntryIterator(TreeMapEntry<K,V> last, |
| TreeMapEntry<K,V> fence) { |
| super(last, fence); |
| } |
| |
| public Map.Entry<K,V> next() { |
| return prevEntry(); |
| } |
| public void remove() { |
| removeDescending(); |
| } |
| } |
| |
| final class DescendingSubMapKeyIterator extends SubMapIterator<K> { |
| DescendingSubMapKeyIterator(TreeMapEntry<K,V> last, |
| TreeMapEntry<K,V> fence) { |
| super(last, fence); |
| } |
| public K next() { |
| return prevEntry().key; |
| } |
| public void remove() { |
| removeDescending(); |
| } |
| } |
| } |
| |
| /** |
| * @serial include |
| */ |
| static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> { |
| private static final long serialVersionUID = 912986545866124060L; |
| |
| AscendingSubMap(TreeMap<K,V> m, |
| boolean fromStart, K lo, boolean loInclusive, |
| boolean toEnd, K hi, boolean hiInclusive) { |
| super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive); |
| } |
| |
| public Comparator<? super K> comparator() { |
| return m.comparator(); |
| } |
| |
| public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, |
| K toKey, boolean toInclusive) { |
| if (!inRange(fromKey, fromInclusive)) |
| throw new IllegalArgumentException("fromKey out of range"); |
| if (!inRange(toKey, toInclusive)) |
| throw new IllegalArgumentException("toKey out of range"); |
| return new AscendingSubMap(m, |
| false, fromKey, fromInclusive, |
| false, toKey, toInclusive); |
| } |
| |
| public NavigableMap<K,V> headMap(K toKey, boolean inclusive) { |
| /* ----- BEGIN android ----- |
| Fix for edge cases |
| if (!inRange(toKey, inclusive)) */ |
| if (!inRange(toKey) && !(!toEnd && m.compare(toKey, hi) == 0 && |
| !hiInclusive && !inclusive)) |
| // ----- END android ----- |
| throw new IllegalArgumentException("toKey out of range"); |
| return new AscendingSubMap(m, |
| fromStart, lo, loInclusive, |
| false, toKey, inclusive); |
| } |
| |
| public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) { |
| /* ----- BEGIN android ----- |
| Fix for edge cases |
| if (!inRange(fromKey, inclusive)) */ |
| if (!inRange(fromKey) && !(!fromStart && m.compare(fromKey, lo) == 0 && |
| !loInclusive && !inclusive)) |
| // ----- END android ----- |
| throw new IllegalArgumentException("fromKey out of range"); |
| return new AscendingSubMap(m, |
| false, fromKey, inclusive, |
| toEnd, hi, hiInclusive); |
| } |
| |
| public NavigableMap<K,V> descendingMap() { |
| NavigableMap<K,V> mv = descendingMapView; |
| return (mv != null) ? mv : |
| (descendingMapView = |
| new DescendingSubMap(m, |
| fromStart, lo, loInclusive, |
| toEnd, hi, hiInclusive)); |
| } |
| |
| Iterator<K> keyIterator() { |
| return new SubMapKeyIterator(absLowest(), absHighFence()); |
| } |
| |
| Iterator<K> descendingKeyIterator() { |
| return new DescendingSubMapKeyIterator(absHighest(), absLowFence()); |
| } |
| |
| final class AscendingEntrySetView extends EntrySetView { |
| public Iterator<Map.Entry<K,V>> iterator() { |
| return new SubMapEntryIterator(absLowest(), absHighFence()); |
| } |
| } |
| |
| public Set<Map.Entry<K,V>> entrySet() { |
| EntrySetView es = entrySetView; |
| return (es != null) ? es : new AscendingEntrySetView(); |
| } |
| |
| TreeMapEntry<K,V> subLowest() { return absLowest(); } |
| TreeMapEntry<K,V> subHighest() { return absHighest(); } |
| TreeMapEntry<K,V> subCeiling(K key) { return absCeiling(key); } |
| TreeMapEntry<K,V> subHigher(K key) { return absHigher(key); } |
| TreeMapEntry<K,V> subFloor(K key) { return absFloor(key); } |
| TreeMapEntry<K,V> subLower(K key) { return absLower(key); } |
| } |
| |
| /** |
| * @serial include |
| */ |
| static final class DescendingSubMap<K,V> extends NavigableSubMap<K,V> { |
| private static final long serialVersionUID = 912986545866120460L; |
| DescendingSubMap(TreeMap<K,V> m, |
| boolean fromStart, K lo, boolean loInclusive, |
| boolean toEnd, K hi, boolean hiInclusive) { |
| super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive); |
| } |
| |
| private final Comparator<? super K> reverseComparator = |
| Collections.reverseOrder(m.comparator); |
| |
| public Comparator<? super K> comparator() { |
| return reverseComparator; |
| } |
| |
| public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, |
| K toKey, boolean toInclusive) { |
| if (!inRange(fromKey, fromInclusive)) |
| throw new IllegalArgumentException("fromKey out of range"); |
| if (!inRange(toKey, toInclusive)) |
| throw new IllegalArgumentException("toKey out of range"); |
| return new DescendingSubMap(m, |
| false, toKey, toInclusive, |
| false, fromKey, fromInclusive); |
| } |
| |
| public NavigableMap<K,V> headMap(K toKey, boolean inclusive) { |
| /* ----- BEGIN android ----- |
| Fix for edge cases |
| if (!inRange(toKey, inclusive)) */ |
| if (!inRange(toKey) && !(!fromStart && m.compare(toKey, lo) == 0 && |
| !loInclusive && !inclusive)) |
| // ----- END android ----- |
| throw new IllegalArgumentException("toKey out of range"); |
| return new DescendingSubMap(m, |
| false, toKey, inclusive, |
| toEnd, hi, hiInclusive); |
| } |
| |
| public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) { |
| /* ----- BEGIN android ----- |
| Fix for edge cases |
| if (!inRange(fromKey, inclusive)) */ |
| if (!inRange(fromKey) && !(!toEnd && m.compare(fromKey, hi) == 0 && |
| !hiInclusive && !inclusive)) |
| // ----- END android ----- |
| throw new IllegalArgumentException("fromKey out of range"); |
| return new DescendingSubMap(m, |
| fromStart, lo, loInclusive, |
| false, fromKey, inclusive); |
| } |
| |
| public NavigableMap<K,V> descendingMap() { |
| NavigableMap<K,V> mv = descendingMapView; |
| return (mv != null) ? mv : |
| (descendingMapView = |
| new AscendingSubMap(m, |
| fromStart, lo, loInclusive, |
| toEnd, hi, hiInclusive)); |
| } |
| |
| Iterator<K> keyIterator() { |
| return new DescendingSubMapKeyIterator(absHighest(), absLowFence()); |
| } |
| |
| Iterator<K> descendingKeyIterator() { |
| return new SubMapKeyIterator(absLowest(), absHighFence()); |
| } |
| |
| final class DescendingEntrySetView extends EntrySetView { |
| public Iterator<Map.Entry<K,V>> iterator() { |
| return new DescendingSubMapEntryIterator(absHighest(), absLowFence()); |
| } |
| } |
| |
| public Set<Map.Entry<K,V>> entrySet() { |
| EntrySetView es = entrySetView; |
| return (es != null) ? es : new DescendingEntrySetView(); |
| } |
| |
| TreeMapEntry<K,V> subLowest() { return absHighest(); } |
| TreeMapEntry<K,V> subHighest() { return absLowest(); } |
| TreeMapEntry<K,V> subCeiling(K key) { return absFloor(key); } |
| TreeMapEntry<K,V> subHigher(K key) { return absLower(key); } |
| TreeMapEntry<K,V> subFloor(K key) { return absCeiling(key); } |
| TreeMapEntry<K,V> subLower(K key) { return absHigher(key); } |
| } |
| |
| /** |
| * This class exists solely for the sake of serialization |
| * compatibility with previous releases of TreeMap that did not |
| * support NavigableMap. It translates an old-version SubMap into |
| * a new-version AscendingSubMap. This class is never otherwise |
| * used. |
| * |
| * @serial include |
| */ |
| private class SubMap extends AbstractMap<K,V> |
| implements SortedMap<K,V>, java.io.Serializable { |
| private static final long serialVersionUID = -6520786458950516097L; |
| private boolean fromStart = false, toEnd = false; |
| private K fromKey, toKey; |
| private Object readResolve() { |
| return new AscendingSubMap(TreeMap.this, |
| fromStart, fromKey, true, |
| toEnd, toKey, false); |
| } |
| public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); } |
| public K lastKey() { throw new InternalError(); } |
| public K firstKey() { throw new InternalError(); } |
| public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); } |
| public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); } |
| public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); } |
| public Comparator<? super K> comparator() { throw new InternalError(); } |
| } |
| |
| |
| // Red-black mechanics |
| |
| private static final boolean RED = false; |
| private static final boolean BLACK = true; |
| |
| /** |
| * Node in the Tree. Doubles as a means to pass key-value pairs back to |
| * user (see Map.Entry). |
| */ |
| |
| static final class TreeMapEntry<K,V> implements Map.Entry<K,V> { |
| K key; |
| V value; |
| TreeMapEntry<K,V> left = null; |
| TreeMapEntry<K,V> right = null; |
| TreeMapEntry<K,V> parent; |
| boolean color = BLACK; |
| |
| /** |
| * Make a new cell with given key, value, and parent, and with |
| * {@code null} child links, and BLACK color. |
| */ |
| TreeMapEntry(K key, V value, TreeMapEntry<K,V> parent) { |
| this.key = key; |
| this.value = value; |
| this.parent = parent; |
| } |
| |
| /** |
| * Returns the key. |
| * |
| * @return the key |
| */ |
| public K getKey() { |
| return key; |
| } |
| |
| /** |
| * Returns the value associated with the key. |
| * |
| * @return the value associated with the key |
| */ |
| public V getValue() { |
| return value; |
| } |
| |
| /** |
| * Replaces the value currently associated with the key with the given |
| * value. |
| * |
| * @return the value associated with the key before this method was |
| * called |
| */ |
| public V setValue(V value) { |
| V oldValue = this.value; |
| this.value = value; |
| return oldValue; |
| } |
| |
| public boolean equals(Object o) { |
| if (!(o instanceof Map.Entry)) |
| return false; |
| Map.Entry<?,?> e = (Map.Entry<?,?>)o; |
| |
| return valEquals(key,e.getKey()) && valEquals(value,e.getValue()); |
| } |
| |
| public int hashCode() { |
| int keyHash = (key==null ? 0 : key.hashCode()); |
| int valueHash = (value==null ? 0 : value.hashCode()); |
| return keyHash ^ valueHash; |
| } |
| |
| public String toString() { |
| return key + "=" + value; |
| } |
| } |
| |
| /** |
| * Returns the first Entry in the TreeMap (according to the TreeMap's |
| * key-sort function). Returns null if the TreeMap is empty. |
| */ |
| final TreeMapEntry<K,V> getFirstEntry() { |
| TreeMapEntry<K,V> p = root; |
| if (p != null) |
| while (p.left != null) |
| p = p.left; |
| return p; |
| } |
| |
| /** |
| * Returns the last Entry in the TreeMap (according to the TreeMap's |
| * key-sort function). Returns null if the TreeMap is empty. |
| */ |
| final TreeMapEntry<K,V> getLastEntry() { |
| TreeMapEntry<K,V> p = root; |
| if (p != null) |
| while (p.right != null) |
| p = p.right; |
| return p; |
| } |
| |
| /** |
| * Returns the successor of the specified Entry, or null if no such. |
| */ |
| static <K,V> TreeMapEntry<K,V> successor(TreeMapEntry<K,V> t) { |
| if (t == null) |
| return null; |
| else if (t.right != null) { |
| TreeMapEntry<K,V> p = t.right; |
| while (p.left != null) |
| p = p.left; |
| return p; |
| } else { |
| TreeMapEntry<K,V> p = t.parent; |
| TreeMapEntry<K,V> ch = t; |
| while (p != null && ch == p.right) { |
| ch = p; |
| p = p.parent; |
| } |
| return p; |
| } |
| } |
| |
| /** |
| * Returns the predecessor of the specified Entry, or null if no such. |
| */ |
| static <K,V> TreeMapEntry<K,V> predecessor(TreeMapEntry<K,V> t) { |
| if (t == null) |
| return null; |
| else if (t.left != null) { |
| TreeMapEntry<K,V> p = t.left; |
| while (p.right != null) |
| p = p.right; |
| return p; |
| } else { |
| TreeMapEntry<K,V> p = t.parent; |
| TreeMapEntry<K,V> ch = t; |
| while (p != null && ch == p.left) { |
| ch = p; |
| p = p.parent; |
| } |
| return p; |
| } |
| } |
| |
| /** |
| * Balancing operations. |
| * |
| * Implementations of rebalancings during insertion and deletion are |
| * slightly different than the CLR version. Rather than using dummy |
| * nilnodes, we use a set of accessors that deal properly with null. They |
| * are used to avoid messiness surrounding nullness checks in the main |
| * algorithms. |
| */ |
| |
| private static <K,V> boolean colorOf(TreeMapEntry<K,V> p) { |
| return (p == null ? BLACK : p.color); |
| } |
| |
| private static <K,V> TreeMapEntry<K,V> parentOf(TreeMapEntry<K,V> p) { |
| return (p == null ? null: p.parent); |
| } |
| |
| private static <K,V> void setColor(TreeMapEntry<K,V> p, boolean c) { |
| if (p != null) |
| p.color = c; |
| } |
| |
| private static <K,V> TreeMapEntry<K,V> leftOf(TreeMapEntry<K,V> p) { |
| return (p == null) ? null: p.left; |
| } |
| |
| private static <K,V> TreeMapEntry<K,V> rightOf(TreeMapEntry<K,V> p) { |
| return (p == null) ? null: p.right; |
| } |
| |
| /** From CLR */ |
| private void rotateLeft(TreeMapEntry<K,V> p) { |
| if (p != null) { |
| TreeMapEntry<K,V> r = p.right; |
| p.right = r.left; |
| if (r.left != null) |
| r.left.parent = p; |
| r.parent = p.parent; |
| if (p.parent == null) |
| root = r; |
| else if (p.parent.left == p) |
| p.parent.left = r; |
| else |
| p.parent.right = r; |
| r.left = p; |
| p.parent = r; |
| } |
| } |
| |
| /** From CLR */ |
| private void rotateRight(TreeMapEntry<K,V> p) { |
| if (p != null) { |
| TreeMapEntry<K,V> l = p.left; |
| p.left = l.right; |
| if (l.right != null) l.right.parent = p; |
| l.parent = p.parent; |
| if (p.parent == null) |
| root = l; |
| else if (p.parent.right == p) |
| p.parent.right = l; |
| else p.parent.left = l; |
| l.right = p; |
| p.parent = l; |
| } |
| } |
| |
| /** From CLR */ |
| private void fixAfterInsertion(TreeMapEntry<K,V> x) { |
| x.color = RED; |
| |
| while (x != null && x != root && x.parent.color == RED) { |
| if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { |
| TreeMapEntry<K,V> y = rightOf(parentOf(parentOf(x))); |
| if (colorOf(y) == RED) { |
| setColor(parentOf(x), BLACK); |
| setColor(y, BLACK); |
| setColor(parentOf(parentOf(x)), RED); |
| x = parentOf(parentOf(x)); |
| } else { |
| if (x == rightOf(parentOf(x))) { |
| x = parentOf(x); |
| rotateLeft(x); |
| } |
| setColor(parentOf(x), BLACK); |
| setColor(parentOf(parentOf(x)), RED); |
| rotateRight(parentOf(parentOf(x))); |
| } |
| } else { |
| TreeMapEntry<K,V> y = leftOf(parentOf(parentOf(x))); |
| if (colorOf(y) == RED) { |
| setColor(parentOf(x), BLACK); |
| setColor(y, BLACK); |
| setColor(parentOf(parentOf(x)), RED); |
| x = parentOf(parentOf(x)); |
| } else { |
| if (x == leftOf(parentOf(x))) { |
| x = parentOf(x); |
| rotateRight(x); |
| } |
| setColor(parentOf(x), BLACK); |
| setColor(parentOf(parentOf(x)), RED); |
| rotateLeft(parentOf(parentOf(x))); |
| } |
| } |
| } |
| root.color = BLACK; |
| } |
| |
| /** |
| * Delete node p, and then rebalance the tree. |
| */ |
| private void deleteEntry(TreeMapEntry<K,V> p) { |
| modCount++; |
| size--; |
| |
| // If strictly internal, copy successor's element to p and then make p |
| // point to successor. |
| if (p.left != null && p.right != null) { |
| TreeMapEntry<K,V> s = successor(p); |
| p.key = s.key; |
| p.value = s.value; |
| p = s; |
| } // p has 2 children |
| |
| // Start fixup at replacement node, if it exists. |
| TreeMapEntry<K,V> replacement = (p.left != null ? p.left : p.right); |
| |
| if (replacement != null) { |
| // Link replacement to parent |
| replacement.parent = p.parent; |
| if (p.parent == null) |
| root = replacement; |
| else if (p == p.parent.left) |
| p.parent.left = replacement; |
| else |
| p.parent.right = replacement; |
| |
| // Null out links so they are OK to use by fixAfterDeletion. |
| p.left = p.right = p.parent = null; |
| |
| // Fix replacement |
| if (p.color == BLACK) |
| fixAfterDeletion(replacement); |
| } else if (p.parent == null) { // return if we are the only node. |
| root = null; |
| } else { // No children. Use self as phantom replacement and unlink. |
| if (p.color == BLACK) |
| fixAfterDeletion(p); |
| |
| if (p.parent != null) { |
| if (p == p.parent.left) |
| p.parent.left = null; |
| else if (p == p.parent.right) |
| p.parent.right = null; |
| p.parent = null; |
| } |
| } |
| } |
| |
| /** From CLR */ |
| private void fixAfterDeletion(TreeMapEntry<K,V> x) { |
| while (x != root && colorOf(x) == BLACK) { |
| if (x == leftOf(parentOf(x))) { |
| TreeMapEntry<K,V> sib = rightOf(parentOf(x)); |
| |
| if (colorOf(sib) == RED) { |
| setColor(sib, BLACK); |
| setColor(parentOf(x), RED); |
| rotateLeft(parentOf(x)); |
| sib = rightOf(parentOf(x)); |
| } |
| |
| if (colorOf(leftOf(sib)) == BLACK && |
| colorOf(rightOf(sib)) == BLACK) { |
| setColor(sib, RED); |
| x = parentOf(x); |
| } else { |
| if (colorOf(rightOf(sib)) == BLACK) { |
| setColor(leftOf(sib), BLACK); |
| setColor(sib, RED); |
| rotateRight(sib); |
| sib = rightOf(parentOf(x)); |
| } |
| setColor(sib, colorOf(parentOf(x))); |
| setColor(parentOf(x), BLACK); |
| setColor(rightOf(sib), BLACK); |
| rotateLeft(parentOf(x)); |
| x = root; |
| } |
| } else { // symmetric |
| TreeMapEntry<K,V> sib = leftOf(parentOf(x)); |
| |
| if (colorOf(sib) == RED) { |
| setColor(sib, BLACK); |
| setColor(parentOf(x), RED); |
| rotateRight(parentOf(x)); |
| sib = leftOf(parentOf(x)); |
| } |
| |
| if (colorOf(rightOf(sib)) == BLACK && |
| colorOf(leftOf(sib)) == BLACK) { |
| setColor(sib, RED); |
| x = parentOf(x); |
| } else { |
| if (colorOf(leftOf(sib)) == BLACK) { |
| setColor(rightOf(sib), BLACK); |
| setColor(sib, RED); |
| rotateLeft(sib); |
| sib = leftOf(parentOf(x)); |
| } |
| setColor(sib, colorOf(parentOf(x))); |
| setColor(parentOf(x), BLACK); |
| setColor(leftOf(sib), BLACK); |
| rotateRight(parentOf(x)); |
| x = root; |
| } |
| } |
| } |
| |
| setColor(x, BLACK); |
| } |
| |
| private static final long serialVersionUID = 919286545866124006L; |
| |
| /** |
| * Save the state of the {@code TreeMap} instance to a stream (i.e., |
| * serialize it). |
| * |
| * @serialData The <em>size</em> of the TreeMap (the number of key-value |
| * mappings) is emitted (int), followed by the key (Object) |
| * and value (Object) for each key-value mapping represented |
| * by the TreeMap. The key-value mappings are emitted in |
| * key-order (as determined by the TreeMap's Comparator, |
| * or by the keys' natural ordering if the TreeMap has no |
| * Comparator). |
| */ |
| private void writeObject(java.io.ObjectOutputStream s) |
| throws java.io.IOException { |
| // Write out the Comparator and any hidden stuff |
| s.defaultWriteObject(); |
| |
| // Write out size (number of Mappings) |
| s.writeInt(size); |
| |
| // Write out keys and values (alternating) |
| for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) { |
| Map.Entry<K,V> e = i.next(); |
| s.writeObject(e.getKey()); |
| s.writeObject(e.getValue()); |
| } |
| } |
| |
| /** |
| * Reconstitute the {@code TreeMap} instance from a stream (i.e., |
| * deserialize it). |
| */ |
| private void readObject(final java.io.ObjectInputStream s) |
| throws java.io.IOException, ClassNotFoundException { |
| // Read in the Comparator and any hidden stuff |
| s.defaultReadObject(); |
| |
| // Read in size |
| int size = s.readInt(); |
| |
| buildFromSorted(size, null, s, null); |
| } |
| |
| /** Intended to be called only from TreeSet.readObject */ |
| void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal) |
| throws java.io.IOException, ClassNotFoundException { |
| buildFromSorted(size, null, s, defaultVal); |
| } |
| |
| /** Intended to be called only from TreeSet.addAll */ |
| void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) { |
| try { |
| buildFromSorted(set.size(), set.iterator(), null, defaultVal); |
| } catch (java.io.IOException cannotHappen) { |
| } catch (ClassNotFoundException cannotHappen) { |
| } |
| } |
| |
| |
| /** |
| * Linear time tree building algorithm from sorted data. Can accept keys |
| * and/or values from iterator or stream. This leads to too many |
| * parameters, but seems better than alternatives. The four formats |
| * that this method accepts are: |
| * |
| * 1) An iterator of Map.Entries. (it != null, defaultVal == null). |
| * 2) An iterator of keys. (it != null, defaultVal != null). |
| * 3) A stream of alternating serialized keys and values. |
| * (it == null, defaultVal == null). |
| * 4) A stream of serialized keys. (it == null, defaultVal != null). |
| * |
| * It is assumed that the comparator of the TreeMap is already set prior |
| * to calling this method. |
| * |
| * @param size the number of keys (or key-value pairs) to be read from |
| * the iterator or stream |
| * @param it If non-null, new entries are created from entries |
| * or keys read from this iterator. |
| * @param str If non-null, new entries are created from keys and |
| * possibly values read from this stream in serialized form. |
| * Exactly one of it and str should be non-null. |
| * @param defaultVal if non-null, this default value is used for |
| * each value in the map. If null, each value is read from |
| * iterator or stream, as described above. |
| * @throws IOException propagated from stream reads. This cannot |
| * occur if str is null. |
| * @throws ClassNotFoundException propagated from readObject. |
| * This cannot occur if str is null. |
| */ |
| private void buildFromSorted(int size, Iterator it, |
| java.io.ObjectInputStream str, |
| V defaultVal) |
| throws java.io.IOException, ClassNotFoundException { |
| this.size = size; |
| root = buildFromSorted(0, 0, size-1, computeRedLevel(size), |
| it, str, defaultVal); |
| } |
| |
| /** |
| * Recursive "helper method" that does the real work of the |
| * previous method. Identically named parameters have |
| * identical definitions. Additional parameters are documented below. |
| * It is assumed that the comparator and size fields of the TreeMap are |
| * already set prior to calling this method. (It ignores both fields.) |
| * |
| * @param level the current level of tree. Initial call should be 0. |
| * @param lo the first element index of this subtree. Initial should be 0. |
| * @param hi the last element index of this subtree. Initial should be |
| * size-1. |
| * @param redLevel the level at which nodes should be red. |
| * Must be equal to computeRedLevel for tree of this size. |
| */ |
| private final TreeMapEntry<K,V> buildFromSorted(int level, int lo, int hi, |
| int redLevel, |
| Iterator it, |
| java.io.ObjectInputStream str, |
| V defaultVal) |
| throws java.io.IOException, ClassNotFoundException { |
| /* |
| * Strategy: The root is the middlemost element. To get to it, we |
| * have to first recursively construct the entire left subtree, |
| * so as to grab all of its elements. We can then proceed with right |
| * subtree. |
| * |
| * The lo and hi arguments are the minimum and maximum |
| * indices to pull out of the iterator or stream for current subtree. |
| * They are not actually indexed, we just proceed sequentially, |
| * ensuring that items are extracted in corresponding order. |
| */ |
| |
| if (hi < lo) return null; |
| |
| int mid = (lo + hi) >>> 1; |
| |
| TreeMapEntry<K,V> left = null; |
| if (lo < mid) |
| left = buildFromSorted(level+1, lo, mid - 1, redLevel, |
| it, str, defaultVal); |
| |
| // extract key and/or value from iterator or stream |
| K key; |
| V value; |
| if (it != null) { |
| if (defaultVal==null) { |
| Map.Entry<K,V> entry = (Map.Entry<K,V>)it.next(); |
| key = entry.getKey(); |
| value = entry.getValue(); |
| } else { |
| key = (K)it.next(); |
| value = defaultVal; |
| } |
| } else { // use stream |
| key = (K) str.readObject(); |
| value = (defaultVal != null ? defaultVal : (V) str.readObject()); |
| } |
| |
| TreeMapEntry<K,V> middle = new TreeMapEntry<>(key, value, null); |
| |
| // color nodes in non-full bottommost level red |
| if (level == redLevel) |
| middle.color = RED; |
| |
| if (left != null) { |
| middle.left = left; |
| left.parent = middle; |
| } |
| |
| if (mid < hi) { |
| TreeMapEntry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel, |
| it, str, defaultVal); |
| middle.right = right; |
| right.parent = middle; |
| } |
| |
| return middle; |
| } |
| |
| /** |
| * Find the level down to which to assign all nodes BLACK. This is the |
| * last `full' level of the complete binary tree produced by |
| * buildTree. The remaining nodes are colored RED. (This makes a `nice' |
| * set of color assignments wrt future insertions.) This level number is |
| * computed by finding the number of splits needed to reach the zeroeth |
| * node. (The answer is ~lg(N), but in any case must be computed by same |
| * quick O(lg(N)) loop.) |
| */ |
| private static int computeRedLevel(int sz) { |
| int level = 0; |
| for (int m = sz - 1; m >= 0; m = m / 2 - 1) |
| level++; |
| return level; |
| } |
| } |
