jaroslav@1258: /*
jaroslav@1258: * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved.
jaroslav@1258: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
jaroslav@1258: *
jaroslav@1258: * This code is free software; you can redistribute it and/or modify it
jaroslav@1258: * under the terms of the GNU General Public License version 2 only, as
jaroslav@1258: * published by the Free Software Foundation. Oracle designates this
jaroslav@1258: * particular file as subject to the "Classpath" exception as provided
jaroslav@1258: * by Oracle in the LICENSE file that accompanied this code.
jaroslav@1258: *
jaroslav@1258: * This code is distributed in the hope that it will be useful, but WITHOUT
jaroslav@1258: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
jaroslav@1258: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
jaroslav@1258: * version 2 for more details (a copy is included in the LICENSE file that
jaroslav@1258: * accompanied this code).
jaroslav@1258: *
jaroslav@1258: * You should have received a copy of the GNU General Public License version
jaroslav@1258: * 2 along with this work; if not, write to the Free Software Foundation,
jaroslav@1258: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
jaroslav@1258: *
jaroslav@1258: * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
jaroslav@1258: * or visit www.oracle.com if you need additional information or have any
jaroslav@1258: * questions.
jaroslav@1258: */
jaroslav@1258:
jaroslav@1258: package java.util;
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * A Red-Black tree based {@link NavigableMap} implementation.
jaroslav@1258: * The map is sorted according to the {@linkplain Comparable natural
jaroslav@1258: * ordering} of its keys, or by a {@link Comparator} provided at map
jaroslav@1258: * creation time, depending on which constructor is used.
jaroslav@1258: *
jaroslav@1258: * This implementation provides guaranteed log(n) time cost for the
jaroslav@1258: * {@code containsKey}, {@code get}, {@code put} and {@code remove}
jaroslav@1258: * operations. Algorithms are adaptations of those in Cormen, Leiserson, and
jaroslav@1258: * Rivest's Introduction to Algorithms.
jaroslav@1258: *
jaroslav@1258: *
Note that the ordering maintained by a tree map, like any sorted map, and
jaroslav@1258: * whether or not an explicit comparator is provided, must be consistent
jaroslav@1258: * with {@code equals} if this sorted map is to correctly implement the
jaroslav@1258: * {@code Map} interface. (See {@code Comparable} or {@code Comparator} for a
jaroslav@1258: * precise definition of consistent with equals.) This is so because
jaroslav@1258: * the {@code Map} interface is defined in terms of the {@code equals}
jaroslav@1258: * operation, but a sorted map performs all key comparisons using its {@code
jaroslav@1258: * compareTo} (or {@code compare}) method, so two keys that are deemed equal by
jaroslav@1258: * this method are, from the standpoint of the sorted map, equal. The behavior
jaroslav@1258: * of a sorted map is well-defined even if its ordering is
jaroslav@1258: * inconsistent with {@code equals}; it just fails to obey the general contract
jaroslav@1258: * of the {@code Map} interface.
jaroslav@1258: *
jaroslav@1258: *
Note that this implementation is not synchronized.
jaroslav@1258: * If multiple threads access a map concurrently, and at least one of the
jaroslav@1258: * threads modifies the map structurally, it must be synchronized
jaroslav@1258: * externally. (A structural modification is any operation that adds or
jaroslav@1258: * deletes one or more mappings; merely changing the value associated
jaroslav@1258: * with an existing key is not a structural modification.) This is
jaroslav@1258: * typically accomplished by synchronizing on some object that naturally
jaroslav@1258: * encapsulates the map.
jaroslav@1258: * If no such object exists, the map should be "wrapped" using the
jaroslav@1258: * {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap}
jaroslav@1258: * method. This is best done at creation time, to prevent accidental
jaroslav@1258: * unsynchronized access to the map:
jaroslav@1258: * SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
jaroslav@1258: *
jaroslav@1258: * The iterators returned by the {@code iterator} method of the collections
jaroslav@1258: * returned by all of this class's "collection view methods" are
jaroslav@1258: * fail-fast: if the map is structurally modified at any time after
jaroslav@1258: * the iterator is created, in any way except through the iterator's own
jaroslav@1258: * {@code remove} method, the iterator will throw a {@link
jaroslav@1258: * ConcurrentModificationException}. Thus, in the face of concurrent
jaroslav@1258: * modification, the iterator fails quickly and cleanly, rather than risking
jaroslav@1258: * arbitrary, non-deterministic behavior at an undetermined time in the future.
jaroslav@1258: *
jaroslav@1258: *
Note that the fail-fast behavior of an iterator cannot be guaranteed
jaroslav@1258: * as it is, generally speaking, impossible to make any hard guarantees in the
jaroslav@1258: * presence of unsynchronized concurrent modification. Fail-fast iterators
jaroslav@1258: * throw {@code ConcurrentModificationException} on a best-effort basis.
jaroslav@1258: * Therefore, it would be wrong to write a program that depended on this
jaroslav@1258: * exception for its correctness: the fail-fast behavior of iterators
jaroslav@1258: * should be used only to detect bugs.
jaroslav@1258: *
jaroslav@1258: *
All {@code Map.Entry} pairs returned by methods in this class
jaroslav@1258: * and its views represent snapshots of mappings at the time they were
jaroslav@1258: * produced. They do not support the {@code Entry.setValue}
jaroslav@1258: * method. (Note however that it is possible to change mappings in the
jaroslav@1258: * associated map using {@code put}.)
jaroslav@1258: *
jaroslav@1258: *
This class is a member of the
jaroslav@1258: *
jaroslav@1258: * Java Collections Framework.
jaroslav@1258: *
jaroslav@1258: * @param the type of keys maintained by this map
jaroslav@1258: * @param the type of mapped values
jaroslav@1258: *
jaroslav@1258: * @author Josh Bloch and Doug Lea
jaroslav@1258: * @see Map
jaroslav@1258: * @see HashMap
jaroslav@1258: * @see Hashtable
jaroslav@1258: * @see Comparable
jaroslav@1258: * @see Comparator
jaroslav@1258: * @see Collection
jaroslav@1258: * @since 1.2
jaroslav@1258: */
jaroslav@1258:
jaroslav@1258: public class TreeMap
jaroslav@1258: extends AbstractMap
jaroslav@1258: implements NavigableMap, Cloneable, java.io.Serializable
jaroslav@1258: {
jaroslav@1258: /**
jaroslav@1258: * The comparator used to maintain order in this tree map, or
jaroslav@1258: * null if it uses the natural ordering of its keys.
jaroslav@1258: *
jaroslav@1258: * @serial
jaroslav@1258: */
jaroslav@1258: private final Comparator comparator;
jaroslav@1258:
jaroslav@1258: private transient Entry root = null;
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * The number of entries in the tree
jaroslav@1258: */
jaroslav@1258: private transient int size = 0;
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * The number of structural modifications to the tree.
jaroslav@1258: */
jaroslav@1258: private transient int modCount = 0;
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Constructs a new, empty tree map, using the natural ordering of its
jaroslav@1258: * keys. All keys inserted into the map must implement the {@link
jaroslav@1258: * Comparable} interface. Furthermore, all such keys must be
jaroslav@1258: * mutually comparable: {@code k1.compareTo(k2)} must not throw
jaroslav@1258: * a {@code ClassCastException} for any keys {@code k1} and
jaroslav@1258: * {@code k2} in the map. If the user attempts to put a key into the
jaroslav@1258: * map that violates this constraint (for example, the user attempts to
jaroslav@1258: * put a string key into a map whose keys are integers), the
jaroslav@1258: * {@code put(Object key, Object value)} call will throw a
jaroslav@1258: * {@code ClassCastException}.
jaroslav@1258: */
jaroslav@1258: public TreeMap() {
jaroslav@1258: comparator = null;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Constructs a new, empty tree map, ordered according to the given
jaroslav@1258: * comparator. All keys inserted into the map must be mutually
jaroslav@1258: * comparable by the given comparator: {@code comparator.compare(k1,
jaroslav@1258: * k2)} must not throw a {@code ClassCastException} for any keys
jaroslav@1258: * {@code k1} and {@code k2} in the map. If the user attempts to put
jaroslav@1258: * a key into the map that violates this constraint, the {@code put(Object
jaroslav@1258: * key, Object value)} call will throw a
jaroslav@1258: * {@code ClassCastException}.
jaroslav@1258: *
jaroslav@1258: * @param comparator the comparator that will be used to order this map.
jaroslav@1258: * If {@code null}, the {@linkplain Comparable natural
jaroslav@1258: * ordering} of the keys will be used.
jaroslav@1258: */
jaroslav@1258: public TreeMap(Comparator comparator) {
jaroslav@1258: this.comparator = comparator;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Constructs a new tree map containing the same mappings as the given
jaroslav@1258: * map, ordered according to the natural ordering of its keys.
jaroslav@1258: * All keys inserted into the new map must implement the {@link
jaroslav@1258: * Comparable} interface. Furthermore, all such keys must be
jaroslav@1258: * mutually comparable: {@code k1.compareTo(k2)} must not throw
jaroslav@1258: * a {@code ClassCastException} for any keys {@code k1} and
jaroslav@1258: * {@code k2} in the map. This method runs in n*log(n) time.
jaroslav@1258: *
jaroslav@1258: * @param m the map whose mappings are to be placed in this map
jaroslav@1258: * @throws ClassCastException if the keys in m are not {@link Comparable},
jaroslav@1258: * or are not mutually comparable
jaroslav@1258: * @throws NullPointerException if the specified map is null
jaroslav@1258: */
jaroslav@1258: public TreeMap(Map m) {
jaroslav@1258: comparator = null;
jaroslav@1258: putAll(m);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Constructs a new tree map containing the same mappings and
jaroslav@1258: * using the same ordering as the specified sorted map. This
jaroslav@1258: * method runs in linear time.
jaroslav@1258: *
jaroslav@1258: * @param m the sorted map whose mappings are to be placed in this map,
jaroslav@1258: * and whose comparator is to be used to sort this map
jaroslav@1258: * @throws NullPointerException if the specified map is null
jaroslav@1258: */
jaroslav@1258: public TreeMap(SortedMap m) {
jaroslav@1258: comparator = m.comparator();
jaroslav@1258: try {
jaroslav@1258: buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
jaroslav@1258: } catch (java.io.IOException cannotHappen) {
jaroslav@1258: } catch (ClassNotFoundException cannotHappen) {
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258:
jaroslav@1258: // Query Operations
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Returns the number of key-value mappings in this map.
jaroslav@1258: *
jaroslav@1258: * @return the number of key-value mappings in this map
jaroslav@1258: */
jaroslav@1258: public int size() {
jaroslav@1258: return size;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Returns {@code true} if this map contains a mapping for the specified
jaroslav@1258: * key.
jaroslav@1258: *
jaroslav@1258: * @param key key whose presence in this map is to be tested
jaroslav@1258: * @return {@code true} if this map contains a mapping for the
jaroslav@1258: * specified key
jaroslav@1258: * @throws ClassCastException if the specified key cannot be compared
jaroslav@1258: * with the keys currently in the map
jaroslav@1258: * @throws NullPointerException if the specified key is null
jaroslav@1258: * and this map uses natural ordering, or its comparator
jaroslav@1258: * does not permit null keys
jaroslav@1258: */
jaroslav@1258: public boolean containsKey(Object key) {
jaroslav@1258: return getEntry(key) != null;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Returns {@code true} if this map maps one or more keys to the
jaroslav@1258: * specified value. More formally, returns {@code true} if and only if
jaroslav@1258: * this map contains at least one mapping to a value {@code v} such
jaroslav@1258: * that {@code (value==null ? v==null : value.equals(v))}. This
jaroslav@1258: * operation will probably require time linear in the map size for
jaroslav@1258: * most implementations.
jaroslav@1258: *
jaroslav@1258: * @param value value whose presence in this map is to be tested
jaroslav@1258: * @return {@code true} if a mapping to {@code value} exists;
jaroslav@1258: * {@code false} otherwise
jaroslav@1258: * @since 1.2
jaroslav@1258: */
jaroslav@1258: public boolean containsValue(Object value) {
jaroslav@1258: for (Entry e = getFirstEntry(); e != null; e = successor(e))
jaroslav@1258: if (valEquals(value, e.value))
jaroslav@1258: return true;
jaroslav@1258: return false;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Returns the value to which the specified key is mapped,
jaroslav@1258: * or {@code null} if this map contains no mapping for the key.
jaroslav@1258: *
jaroslav@1258: * More formally, if this map contains a mapping from a key
jaroslav@1258: * {@code k} to a value {@code v} such that {@code key} compares
jaroslav@1258: * equal to {@code k} according to the map's ordering, then this
jaroslav@1258: * method returns {@code v}; otherwise it returns {@code null}.
jaroslav@1258: * (There can be at most one such mapping.)
jaroslav@1258: *
jaroslav@1258: *
A return value of {@code null} does not necessarily
jaroslav@1258: * indicate that the map contains no mapping for the key; it's also
jaroslav@1258: * possible that the map explicitly maps the key to {@code null}.
jaroslav@1258: * The {@link #containsKey containsKey} operation may be used to
jaroslav@1258: * distinguish these two cases.
jaroslav@1258: *
jaroslav@1258: * @throws ClassCastException if the specified key cannot be compared
jaroslav@1258: * with the keys currently in the map
jaroslav@1258: * @throws NullPointerException if the specified key is null
jaroslav@1258: * and this map uses natural ordering, or its comparator
jaroslav@1258: * does not permit null keys
jaroslav@1258: */
jaroslav@1258: public V get(Object key) {
jaroslav@1258: Entry p = getEntry(key);
jaroslav@1258: return (p==null ? null : p.value);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public Comparator comparator() {
jaroslav@1258: return comparator;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @throws NoSuchElementException {@inheritDoc}
jaroslav@1258: */
jaroslav@1258: public K firstKey() {
jaroslav@1258: return key(getFirstEntry());
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @throws NoSuchElementException {@inheritDoc}
jaroslav@1258: */
jaroslav@1258: public K lastKey() {
jaroslav@1258: return key(getLastEntry());
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Copies all of the mappings from the specified map to this map.
jaroslav@1258: * These mappings replace any mappings that this map had for any
jaroslav@1258: * of the keys currently in the specified map.
jaroslav@1258: *
jaroslav@1258: * @param map mappings to be stored in this map
jaroslav@1258: * @throws ClassCastException if the class of a key or value in
jaroslav@1258: * the specified map prevents it from being stored in this map
jaroslav@1258: * @throws NullPointerException if the specified map is null or
jaroslav@1258: * the specified map contains a null key and this map does not
jaroslav@1258: * permit null keys
jaroslav@1258: */
jaroslav@1258: public void putAll(Map map) {
jaroslav@1258: int mapSize = map.size();
jaroslav@1258: if (size==0 && mapSize!=0 && map instanceof SortedMap) {
jaroslav@1258: Comparator c = ((SortedMap)map).comparator();
jaroslav@1258: if (c == comparator || (c != null && c.equals(comparator))) {
jaroslav@1258: ++modCount;
jaroslav@1258: try {
jaroslav@1258: buildFromSorted(mapSize, map.entrySet().iterator(),
jaroslav@1258: null, null);
jaroslav@1258: } catch (java.io.IOException cannotHappen) {
jaroslav@1258: } catch (ClassNotFoundException cannotHappen) {
jaroslav@1258: }
jaroslav@1258: return;
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258: super.putAll(map);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Returns this map's entry for the given key, or {@code null} if the map
jaroslav@1258: * does not contain an entry for the key.
jaroslav@1258: *
jaroslav@1258: * @return this map's entry for the given key, or {@code null} if the map
jaroslav@1258: * does not contain an entry for the key
jaroslav@1258: * @throws ClassCastException if the specified key cannot be compared
jaroslav@1258: * with the keys currently in the map
jaroslav@1258: * @throws NullPointerException if the specified key is null
jaroslav@1258: * and this map uses natural ordering, or its comparator
jaroslav@1258: * does not permit null keys
jaroslav@1258: */
jaroslav@1258: final Entry getEntry(Object key) {
jaroslav@1258: // Offload comparator-based version for sake of performance
jaroslav@1258: if (comparator != null)
jaroslav@1258: return getEntryUsingComparator(key);
jaroslav@1258: if (key == null)
jaroslav@1258: throw new NullPointerException();
jaroslav@1258: Comparable k = (Comparable) key;
jaroslav@1258: Entry p = root;
jaroslav@1258: while (p != null) {
jaroslav@1258: int cmp = k.compareTo(p.key);
jaroslav@1258: if (cmp < 0)
jaroslav@1258: p = p.left;
jaroslav@1258: else if (cmp > 0)
jaroslav@1258: p = p.right;
jaroslav@1258: else
jaroslav@1258: return p;
jaroslav@1258: }
jaroslav@1258: return null;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Version of getEntry using comparator. Split off from getEntry
jaroslav@1258: * for performance. (This is not worth doing for most methods,
jaroslav@1258: * that are less dependent on comparator performance, but is
jaroslav@1258: * worthwhile here.)
jaroslav@1258: */
jaroslav@1258: final Entry getEntryUsingComparator(Object key) {
jaroslav@1258: K k = (K) key;
jaroslav@1258: Comparator cpr = comparator;
jaroslav@1258: if (cpr != null) {
jaroslav@1258: Entry p = root;
jaroslav@1258: while (p != null) {
jaroslav@1258: int cmp = cpr.compare(k, p.key);
jaroslav@1258: if (cmp < 0)
jaroslav@1258: p = p.left;
jaroslav@1258: else if (cmp > 0)
jaroslav@1258: p = p.right;
jaroslav@1258: else
jaroslav@1258: return p;
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258: return null;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Gets the entry corresponding to the specified key; if no such entry
jaroslav@1258: * exists, returns the entry for the least key greater than the specified
jaroslav@1258: * key; if no such entry exists (i.e., the greatest key in the Tree is less
jaroslav@1258: * than the specified key), returns {@code null}.
jaroslav@1258: */
jaroslav@1258: final Entry getCeilingEntry(K key) {
jaroslav@1258: Entry p = root;
jaroslav@1258: while (p != null) {
jaroslav@1258: int cmp = compare(key, p.key);
jaroslav@1258: if (cmp < 0) {
jaroslav@1258: if (p.left != null)
jaroslav@1258: p = p.left;
jaroslav@1258: else
jaroslav@1258: return p;
jaroslav@1258: } else if (cmp > 0) {
jaroslav@1258: if (p.right != null) {
jaroslav@1258: p = p.right;
jaroslav@1258: } else {
jaroslav@1258: Entry parent = p.parent;
jaroslav@1258: Entry ch = p;
jaroslav@1258: while (parent != null && ch == parent.right) {
jaroslav@1258: ch = parent;
jaroslav@1258: parent = parent.parent;
jaroslav@1258: }
jaroslav@1258: return parent;
jaroslav@1258: }
jaroslav@1258: } else
jaroslav@1258: return p;
jaroslav@1258: }
jaroslav@1258: return null;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Gets the entry corresponding to the specified key; if no such entry
jaroslav@1258: * exists, returns the entry for the greatest key less than the specified
jaroslav@1258: * key; if no such entry exists, returns {@code null}.
jaroslav@1258: */
jaroslav@1258: final Entry getFloorEntry(K key) {
jaroslav@1258: Entry p = root;
jaroslav@1258: while (p != null) {
jaroslav@1258: int cmp = compare(key, p.key);
jaroslav@1258: if (cmp > 0) {
jaroslav@1258: if (p.right != null)
jaroslav@1258: p = p.right;
jaroslav@1258: else
jaroslav@1258: return p;
jaroslav@1258: } else if (cmp < 0) {
jaroslav@1258: if (p.left != null) {
jaroslav@1258: p = p.left;
jaroslav@1258: } else {
jaroslav@1258: Entry parent = p.parent;
jaroslav@1258: Entry ch = p;
jaroslav@1258: while (parent != null && ch == parent.left) {
jaroslav@1258: ch = parent;
jaroslav@1258: parent = parent.parent;
jaroslav@1258: }
jaroslav@1258: return parent;
jaroslav@1258: }
jaroslav@1258: } else
jaroslav@1258: return p;
jaroslav@1258:
jaroslav@1258: }
jaroslav@1258: return null;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Gets the entry for the least key greater than the specified
jaroslav@1258: * key; if no such entry exists, returns the entry for the least
jaroslav@1258: * key greater than the specified key; if no such entry exists
jaroslav@1258: * returns {@code null}.
jaroslav@1258: */
jaroslav@1258: final Entry getHigherEntry(K key) {
jaroslav@1258: Entry p = root;
jaroslav@1258: while (p != null) {
jaroslav@1258: int cmp = compare(key, p.key);
jaroslav@1258: if (cmp < 0) {
jaroslav@1258: if (p.left != null)
jaroslav@1258: p = p.left;
jaroslav@1258: else
jaroslav@1258: return p;
jaroslav@1258: } else {
jaroslav@1258: if (p.right != null) {
jaroslav@1258: p = p.right;
jaroslav@1258: } else {
jaroslav@1258: Entry parent = p.parent;
jaroslav@1258: Entry ch = p;
jaroslav@1258: while (parent != null && ch == parent.right) {
jaroslav@1258: ch = parent;
jaroslav@1258: parent = parent.parent;
jaroslav@1258: }
jaroslav@1258: return parent;
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258: return null;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Returns the entry for the greatest key less than the specified key; if
jaroslav@1258: * no such entry exists (i.e., the least key in the Tree is greater than
jaroslav@1258: * the specified key), returns {@code null}.
jaroslav@1258: */
jaroslav@1258: final Entry getLowerEntry(K key) {
jaroslav@1258: Entry p = root;
jaroslav@1258: while (p != null) {
jaroslav@1258: int cmp = compare(key, p.key);
jaroslav@1258: if (cmp > 0) {
jaroslav@1258: if (p.right != null)
jaroslav@1258: p = p.right;
jaroslav@1258: else
jaroslav@1258: return p;
jaroslav@1258: } else {
jaroslav@1258: if (p.left != null) {
jaroslav@1258: p = p.left;
jaroslav@1258: } else {
jaroslav@1258: Entry parent = p.parent;
jaroslav@1258: Entry ch = p;
jaroslav@1258: while (parent != null && ch == parent.left) {
jaroslav@1258: ch = parent;
jaroslav@1258: parent = parent.parent;
jaroslav@1258: }
jaroslav@1258: return parent;
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258: return null;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Associates the specified value with the specified key in this map.
jaroslav@1258: * If the map previously contained a mapping for the key, the old
jaroslav@1258: * value is replaced.
jaroslav@1258: *
jaroslav@1258: * @param key key with which the specified value is to be associated
jaroslav@1258: * @param value value to be associated with the specified key
jaroslav@1258: *
jaroslav@1258: * @return the previous value associated with {@code key}, or
jaroslav@1258: * {@code null} if there was no mapping for {@code key}.
jaroslav@1258: * (A {@code null} return can also indicate that the map
jaroslav@1258: * previously associated {@code null} with {@code key}.)
jaroslav@1258: * @throws ClassCastException if the specified key cannot be compared
jaroslav@1258: * with the keys currently in the map
jaroslav@1258: * @throws NullPointerException if the specified key is null
jaroslav@1258: * and this map uses natural ordering, or its comparator
jaroslav@1258: * does not permit null keys
jaroslav@1258: */
jaroslav@1258: public V put(K key, V value) {
jaroslav@1258: Entry t = root;
jaroslav@1258: if (t == null) {
jaroslav@1258: compare(key, key); // type (and possibly null) check
jaroslav@1258:
jaroslav@1258: root = new Entry<>(key, value, null);
jaroslav@1258: size = 1;
jaroslav@1258: modCount++;
jaroslav@1258: return null;
jaroslav@1258: }
jaroslav@1258: int cmp;
jaroslav@1258: Entry parent;
jaroslav@1258: // split comparator and comparable paths
jaroslav@1258: Comparator cpr = comparator;
jaroslav@1258: if (cpr != null) {
jaroslav@1258: do {
jaroslav@1258: parent = t;
jaroslav@1258: cmp = cpr.compare(key, t.key);
jaroslav@1258: if (cmp < 0)
jaroslav@1258: t = t.left;
jaroslav@1258: else if (cmp > 0)
jaroslav@1258: t = t.right;
jaroslav@1258: else
jaroslav@1258: return t.setValue(value);
jaroslav@1258: } while (t != null);
jaroslav@1258: }
jaroslav@1258: else {
jaroslav@1258: if (key == null)
jaroslav@1258: throw new NullPointerException();
jaroslav@1258: Comparable k = (Comparable) key;
jaroslav@1258: do {
jaroslav@1258: parent = t;
jaroslav@1258: cmp = k.compareTo(t.key);
jaroslav@1258: if (cmp < 0)
jaroslav@1258: t = t.left;
jaroslav@1258: else if (cmp > 0)
jaroslav@1258: t = t.right;
jaroslav@1258: else
jaroslav@1258: return t.setValue(value);
jaroslav@1258: } while (t != null);
jaroslav@1258: }
jaroslav@1258: Entry e = new Entry<>(key, value, parent);
jaroslav@1258: if (cmp < 0)
jaroslav@1258: parent.left = e;
jaroslav@1258: else
jaroslav@1258: parent.right = e;
jaroslav@1258: fixAfterInsertion(e);
jaroslav@1258: size++;
jaroslav@1258: modCount++;
jaroslav@1258: return null;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Removes the mapping for this key from this TreeMap if present.
jaroslav@1258: *
jaroslav@1258: * @param key key for which mapping should be removed
jaroslav@1258: * @return the previous value associated with {@code key}, or
jaroslav@1258: * {@code null} if there was no mapping for {@code key}.
jaroslav@1258: * (A {@code null} return can also indicate that the map
jaroslav@1258: * previously associated {@code null} with {@code key}.)
jaroslav@1258: * @throws ClassCastException if the specified key cannot be compared
jaroslav@1258: * with the keys currently in the map
jaroslav@1258: * @throws NullPointerException if the specified key is null
jaroslav@1258: * and this map uses natural ordering, or its comparator
jaroslav@1258: * does not permit null keys
jaroslav@1258: */
jaroslav@1258: public V remove(Object key) {
jaroslav@1258: Entry p = getEntry(key);
jaroslav@1258: if (p == null)
jaroslav@1258: return null;
jaroslav@1258:
jaroslav@1258: V oldValue = p.value;
jaroslav@1258: deleteEntry(p);
jaroslav@1258: return oldValue;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Removes all of the mappings from this map.
jaroslav@1258: * The map will be empty after this call returns.
jaroslav@1258: */
jaroslav@1258: public void clear() {
jaroslav@1258: modCount++;
jaroslav@1258: size = 0;
jaroslav@1258: root = null;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Returns a shallow copy of this {@code TreeMap} instance. (The keys and
jaroslav@1258: * values themselves are not cloned.)
jaroslav@1258: *
jaroslav@1258: * @return a shallow copy of this map
jaroslav@1258: */
jaroslav@1258: public Object clone() {
jaroslav@1258: TreeMap clone = null;
jaroslav@1258: try {
jaroslav@1258: clone = (TreeMap) super.clone();
jaroslav@1258: } catch (CloneNotSupportedException e) {
jaroslav@1258: throw new InternalError();
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: // Put clone into "virgin" state (except for comparator)
jaroslav@1258: clone.root = null;
jaroslav@1258: clone.size = 0;
jaroslav@1258: clone.modCount = 0;
jaroslav@1258: clone.entrySet = null;
jaroslav@1258: clone.navigableKeySet = null;
jaroslav@1258: clone.descendingMap = null;
jaroslav@1258:
jaroslav@1258: // Initialize clone with our mappings
jaroslav@1258: try {
jaroslav@1258: clone.buildFromSorted(size, entrySet().iterator(), null, null);
jaroslav@1258: } catch (java.io.IOException cannotHappen) {
jaroslav@1258: } catch (ClassNotFoundException cannotHappen) {
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: return clone;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: // NavigableMap API methods
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @since 1.6
jaroslav@1258: */
jaroslav@1258: public Map.Entry firstEntry() {
jaroslav@1258: return exportEntry(getFirstEntry());
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @since 1.6
jaroslav@1258: */
jaroslav@1258: public Map.Entry lastEntry() {
jaroslav@1258: return exportEntry(getLastEntry());
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @since 1.6
jaroslav@1258: */
jaroslav@1258: public Map.Entry pollFirstEntry() {
jaroslav@1258: Entry p = getFirstEntry();
jaroslav@1258: Map.Entry result = exportEntry(p);
jaroslav@1258: if (p != null)
jaroslav@1258: deleteEntry(p);
jaroslav@1258: return result;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @since 1.6
jaroslav@1258: */
jaroslav@1258: public Map.Entry pollLastEntry() {
jaroslav@1258: Entry p = getLastEntry();
jaroslav@1258: Map.Entry result = exportEntry(p);
jaroslav@1258: if (p != null)
jaroslav@1258: deleteEntry(p);
jaroslav@1258: return result;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @throws ClassCastException {@inheritDoc}
jaroslav@1258: * @throws NullPointerException if the specified key is null
jaroslav@1258: * and this map uses natural ordering, or its comparator
jaroslav@1258: * does not permit null keys
jaroslav@1258: * @since 1.6
jaroslav@1258: */
jaroslav@1258: public Map.Entry lowerEntry(K key) {
jaroslav@1258: return exportEntry(getLowerEntry(key));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @throws ClassCastException {@inheritDoc}
jaroslav@1258: * @throws NullPointerException if the specified key is null
jaroslav@1258: * and this map uses natural ordering, or its comparator
jaroslav@1258: * does not permit null keys
jaroslav@1258: * @since 1.6
jaroslav@1258: */
jaroslav@1258: public K lowerKey(K key) {
jaroslav@1258: return keyOrNull(getLowerEntry(key));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @throws ClassCastException {@inheritDoc}
jaroslav@1258: * @throws NullPointerException if the specified key is null
jaroslav@1258: * and this map uses natural ordering, or its comparator
jaroslav@1258: * does not permit null keys
jaroslav@1258: * @since 1.6
jaroslav@1258: */
jaroslav@1258: public Map.Entry floorEntry(K key) {
jaroslav@1258: return exportEntry(getFloorEntry(key));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @throws ClassCastException {@inheritDoc}
jaroslav@1258: * @throws NullPointerException if the specified key is null
jaroslav@1258: * and this map uses natural ordering, or its comparator
jaroslav@1258: * does not permit null keys
jaroslav@1258: * @since 1.6
jaroslav@1258: */
jaroslav@1258: public K floorKey(K key) {
jaroslav@1258: return keyOrNull(getFloorEntry(key));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @throws ClassCastException {@inheritDoc}
jaroslav@1258: * @throws NullPointerException if the specified key is null
jaroslav@1258: * and this map uses natural ordering, or its comparator
jaroslav@1258: * does not permit null keys
jaroslav@1258: * @since 1.6
jaroslav@1258: */
jaroslav@1258: public Map.Entry ceilingEntry(K key) {
jaroslav@1258: return exportEntry(getCeilingEntry(key));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @throws ClassCastException {@inheritDoc}
jaroslav@1258: * @throws NullPointerException if the specified key is null
jaroslav@1258: * and this map uses natural ordering, or its comparator
jaroslav@1258: * does not permit null keys
jaroslav@1258: * @since 1.6
jaroslav@1258: */
jaroslav@1258: public K ceilingKey(K key) {
jaroslav@1258: return keyOrNull(getCeilingEntry(key));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @throws ClassCastException {@inheritDoc}
jaroslav@1258: * @throws NullPointerException if the specified key is null
jaroslav@1258: * and this map uses natural ordering, or its comparator
jaroslav@1258: * does not permit null keys
jaroslav@1258: * @since 1.6
jaroslav@1258: */
jaroslav@1258: public Map.Entry higherEntry(K key) {
jaroslav@1258: return exportEntry(getHigherEntry(key));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @throws ClassCastException {@inheritDoc}
jaroslav@1258: * @throws NullPointerException if the specified key is null
jaroslav@1258: * and this map uses natural ordering, or its comparator
jaroslav@1258: * does not permit null keys
jaroslav@1258: * @since 1.6
jaroslav@1258: */
jaroslav@1258: public K higherKey(K key) {
jaroslav@1258: return keyOrNull(getHigherEntry(key));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: // Views
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Fields initialized to contain an instance of the entry set view
jaroslav@1258: * the first time this view is requested. Views are stateless, so
jaroslav@1258: * there's no reason to create more than one.
jaroslav@1258: */
jaroslav@1258: private transient EntrySet entrySet = null;
jaroslav@1258: private transient KeySet navigableKeySet = null;
jaroslav@1258: private transient NavigableMap descendingMap = null;
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Returns a {@link Set} view of the keys contained in this map.
jaroslav@1258: * The set's iterator returns the keys in ascending order.
jaroslav@1258: * The set is backed by the map, so changes to the map are
jaroslav@1258: * reflected in the set, and vice-versa. If the map is modified
jaroslav@1258: * while an iteration over the set is in progress (except through
jaroslav@1258: * the iterator's own {@code remove} operation), the results of
jaroslav@1258: * the iteration are undefined. The set supports element removal,
jaroslav@1258: * which removes the corresponding mapping from the map, via the
jaroslav@1258: * {@code Iterator.remove}, {@code Set.remove},
jaroslav@1258: * {@code removeAll}, {@code retainAll}, and {@code clear}
jaroslav@1258: * operations. It does not support the {@code add} or {@code addAll}
jaroslav@1258: * operations.
jaroslav@1258: */
jaroslav@1258: public Set keySet() {
jaroslav@1258: return navigableKeySet();
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @since 1.6
jaroslav@1258: */
jaroslav@1258: public NavigableSet navigableKeySet() {
jaroslav@1258: KeySet nks = navigableKeySet;
jaroslav@1258: return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @since 1.6
jaroslav@1258: */
jaroslav@1258: public NavigableSet descendingKeySet() {
jaroslav@1258: return descendingMap().navigableKeySet();
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Returns a {@link Collection} view of the values contained in this map.
jaroslav@1258: * The collection's iterator returns the values in ascending order
jaroslav@1258: * of the corresponding keys.
jaroslav@1258: * The collection is backed by the map, so changes to the map are
jaroslav@1258: * reflected in the collection, and vice-versa. If the map is
jaroslav@1258: * modified while an iteration over the collection is in progress
jaroslav@1258: * (except through the iterator's own {@code remove} operation),
jaroslav@1258: * the results of the iteration are undefined. The collection
jaroslav@1258: * supports element removal, which removes the corresponding
jaroslav@1258: * mapping from the map, via the {@code Iterator.remove},
jaroslav@1258: * {@code Collection.remove}, {@code removeAll},
jaroslav@1258: * {@code retainAll} and {@code clear} operations. It does not
jaroslav@1258: * support the {@code add} or {@code addAll} operations.
jaroslav@1258: */
jaroslav@1258: public Collection values() {
jaroslav@1258: Collection vs = values;
jaroslav@1258: return (vs != null) ? vs : (values = new Values());
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Returns a {@link Set} view of the mappings contained in this map.
jaroslav@1258: * The set's iterator returns the entries in ascending key order.
jaroslav@1258: * The set is backed by the map, so changes to the map are
jaroslav@1258: * reflected in the set, and vice-versa. If the map is modified
jaroslav@1258: * while an iteration over the set is in progress (except through
jaroslav@1258: * the iterator's own {@code remove} operation, or through the
jaroslav@1258: * {@code setValue} operation on a map entry returned by the
jaroslav@1258: * iterator) the results of the iteration are undefined. The set
jaroslav@1258: * supports element removal, which removes the corresponding
jaroslav@1258: * mapping from the map, via the {@code Iterator.remove},
jaroslav@1258: * {@code Set.remove}, {@code removeAll}, {@code retainAll} and
jaroslav@1258: * {@code clear} operations. It does not support the
jaroslav@1258: * {@code add} or {@code addAll} operations.
jaroslav@1258: */
jaroslav@1258: public Set> entrySet() {
jaroslav@1258: EntrySet es = entrySet;
jaroslav@1258: return (es != null) ? es : (entrySet = new EntrySet());
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @since 1.6
jaroslav@1258: */
jaroslav@1258: public NavigableMap descendingMap() {
jaroslav@1258: NavigableMap km = descendingMap;
jaroslav@1258: return (km != null) ? km :
jaroslav@1258: (descendingMap = new DescendingSubMap(this,
jaroslav@1258: true, null, true,
jaroslav@1258: true, null, true));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @throws ClassCastException {@inheritDoc}
jaroslav@1258: * @throws NullPointerException if {@code fromKey} or {@code toKey} is
jaroslav@1258: * null and this map uses natural ordering, or its comparator
jaroslav@1258: * does not permit null keys
jaroslav@1258: * @throws IllegalArgumentException {@inheritDoc}
jaroslav@1258: * @since 1.6
jaroslav@1258: */
jaroslav@1258: public NavigableMap subMap(K fromKey, boolean fromInclusive,
jaroslav@1258: K toKey, boolean toInclusive) {
jaroslav@1258: return new AscendingSubMap(this,
jaroslav@1258: false, fromKey, fromInclusive,
jaroslav@1258: false, toKey, toInclusive);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @throws ClassCastException {@inheritDoc}
jaroslav@1258: * @throws NullPointerException if {@code toKey} is null
jaroslav@1258: * and this map uses natural ordering, or its comparator
jaroslav@1258: * does not permit null keys
jaroslav@1258: * @throws IllegalArgumentException {@inheritDoc}
jaroslav@1258: * @since 1.6
jaroslav@1258: */
jaroslav@1258: public NavigableMap headMap(K toKey, boolean inclusive) {
jaroslav@1258: return new AscendingSubMap(this,
jaroslav@1258: true, null, true,
jaroslav@1258: false, toKey, inclusive);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @throws ClassCastException {@inheritDoc}
jaroslav@1258: * @throws NullPointerException if {@code fromKey} is null
jaroslav@1258: * and this map uses natural ordering, or its comparator
jaroslav@1258: * does not permit null keys
jaroslav@1258: * @throws IllegalArgumentException {@inheritDoc}
jaroslav@1258: * @since 1.6
jaroslav@1258: */
jaroslav@1258: public NavigableMap tailMap(K fromKey, boolean inclusive) {
jaroslav@1258: return new AscendingSubMap(this,
jaroslav@1258: false, fromKey, inclusive,
jaroslav@1258: true, null, true);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @throws ClassCastException {@inheritDoc}
jaroslav@1258: * @throws NullPointerException if {@code fromKey} or {@code toKey} is
jaroslav@1258: * null and this map uses natural ordering, or its comparator
jaroslav@1258: * does not permit null keys
jaroslav@1258: * @throws IllegalArgumentException {@inheritDoc}
jaroslav@1258: */
jaroslav@1258: public SortedMap subMap(K fromKey, K toKey) {
jaroslav@1258: return subMap(fromKey, true, toKey, false);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @throws ClassCastException {@inheritDoc}
jaroslav@1258: * @throws NullPointerException if {@code toKey} is null
jaroslav@1258: * and this map uses natural ordering, or its comparator
jaroslav@1258: * does not permit null keys
jaroslav@1258: * @throws IllegalArgumentException {@inheritDoc}
jaroslav@1258: */
jaroslav@1258: public SortedMap headMap(K toKey) {
jaroslav@1258: return headMap(toKey, false);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @throws ClassCastException {@inheritDoc}
jaroslav@1258: * @throws NullPointerException if {@code fromKey} is null
jaroslav@1258: * and this map uses natural ordering, or its comparator
jaroslav@1258: * does not permit null keys
jaroslav@1258: * @throws IllegalArgumentException {@inheritDoc}
jaroslav@1258: */
jaroslav@1258: public SortedMap tailMap(K fromKey) {
jaroslav@1258: return tailMap(fromKey, true);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: // View class support
jaroslav@1258:
jaroslav@1258: class Values extends AbstractCollection {
jaroslav@1258: public Iterator iterator() {
jaroslav@1258: return new ValueIterator(getFirstEntry());
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public int size() {
jaroslav@1258: return TreeMap.this.size();
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public boolean contains(Object o) {
jaroslav@1258: return TreeMap.this.containsValue(o);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public boolean remove(Object o) {
jaroslav@1258: for (Entry e = getFirstEntry(); e != null; e = successor(e)) {
jaroslav@1258: if (valEquals(e.getValue(), o)) {
jaroslav@1258: deleteEntry(e);
jaroslav@1258: return true;
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258: return false;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public void clear() {
jaroslav@1258: TreeMap.this.clear();
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: class EntrySet extends AbstractSet> {
jaroslav@1258: public Iterator> iterator() {
jaroslav@1258: return new EntryIterator(getFirstEntry());
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public boolean contains(Object o) {
jaroslav@1258: if (!(o instanceof Map.Entry))
jaroslav@1258: return false;
jaroslav@1258: Map.Entry entry = (Map.Entry) o;
jaroslav@1258: V value = entry.getValue();
jaroslav@1258: Entry p = getEntry(entry.getKey());
jaroslav@1258: return p != null && valEquals(p.getValue(), value);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public boolean remove(Object o) {
jaroslav@1258: if (!(o instanceof Map.Entry))
jaroslav@1258: return false;
jaroslav@1258: Map.Entry entry = (Map.Entry) o;
jaroslav@1258: V value = entry.getValue();
jaroslav@1258: Entry p = getEntry(entry.getKey());
jaroslav@1258: if (p != null && valEquals(p.getValue(), value)) {
jaroslav@1258: deleteEntry(p);
jaroslav@1258: return true;
jaroslav@1258: }
jaroslav@1258: return false;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public int size() {
jaroslav@1258: return TreeMap.this.size();
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public void clear() {
jaroslav@1258: TreeMap.this.clear();
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /*
jaroslav@1258: * Unlike Values and EntrySet, the KeySet class is static,
jaroslav@1258: * delegating to a NavigableMap to allow use by SubMaps, which
jaroslav@1258: * outweighs the ugliness of needing type-tests for the following
jaroslav@1258: * Iterator methods that are defined appropriately in main versus
jaroslav@1258: * submap classes.
jaroslav@1258: */
jaroslav@1258:
jaroslav@1258: Iterator keyIterator() {
jaroslav@1258: return new KeyIterator(getFirstEntry());
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: Iterator descendingKeyIterator() {
jaroslav@1258: return new DescendingKeyIterator(getLastEntry());
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: static final class KeySet extends AbstractSet implements NavigableSet {
jaroslav@1258: private final NavigableMap m;
jaroslav@1258: KeySet(NavigableMap map) { m = map; }
jaroslav@1258:
jaroslav@1258: public Iterator iterator() {
jaroslav@1258: if (m instanceof TreeMap)
jaroslav@1258: return ((TreeMap)m).keyIterator();
jaroslav@1258: else
jaroslav@1258: return (Iterator)(((TreeMap.NavigableSubMap)m).keyIterator());
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public Iterator descendingIterator() {
jaroslav@1258: if (m instanceof TreeMap)
jaroslav@1258: return ((TreeMap)m).descendingKeyIterator();
jaroslav@1258: else
jaroslav@1258: return (Iterator)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public int size() { return m.size(); }
jaroslav@1258: public boolean isEmpty() { return m.isEmpty(); }
jaroslav@1258: public boolean contains(Object o) { return m.containsKey(o); }
jaroslav@1258: public void clear() { m.clear(); }
jaroslav@1258: public E lower(E e) { return m.lowerKey(e); }
jaroslav@1258: public E floor(E e) { return m.floorKey(e); }
jaroslav@1258: public E ceiling(E e) { return m.ceilingKey(e); }
jaroslav@1258: public E higher(E e) { return m.higherKey(e); }
jaroslav@1258: public E first() { return m.firstKey(); }
jaroslav@1258: public E last() { return m.lastKey(); }
jaroslav@1258: public Comparator comparator() { return m.comparator(); }
jaroslav@1258: public E pollFirst() {
jaroslav@1258: Map.Entry e = m.pollFirstEntry();
jaroslav@1258: return (e == null) ? null : e.getKey();
jaroslav@1258: }
jaroslav@1258: public E pollLast() {
jaroslav@1258: Map.Entry e = m.pollLastEntry();
jaroslav@1258: return (e == null) ? null : e.getKey();
jaroslav@1258: }
jaroslav@1258: public boolean remove(Object o) {
jaroslav@1258: int oldSize = size();
jaroslav@1258: m.remove(o);
jaroslav@1258: return size() != oldSize;
jaroslav@1258: }
jaroslav@1258: public NavigableSet subSet(E fromElement, boolean fromInclusive,
jaroslav@1258: E toElement, boolean toInclusive) {
jaroslav@1258: return new KeySet<>(m.subMap(fromElement, fromInclusive,
jaroslav@1258: toElement, toInclusive));
jaroslav@1258: }
jaroslav@1258: public NavigableSet headSet(E toElement, boolean inclusive) {
jaroslav@1258: return new KeySet<>(m.headMap(toElement, inclusive));
jaroslav@1258: }
jaroslav@1258: public NavigableSet tailSet(E fromElement, boolean inclusive) {
jaroslav@1258: return new KeySet<>(m.tailMap(fromElement, inclusive));
jaroslav@1258: }
jaroslav@1258: public SortedSet subSet(E fromElement, E toElement) {
jaroslav@1258: return subSet(fromElement, true, toElement, false);
jaroslav@1258: }
jaroslav@1258: public SortedSet headSet(E toElement) {
jaroslav@1258: return headSet(toElement, false);
jaroslav@1258: }
jaroslav@1258: public SortedSet tailSet(E fromElement) {
jaroslav@1258: return tailSet(fromElement, true);
jaroslav@1258: }
jaroslav@1258: public NavigableSet descendingSet() {
jaroslav@1258: return new KeySet(m.descendingMap());
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Base class for TreeMap Iterators
jaroslav@1258: */
jaroslav@1258: abstract class PrivateEntryIterator implements Iterator {
jaroslav@1258: Entry next;
jaroslav@1258: Entry lastReturned;
jaroslav@1258: int expectedModCount;
jaroslav@1258:
jaroslav@1258: PrivateEntryIterator(Entry first) {
jaroslav@1258: expectedModCount = modCount;
jaroslav@1258: lastReturned = null;
jaroslav@1258: next = first;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final boolean hasNext() {
jaroslav@1258: return next != null;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final Entry nextEntry() {
jaroslav@1258: Entry e = next;
jaroslav@1258: if (e == null)
jaroslav@1258: throw new NoSuchElementException();
jaroslav@1258: if (modCount != expectedModCount)
jaroslav@1258: throw new ConcurrentModificationException();
jaroslav@1258: next = successor(e);
jaroslav@1258: lastReturned = e;
jaroslav@1258: return e;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final Entry prevEntry() {
jaroslav@1258: Entry e = next;
jaroslav@1258: if (e == null)
jaroslav@1258: throw new NoSuchElementException();
jaroslav@1258: if (modCount != expectedModCount)
jaroslav@1258: throw new ConcurrentModificationException();
jaroslav@1258: next = predecessor(e);
jaroslav@1258: lastReturned = e;
jaroslav@1258: return e;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public void remove() {
jaroslav@1258: if (lastReturned == null)
jaroslav@1258: throw new IllegalStateException();
jaroslav@1258: if (modCount != expectedModCount)
jaroslav@1258: throw new ConcurrentModificationException();
jaroslav@1258: // deleted entries are replaced by their successors
jaroslav@1258: if (lastReturned.left != null && lastReturned.right != null)
jaroslav@1258: next = lastReturned;
jaroslav@1258: deleteEntry(lastReturned);
jaroslav@1258: expectedModCount = modCount;
jaroslav@1258: lastReturned = null;
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final class EntryIterator extends PrivateEntryIterator> {
jaroslav@1258: EntryIterator(Entry first) {
jaroslav@1258: super(first);
jaroslav@1258: }
jaroslav@1258: public Map.Entry next() {
jaroslav@1258: return nextEntry();
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final class ValueIterator extends PrivateEntryIterator {
jaroslav@1258: ValueIterator(Entry first) {
jaroslav@1258: super(first);
jaroslav@1258: }
jaroslav@1258: public V next() {
jaroslav@1258: return nextEntry().value;
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final class KeyIterator extends PrivateEntryIterator {
jaroslav@1258: KeyIterator(Entry first) {
jaroslav@1258: super(first);
jaroslav@1258: }
jaroslav@1258: public K next() {
jaroslav@1258: return nextEntry().key;
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final class DescendingKeyIterator extends PrivateEntryIterator {
jaroslav@1258: DescendingKeyIterator(Entry first) {
jaroslav@1258: super(first);
jaroslav@1258: }
jaroslav@1258: public K next() {
jaroslav@1258: return prevEntry().key;
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: // Little utilities
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Compares two keys using the correct comparison method for this TreeMap.
jaroslav@1258: */
jaroslav@1258: final int compare(Object k1, Object k2) {
jaroslav@1258: return comparator==null ? ((Comparable)k1).compareTo((K)k2)
jaroslav@1258: : comparator.compare((K)k1, (K)k2);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Test two values for equality. Differs from o1.equals(o2) only in
jaroslav@1258: * that it copes with {@code null} o1 properly.
jaroslav@1258: */
jaroslav@1258: static final boolean valEquals(Object o1, Object o2) {
jaroslav@1258: return (o1==null ? o2==null : o1.equals(o2));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Return SimpleImmutableEntry for entry, or null if null
jaroslav@1258: */
jaroslav@1258: static Map.Entry exportEntry(TreeMap.Entry e) {
jaroslav@1258: return (e == null) ? null :
jaroslav@1258: new AbstractMap.SimpleImmutableEntry<>(e);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Return key for entry, or null if null
jaroslav@1258: */
jaroslav@1258: static K keyOrNull(TreeMap.Entry e) {
jaroslav@1258: return (e == null) ? null : e.key;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Returns the key corresponding to the specified Entry.
jaroslav@1258: * @throws NoSuchElementException if the Entry is null
jaroslav@1258: */
jaroslav@1258: static K key(Entry e) {
jaroslav@1258: if (e==null)
jaroslav@1258: throw new NoSuchElementException();
jaroslav@1258: return e.key;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258:
jaroslav@1258: // SubMaps
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Dummy value serving as unmatchable fence key for unbounded
jaroslav@1258: * SubMapIterators
jaroslav@1258: */
jaroslav@1258: private static final Object UNBOUNDED = new Object();
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @serial include
jaroslav@1258: */
jaroslav@1258: abstract static class NavigableSubMap extends AbstractMap
jaroslav@1258: implements NavigableMap, java.io.Serializable {
jaroslav@1258: /**
jaroslav@1258: * The backing map.
jaroslav@1258: */
jaroslav@1258: final TreeMap m;
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Endpoints are represented as triples (fromStart, lo,
jaroslav@1258: * loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
jaroslav@1258: * true, then the low (absolute) bound is the start of the
jaroslav@1258: * backing map, and the other values are ignored. Otherwise,
jaroslav@1258: * if loInclusive is true, lo is the inclusive bound, else lo
jaroslav@1258: * is the exclusive bound. Similarly for the upper bound.
jaroslav@1258: */
jaroslav@1258: final K lo, hi;
jaroslav@1258: final boolean fromStart, toEnd;
jaroslav@1258: final boolean loInclusive, hiInclusive;
jaroslav@1258:
jaroslav@1258: NavigableSubMap(TreeMap m,
jaroslav@1258: boolean fromStart, K lo, boolean loInclusive,
jaroslav@1258: boolean toEnd, K hi, boolean hiInclusive) {
jaroslav@1258: if (!fromStart && !toEnd) {
jaroslav@1258: if (m.compare(lo, hi) > 0)
jaroslav@1258: throw new IllegalArgumentException("fromKey > toKey");
jaroslav@1258: } else {
jaroslav@1258: if (!fromStart) // type check
jaroslav@1258: m.compare(lo, lo);
jaroslav@1258: if (!toEnd)
jaroslav@1258: m.compare(hi, hi);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: this.m = m;
jaroslav@1258: this.fromStart = fromStart;
jaroslav@1258: this.lo = lo;
jaroslav@1258: this.loInclusive = loInclusive;
jaroslav@1258: this.toEnd = toEnd;
jaroslav@1258: this.hi = hi;
jaroslav@1258: this.hiInclusive = hiInclusive;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: // internal utilities
jaroslav@1258:
jaroslav@1258: final boolean tooLow(Object key) {
jaroslav@1258: if (!fromStart) {
jaroslav@1258: int c = m.compare(key, lo);
jaroslav@1258: if (c < 0 || (c == 0 && !loInclusive))
jaroslav@1258: return true;
jaroslav@1258: }
jaroslav@1258: return false;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final boolean tooHigh(Object key) {
jaroslav@1258: if (!toEnd) {
jaroslav@1258: int c = m.compare(key, hi);
jaroslav@1258: if (c > 0 || (c == 0 && !hiInclusive))
jaroslav@1258: return true;
jaroslav@1258: }
jaroslav@1258: return false;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final boolean inRange(Object key) {
jaroslav@1258: return !tooLow(key) && !tooHigh(key);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final boolean inClosedRange(Object key) {
jaroslav@1258: return (fromStart || m.compare(key, lo) >= 0)
jaroslav@1258: && (toEnd || m.compare(hi, key) >= 0);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final boolean inRange(Object key, boolean inclusive) {
jaroslav@1258: return inclusive ? inRange(key) : inClosedRange(key);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /*
jaroslav@1258: * Absolute versions of relation operations.
jaroslav@1258: * Subclasses map to these using like-named "sub"
jaroslav@1258: * versions that invert senses for descending maps
jaroslav@1258: */
jaroslav@1258:
jaroslav@1258: final TreeMap.Entry absLowest() {
jaroslav@1258: TreeMap.Entry e =
jaroslav@1258: (fromStart ? m.getFirstEntry() :
jaroslav@1258: (loInclusive ? m.getCeilingEntry(lo) :
jaroslav@1258: m.getHigherEntry(lo)));
jaroslav@1258: return (e == null || tooHigh(e.key)) ? null : e;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final TreeMap.Entry absHighest() {
jaroslav@1258: TreeMap.Entry e =
jaroslav@1258: (toEnd ? m.getLastEntry() :
jaroslav@1258: (hiInclusive ? m.getFloorEntry(hi) :
jaroslav@1258: m.getLowerEntry(hi)));
jaroslav@1258: return (e == null || tooLow(e.key)) ? null : e;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final TreeMap.Entry absCeiling(K key) {
jaroslav@1258: if (tooLow(key))
jaroslav@1258: return absLowest();
jaroslav@1258: TreeMap.Entry e = m.getCeilingEntry(key);
jaroslav@1258: return (e == null || tooHigh(e.key)) ? null : e;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final TreeMap.Entry absHigher(K key) {
jaroslav@1258: if (tooLow(key))
jaroslav@1258: return absLowest();
jaroslav@1258: TreeMap.Entry e = m.getHigherEntry(key);
jaroslav@1258: return (e == null || tooHigh(e.key)) ? null : e;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final TreeMap.Entry absFloor(K key) {
jaroslav@1258: if (tooHigh(key))
jaroslav@1258: return absHighest();
jaroslav@1258: TreeMap.Entry e = m.getFloorEntry(key);
jaroslav@1258: return (e == null || tooLow(e.key)) ? null : e;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final TreeMap.Entry absLower(K key) {
jaroslav@1258: if (tooHigh(key))
jaroslav@1258: return absHighest();
jaroslav@1258: TreeMap.Entry e = m.getLowerEntry(key);
jaroslav@1258: return (e == null || tooLow(e.key)) ? null : e;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /** Returns the absolute high fence for ascending traversal */
jaroslav@1258: final TreeMap.Entry absHighFence() {
jaroslav@1258: return (toEnd ? null : (hiInclusive ?
jaroslav@1258: m.getHigherEntry(hi) :
jaroslav@1258: m.getCeilingEntry(hi)));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /** Return the absolute low fence for descending traversal */
jaroslav@1258: final TreeMap.Entry absLowFence() {
jaroslav@1258: return (fromStart ? null : (loInclusive ?
jaroslav@1258: m.getLowerEntry(lo) :
jaroslav@1258: m.getFloorEntry(lo)));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: // Abstract methods defined in ascending vs descending classes
jaroslav@1258: // These relay to the appropriate absolute versions
jaroslav@1258:
jaroslav@1258: abstract TreeMap.Entry subLowest();
jaroslav@1258: abstract TreeMap.Entry subHighest();
jaroslav@1258: abstract TreeMap.Entry subCeiling(K key);
jaroslav@1258: abstract TreeMap.Entry subHigher(K key);
jaroslav@1258: abstract TreeMap.Entry subFloor(K key);
jaroslav@1258: abstract TreeMap.Entry subLower(K key);
jaroslav@1258:
jaroslav@1258: /** Returns ascending iterator from the perspective of this submap */
jaroslav@1258: abstract Iterator keyIterator();
jaroslav@1258:
jaroslav@1258: /** Returns descending iterator from the perspective of this submap */
jaroslav@1258: abstract Iterator descendingKeyIterator();
jaroslav@1258:
jaroslav@1258: // public methods
jaroslav@1258:
jaroslav@1258: public boolean isEmpty() {
jaroslav@1258: return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public int size() {
jaroslav@1258: return (fromStart && toEnd) ? m.size() : entrySet().size();
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final boolean containsKey(Object key) {
jaroslav@1258: return inRange(key) && m.containsKey(key);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final V put(K key, V value) {
jaroslav@1258: if (!inRange(key))
jaroslav@1258: throw new IllegalArgumentException("key out of range");
jaroslav@1258: return m.put(key, value);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final V get(Object key) {
jaroslav@1258: return !inRange(key) ? null : m.get(key);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final V remove(Object key) {
jaroslav@1258: return !inRange(key) ? null : m.remove(key);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final Map.Entry ceilingEntry(K key) {
jaroslav@1258: return exportEntry(subCeiling(key));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final K ceilingKey(K key) {
jaroslav@1258: return keyOrNull(subCeiling(key));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final Map.Entry higherEntry(K key) {
jaroslav@1258: return exportEntry(subHigher(key));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final K higherKey(K key) {
jaroslav@1258: return keyOrNull(subHigher(key));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final Map.Entry floorEntry(K key) {
jaroslav@1258: return exportEntry(subFloor(key));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final K floorKey(K key) {
jaroslav@1258: return keyOrNull(subFloor(key));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final Map.Entry lowerEntry(K key) {
jaroslav@1258: return exportEntry(subLower(key));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final K lowerKey(K key) {
jaroslav@1258: return keyOrNull(subLower(key));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final K firstKey() {
jaroslav@1258: return key(subLowest());
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final K lastKey() {
jaroslav@1258: return key(subHighest());
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final Map.Entry firstEntry() {
jaroslav@1258: return exportEntry(subLowest());
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final Map.Entry lastEntry() {
jaroslav@1258: return exportEntry(subHighest());
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final Map.Entry pollFirstEntry() {
jaroslav@1258: TreeMap.Entry e = subLowest();
jaroslav@1258: Map.Entry result = exportEntry(e);
jaroslav@1258: if (e != null)
jaroslav@1258: m.deleteEntry(e);
jaroslav@1258: return result;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final Map.Entry pollLastEntry() {
jaroslav@1258: TreeMap.Entry e = subHighest();
jaroslav@1258: Map.Entry result = exportEntry(e);
jaroslav@1258: if (e != null)
jaroslav@1258: m.deleteEntry(e);
jaroslav@1258: return result;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: // Views
jaroslav@1258: transient NavigableMap descendingMapView = null;
jaroslav@1258: transient EntrySetView entrySetView = null;
jaroslav@1258: transient KeySet navigableKeySetView = null;
jaroslav@1258:
jaroslav@1258: public final NavigableSet navigableKeySet() {
jaroslav@1258: KeySet nksv = navigableKeySetView;
jaroslav@1258: return (nksv != null) ? nksv :
jaroslav@1258: (navigableKeySetView = new TreeMap.KeySet(this));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final Set keySet() {
jaroslav@1258: return navigableKeySet();
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public NavigableSet descendingKeySet() {
jaroslav@1258: return descendingMap().navigableKeySet();
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final SortedMap subMap(K fromKey, K toKey) {
jaroslav@1258: return subMap(fromKey, true, toKey, false);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final SortedMap headMap(K toKey) {
jaroslav@1258: return headMap(toKey, false);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final SortedMap tailMap(K fromKey) {
jaroslav@1258: return tailMap(fromKey, true);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: // View classes
jaroslav@1258:
jaroslav@1258: abstract class EntrySetView extends AbstractSet> {
jaroslav@1258: private transient int size = -1, sizeModCount;
jaroslav@1258:
jaroslav@1258: public int size() {
jaroslav@1258: if (fromStart && toEnd)
jaroslav@1258: return m.size();
jaroslav@1258: if (size == -1 || sizeModCount != m.modCount) {
jaroslav@1258: sizeModCount = m.modCount;
jaroslav@1258: size = 0;
jaroslav@1258: Iterator i = iterator();
jaroslav@1258: while (i.hasNext()) {
jaroslav@1258: size++;
jaroslav@1258: i.next();
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258: return size;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public boolean isEmpty() {
jaroslav@1258: TreeMap.Entry n = absLowest();
jaroslav@1258: return n == null || tooHigh(n.key);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public boolean contains(Object o) {
jaroslav@1258: if (!(o instanceof Map.Entry))
jaroslav@1258: return false;
jaroslav@1258: Map.Entry entry = (Map.Entry) o;
jaroslav@1258: K key = entry.getKey();
jaroslav@1258: if (!inRange(key))
jaroslav@1258: return false;
jaroslav@1258: TreeMap.Entry node = m.getEntry(key);
jaroslav@1258: return node != null &&
jaroslav@1258: valEquals(node.getValue(), entry.getValue());
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public boolean remove(Object o) {
jaroslav@1258: if (!(o instanceof Map.Entry))
jaroslav@1258: return false;
jaroslav@1258: Map.Entry entry = (Map.Entry) o;
jaroslav@1258: K key = entry.getKey();
jaroslav@1258: if (!inRange(key))
jaroslav@1258: return false;
jaroslav@1258: TreeMap.Entry node = m.getEntry(key);
jaroslav@1258: if (node!=null && valEquals(node.getValue(),
jaroslav@1258: entry.getValue())) {
jaroslav@1258: m.deleteEntry(node);
jaroslav@1258: return true;
jaroslav@1258: }
jaroslav@1258: return false;
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Iterators for SubMaps
jaroslav@1258: */
jaroslav@1258: abstract class SubMapIterator implements Iterator {
jaroslav@1258: TreeMap.Entry lastReturned;
jaroslav@1258: TreeMap.Entry next;
jaroslav@1258: final Object fenceKey;
jaroslav@1258: int expectedModCount;
jaroslav@1258:
jaroslav@1258: SubMapIterator(TreeMap.Entry first,
jaroslav@1258: TreeMap.Entry fence) {
jaroslav@1258: expectedModCount = m.modCount;
jaroslav@1258: lastReturned = null;
jaroslav@1258: next = first;
jaroslav@1258: fenceKey = fence == null ? UNBOUNDED : fence.key;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public final boolean hasNext() {
jaroslav@1258: return next != null && next.key != fenceKey;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final TreeMap.Entry nextEntry() {
jaroslav@1258: TreeMap.Entry e = next;
jaroslav@1258: if (e == null || e.key == fenceKey)
jaroslav@1258: throw new NoSuchElementException();
jaroslav@1258: if (m.modCount != expectedModCount)
jaroslav@1258: throw new ConcurrentModificationException();
jaroslav@1258: next = successor(e);
jaroslav@1258: lastReturned = e;
jaroslav@1258: return e;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final TreeMap.Entry prevEntry() {
jaroslav@1258: TreeMap.Entry e = next;
jaroslav@1258: if (e == null || e.key == fenceKey)
jaroslav@1258: throw new NoSuchElementException();
jaroslav@1258: if (m.modCount != expectedModCount)
jaroslav@1258: throw new ConcurrentModificationException();
jaroslav@1258: next = predecessor(e);
jaroslav@1258: lastReturned = e;
jaroslav@1258: return e;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final void removeAscending() {
jaroslav@1258: if (lastReturned == null)
jaroslav@1258: throw new IllegalStateException();
jaroslav@1258: if (m.modCount != expectedModCount)
jaroslav@1258: throw new ConcurrentModificationException();
jaroslav@1258: // deleted entries are replaced by their successors
jaroslav@1258: if (lastReturned.left != null && lastReturned.right != null)
jaroslav@1258: next = lastReturned;
jaroslav@1258: m.deleteEntry(lastReturned);
jaroslav@1258: lastReturned = null;
jaroslav@1258: expectedModCount = m.modCount;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final void removeDescending() {
jaroslav@1258: if (lastReturned == null)
jaroslav@1258: throw new IllegalStateException();
jaroslav@1258: if (m.modCount != expectedModCount)
jaroslav@1258: throw new ConcurrentModificationException();
jaroslav@1258: m.deleteEntry(lastReturned);
jaroslav@1258: lastReturned = null;
jaroslav@1258: expectedModCount = m.modCount;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final class SubMapEntryIterator extends SubMapIterator> {
jaroslav@1258: SubMapEntryIterator(TreeMap.Entry first,
jaroslav@1258: TreeMap.Entry fence) {
jaroslav@1258: super(first, fence);
jaroslav@1258: }
jaroslav@1258: public Map.Entry next() {
jaroslav@1258: return nextEntry();
jaroslav@1258: }
jaroslav@1258: public void remove() {
jaroslav@1258: removeAscending();
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final class SubMapKeyIterator extends SubMapIterator {
jaroslav@1258: SubMapKeyIterator(TreeMap.Entry first,
jaroslav@1258: TreeMap.Entry fence) {
jaroslav@1258: super(first, fence);
jaroslav@1258: }
jaroslav@1258: public K next() {
jaroslav@1258: return nextEntry().key;
jaroslav@1258: }
jaroslav@1258: public void remove() {
jaroslav@1258: removeAscending();
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final class DescendingSubMapEntryIterator extends SubMapIterator> {
jaroslav@1258: DescendingSubMapEntryIterator(TreeMap.Entry last,
jaroslav@1258: TreeMap.Entry fence) {
jaroslav@1258: super(last, fence);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public Map.Entry next() {
jaroslav@1258: return prevEntry();
jaroslav@1258: }
jaroslav@1258: public void remove() {
jaroslav@1258: removeDescending();
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final class DescendingSubMapKeyIterator extends SubMapIterator {
jaroslav@1258: DescendingSubMapKeyIterator(TreeMap.Entry last,
jaroslav@1258: TreeMap.Entry fence) {
jaroslav@1258: super(last, fence);
jaroslav@1258: }
jaroslav@1258: public K next() {
jaroslav@1258: return prevEntry().key;
jaroslav@1258: }
jaroslav@1258: public void remove() {
jaroslav@1258: removeDescending();
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @serial include
jaroslav@1258: */
jaroslav@1258: static final class AscendingSubMap extends NavigableSubMap {
jaroslav@1258: private static final long serialVersionUID = 912986545866124060L;
jaroslav@1258:
jaroslav@1258: AscendingSubMap(TreeMap m,
jaroslav@1258: boolean fromStart, K lo, boolean loInclusive,
jaroslav@1258: boolean toEnd, K hi, boolean hiInclusive) {
jaroslav@1258: super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public Comparator comparator() {
jaroslav@1258: return m.comparator();
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public NavigableMap subMap(K fromKey, boolean fromInclusive,
jaroslav@1258: K toKey, boolean toInclusive) {
jaroslav@1258: if (!inRange(fromKey, fromInclusive))
jaroslav@1258: throw new IllegalArgumentException("fromKey out of range");
jaroslav@1258: if (!inRange(toKey, toInclusive))
jaroslav@1258: throw new IllegalArgumentException("toKey out of range");
jaroslav@1258: return new AscendingSubMap(m,
jaroslav@1258: false, fromKey, fromInclusive,
jaroslav@1258: false, toKey, toInclusive);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public NavigableMap headMap(K toKey, boolean inclusive) {
jaroslav@1258: if (!inRange(toKey, inclusive))
jaroslav@1258: throw new IllegalArgumentException("toKey out of range");
jaroslav@1258: return new AscendingSubMap(m,
jaroslav@1258: fromStart, lo, loInclusive,
jaroslav@1258: false, toKey, inclusive);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public NavigableMap tailMap(K fromKey, boolean inclusive) {
jaroslav@1258: if (!inRange(fromKey, inclusive))
jaroslav@1258: throw new IllegalArgumentException("fromKey out of range");
jaroslav@1258: return new AscendingSubMap(m,
jaroslav@1258: false, fromKey, inclusive,
jaroslav@1258: toEnd, hi, hiInclusive);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public NavigableMap descendingMap() {
jaroslav@1258: NavigableMap mv = descendingMapView;
jaroslav@1258: return (mv != null) ? mv :
jaroslav@1258: (descendingMapView =
jaroslav@1258: new DescendingSubMap(m,
jaroslav@1258: fromStart, lo, loInclusive,
jaroslav@1258: toEnd, hi, hiInclusive));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: Iterator keyIterator() {
jaroslav@1258: return new SubMapKeyIterator(absLowest(), absHighFence());
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: Iterator descendingKeyIterator() {
jaroslav@1258: return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final class AscendingEntrySetView extends EntrySetView {
jaroslav@1258: public Iterator> iterator() {
jaroslav@1258: return new SubMapEntryIterator(absLowest(), absHighFence());
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public Set> entrySet() {
jaroslav@1258: EntrySetView es = entrySetView;
jaroslav@1258: return (es != null) ? es : new AscendingEntrySetView();
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: TreeMap.Entry subLowest() { return absLowest(); }
jaroslav@1258: TreeMap.Entry subHighest() { return absHighest(); }
jaroslav@1258: TreeMap.Entry subCeiling(K key) { return absCeiling(key); }
jaroslav@1258: TreeMap.Entry subHigher(K key) { return absHigher(key); }
jaroslav@1258: TreeMap.Entry subFloor(K key) { return absFloor(key); }
jaroslav@1258: TreeMap.Entry subLower(K key) { return absLower(key); }
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * @serial include
jaroslav@1258: */
jaroslav@1258: static final class DescendingSubMap extends NavigableSubMap {
jaroslav@1258: private static final long serialVersionUID = 912986545866120460L;
jaroslav@1258: DescendingSubMap(TreeMap m,
jaroslav@1258: boolean fromStart, K lo, boolean loInclusive,
jaroslav@1258: boolean toEnd, K hi, boolean hiInclusive) {
jaroslav@1258: super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: private final Comparator reverseComparator =
jaroslav@1258: Collections.reverseOrder(m.comparator);
jaroslav@1258:
jaroslav@1258: public Comparator comparator() {
jaroslav@1258: return reverseComparator;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public NavigableMap subMap(K fromKey, boolean fromInclusive,
jaroslav@1258: K toKey, boolean toInclusive) {
jaroslav@1258: if (!inRange(fromKey, fromInclusive))
jaroslav@1258: throw new IllegalArgumentException("fromKey out of range");
jaroslav@1258: if (!inRange(toKey, toInclusive))
jaroslav@1258: throw new IllegalArgumentException("toKey out of range");
jaroslav@1258: return new DescendingSubMap(m,
jaroslav@1258: false, toKey, toInclusive,
jaroslav@1258: false, fromKey, fromInclusive);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public NavigableMap headMap(K toKey, boolean inclusive) {
jaroslav@1258: if (!inRange(toKey, inclusive))
jaroslav@1258: throw new IllegalArgumentException("toKey out of range");
jaroslav@1258: return new DescendingSubMap(m,
jaroslav@1258: false, toKey, inclusive,
jaroslav@1258: toEnd, hi, hiInclusive);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public NavigableMap tailMap(K fromKey, boolean inclusive) {
jaroslav@1258: if (!inRange(fromKey, inclusive))
jaroslav@1258: throw new IllegalArgumentException("fromKey out of range");
jaroslav@1258: return new DescendingSubMap(m,
jaroslav@1258: fromStart, lo, loInclusive,
jaroslav@1258: false, fromKey, inclusive);
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public NavigableMap descendingMap() {
jaroslav@1258: NavigableMap mv = descendingMapView;
jaroslav@1258: return (mv != null) ? mv :
jaroslav@1258: (descendingMapView =
jaroslav@1258: new AscendingSubMap(m,
jaroslav@1258: fromStart, lo, loInclusive,
jaroslav@1258: toEnd, hi, hiInclusive));
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: Iterator keyIterator() {
jaroslav@1258: return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: Iterator descendingKeyIterator() {
jaroslav@1258: return new SubMapKeyIterator(absLowest(), absHighFence());
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: final class DescendingEntrySetView extends EntrySetView {
jaroslav@1258: public Iterator> iterator() {
jaroslav@1258: return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public Set> entrySet() {
jaroslav@1258: EntrySetView es = entrySetView;
jaroslav@1258: return (es != null) ? es : new DescendingEntrySetView();
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: TreeMap.Entry subLowest() { return absHighest(); }
jaroslav@1258: TreeMap.Entry subHighest() { return absLowest(); }
jaroslav@1258: TreeMap.Entry subCeiling(K key) { return absFloor(key); }
jaroslav@1258: TreeMap.Entry subHigher(K key) { return absLower(key); }
jaroslav@1258: TreeMap.Entry subFloor(K key) { return absCeiling(key); }
jaroslav@1258: TreeMap.Entry subLower(K key) { return absHigher(key); }
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * This class exists solely for the sake of serialization
jaroslav@1258: * compatibility with previous releases of TreeMap that did not
jaroslav@1258: * support NavigableMap. It translates an old-version SubMap into
jaroslav@1258: * a new-version AscendingSubMap. This class is never otherwise
jaroslav@1258: * used.
jaroslav@1258: *
jaroslav@1258: * @serial include
jaroslav@1258: */
jaroslav@1258: private class SubMap extends AbstractMap
jaroslav@1258: implements SortedMap, java.io.Serializable {
jaroslav@1258: private static final long serialVersionUID = -6520786458950516097L;
jaroslav@1258: private boolean fromStart = false, toEnd = false;
jaroslav@1258: private K fromKey, toKey;
jaroslav@1258: private Object readResolve() {
jaroslav@1258: return new AscendingSubMap(TreeMap.this,
jaroslav@1258: fromStart, fromKey, true,
jaroslav@1258: toEnd, toKey, false);
jaroslav@1258: }
jaroslav@1258: public Set> entrySet() { throw new InternalError(); }
jaroslav@1258: public K lastKey() { throw new InternalError(); }
jaroslav@1258: public K firstKey() { throw new InternalError(); }
jaroslav@1258: public SortedMap subMap(K fromKey, K toKey) { throw new InternalError(); }
jaroslav@1258: public SortedMap headMap(K toKey) { throw new InternalError(); }
jaroslav@1258: public SortedMap tailMap(K fromKey) { throw new InternalError(); }
jaroslav@1258: public Comparator comparator() { throw new InternalError(); }
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258:
jaroslav@1258: // Red-black mechanics
jaroslav@1258:
jaroslav@1258: private static final boolean RED = false;
jaroslav@1258: private static final boolean BLACK = true;
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Node in the Tree. Doubles as a means to pass key-value pairs back to
jaroslav@1258: * user (see Map.Entry).
jaroslav@1258: */
jaroslav@1258:
jaroslav@1258: static final class Entry implements Map.Entry {
jaroslav@1258: K key;
jaroslav@1258: V value;
jaroslav@1258: Entry left = null;
jaroslav@1258: Entry right = null;
jaroslav@1258: Entry parent;
jaroslav@1258: boolean color = BLACK;
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Make a new cell with given key, value, and parent, and with
jaroslav@1258: * {@code null} child links, and BLACK color.
jaroslav@1258: */
jaroslav@1258: Entry(K key, V value, Entry parent) {
jaroslav@1258: this.key = key;
jaroslav@1258: this.value = value;
jaroslav@1258: this.parent = parent;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Returns the key.
jaroslav@1258: *
jaroslav@1258: * @return the key
jaroslav@1258: */
jaroslav@1258: public K getKey() {
jaroslav@1258: return key;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Returns the value associated with the key.
jaroslav@1258: *
jaroslav@1258: * @return the value associated with the key
jaroslav@1258: */
jaroslav@1258: public V getValue() {
jaroslav@1258: return value;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Replaces the value currently associated with the key with the given
jaroslav@1258: * value.
jaroslav@1258: *
jaroslav@1258: * @return the value associated with the key before this method was
jaroslav@1258: * called
jaroslav@1258: */
jaroslav@1258: public V setValue(V value) {
jaroslav@1258: V oldValue = this.value;
jaroslav@1258: this.value = value;
jaroslav@1258: return oldValue;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public boolean equals(Object o) {
jaroslav@1258: if (!(o instanceof Map.Entry))
jaroslav@1258: return false;
jaroslav@1258: Map.Entry e = (Map.Entry)o;
jaroslav@1258:
jaroslav@1258: return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public int hashCode() {
jaroslav@1258: int keyHash = (key==null ? 0 : key.hashCode());
jaroslav@1258: int valueHash = (value==null ? 0 : value.hashCode());
jaroslav@1258: return keyHash ^ valueHash;
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: public String toString() {
jaroslav@1258: return key + "=" + value;
jaroslav@1258: }
jaroslav@1258: }
jaroslav@1258:
jaroslav@1258: /**
jaroslav@1258: * Returns the first Entry in the TreeMap (according to the TreeMap's
jaroslav@1258: * key-sort function). Returns null if the TreeMap is empty.
jaroslav@1258: */
jaroslav@1258: final Entry getFirstEntry() {
jaroslav@1258: Entry