| /* TreeMap.java -- a class providing a basic Red-Black Tree data structure, |
| mapping Object --> Object |
| Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006 Free Software Foundation, Inc. |
| |
| This file is part of GNU Classpath. |
| |
| GNU Classpath is free software; you can redistribute it and/or modify |
| it under the terms of the GNU General Public License as published by |
| the Free Software Foundation; either version 2, or (at your option) |
| any later version. |
| |
| GNU Classpath 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 for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with GNU Classpath; see the file COPYING. If not, write to the |
| Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA |
| 02110-1301 USA. |
| |
| Linking this library statically or dynamically with other modules is |
| making a combined work based on this library. Thus, the terms and |
| conditions of the GNU General Public License cover the whole |
| combination. |
| |
| As a special exception, the copyright holders of this library give you |
| permission to link this library with independent modules to produce an |
| executable, regardless of the license terms of these independent |
| modules, and to copy and distribute the resulting executable under |
| terms of your choice, provided that you also meet, for each linked |
| independent module, the terms and conditions of the license of that |
| module. An independent module is a module which is not derived from |
| or based on this library. If you modify this library, you may extend |
| this exception to your version of the library, but you are not |
| obligated to do so. If you do not wish to do so, delete this |
| exception statement from your version. */ |
| |
| |
| package java.util; |
| |
| import java.io.IOException; |
| import java.io.ObjectInputStream; |
| import java.io.ObjectOutputStream; |
| import java.io.Serializable; |
| |
| /** |
| * This class provides a red-black tree implementation of the SortedMap |
| * interface. Elements in the Map will be sorted by either a user-provided |
| * Comparator object, or by the natural ordering of the keys. |
| * |
| * The algorithms are adopted from Corman, Leiserson, and Rivest's |
| * <i>Introduction to Algorithms.</i> TreeMap guarantees O(log n) |
| * insertion and deletion of elements. That being said, there is a large |
| * enough constant coefficient in front of that "log n" (overhead involved |
| * in keeping the tree balanced), that TreeMap may not be the best choice |
| * for small collections. If something is already sorted, you may want to |
| * just use a LinkedHashMap to maintain the order while providing O(1) access. |
| * |
| * TreeMap is a part of the JDK1.2 Collections API. Null keys are allowed |
| * only if a Comparator is used which can deal with them; natural ordering |
| * cannot cope with null. Null values are always allowed. Note that the |
| * ordering must be <i>consistent with equals</i> to correctly implement |
| * the Map interface. If this condition is violated, the map is still |
| * well-behaved, but you may have suprising results when comparing it to |
| * other maps.<p> |
| * |
| * This implementation is not synchronized. If you need to share this between |
| * multiple threads, do something like:<br> |
| * <code>SortedMap m |
| * = Collections.synchronizedSortedMap(new TreeMap(...));</code><p> |
| * |
| * The iterators are <i>fail-fast</i>, meaning that any structural |
| * modification, except for <code>remove()</code> called on the iterator |
| * itself, cause the iterator to throw a |
| * <code>ConcurrentModificationException</code> rather than exhibit |
| * non-deterministic behavior. |
| * |
| * @author Jon Zeppieri |
| * @author Bryce McKinlay |
| * @author Eric Blake (ebb9@email.byu.edu) |
| * @author Andrew John Hughes (gnu_andrew@member.fsf.org) |
| * @see Map |
| * @see HashMap |
| * @see Hashtable |
| * @see LinkedHashMap |
| * @see Comparable |
| * @see Comparator |
| * @see Collection |
| * @see Collections#synchronizedSortedMap(SortedMap) |
| * @since 1.2 |
| * @status updated to 1.6 |
| */ |
| public class TreeMap<K, V> extends AbstractMap<K, V> |
| implements NavigableMap<K, V>, Cloneable, Serializable |
| { |
| // Implementation note: |
| // A red-black tree is a binary search tree with the additional properties |
| // that all paths to a leaf node visit the same number of black nodes, |
| // and no red node has red children. To avoid some null-pointer checks, |
| // we use the special node nil which is always black, has no relatives, |
| // and has key and value of null (but is not equal to a mapping of null). |
| |
| /** |
| * Compatible with JDK 1.2. |
| */ |
| private static final long serialVersionUID = 919286545866124006L; |
| |
| /** |
| * Color status of a node. Package visible for use by nested classes. |
| */ |
| static final int RED = -1, |
| BLACK = 1; |
| |
| /** |
| * Sentinal node, used to avoid null checks for corner cases and make the |
| * delete rebalance code simpler. The rebalance code must never assign |
| * the parent, left, or right of nil, but may safely reassign the color |
| * to be black. This object must never be used as a key in a TreeMap, or |
| * it will break bounds checking of a SubMap. |
| */ |
| static final Node nil = new Node(null, null, BLACK); |
| static |
| { |
| // Nil is self-referential, so we must initialize it after creation. |
| nil.parent = nil; |
| nil.left = nil; |
| nil.right = nil; |
| } |
| |
| /** |
| * The root node of this TreeMap. |
| */ |
| private transient Node root; |
| |
| /** |
| * The size of this TreeMap. Package visible for use by nested classes. |
| */ |
| transient int size; |
| |
| /** |
| * The cache for {@link #entrySet()}. |
| */ |
| private transient Set<Map.Entry<K,V>> entries; |
| |
| /** |
| * The cache for {@link #descendingMap()}. |
| */ |
| private transient NavigableMap<K,V> descendingMap; |
| |
| /** |
| * The cache for {@link #navigableKeySet()}. |
| */ |
| private transient NavigableSet<K> nKeys; |
| |
| /** |
| * Counts the number of modifications this TreeMap has undergone, used |
| * by Iterators to know when to throw ConcurrentModificationExceptions. |
| * Package visible for use by nested classes. |
| */ |
| transient int modCount; |
| |
| /** |
| * This TreeMap's comparator, or null for natural ordering. |
| * Package visible for use by nested classes. |
| * @serial the comparator ordering this tree, or null |
| */ |
| final Comparator<? super K> comparator; |
| |
| /** |
| * Class to represent an entry in the tree. Holds a single key-value pair, |
| * plus pointers to parent and child nodes. |
| * |
| * @author Eric Blake (ebb9@email.byu.edu) |
| */ |
| private static final class Node<K, V> extends AbstractMap.SimpleEntry<K, V> |
| { |
| // All fields package visible for use by nested classes. |
| /** The color of this node. */ |
| int color; |
| |
| /** The left child node. */ |
| Node<K, V> left = nil; |
| /** The right child node. */ |
| Node<K, V> right = nil; |
| /** The parent node. */ |
| Node<K, V> parent = nil; |
| |
| /** |
| * Simple constructor. |
| * @param key the key |
| * @param value the value |
| */ |
| Node(K key, V value, int color) |
| { |
| super(key, value); |
| this.color = color; |
| } |
| } |
| |
| /** |
| * Instantiate a new TreeMap with no elements, using the keys' natural |
| * ordering to sort. All entries in the map must have a key which implements |
| * Comparable, and which are <i>mutually comparable</i>, otherwise map |
| * operations may throw a {@link ClassCastException}. Attempts to use |
| * a null key will throw a {@link NullPointerException}. |
| * |
| * @see Comparable |
| */ |
| public TreeMap() |
| { |
| this((Comparator) null); |
| } |
| |
| /** |
| * Instantiate a new TreeMap with no elements, using the provided comparator |
| * to sort. All entries in the map must have keys which are mutually |
| * comparable by the Comparator, otherwise map operations may throw a |
| * {@link ClassCastException}. |
| * |
| * @param c the sort order for the keys of this map, or null |
| * for the natural order |
| */ |
| public TreeMap(Comparator<? super K> c) |
| { |
| comparator = c; |
| fabricateTree(0); |
| } |
| |
| /** |
| * Instantiate a new TreeMap, initializing it with all of the elements in |
| * the provided Map. The elements will be sorted using the natural |
| * ordering of the keys. This algorithm runs in n*log(n) time. All entries |
| * in the map must have keys which implement Comparable and are mutually |
| * comparable, otherwise map operations may throw a |
| * {@link ClassCastException}. |
| * |
| * @param map a Map, whose entries will be put into this TreeMap |
| * @throws ClassCastException if the keys in the provided Map are not |
| * comparable |
| * @throws NullPointerException if map is null |
| * @see Comparable |
| */ |
| public TreeMap(Map<? extends K, ? extends V> map) |
| { |
| this((Comparator) null); |
| putAll(map); |
| } |
| |
| /** |
| * Instantiate a new TreeMap, initializing it with all of the elements in |
| * the provided SortedMap. The elements will be sorted using the same |
| * comparator as in the provided SortedMap. This runs in linear time. |
| * |
| * @param sm a SortedMap, whose entries will be put into this TreeMap |
| * @throws NullPointerException if sm is null |
| */ |
| public TreeMap(SortedMap<K, ? extends V> sm) |
| { |
| this(sm.comparator()); |
| int pos = sm.size(); |
| Iterator itr = sm.entrySet().iterator(); |
| |
| fabricateTree(pos); |
| Node node = firstNode(); |
| |
| while (--pos >= 0) |
| { |
| Map.Entry me = (Map.Entry) itr.next(); |
| node.key = me.getKey(); |
| node.value = me.getValue(); |
| node = successor(node); |
| } |
| } |
| |
| /** |
| * Clears the Map so it has no keys. This is O(1). |
| */ |
| public void clear() |
| { |
| if (size > 0) |
| { |
| modCount++; |
| root = nil; |
| size = 0; |
| } |
| } |
| |
| /** |
| * Returns a shallow clone of this TreeMap. The Map itself is cloned, |
| * but its contents are not. |
| * |
| * @return the clone |
| */ |
| public Object clone() |
| { |
| TreeMap copy = null; |
| try |
| { |
| copy = (TreeMap) super.clone(); |
| } |
| catch (CloneNotSupportedException x) |
| { |
| } |
| copy.entries = null; |
| copy.fabricateTree(size); |
| |
| Node node = firstNode(); |
| Node cnode = copy.firstNode(); |
| |
| while (node != nil) |
| { |
| cnode.key = node.key; |
| cnode.value = node.value; |
| node = successor(node); |
| cnode = copy.successor(cnode); |
| } |
| return copy; |
| } |
| |
| /** |
| * Return the comparator used to sort this map, or null if it is by |
| * natural order. |
| * |
| * @return the map's comparator |
| */ |
| public Comparator<? super K> comparator() |
| { |
| return comparator; |
| } |
| |
| /** |
| * Returns true if the map contains a mapping for the given key. |
| * |
| * @param key the key to look for |
| * @return true if the key has a mapping |
| * @throws ClassCastException if key is not comparable to map elements |
| * @throws NullPointerException if key is null and the comparator is not |
| * tolerant of nulls |
| */ |
| public boolean containsKey(Object key) |
| { |
| return getNode((K) key) != nil; |
| } |
| |
| /** |
| * Returns true if the map contains at least one mapping to the given value. |
| * This requires linear time. |
| * |
| * @param value the value to look for |
| * @return true if the value appears in a mapping |
| */ |
| public boolean containsValue(Object value) |
| { |
| Node node = firstNode(); |
| while (node != nil) |
| { |
| if (equals(value, node.value)) |
| return true; |
| node = successor(node); |
| } |
| return false; |
| } |
| |
| /** |
| * Returns a "set view" of this TreeMap's entries. The set is backed by |
| * the TreeMap, so changes in one show up in the other. The set supports |
| * element removal, but not element addition.<p> |
| * |
| * Note that the iterators for all three views, from keySet(), entrySet(), |
| * and values(), traverse the TreeMap in sorted sequence. |
| * |
| * @return a set view of the entries |
| * @see #keySet() |
| * @see #values() |
| * @see Map.Entry |
| */ |
| public Set<Map.Entry<K,V>> entrySet() |
| { |
| if (entries == null) |
| // Create an AbstractSet with custom implementations of those methods |
| // that can be overriden easily and efficiently. |
| entries = new NavigableEntrySet(); |
| return entries; |
| } |
| |
| /** |
| * Returns the first (lowest) key in the map. |
| * |
| * @return the first key |
| * @throws NoSuchElementException if the map is empty |
| */ |
| public K firstKey() |
| { |
| if (root == nil) |
| throw new NoSuchElementException(); |
| return firstNode().key; |
| } |
| |
| /** |
| * Return the value in this TreeMap associated with the supplied key, |
| * or <code>null</code> if the key maps to nothing. NOTE: Since the value |
| * could also be null, you must use containsKey to see if this key |
| * actually maps to something. |
| * |
| * @param key the key for which to fetch an associated value |
| * @return what the key maps to, if present |
| * @throws ClassCastException if key is not comparable to elements in the map |
| * @throws NullPointerException if key is null but the comparator does not |
| * tolerate nulls |
| * @see #put(Object, Object) |
| * @see #containsKey(Object) |
| */ |
| public V get(Object key) |
| { |
| // Exploit fact that nil.value == null. |
| return getNode((K) key).value; |
| } |
| |
| /** |
| * Returns a view of this Map including all entries with keys less than |
| * <code>toKey</code>. The returned map is backed by the original, so changes |
| * in one appear in the other. The submap will throw an |
| * {@link IllegalArgumentException} for any attempt to access or add an |
| * element beyond the specified cutoff. The returned map does not include |
| * the endpoint; if you want inclusion, pass the successor element |
| * or call <code>headMap(toKey, true)</code>. This is equivalent to |
| * calling <code>headMap(toKey, false)</code>. |
| * |
| * @param toKey the (exclusive) cutoff point |
| * @return a view of the map less than the cutoff |
| * @throws ClassCastException if <code>toKey</code> is not compatible with |
| * the comparator (or is not Comparable, for natural ordering) |
| * @throws NullPointerException if toKey is null, but the comparator does not |
| * tolerate null elements |
| */ |
| public SortedMap<K, V> headMap(K toKey) |
| { |
| return headMap(toKey, false); |
| } |
| |
| /** |
| * Returns a view of this Map including all entries with keys less than |
| * (or equal to, if <code>inclusive</code> is true) <code>toKey</code>. |
| * The returned map is backed by the original, so changes in one appear |
| * in the other. The submap will throw an {@link IllegalArgumentException} |
| * for any attempt to access or add an element beyond the specified cutoff. |
| * |
| * @param toKey the cutoff point |
| * @param inclusive true if the cutoff point should be included. |
| * @return a view of the map less than (or equal to, if <code>inclusive</code> |
| * is true) the cutoff. |
| * @throws ClassCastException if <code>toKey</code> is not compatible with |
| * the comparator (or is not Comparable, for natural ordering) |
| * @throws NullPointerException if toKey is null, but the comparator does not |
| * tolerate null elements |
| */ |
| public NavigableMap<K, V> headMap(K toKey, boolean inclusive) |
| { |
| return new SubMap((K)(Object)nil, inclusive |
| ? successor(getNode(toKey)).key : toKey); |
| } |
| |
| /** |
| * Returns a "set view" of this TreeMap's keys. The set is backed by the |
| * TreeMap, so changes in one show up in the other. The set supports |
| * element removal, but not element addition. |
| * |
| * @return a set view of the keys |
| * @see #values() |
| * @see #entrySet() |
| */ |
| public Set<K> keySet() |
| { |
| if (keys == null) |
| // Create an AbstractSet with custom implementations of those methods |
| // that can be overriden easily and efficiently. |
| keys = new KeySet(); |
| return keys; |
| } |
| |
| /** |
| * Returns the last (highest) key in the map. |
| * |
| * @return the last key |
| * @throws NoSuchElementException if the map is empty |
| */ |
| public K lastKey() |
| { |
| if (root == nil) |
| throw new NoSuchElementException("empty"); |
| return lastNode().key; |
| } |
| |
| /** |
| * Puts the supplied value into the Map, mapped by the supplied key. |
| * The value may be retrieved by any object which <code>equals()</code> |
| * this key. NOTE: Since the prior value could also be null, you must |
| * first use containsKey if you want to see if you are replacing the |
| * key's mapping. |
| * |
| * @param key the key used to locate the value |
| * @param value the value to be stored in the Map |
| * @return the prior mapping of the key, or null if there was none |
| * @throws ClassCastException if key is not comparable to current map keys |
| * @throws NullPointerException if key is null, but the comparator does |
| * not tolerate nulls |
| * @see #get(Object) |
| * @see Object#equals(Object) |
| */ |
| public V put(K key, V value) |
| { |
| Node<K,V> current = root; |
| Node<K,V> parent = nil; |
| int comparison = 0; |
| |
| // Find new node's parent. |
| while (current != nil) |
| { |
| parent = current; |
| comparison = compare(key, current.key); |
| if (comparison > 0) |
| current = current.right; |
| else if (comparison < 0) |
| current = current.left; |
| else // Key already in tree. |
| return current.setValue(value); |
| } |
| |
| // Set up new node. |
| Node n = new Node(key, value, RED); |
| n.parent = parent; |
| |
| // Insert node in tree. |
| modCount++; |
| size++; |
| if (parent == nil) |
| { |
| // Special case inserting into an empty tree. |
| root = n; |
| return null; |
| } |
| if (comparison > 0) |
| parent.right = n; |
| else |
| parent.left = n; |
| |
| // Rebalance after insert. |
| insertFixup(n); |
| return null; |
| } |
| |
| /** |
| * Copies all elements of the given map into this TreeMap. If this map |
| * already has a mapping for a key, the new mapping replaces the current |
| * one. |
| * |
| * @param m the map to be added |
| * @throws ClassCastException if a key in m is not comparable with keys |
| * in the map |
| * @throws NullPointerException if a key in m is null, and the comparator |
| * does not tolerate nulls |
| */ |
| public void putAll(Map<? extends K, ? extends V> m) |
| { |
| Iterator itr = m.entrySet().iterator(); |
| int pos = m.size(); |
| while (--pos >= 0) |
| { |
| Map.Entry<K,V> e = (Map.Entry<K,V>) itr.next(); |
| put(e.getKey(), e.getValue()); |
| } |
| } |
| |
| /** |
| * Removes from the TreeMap and returns the value which is mapped by the |
| * supplied key. If the key maps to nothing, then the TreeMap remains |
| * unchanged, and <code>null</code> is returned. NOTE: Since the value |
| * could also be null, you must use containsKey to see if you are |
| * actually removing a mapping. |
| * |
| * @param key the key used to locate the value to remove |
| * @return whatever the key mapped to, if present |
| * @throws ClassCastException if key is not comparable to current map keys |
| * @throws NullPointerException if key is null, but the comparator does |
| * not tolerate nulls |
| */ |
| public V remove(Object key) |
| { |
| Node<K, V> n = getNode((K)key); |
| if (n == nil) |
| return null; |
| // Note: removeNode can alter the contents of n, so save value now. |
| V result = n.value; |
| removeNode(n); |
| return result; |
| } |
| |
| /** |
| * Returns the number of key-value mappings currently in this Map. |
| * |
| * @return the size |
| */ |
| public int size() |
| { |
| return size; |
| } |
| |
| /** |
| * Returns a view of this Map including all entries with keys greater or |
| * equal to <code>fromKey</code> and less than <code>toKey</code> (a |
| * half-open interval). The returned map is backed by the original, so |
| * changes in one appear in the other. The submap will throw an |
| * {@link IllegalArgumentException} for any attempt to access or add an |
| * element beyond the specified cutoffs. The returned map includes the low |
| * endpoint but not the high; if you want to reverse this behavior on |
| * either end, pass in the successor element or call |
| * {@link #subMap(K,boolean,K,boolean)}. This call is equivalent to |
| * <code>subMap(fromKey, true, toKey, false)</code>. |
| * |
| * @param fromKey the (inclusive) low cutoff point |
| * @param toKey the (exclusive) high cutoff point |
| * @return a view of the map between the cutoffs |
| * @throws ClassCastException if either cutoff is not compatible with |
| * the comparator (or is not Comparable, for natural ordering) |
| * @throws NullPointerException if fromKey or toKey is null, but the |
| * comparator does not tolerate null elements |
| * @throws IllegalArgumentException if fromKey is greater than toKey |
| */ |
| public SortedMap<K, V> subMap(K fromKey, K toKey) |
| { |
| return subMap(fromKey, true, toKey, false); |
| } |
| |
| /** |
| * Returns a view of this Map including all entries with keys greater (or |
| * equal to, if <code>fromInclusive</code> is true) <code>fromKey</code> and |
| * less than (or equal to, if <code>toInclusive</code> is true) |
| * <code>toKey</code>. The returned map is backed by the original, so |
| * changes in one appear in the other. The submap will throw an |
| * {@link IllegalArgumentException} for any attempt to access or add an |
| * element beyond the specified cutoffs. |
| * |
| * @param fromKey the low cutoff point |
| * @param fromInclusive true if the low cutoff point should be included. |
| * @param toKey the high cutoff point |
| * @param toInclusive true if the high cutoff point should be included. |
| * @return a view of the map for the specified range. |
| * @throws ClassCastException if either cutoff is not compatible with |
| * the comparator (or is not Comparable, for natural ordering) |
| * @throws NullPointerException if fromKey or toKey is null, but the |
| * comparator does not tolerate null elements |
| * @throws IllegalArgumentException if fromKey is greater than toKey |
| */ |
| public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, |
| K toKey, boolean toInclusive) |
| { |
| return new SubMap(fromInclusive ? fromKey : successor(getNode(fromKey)).key, |
| toInclusive ? successor(getNode(toKey)).key : toKey); |
| } |
| |
| /** |
| * Returns a view of this Map including all entries with keys greater or |
| * equal to <code>fromKey</code>. The returned map is backed by the |
| * original, so changes in one appear in the other. The submap will throw an |
| * {@link IllegalArgumentException} for any attempt to access or add an |
| * element beyond the specified cutoff. The returned map includes the |
| * endpoint; if you want to exclude it, pass in the successor element. |
| * This is equivalent to calling <code>tailMap(fromKey, true)</code>. |
| * |
| * @param fromKey the (inclusive) low cutoff point |
| * @return a view of the map above the cutoff |
| * @throws ClassCastException if <code>fromKey</code> is not compatible with |
| * the comparator (or is not Comparable, for natural ordering) |
| * @throws NullPointerException if fromKey is null, but the comparator |
| * does not tolerate null elements |
| */ |
| public SortedMap<K, V> tailMap(K fromKey) |
| { |
| return tailMap(fromKey, true); |
| } |
| |
| /** |
| * Returns a view of this Map including all entries with keys greater or |
| * equal to <code>fromKey</code>. The returned map is backed by the |
| * original, so changes in one appear in the other. The submap will throw an |
| * {@link IllegalArgumentException} for any attempt to access or add an |
| * element beyond the specified cutoff. The returned map includes the |
| * endpoint; if you want to exclude it, pass in the successor element. |
| * |
| * @param fromKey the low cutoff point |
| * @param inclusive true if the cutoff point should be included. |
| * @return a view of the map above the cutoff |
| * @throws ClassCastException if <code>fromKey</code> is not compatible with |
| * the comparator (or is not Comparable, for natural ordering) |
| * @throws NullPointerException if fromKey is null, but the comparator |
| * does not tolerate null elements |
| */ |
| public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) |
| { |
| return new SubMap(inclusive ? fromKey : successor(getNode(fromKey)).key, |
| (K)(Object)nil); |
| } |
| |
| /** |
| * Returns a "collection view" (or "bag view") of this TreeMap's values. |
| * The collection is backed by the TreeMap, so changes in one show up |
| * in the other. The collection supports element removal, but not element |
| * addition. |
| * |
| * @return a bag view of the values |
| * @see #keySet() |
| * @see #entrySet() |
| */ |
| public Collection<V> values() |
| { |
| if (values == null) |
| // We don't bother overriding many of the optional methods, as doing so |
| // wouldn't provide any significant performance advantage. |
| values = new AbstractCollection<V>() |
| { |
| public int size() |
| { |
| return size; |
| } |
| |
| public Iterator<V> iterator() |
| { |
| return new TreeIterator(VALUES); |
| } |
| |
| public void clear() |
| { |
| TreeMap.this.clear(); |
| } |
| }; |
| return values; |
| } |
| |
| /** |
| * Compares two elements by the set comparator, or by natural ordering. |
| * Package visible for use by nested classes. |
| * |
| * @param o1 the first object |
| * @param o2 the second object |
| * @throws ClassCastException if o1 and o2 are not mutually comparable, |
| * or are not Comparable with natural ordering |
| * @throws NullPointerException if o1 or o2 is null with natural ordering |
| */ |
| final int compare(K o1, K o2) |
| { |
| return (comparator == null |
| ? ((Comparable) o1).compareTo(o2) |
| : comparator.compare(o1, o2)); |
| } |
| |
| /** |
| * Maintain red-black balance after deleting a node. |
| * |
| * @param node the child of the node just deleted, possibly nil |
| * @param parent the parent of the node just deleted, never nil |
| */ |
| private void deleteFixup(Node<K,V> node, Node<K,V> parent) |
| { |
| // if (parent == nil) |
| // throw new InternalError(); |
| // If a black node has been removed, we need to rebalance to avoid |
| // violating the "same number of black nodes on any path" rule. If |
| // node is red, we can simply recolor it black and all is well. |
| while (node != root && node.color == BLACK) |
| { |
| if (node == parent.left) |
| { |
| // Rebalance left side. |
| Node<K,V> sibling = parent.right; |
| // if (sibling == nil) |
| // throw new InternalError(); |
| if (sibling.color == RED) |
| { |
| // Case 1: Sibling is red. |
| // Recolor sibling and parent, and rotate parent left. |
| sibling.color = BLACK; |
| parent.color = RED; |
| rotateLeft(parent); |
| sibling = parent.right; |
| } |
| |
| if (sibling.left.color == BLACK && sibling.right.color == BLACK) |
| { |
| // Case 2: Sibling has no red children. |
| // Recolor sibling, and move to parent. |
| sibling.color = RED; |
| node = parent; |
| parent = parent.parent; |
| } |
| else |
| { |
| if (sibling.right.color == BLACK) |
| { |
| // Case 3: Sibling has red left child. |
| // Recolor sibling and left child, rotate sibling right. |
| sibling.left.color = BLACK; |
| sibling.color = RED; |
| rotateRight(sibling); |
| sibling = parent.right; |
| } |
| // Case 4: Sibling has red right child. Recolor sibling, |
| // right child, and parent, and rotate parent left. |
| sibling.color = parent.color; |
| parent.color = BLACK; |
| sibling.right.color = BLACK; |
| rotateLeft(parent); |
| node = root; // Finished. |
| } |
| } |
| else |
| { |
| // Symmetric "mirror" of left-side case. |
| Node<K,V> sibling = parent.left; |
| // if (sibling == nil) |
| // throw new InternalError(); |
| if (sibling.color == RED) |
| { |
| // Case 1: Sibling is red. |
| // Recolor sibling and parent, and rotate parent right. |
| sibling.color = BLACK; |
| parent.color = RED; |
| rotateRight(parent); |
| sibling = parent.left; |
| } |
| |
| if (sibling.right.color == BLACK && sibling.left.color == BLACK) |
| { |
| // Case 2: Sibling has no red children. |
| // Recolor sibling, and move to parent. |
| sibling.color = RED; |
| node = parent; |
| parent = parent.parent; |
| } |
| else |
| { |
| if (sibling.left.color == BLACK) |
| { |
| // Case 3: Sibling has red right child. |
| // Recolor sibling and right child, rotate sibling left. |
| sibling.right.color = BLACK; |
| sibling.color = RED; |
| rotateLeft(sibling); |
| sibling = parent.left; |
| } |
| // Case 4: Sibling has red left child. Recolor sibling, |
| // left child, and parent, and rotate parent right. |
| sibling.color = parent.color; |
| parent.color = BLACK; |
| sibling.left.color = BLACK; |
| rotateRight(parent); |
| node = root; // Finished. |
| } |
| } |
| } |
| node.color = BLACK; |
| } |
| |
| /** |
| * Construct a perfectly balanced tree consisting of n "blank" nodes. This |
| * permits a tree to be generated from pre-sorted input in linear time. |
| * |
| * @param count the number of blank nodes, non-negative |
| */ |
| private void fabricateTree(final int count) |
| { |
| if (count == 0) |
| { |
| root = nil; |
| size = 0; |
| return; |
| } |
| |
| // We color every row of nodes black, except for the overflow nodes. |
| // I believe that this is the optimal arrangement. We construct the tree |
| // in place by temporarily linking each node to the next node in the row, |
| // then updating those links to the children when working on the next row. |
| |
| // Make the root node. |
| root = new Node(null, null, BLACK); |
| size = count; |
| Node row = root; |
| int rowsize; |
| |
| // Fill each row that is completely full of nodes. |
| for (rowsize = 2; rowsize + rowsize <= count; rowsize <<= 1) |
| { |
| Node parent = row; |
| Node last = null; |
| for (int i = 0; i < rowsize; i += 2) |
| { |
| Node left = new Node(null, null, BLACK); |
| Node right = new Node(null, null, BLACK); |
| left.parent = parent; |
| left.right = right; |
| right.parent = parent; |
| parent.left = left; |
| Node next = parent.right; |
| parent.right = right; |
| parent = next; |
| if (last != null) |
| last.right = left; |
| last = right; |
| } |
| row = row.left; |
| } |
| |
| // Now do the partial final row in red. |
| int overflow = count - rowsize; |
| Node parent = row; |
| int i; |
| for (i = 0; i < overflow; i += 2) |
| { |
| Node left = new Node(null, null, RED); |
| Node right = new Node(null, null, RED); |
| left.parent = parent; |
| right.parent = parent; |
| parent.left = left; |
| Node next = parent.right; |
| parent.right = right; |
| parent = next; |
| } |
| // Add a lone left node if necessary. |
| if (i - overflow == 0) |
| { |
| Node left = new Node(null, null, RED); |
| left.parent = parent; |
| parent.left = left; |
| parent = parent.right; |
| left.parent.right = nil; |
| } |
| // Unlink the remaining nodes of the previous row. |
| while (parent != nil) |
| { |
| Node next = parent.right; |
| parent.right = nil; |
| parent = next; |
| } |
| } |
| |
| /** |
| * Returns the first sorted node in the map, or nil if empty. Package |
| * visible for use by nested classes. |
| * |
| * @return the first node |
| */ |
| final Node<K, V> firstNode() |
| { |
| // Exploit fact that nil.left == nil. |
| Node node = root; |
| while (node.left != nil) |
| node = node.left; |
| return node; |
| } |
| |
| /** |
| * Return the TreeMap.Node associated with key, or the nil node if no such |
| * node exists in the tree. Package visible for use by nested classes. |
| * |
| * @param key the key to search for |
| * @return the node where the key is found, or nil |
| */ |
| final Node<K, V> getNode(K key) |
| { |
| Node<K,V> current = root; |
| while (current != nil) |
| { |
| int comparison = compare(key, current.key); |
| if (comparison > 0) |
| current = current.right; |
| else if (comparison < 0) |
| current = current.left; |
| else |
| return current; |
| } |
| return current; |
| } |
| |
| /** |
| * Find the "highest" node which is < key. If key is nil, return last |
| * node. Package visible for use by nested classes. |
| * |
| * @param key the upper bound, exclusive |
| * @return the previous node |
| */ |
| final Node<K,V> highestLessThan(K key) |
| { |
| return highestLessThan(key, false); |
| } |
| |
| /** |
| * Find the "highest" node which is < (or equal to, |
| * if <code>equal</code> is true) key. If key is nil, |
| * return last node. Package visible for use by nested |
| * classes. |
| * |
| * @param key the upper bound, exclusive |
| * @param equal true if the key should be returned if found. |
| * @return the previous node |
| */ |
| final Node<K,V> highestLessThan(K key, boolean equal) |
| { |
| if (key == nil) |
| return lastNode(); |
| |
| Node<K,V> last = nil; |
| Node<K,V> current = root; |
| int comparison = 0; |
| |
| while (current != nil) |
| { |
| last = current; |
| comparison = compare(key, current.key); |
| if (comparison > 0) |
| current = current.right; |
| else if (comparison < 0) |
| current = current.left; |
| else // Exact match. |
| return (equal ? last : predecessor(last)); |
| } |
| return comparison < 0 ? predecessor(last) : last; |
| } |
| |
| /** |
| * Maintain red-black balance after inserting a new node. |
| * |
| * @param n the newly inserted node |
| */ |
| private void insertFixup(Node<K,V> n) |
| { |
| // Only need to rebalance when parent is a RED node, and while at least |
| // 2 levels deep into the tree (ie: node has a grandparent). Remember |
| // that nil.color == BLACK. |
| while (n.parent.color == RED && n.parent.parent != nil) |
| { |
| if (n.parent == n.parent.parent.left) |
| { |
| Node uncle = n.parent.parent.right; |
| // Uncle may be nil, in which case it is BLACK. |
| if (uncle.color == RED) |
| { |
| // Case 1. Uncle is RED: Change colors of parent, uncle, |
| // and grandparent, and move n to grandparent. |
| n.parent.color = BLACK; |
| uncle.color = BLACK; |
| uncle.parent.color = RED; |
| n = uncle.parent; |
| } |
| else |
| { |
| if (n == n.parent.right) |
| { |
| // Case 2. Uncle is BLACK and x is right child. |
| // Move n to parent, and rotate n left. |
| n = n.parent; |
| rotateLeft(n); |
| } |
| // Case 3. Uncle is BLACK and x is left child. |
| // Recolor parent, grandparent, and rotate grandparent right. |
| n.parent.color = BLACK; |
| n.parent.parent.color = RED; |
| rotateRight(n.parent.parent); |
| } |
| } |
| else |
| { |
| // Mirror image of above code. |
| Node uncle = n.parent.parent.left; |
| // Uncle may be nil, in which case it is BLACK. |
| if (uncle.color == RED) |
| { |
| // Case 1. Uncle is RED: Change colors of parent, uncle, |
| // and grandparent, and move n to grandparent. |
| n.parent.color = BLACK; |
| uncle.color = BLACK; |
| uncle.parent.color = RED; |
| n = uncle.parent; |
| } |
| else |
| { |
| if (n == n.parent.left) |
| { |
| // Case 2. Uncle is BLACK and x is left child. |
| // Move n to parent, and rotate n right. |
| n = n.parent; |
| rotateRight(n); |
| } |
| // Case 3. Uncle is BLACK and x is right child. |
| // Recolor parent, grandparent, and rotate grandparent left. |
| n.parent.color = BLACK; |
| n.parent.parent.color = RED; |
| rotateLeft(n.parent.parent); |
| } |
| } |
| } |
| root.color = BLACK; |
| } |
| |
| /** |
| * Returns the last sorted node in the map, or nil if empty. |
| * |
| * @return the last node |
| */ |
| private Node<K,V> lastNode() |
| { |
| // Exploit fact that nil.right == nil. |
| Node node = root; |
| while (node.right != nil) |
| node = node.right; |
| return node; |
| } |
| |
| /** |
| * Find the "lowest" node which is >= key. If key is nil, return either |
| * nil or the first node, depending on the parameter first. Package visible |
| * for use by nested classes. |
| * |
| * @param key the lower bound, inclusive |
| * @param first true to return the first element instead of nil for nil key |
| * @return the next node |
| */ |
| final Node<K,V> lowestGreaterThan(K key, boolean first) |
| { |
| return lowestGreaterThan(key, first, true); |
| } |
| |
| /** |
| * Find the "lowest" node which is > (or equal to, if <code>equal</code> |
| * is true) key. If key is nil, return either nil or the first node, depending |
| * on the parameter first. Package visible for use by nested classes. |
| * |
| * @param key the lower bound, inclusive |
| * @param first true to return the first element instead of nil for nil key |
| * @param equal true if the key should be returned if found. |
| * @return the next node |
| */ |
| final Node<K,V> lowestGreaterThan(K key, boolean first, boolean equal) |
| { |
| if (key == nil) |
| return first ? firstNode() : nil; |
| |
| Node<K,V> last = nil; |
| Node<K,V> current = root; |
| int comparison = 0; |
| |
| while (current != nil) |
| { |
| last = current; |
| comparison = compare(key, current.key); |
| if (comparison > 0) |
| current = current.right; |
| else if (comparison < 0) |
| current = current.left; |
| else |
| return (equal ? current : successor(current)); |
| } |
| return comparison > 0 ? successor(last) : last; |
| } |
| |
| /** |
| * Return the node preceding the given one, or nil if there isn't one. |
| * |
| * @param node the current node, not nil |
| * @return the prior node in sorted order |
| */ |
| private Node<K,V> predecessor(Node<K,V> node) |
| { |
| if (node.left != nil) |
| { |
| node = node.left; |
| while (node.right != nil) |
| node = node.right; |
| return node; |
| } |
| |
| Node parent = node.parent; |
| // Exploit fact that nil.left == nil and node is non-nil. |
| while (node == parent.left) |
| { |
| node = parent; |
| parent = node.parent; |
| } |
| return parent; |
| } |
| |
| /** |
| * Construct a tree from sorted keys in linear time. Package visible for |
| * use by TreeSet. |
| * |
| * @param s the stream to read from |
| * @param count the number of keys to read |
| * @param readValues true to read values, false to insert "" as the value |
| * @throws ClassNotFoundException if the underlying stream fails |
| * @throws IOException if the underlying stream fails |
| * @see #readObject(ObjectInputStream) |
| * @see TreeSet#readObject(ObjectInputStream) |
| */ |
| final void putFromObjStream(ObjectInputStream s, int count, |
| boolean readValues) |
| throws IOException, ClassNotFoundException |
| { |
| fabricateTree(count); |
| Node node = firstNode(); |
| |
| while (--count >= 0) |
| { |
| node.key = s.readObject(); |
| node.value = readValues ? s.readObject() : ""; |
| node = successor(node); |
| } |
| } |
| |
| /** |
| * Construct a tree from sorted keys in linear time, with values of "". |
| * Package visible for use by TreeSet, which uses a value type of String. |
| * |
| * @param keys the iterator over the sorted keys |
| * @param count the number of nodes to insert |
| * @see TreeSet#TreeSet(SortedSet) |
| */ |
| final void putKeysLinear(Iterator<K> keys, int count) |
| { |
| fabricateTree(count); |
| Node<K,V> node = firstNode(); |
| |
| while (--count >= 0) |
| { |
| node.key = keys.next(); |
| node.value = (V) ""; |
| node = successor(node); |
| } |
| } |
| |
| /** |
| * Deserializes this object from the given stream. |
| * |
| * @param s the stream to read from |
| * @throws ClassNotFoundException if the underlying stream fails |
| * @throws IOException if the underlying stream fails |
| * @serialData the <i>size</i> (int), followed by key (Object) and value |
| * (Object) pairs in sorted order |
| */ |
| private void readObject(ObjectInputStream s) |
| throws IOException, ClassNotFoundException |
| { |
| s.defaultReadObject(); |
| int size = s.readInt(); |
| putFromObjStream(s, size, true); |
| } |
| |
| /** |
| * Remove node from tree. This will increment modCount and decrement size. |
| * Node must exist in the tree. Package visible for use by nested classes. |
| * |
| * @param node the node to remove |
| */ |
| final void removeNode(Node<K,V> node) |
| { |
| Node<K,V> splice; |
| Node<K,V> child; |
| |
| modCount++; |
| size--; |
| |
| // Find splice, the node at the position to actually remove from the tree. |
| if (node.left == nil) |
| { |
| // Node to be deleted has 0 or 1 children. |
| splice = node; |
| child = node.right; |
| } |
| else if (node.right == nil) |
| { |
| // Node to be deleted has 1 child. |
| splice = node; |
| child = node.left; |
| } |
| else |
| { |
| // Node has 2 children. Splice is node's predecessor, and we swap |
| // its contents into node. |
| splice = node.left; |
| while (splice.right != nil) |
| splice = splice.right; |
| child = splice.left; |
| node.key = splice.key; |
| node.value = splice.value; |
| } |
| |
| // Unlink splice from the tree. |
| Node parent = splice.parent; |
| if (child != nil) |
| child.parent = parent; |
| if (parent == nil) |
| { |
| // Special case for 0 or 1 node remaining. |
| root = child; |
| return; |
| } |
| if (splice == parent.left) |
| parent.left = child; |
| else |
| parent.right = child; |
| |
| if (splice.color == BLACK) |
| deleteFixup(child, parent); |
| } |
| |
| /** |
| * Rotate node n to the left. |
| * |
| * @param node the node to rotate |
| */ |
| private void rotateLeft(Node<K,V> node) |
| { |
| Node child = node.right; |
| // if (node == nil || child == nil) |
| // throw new InternalError(); |
| |
| // Establish node.right link. |
| node.right = child.left; |
| if (child.left != nil) |
| child.left.parent = node; |
| |
| // Establish child->parent link. |
| child.parent = node.parent; |
| if (node.parent != nil) |
| { |
| if (node == node.parent.left) |
| node.parent.left = child; |
| else |
| node.parent.right = child; |
| } |
| else |
| root = child; |
| |
| // Link n and child. |
| child.left = node; |
| node.parent = child; |
| } |
| |
| /** |
| * Rotate node n to the right. |
| * |
| * @param node the node to rotate |
| */ |
| private void rotateRight(Node<K,V> node) |
| { |
| Node child = node.left; |
| // if (node == nil || child == nil) |
| // throw new InternalError(); |
| |
| // Establish node.left link. |
| node.left = child.right; |
| if (child.right != nil) |
| child.right.parent = node; |
| |
| // Establish child->parent link. |
| child.parent = node.parent; |
| if (node.parent != nil) |
| { |
| if (node == node.parent.right) |
| node.parent.right = child; |
| else |
| node.parent.left = child; |
| } |
| else |
| root = child; |
| |
| // Link n and child. |
| child.right = node; |
| node.parent = child; |
| } |
| |
| /** |
| * Return the node following the given one, or nil if there isn't one. |
| * Package visible for use by nested classes. |
| * |
| * @param node the current node, not nil |
| * @return the next node in sorted order |
| */ |
| final Node<K,V> successor(Node<K,V> node) |
| { |
| if (node.right != nil) |
| { |
| node = node.right; |
| while (node.left != nil) |
| node = node.left; |
| return node; |
| } |
| |
| Node<K,V> parent = node.parent; |
| // Exploit fact that nil.right == nil and node is non-nil. |
| while (node == parent.right) |
| { |
| node = parent; |
| parent = parent.parent; |
| } |
| return parent; |
| } |
| |
| /** |
| * Serializes this object to the given stream. |
| * |
| * @param s the stream to write to |
| * @throws IOException if the underlying stream fails |
| * @serialData the <i>size</i> (int), followed by key (Object) and value |
| * (Object) pairs in sorted order |
| */ |
| private void writeObject(ObjectOutputStream s) throws IOException |
| { |
| s.defaultWriteObject(); |
| |
| Node node = firstNode(); |
| s.writeInt(size); |
| while (node != nil) |
| { |
| s.writeObject(node.key); |
| s.writeObject(node.value); |
| node = successor(node); |
| } |
| } |
| |
| /** |
| * Iterate over TreeMap's entries. This implementation is parameterized |
| * to give a sequential view of keys, values, or entries. |
| * |
| * @author Eric Blake (ebb9@email.byu.edu) |
| */ |
| private final class TreeIterator implements Iterator |
| { |
| /** |
| * The type of this Iterator: {@link #KEYS}, {@link #VALUES}, |
| * or {@link #ENTRIES}. |
| */ |
| private final int type; |
| /** The number of modifications to the backing Map that we know about. */ |
| private int knownMod = modCount; |
| /** The last Entry returned by a next() call. */ |
| private Node last; |
| /** The next entry that should be returned by next(). */ |
| private Node next; |
| /** |
| * The last node visible to this iterator. This is used when iterating |
| * on a SubMap. |
| */ |
| private final Node max; |
| |
| /** |
| * Construct a new TreeIterator with the supplied type. |
| * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} |
| */ |
| TreeIterator(int type) |
| { |
| this(type, firstNode(), nil); |
| } |
| |
| /** |
| * Construct a new TreeIterator with the supplied type. Iteration will |
| * be from "first" (inclusive) to "max" (exclusive). |
| * |
| * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} |
| * @param first where to start iteration, nil for empty iterator |
| * @param max the cutoff for iteration, nil for all remaining nodes |
| */ |
| TreeIterator(int type, Node first, Node max) |
| { |
| this.type = type; |
| this.next = first; |
| this.max = max; |
| } |
| |
| /** |
| * Returns true if the Iterator has more elements. |
| * @return true if there are more elements |
| */ |
| public boolean hasNext() |
| { |
| return next != max; |
| } |
| |
| /** |
| * Returns the next element in the Iterator's sequential view. |
| * @return the next element |
| * @throws ConcurrentModificationException if the TreeMap was modified |
| * @throws NoSuchElementException if there is none |
| */ |
| public Object next() |
| { |
| if (knownMod != modCount) |
| throw new ConcurrentModificationException(); |
| if (next == max) |
| throw new NoSuchElementException(); |
| last = next; |
| next = successor(last); |
| |
| if (type == VALUES) |
| return last.value; |
| else if (type == KEYS) |
| return last.key; |
| return last; |
| } |
| |
| /** |
| * Removes from the backing TreeMap the last element which was fetched |
| * with the <code>next()</code> method. |
| * @throws ConcurrentModificationException if the TreeMap was modified |
| * @throws IllegalStateException if called when there is no last element |
| */ |
| public void remove() |
| { |
| if (last == null) |
| throw new IllegalStateException(); |
| if (knownMod != modCount) |
| throw new ConcurrentModificationException(); |
| |
| removeNode(last); |
| last = null; |
| knownMod++; |
| } |
| } // class TreeIterator |
| |
| /** |
| * Implementation of {@link #subMap(Object, Object)} and other map |
| * ranges. This class provides a view of a portion of the original backing |
| * map, and throws {@link IllegalArgumentException} for attempts to |
| * access beyond that range. |
| * |
| * @author Eric Blake (ebb9@email.byu.edu) |
| */ |
| private final class SubMap |
| extends AbstractMap<K,V> |
| implements NavigableMap<K,V> |
| { |
| /** |
| * The lower range of this view, inclusive, or nil for unbounded. |
| * Package visible for use by nested classes. |
| */ |
| final K minKey; |
| |
| /** |
| * The upper range of this view, exclusive, or nil for unbounded. |
| * Package visible for use by nested classes. |
| */ |
| final K maxKey; |
| |
| /** |
| * The cache for {@link #entrySet()}. |
| */ |
| private Set<Map.Entry<K,V>> entries; |
| |
| /** |
| * The cache for {@link #descendingMap()}. |
| */ |
| private NavigableMap<K,V> descendingMap; |
| |
| /** |
| * The cache for {@link #navigableKeySet()}. |
| */ |
| private NavigableSet<K> nKeys; |
| |
| /** |
| * Create a SubMap representing the elements between minKey (inclusive) |
| * and maxKey (exclusive). If minKey is nil, SubMap has no lower bound |
| * (headMap). If maxKey is nil, the SubMap has no upper bound (tailMap). |
| * |
| * @param minKey the lower bound |
| * @param maxKey the upper bound |
| * @throws IllegalArgumentException if minKey > maxKey |
| */ |
| SubMap(K minKey, K maxKey) |
| { |
| if (minKey != nil && maxKey != nil && compare(minKey, maxKey) > 0) |
| throw new IllegalArgumentException("fromKey > toKey"); |
| this.minKey = minKey; |
| this.maxKey = maxKey; |
| } |
| |
| /** |
| * Check if "key" is in within the range bounds for this SubMap. The |
| * lower ("from") SubMap range is inclusive, and the upper ("to") bound |
| * is exclusive. Package visible for use by nested classes. |
| * |
| * @param key the key to check |
| * @return true if the key is in range |
| */ |
| boolean keyInRange(K key) |
| { |
| return ((minKey == nil || compare(key, minKey) >= 0) |
| && (maxKey == nil || compare(key, maxKey) < 0)); |
| } |
| |
| public Entry<K,V> ceilingEntry(K key) |
| { |
| Entry<K,V> n = TreeMap.this.ceilingEntry(key); |
| if (n != null && keyInRange(n.getKey())) |
| return n; |
| return null; |
| } |
| |
| public K ceilingKey(K key) |
| { |
| K found = TreeMap.this.ceilingKey(key); |
| if (keyInRange(found)) |
| return found; |
| else |
| return null; |
| } |
| |
| public NavigableSet<K> descendingKeySet() |
| { |
| return descendingMap().navigableKeySet(); |
| } |
| |
| public NavigableMap<K,V> descendingMap() |
| { |
| if (descendingMap == null) |
| descendingMap = new DescendingMap(this); |
| return descendingMap; |
| } |
| |
| public void clear() |
| { |
| Node next = lowestGreaterThan(minKey, true); |
| Node max = lowestGreaterThan(maxKey, false); |
| while (next != max) |
| { |
| Node current = next; |
| next = successor(current); |
| removeNode(current); |
| } |
| } |
| |
| public Comparator<? super K> comparator() |
| { |
| return comparator; |
| } |
| |
| public boolean containsKey(Object key) |
| { |
| return keyInRange((K) key) && TreeMap.this.containsKey(key); |
| } |
| |
| public boolean containsValue(Object value) |
| { |
| Node node = lowestGreaterThan(minKey, true); |
| Node max = lowestGreaterThan(maxKey, false); |
| while (node != max) |
| { |
| if (equals(value, node.getValue())) |
| return true; |
| node = successor(node); |
| } |
| return false; |
| } |
| |
| public Set<Map.Entry<K,V>> entrySet() |
| { |
| if (entries == null) |
| // Create an AbstractSet with custom implementations of those methods |
| // that can be overriden easily and efficiently. |
| entries = new SubMap.NavigableEntrySet(); |
| return entries; |
| } |
| |
| public Entry<K,V> firstEntry() |
| { |
| Node<K,V> node = lowestGreaterThan(minKey, true); |
| if (node == nil || ! keyInRange(node.key)) |
| return null; |
| return node; |
| } |
| |
| public K firstKey() |
| { |
| Entry<K,V> e = firstEntry(); |
| if (e == null) |
| throw new NoSuchElementException(); |
| return e.getKey(); |
| } |
| |
| public Entry<K,V> floorEntry(K key) |
| { |
| Entry<K,V> n = TreeMap.this.floorEntry(key); |
| if (n != null && keyInRange(n.getKey())) |
| return n; |
| return null; |
| } |
| |
| public K floorKey(K key) |
| { |
| K found = TreeMap.this.floorKey(key); |
| if (keyInRange(found)) |
| return found; |
| else |
| return null; |
| } |
| |
| public V get(Object key) |
| { |
| if (keyInRange((K) key)) |
| return TreeMap.this.get(key); |
| return null; |
| } |
| |
| public SortedMap<K,V> headMap(K toKey) |
| { |
| return headMap(toKey, false); |
| } |
| |
| public NavigableMap<K,V> headMap(K toKey, boolean inclusive) |
| { |
| if (!keyInRange(toKey)) |
| throw new IllegalArgumentException("Key outside submap range"); |
| return new SubMap(minKey, (inclusive ? |
| successor(getNode(toKey)).key : toKey)); |
| } |
| |
| public Set<K> keySet() |
| { |
| if (this.keys == null) |
| // Create an AbstractSet with custom implementations of those methods |
| // that can be overriden easily and efficiently. |
| this.keys = new SubMap.KeySet(); |
| return this.keys; |
| } |
| |
| public Entry<K,V> higherEntry(K key) |
| { |
| Entry<K,V> n = TreeMap.this.higherEntry(key); |
| if (n != null && keyInRange(n.getKey())) |
| return n; |
| return null; |
| } |
| |
| public K higherKey(K key) |
| { |
| K found = TreeMap.this.higherKey(key); |
| if (keyInRange(found)) |
| return found; |
| else |
| return null; |
| } |
| |
| public Entry<K,V> lastEntry() |
| { |
| return lowerEntry(maxKey); |
| } |
| |
| public K lastKey() |
| { |
| Entry<K,V> e = lastEntry(); |
| if (e == null) |
| throw new NoSuchElementException(); |
| return e.getKey(); |
| } |
| |
| public Entry<K,V> lowerEntry(K key) |
| { |
| Entry<K,V> n = TreeMap.this.lowerEntry(key); |
| if (n != null && keyInRange(n.getKey())) |
| return n; |
| return null; |
| } |
| |
| public K lowerKey(K key) |
| { |
| K found = TreeMap.this.lowerKey(key); |
| if (keyInRange(found)) |
| return found; |
| else |
| return null; |
| } |
| |
| public NavigableSet<K> navigableKeySet() |
| { |
| if (this.nKeys == null) |
| // Create an AbstractSet with custom implementations of those methods |
| // that can be overriden easily and efficiently. |
| this.nKeys = new SubMap.NavigableKeySet(); |
| return this.nKeys; |
| } |
| |
| public Entry<K,V> pollFirstEntry() |
| { |
| Entry<K,V> e = firstEntry(); |
| if (e != null) |
| removeNode((Node<K,V>) e); |
| return e; |
| } |
| |
| public Entry<K,V> pollLastEntry() |
| { |
| Entry<K,V> e = lastEntry(); |
| if (e != null) |
| removeNode((Node<K,V>) e); |
| return e; |
| } |
| |
| public V put(K key, V value) |
| { |
| if (! keyInRange(key)) |
| throw new IllegalArgumentException("Key outside range"); |
| return TreeMap.this.put(key, value); |
| } |
| |
| public V remove(Object key) |
| { |
| if (keyInRange((K)key)) |
| return TreeMap.this.remove(key); |
| return null; |
| } |
| |
| public int size() |
| { |
| Node node = lowestGreaterThan(minKey, true); |
| Node max = lowestGreaterThan(maxKey, false); |
| int count = 0; |
| while (node != max) |
| { |
| count++; |
| node = successor(node); |
| } |
| return count; |
| } |
| |
| public SortedMap<K,V> subMap(K fromKey, K toKey) |
| { |
| return subMap(fromKey, true, toKey, false); |
| } |
| |
| public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, |
| K toKey, boolean toInclusive) |
| { |
| if (! keyInRange(fromKey) || ! keyInRange(toKey)) |
| throw new IllegalArgumentException("key outside range"); |
| return new SubMap(fromInclusive ? fromKey : successor(getNode(fromKey)).key, |
| toInclusive ? successor(getNode(toKey)).key : toKey); |
| } |
| |
| public SortedMap<K, V> tailMap(K fromKey) |
| { |
| return tailMap(fromKey, true); |
| } |
| |
| public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) |
| { |
| if (! keyInRange(fromKey)) |
| throw new IllegalArgumentException("key outside range"); |
| return new SubMap(inclusive ? fromKey : successor(getNode(fromKey)).key, |
| maxKey); |
| } |
| |
| public Collection<V> values() |
| { |
| if (this.values == null) |
| // Create an AbstractCollection with custom implementations of those |
| // methods that can be overriden easily and efficiently. |
| this.values = new AbstractCollection() |
| { |
| public int size() |
| { |
| return SubMap.this.size(); |
| } |
| |
| public Iterator<V> iterator() |
| { |
| Node first = lowestGreaterThan(minKey, true); |
| Node max = lowestGreaterThan(maxKey, false); |
| return new TreeIterator(VALUES, first, max); |
| } |
| |
| public void clear() |
| { |
| SubMap.this.clear(); |
| } |
| }; |
| return this.values; |
| } |
| |
| private class KeySet |
| extends AbstractSet<K> |
| { |
| public int size() |
| { |
| return SubMap.this.size(); |
| } |
| |
| public Iterator<K> iterator() |
| { |
| Node first = lowestGreaterThan(minKey, true); |
| Node max = lowestGreaterThan(maxKey, false); |
| return new TreeIterator(KEYS, first, max); |
| } |
| |
| public void clear() |
| { |
| SubMap.this.clear(); |
| } |
| |
| public boolean contains(Object o) |
| { |
| if (! keyInRange((K) o)) |
| return false; |
| return getNode((K) o) != nil; |
| } |
| |
| public boolean remove(Object o) |
| { |
| if (! keyInRange((K) o)) |
| return false; |
| Node n = getNode((K) o); |
| if (n != nil) |
| { |
| removeNode(n); |
| return true; |
| } |
| return false; |
| } |
| |
| } // class SubMap.KeySet |
| |
| private final class NavigableKeySet |
| extends KeySet |
| implements NavigableSet<K> |
| { |
| |
| public K ceiling(K k) |
| { |
| return SubMap.this.ceilingKey(k); |
| } |
| |
| public Comparator<? super K> comparator() |
| { |
| return comparator; |
| } |
| |
| public Iterator<K> descendingIterator() |
| { |
| return descendingSet().iterator(); |
| } |
| |
| public NavigableSet<K> descendingSet() |
| { |
| return new DescendingSet(this); |
| } |
| |
| public K first() |
| { |
| return SubMap.this.firstKey(); |
| } |
| |
| public K floor(K k) |
| { |
| return SubMap.this.floorKey(k); |
| } |
| |
| public SortedSet<K> headSet(K to) |
| { |
| return headSet(to, false); |
| } |
| |
| public NavigableSet<K> headSet(K to, boolean inclusive) |
| { |
| return SubMap.this.headMap(to, inclusive).navigableKeySet(); |
| } |
| |
| public K higher(K k) |
| { |
| return SubMap.this.higherKey(k); |
| } |
| |
| public K last() |
| { |
| return SubMap.this.lastKey(); |
| } |
| |
| public K lower(K k) |
| { |
| return SubMap.this.lowerKey(k); |
| } |
| |
| public K pollFirst() |
| { |
| return SubMap.this.pollFirstEntry().getKey(); |
| } |
| |
| public K pollLast() |
| { |
| return SubMap.this.pollLastEntry().getKey(); |
| } |
| |
| public SortedSet<K> subSet(K from, K to) |
| { |
| return subSet(from, true, to, false); |
| } |
| |
| public NavigableSet<K> subSet(K from, boolean fromInclusive, |
| K to, boolean toInclusive) |
| { |
| return SubMap.this.subMap(from, fromInclusive, |
| to, toInclusive).navigableKeySet(); |
| } |
| |
| public SortedSet<K> tailSet(K from) |
| { |
| return tailSet(from, true); |
| } |
| |
| public NavigableSet<K> tailSet(K from, boolean inclusive) |
| { |
| return SubMap.this.tailMap(from, inclusive).navigableKeySet(); |
| } |
| |
| } // class SubMap.NavigableKeySet |
| |
| /** |
| * Implementation of {@link #entrySet()}. |
| */ |
| private class EntrySet |
| extends AbstractSet<Entry<K,V>> |
| { |
| |
| public int size() |
| { |
| return SubMap.this.size(); |
| } |
| |
| public Iterator<Map.Entry<K,V>> iterator() |
| { |
| Node first = lowestGreaterThan(minKey, true); |
| Node max = lowestGreaterThan(maxKey, false); |
| return new TreeIterator(ENTRIES, first, max); |
| } |
| |
| public void clear() |
| { |
| SubMap.this.clear(); |
| } |
| |
| public boolean contains(Object o) |
| { |
| if (! (o instanceof Map.Entry)) |
| return false; |
| Map.Entry<K,V> me = (Map.Entry<K,V>) o; |
| K key = me.getKey(); |
| if (! keyInRange(key)) |
| return false; |
| Node<K,V> n = getNode(key); |
| return n != nil && AbstractSet.equals(me.getValue(), n.value); |
| } |
| |
| public boolean remove(Object o) |
| { |
| if (! (o instanceof Map.Entry)) |
| return false; |
| Map.Entry<K,V> me = (Map.Entry<K,V>) o; |
| K key = me.getKey(); |
| if (! keyInRange(key)) |
| return false; |
| Node<K,V> n = getNode(key); |
| if (n != nil && AbstractSet.equals(me.getValue(), n.value)) |
| { |
| removeNode(n); |
| return true; |
| } |
| return false; |
| } |
| } // class SubMap.EntrySet |
| |
| private final class NavigableEntrySet |
| extends EntrySet |
| implements NavigableSet<Entry<K,V>> |
| { |
| |
| public Entry<K,V> ceiling(Entry<K,V> e) |
| { |
| return SubMap.this.ceilingEntry(e.getKey()); |
| } |
| |
| public Comparator<? super Entry<K,V>> comparator() |
| { |
| return new Comparator<Entry<K,V>>() |
| { |
| public int compare(Entry<K,V> t1, Entry<K,V> t2) |
| { |
| return comparator.compare(t1.getKey(), t2.getKey()); |
| } |
| }; |
| } |
| |
| public Iterator<Entry<K,V>> descendingIterator() |
| { |
| return descendingSet().iterator(); |
| } |
| |
| public NavigableSet<Entry<K,V>> descendingSet() |
| { |
| return new DescendingSet(this); |
| } |
| |
| public Entry<K,V> first() |
| { |
| return SubMap.this.firstEntry(); |
| } |
| |
| public Entry<K,V> floor(Entry<K,V> e) |
| { |
| return SubMap.this.floorEntry(e.getKey()); |
| } |
| |
| public SortedSet<Entry<K,V>> headSet(Entry<K,V> to) |
| { |
| return headSet(to, false); |
| } |
| |
| public NavigableSet<Entry<K,V>> headSet(Entry<K,V> to, boolean inclusive) |
| { |
| return (NavigableSet<Entry<K,V>>) |
| SubMap.this.headMap(to.getKey(), inclusive).entrySet(); |
| } |
| |
| public Entry<K,V> higher(Entry<K,V> e) |
| { |
| return SubMap.this.higherEntry(e.getKey()); |
| } |
| |
| public Entry<K,V> last() |
| { |
| return SubMap.this.lastEntry(); |
| } |
| |
| public Entry<K,V> lower(Entry<K,V> e) |
| { |
| return SubMap.this.lowerEntry(e.getKey()); |
| } |
| |
| public Entry<K,V> pollFirst() |
| { |
| return SubMap.this.pollFirstEntry(); |
| } |
| |
| public Entry<K,V> pollLast() |
| { |
| return SubMap.this.pollLastEntry(); |
| } |
| |
| public SortedSet<Entry<K,V>> subSet(Entry<K,V> from, Entry<K,V> to) |
| { |
| return subSet(from, true, to, false); |
| } |
| |
| public NavigableSet<Entry<K,V>> subSet(Entry<K,V> from, boolean fromInclusive, |
| Entry<K,V> to, boolean toInclusive) |
| { |
| return (NavigableSet<Entry<K,V>>) |
| SubMap.this.subMap(from.getKey(), fromInclusive, |
| to.getKey(), toInclusive).entrySet(); |
| } |
| |
| public SortedSet<Entry<K,V>> tailSet(Entry<K,V> from) |
| { |
| return tailSet(from, true); |
| } |
| |
| public NavigableSet<Entry<K,V>> tailSet(Entry<K,V> from, boolean inclusive) |
| { |
| return (NavigableSet<Entry<K,V>>) |
| SubMap.this.tailMap(from.getKey(), inclusive).navigableKeySet(); |
| } |
| |
| } // class SubMap.NavigableEntrySet |
| |
| } // class SubMap |
| |
| /** |
| * Returns the entry associated with the least or lowest key |
| * that is greater than or equal to the specified key, or |
| * <code>null</code> if there is no such key. |
| * |
| * @param key the key relative to the returned entry. |
| * @return the entry with the least key greater than or equal |
| * to the given key, or <code>null</code> if there is |
| * no such key. |
| * @throws ClassCastException if the specified key can not |
| * be compared with those in the map. |
| * @throws NullPointerException if the key is <code>null</code> |
| * and this map either uses natural |
| * ordering or a comparator that does |
| * not permit null keys. |
| * @since 1.6 |
| */ |
| public Entry<K,V> ceilingEntry(K key) |
| { |
| Node<K,V> n = lowestGreaterThan(key, false); |
| return (n == nil) ? null : n; |
| } |
| |
| /** |
| * Returns the the least or lowest key that is greater than |
| * or equal to the specified key, or <code>null</code> if |
| * there is no such key. |
| * |
| * @param key the key relative to the returned entry. |
| * @return the least key greater than or equal to the given key, |
| * or <code>null</code> if there is no such key. |
| * @throws ClassCastException if the specified key can not |
| * be compared with those in the map. |
| * @throws NullPointerException if the key is <code>null</code> |
| * and this map either uses natural |
| * ordering or a comparator that does |
| * not permit null keys. |
| * @since 1.6 |
| */ |
| public K ceilingKey(K key) |
| { |
| Entry<K,V> e = ceilingEntry(key); |
| return (e == null) ? null : e.getKey(); |
| } |
| |
| /** |
| * Returns a reverse ordered {@link NavigableSet} view of this |
| * map's keys. The set is backed by the {@link TreeMap}, so changes |
| * in one show up in the other. The set supports element removal, |
| * but not element addition. |
| * |
| * @return a reverse ordered set view of the keys. |
| * @since 1.6 |
| * @see #descendingMap() |
| */ |
| public NavigableSet<K> descendingKeySet() |
| { |
| return descendingMap().navigableKeySet(); |
| } |
| |
| /** |
| * Returns a view of the map in reverse order. The descending map |
| * is backed by the original map, so that changes affect both maps. |
| * Any changes occurring to either map while an iteration is taking |
| * place (with the exception of a {@link Iterator#remove()} operation) |
| * result in undefined behaviour from the iteration. The ordering |
| * of the descending map is the same as for a map with a |
| * {@link Comparator} given by {@link Collections#reverseOrder()}, |
| * and calling {@link #descendingMap()} on the descending map itself |
| * results in a view equivalent to the original map. |
| * |
| * @return a reverse order view of the map. |
| * @since 1.6 |
| */ |
| public NavigableMap<K,V> descendingMap() |
| { |
| if (descendingMap == null) |
| descendingMap = new DescendingMap<K,V>(this); |
| return descendingMap; |
| } |
| |
| /** |
| * Returns the entry associated with the least or lowest key |
| * in the map, or <code>null</code> if the map is empty. |
| * |
| * @return the lowest entry, or <code>null</code> if the map |
| * is empty. |
| * @since 1.6 |
| */ |
| public Entry<K,V> firstEntry() |
| { |
| Node<K,V> n = firstNode(); |
| return (n == nil) ? null : n; |
| } |
| |
| /** |
| * Returns the entry associated with the greatest or highest key |
| * that is less than or equal to the specified key, or |
| * <code>null</code> if there is no such key. |
| * |
| * @param key the key relative to the returned entry. |
| * @return the entry with the greatest key less than or equal |
| * to the given key, or <code>null</code> if there is |
| * no such key. |
| * @throws ClassCastException if the specified key can not |
| * be compared with those in the map. |
| * @throws NullPointerException if the key is <code>null</code> |
| * and this map either uses natural |
| * ordering or a comparator that does |
| * not permit null keys. |
| * @since 1.6 |
| */ |
| public Entry<K,V> floorEntry(K key) |
| { |
| Node<K,V> n = highestLessThan(key, true); |
| return (n == nil) ? null : n; |
| } |
| |
| /** |
| * Returns the the greatest or highest key that is less than |
| * or equal to the specified key, or <code>null</code> if |
| * there is no such key. |
| * |
| * @param key the key relative to the returned entry. |
| * @return the greatest key less than or equal to the given key, |
| * or <code>null</code> if there is no such key. |
| * @throws ClassCastException if the specified key can not |
| * be compared with those in the map. |
| * @throws NullPointerException if the key is <code>null</code> |
| * and this map either uses natural |
| * ordering or a comparator that does |
| * not permit null keys. |
| * @since 1.6 |
| */ |
| public K floorKey(K key) |
| { |
| Entry<K,V> e = floorEntry(key); |
| return (e == null) ? null : e.getKey(); |
| } |
| |
| /** |
| * Returns the entry associated with the least or lowest key |
| * that is strictly greater than the specified key, or |
| * <code>null</code> if there is no such key. |
| * |
| * @param key the key relative to the returned entry. |
| * @return the entry with the least key greater than |
| * the given key, or <code>null</code> if there is |
| * no such key. |
| * @throws ClassCastException if the specified key can not |
| * be compared with those in the map. |
| * @throws NullPointerException if the key is <code>null</code> |
| * and this map either uses natural |
| * ordering or a comparator that does |
| * not permit null keys. |
| * @since 1.6 |
| */ |
| public Entry<K,V> higherEntry(K key) |
| { |
| Node<K,V> n = lowestGreaterThan(key, false, false); |
| return (n == nil) ? null : n; |
| } |
| |
| /** |
| * Returns the the least or lowest key that is strictly |
| * greater than the specified key, or <code>null</code> if |
| * there is no such key. |
| * |
| * @param key the key relative to the returned entry. |
| * @return the least key greater than the given key, |
| * or <code>null</code> if there is no such key. |
| * @throws ClassCastException if the specified key can not |
| * be compared with those in the map. |
| * @throws NullPointerException if the key is <code>null</code> |
| * and this map either uses natural |
| * ordering or a comparator that does |
| * not permit null keys. |
| * @since 1.6 |
| */ |
| public K higherKey(K key) |
| { |
| Entry<K,V> e = higherEntry(key); |
| return (e == null) ? null : e.getKey(); |
| } |
| |
| /** |
| * Returns the entry associated with the greatest or highest key |
| * in the map, or <code>null</code> if the map is empty. |
| * |
| * @return the highest entry, or <code>null</code> if the map |
| * is empty. |
| * @since 1.6 |
| */ |
| public Entry<K,V> lastEntry() |
| { |
| Node<K,V> n = lastNode(); |
| return (n == nil) ? null : n; |
| } |
| |
| /** |
| * Returns the entry associated with the greatest or highest key |
| * that is strictly less than the specified key, or |
| * <code>null</code> if there is no such key. |
| * |
| * @param key the key relative to the returned entry. |
| * @return the entry with the greatest key less than |
| * the given key, or <code>null</code> if there is |
| * no such key. |
| * @throws ClassCastException if the specified key can not |
| * be compared with those in the map. |
| * @throws NullPointerException if the key is <code>null</code> |
| * and this map either uses natural |
| * ordering or a comparator that does |
| * not permit null keys. |
| * @since 1.6 |
| */ |
| public Entry<K,V> lowerEntry(K key) |
| { |
| Node<K,V> n = highestLessThan(key); |
| return (n == nil) ? null : n; |
| } |
| |
| /** |
| * Returns the the greatest or highest key that is strictly |
| * less than the specified key, or <code>null</code> if |
| * there is no such key. |
| * |
| * @param key the key relative to the returned entry. |
| * @return the greatest key less than the given key, |
| * or <code>null</code> if there is no such key. |
| * @throws ClassCastException if the specified key can not |
| * be compared with those in the map. |
| * @throws NullPointerException if the key is <code>null</code> |
| * and this map either uses natural |
| * ordering or a comparator that does |
| * not permit null keys. |
| * @since 1.6 |
| */ |
| public K lowerKey(K key) |
| { |
| Entry<K,V> e = lowerEntry(key); |
| return (e == null) ? null : e.getKey(); |
| } |
| |
| /** |
| * Returns a {@link NavigableSet} view of this map's keys. The set is |
| * backed by the {@link TreeMap}, so changes in one show up in the other. |
| * Any changes occurring to either while an iteration is taking |
| * place (with the exception of a {@link Iterator#remove()} operation) |
| * result in undefined behaviour from the iteration. The ordering |
| * The set supports element removal, but not element addition. |
| * |
| * @return a {@link NavigableSet} view of the keys. |
| * @since 1.6 |
| */ |
| public NavigableSet<K> navigableKeySet() |
| { |
| if (nKeys == null) |
| nKeys = new NavigableKeySet(); |
| return nKeys; |
| } |
| |
| /** |
| * Removes and returns the entry associated with the least |
| * or lowest key in the map, or <code>null</code> if the map |
| * is empty. |
| * |
| * @return the removed first entry, or <code>null</code> if the |
| * map is empty. |
| * @since 1.6 |
| */ |
| public Entry<K,V> pollFirstEntry() |
| { |
| Entry<K,V> e = firstEntry(); |
| if (e != null) |
| removeNode((Node<K,V>)e); |
| return e; |
| } |
| |
| /** |
| * Removes and returns the entry associated with the greatest |
| * or highest key in the map, or <code>null</code> if the map |
| * is empty. |
| * |
| * @return the removed last entry, or <code>null</code> if the |
| * map is empty. |
| * @since 1.6 |
| */ |
| public Entry<K,V> pollLastEntry() |
| { |
| Entry<K,V> e = lastEntry(); |
| if (e != null) |
| removeNode((Node<K,V>)e); |
| return e; |
| } |
| |
| /** |
| * Implementation of {@link #descendingMap()} and associated |
| * derivatives. This class provides a view of the |
| * original backing map in reverse order, and throws |
| * {@link IllegalArgumentException} for attempts to |
| * access beyond that range. |
| * |
| * @author Andrew John Hughes (gnu_andrew@member.fsf.org) |
| */ |
| private static final class DescendingMap<DK,DV> |
| implements NavigableMap<DK,DV> |
| { |
| |
| /** |
| * The cache for {@link #entrySet()}. |
| */ |
| private Set<Map.Entry<DK,DV>> entries; |
| |
| /** |
| * The cache for {@link #keySet()}. |
| */ |
| private Set<DK> keys; |
| |
| /** |
| * The cache for {@link #navigableKeySet()}. |
| */ |
| private NavigableSet<DK> nKeys; |
| |
| /** |
| * The cache for {@link #values()}. |
| */ |
| private Collection<DV> values; |
| |
| /** |
| * The backing {@link NavigableMap}. |
| */ |
| private NavigableMap<DK,DV> map; |
| |
| /** |
| * Create a {@link DescendingMap} around the specified |
| * map. |
| * |
| * @param map the map to wrap. |
| */ |
| public DescendingMap(NavigableMap<DK,DV> map) |
| { |
| this.map = map; |
| } |
| |
| public Map.Entry<DK,DV> ceilingEntry(DK key) |
| { |
| return map.floorEntry(key); |
| } |
| |
| public DK ceilingKey(DK key) |
| { |
| return map.floorKey(key); |
| } |
| |
| public void clear() |
| { |
| map.clear(); |
| } |
| |
| public Comparator<? super DK> comparator() |
| { |
| return Collections.reverseOrder(map.comparator()); |
| } |
| |
| public boolean containsKey(Object o) |
| { |
| return map.containsKey(o); |
| } |
| |
| public boolean containsValue(Object o) |
| { |
| return map.containsValue(o); |
| } |
| |
| public NavigableSet<DK> descendingKeySet() |
| { |
| return descendingMap().navigableKeySet(); |
| } |
| |
| public NavigableMap<DK,DV> descendingMap() |
| { |
| return map; |
| } |
| |
| public Set<Entry<DK,DV>> entrySet() |
| { |
| if (entries == null) |
| entries = |
| new DescendingSet<Entry<DK,DV>>((NavigableSet<Entry<DK,DV>>) |
| map.entrySet()); |
| return entries; |
| } |
| |
| public boolean equals(Object o) |
| { |
| return map.equals(o); |
| } |
| |
| public Entry<DK,DV> firstEntry() |
| { |
| return map.lastEntry(); |
| } |
| |
| public DK firstKey() |
| { |
| return map.lastKey(); |
| } |
| |
| public Entry<DK,DV> floorEntry(DK key) |
| { |
| return map.ceilingEntry(key); |
| } |
| |
| public DK floorKey(DK key) |
| { |
| return map.ceilingKey(key); |
| } |
| |
| public DV get(Object key) |
| { |
| return map.get(key); |
| } |
| |
| public int hashCode() |
| { |
| return map.hashCode(); |
| } |
| |
| public SortedMap<DK,DV> headMap(DK toKey) |
| { |
| return headMap(toKey, false); |
| } |
| |
| public NavigableMap<DK,DV> headMap(DK toKey, boolean inclusive) |
| { |
| return new DescendingMap(map.tailMap(toKey, inclusive)); |
| } |
| |
| public Entry<DK,DV> higherEntry(DK key) |
| { |
| return map.lowerEntry(key); |
| } |
| |
| public DK higherKey(DK key) |
| { |
| return map.lowerKey(key); |
| } |
| |
| public Set<DK> keySet() |
| { |
| if (keys == null) |
| keys = new DescendingSet<DK>(map.navigableKeySet()); |
| return keys; |
| } |
| |
| public boolean isEmpty() |
| { |
| return map.isEmpty(); |
| } |
| |
| public Entry<DK,DV> lastEntry() |
| { |
| return map.firstEntry(); |
| } |
| |
| public DK lastKey() |
| { |
| return map.firstKey(); |
| } |
| |
| public Entry<DK,DV> lowerEntry(DK key) |
| { |
| return map.higherEntry(key); |
| } |
| |
| public DK lowerKey(DK key) |
| { |
| return map.higherKey(key); |
| } |
| |
| public NavigableSet<DK> navigableKeySet() |
| { |
| if (nKeys == null) |
| nKeys = new DescendingSet<DK>(map.navigableKeySet()); |
| return nKeys; |
| } |
| |
| public Entry<DK,DV> pollFirstEntry() |
| { |
| return pollLastEntry(); |
| } |
| |
| public Entry<DK,DV> pollLastEntry() |
| { |
| return pollFirstEntry(); |
| } |
| |
| public DV put(DK key, DV value) |
| { |
| return map.put(key, value); |
| } |
| |
| public void putAll(Map<? extends DK, ? extends DV> m) |
| { |
| map.putAll(m); |
| } |
| |
| public DV remove(Object key) |
| { |
| return map.remove(key); |
| } |
| |
| public int size() |
| { |
| return map.size(); |
| } |
| |
| public SortedMap<DK,DV> subMap(DK fromKey, DK toKey) |
| { |
| return subMap(fromKey, true, toKey, false); |
| } |
| |
| public NavigableMap<DK,DV> subMap(DK fromKey, boolean fromInclusive, |
| DK toKey, boolean toInclusive) |
| { |
| return new DescendingMap(map.subMap(fromKey, fromInclusive, |
| toKey, toInclusive)); |
| } |
| |
| public SortedMap<DK,DV> tailMap(DK fromKey) |
| { |
| return tailMap(fromKey, true); |
| } |
| |
| public NavigableMap<DK,DV> tailMap(DK fromKey, boolean inclusive) |
| { |
| return new DescendingMap(map.headMap(fromKey, inclusive)); |
| } |
| |
| public String toString() |
| { |
| StringBuilder r = new StringBuilder("{"); |
| final Iterator<Entry<DK,DV>> it = entrySet().iterator(); |
| while (it.hasNext()) |
| { |
| final Entry<DK,DV> e = it.next(); |
| r.append(e.getKey()); |
| r.append('='); |
| r.append(e.getValue()); |
| r.append(", "); |
| } |
| r.replace(r.length() - 2, r.length(), "}"); |
| return r.toString(); |
| } |
| |
| public Collection<DV> values() |
| { |
| if (values == null) |
| // Create an AbstractCollection with custom implementations of those |
| // methods that can be overriden easily and efficiently. |
| values = new AbstractCollection() |
| { |
| public int size() |
| { |
| return size(); |
| } |
| |
| public Iterator<DV> iterator() |
| { |
| return new Iterator<DV>() |
| { |
| /** The last Entry returned by a next() call. */ |
| private Entry<DK,DV> last; |
| |
| /** The next entry that should be returned by next(). */ |
| private Entry<DK,DV> next = firstEntry(); |
| |
| public boolean hasNext() |
| { |
| return next != null; |
| } |
| |
| public DV next() |
| { |
| if (next == null) |
| throw new NoSuchElementException(); |
| last = next; |
| next = higherEntry(last.getKey()); |
| |
| return last.getValue(); |
| } |
| |
| public void remove() |
| { |
| if (last == null) |
| throw new IllegalStateException(); |
| |
| DescendingMap.this.remove(last.getKey()); |
| last = null; |
| } |
| }; |
| } |
| |
| public void clear() |
| { |
| clear(); |
| } |
| }; |
| return values; |
| } |
| |
| } // class DescendingMap |
| |
| /** |
| * Implementation of {@link #keySet()}. |
| */ |
| private class KeySet |
| extends AbstractSet<K> |
| { |
| |
| public int size() |
| { |
| return size; |
| } |
| |
| public Iterator<K> iterator() |
| { |
| return new TreeIterator(KEYS); |
| } |
| |
| public void clear() |
| { |
| TreeMap.this.clear(); |
| } |
| |
| public boolean contains(Object o) |
| { |
| return containsKey(o); |
| } |
| |
| public boolean remove(Object key) |
| { |
| Node<K,V> n = getNode((K) key); |
| if (n == nil) |
| return false; |
| removeNode(n); |
| return true; |
| } |
| } // class KeySet |
| |
| /** |
| * Implementation of {@link #navigableKeySet()}. |
| * |
| * @author Andrew John Hughes (gnu_andrew@member.fsf.org) |
| */ |
| private final class NavigableKeySet |
| extends KeySet |
| implements NavigableSet<K> |
| { |
| |
| public K ceiling(K k) |
| { |
| return ceilingKey(k); |
| } |
| |
| public Comparator<? super K> comparator() |
| { |
| return comparator; |
| } |
| |
| public Iterator<K> descendingIterator() |
| { |
| return descendingSet().iterator(); |
| } |
| |
| public NavigableSet<K> descendingSet() |
| { |
| return new DescendingSet<K>(this); |
| } |
| |
| public K first() |
| { |
| return firstKey(); |
| } |
| |
| public K floor(K k) |
| { |
| return floorKey(k); |
| } |
| |
| public SortedSet<K> headSet(K to) |
| { |
| return headSet(to, false); |
| } |
| |
| public NavigableSet<K> headSet(K to, boolean inclusive) |
| { |
| return headMap(to, inclusive).navigableKeySet(); |
| } |
| |
| public K higher(K k) |
| { |
| return higherKey(k); |
| } |
| |
| public K last() |
| { |
| return lastKey(); |
| } |
| |
| public K lower(K k) |
| { |
| return lowerKey(k); |
| } |
| |
| public K pollFirst() |
| { |
| return pollFirstEntry().getKey(); |
| } |
| |
| public K pollLast() |
| { |
| return pollLastEntry().getKey(); |
| } |
| |
| public SortedSet<K> subSet(K from, K to) |
| { |
| return subSet(from, true, to, false); |
| } |
| |
| public NavigableSet<K> subSet(K from, boolean fromInclusive, |
| K to, boolean toInclusive) |
| { |
| return subMap(from, fromInclusive, |
| to, toInclusive).navigableKeySet(); |
| } |
| |
| public SortedSet<K> tailSet(K from) |
| { |
| return tailSet(from, true); |
| } |
| |
| public NavigableSet<K> tailSet(K from, boolean inclusive) |
| { |
| return tailMap(from, inclusive).navigableKeySet(); |
| } |
| |
| |
| } // class NavigableKeySet |
| |
| /** |
| * Implementation of {@link #descendingSet()} and associated |
| * derivatives. This class provides a view of the |
| * original backing set in reverse order, and throws |
| * {@link IllegalArgumentException} for attempts to |
| * access beyond that range. |
| * |
| * @author Andrew John Hughes (gnu_andrew@member.fsf.org) |
| */ |
| private static final class DescendingSet<D> |
| implements NavigableSet<D> |
| { |
| |
| /** |
| * The backing {@link NavigableSet}. |
| */ |
| private NavigableSet<D> set; |
| |
| /** |
| * Create a {@link DescendingSet} around the specified |
| * set. |
| * |
| * @param map the set to wrap. |
| */ |
| public DescendingSet(NavigableSet<D> set) |
| { |
| this.set = set; |
| } |
| |
| public boolean add(D e) |
| { |
| return set.add(e); |
| } |
| |
| public boolean addAll(Collection<? extends D> c) |
| { |
| return set.addAll(c); |
| } |
| |
| public D ceiling(D e) |
| { |
| return set.floor(e); |
| } |
| |
| public void clear() |
| { |
| set.clear(); |
| } |
| |
| public Comparator<? super D> comparator() |
| { |
| return Collections.reverseOrder(set.comparator()); |
| } |
| |
| public boolean contains(Object o) |
| { |
| return set.contains(o); |
| } |
| |
| public boolean containsAll(Collection<?> c) |
| { |
| return set.containsAll(c); |
| } |
| |
| public Iterator<D> descendingIterator() |
| { |
| return descendingSet().iterator(); |
| } |
| |
| public NavigableSet<D> descendingSet() |
| { |
| return set; |
| } |
| |
| public boolean equals(Object o) |
| { |
| return set.equals(o); |
| } |
| |
| public D first() |
| { |
| return set.last(); |
| } |
| |
| public D floor(D e) |
| { |
| return set.ceiling(e); |
| } |
| |
| public int hashCode() |
| { |
| return set.hashCode(); |
| } |
| |
| public SortedSet<D> headSet(D to) |
| { |
| return headSet(to, false); |
| } |
| |
| public NavigableSet<D> headSet(D to, boolean inclusive) |
| { |
| return new DescendingSet(set.tailSet(to, inclusive)); |
| } |
| |
| public D higher(D e) |
| { |
| return set.lower(e); |
| } |
| |
| public boolean isEmpty() |
| { |
| return set.isEmpty(); |
| } |
| |
| public Iterator<D> iterator() |
| { |
| return new Iterator<D>() |
| { |
| |
| /** The last element returned by a next() call. */ |
| private D last; |
| |
| /** The next element that should be returned by next(). */ |
| private D next = first(); |
| |
| public boolean hasNext() |
| { |
| return next != null; |
| } |
| |
| public D next() |
| { |
| if (next == null) |
| throw new NoSuchElementException(); |
| last = next; |
| next = higher(last); |
| |
| return last; |
| } |
| |
| public void remove() |
| { |
| if (last == null) |
| throw new IllegalStateException(); |
| |
| DescendingSet.this.remove(last); |
| last = null; |
| } |
| }; |
| } |
| |
| public D last() |
| { |
| return set.first(); |
| } |
| |
| public D lower(D e) |
| { |
| return set.higher(e); |
| } |
| |
| public D pollFirst() |
| { |
| return set.pollLast(); |
| } |
| |
| public D pollLast() |
| { |
| return set.pollFirst(); |
| } |
| |
| public boolean remove(Object o) |
| { |
| return set.remove(o); |
| } |
| |
| public boolean removeAll(Collection<?> c) |
| { |
| return set.removeAll(c); |
| } |
| |
| public boolean retainAll(Collection<?> c) |
| { |
| return set.retainAll(c); |
| } |
| |
| public int size() |
| { |
| return set.size(); |
| } |
| |
| public SortedSet<D> subSet(D from, D to) |
| { |
| return subSet(from, true, to, false); |
| } |
| |
| public NavigableSet<D> subSet(D from, boolean fromInclusive, |
| D to, boolean toInclusive) |
| { |
| return new DescendingSet(set.subSet(from, fromInclusive, |
| to, toInclusive)); |
| } |
| |
| public SortedSet<D> tailSet(D from) |
| { |
| return tailSet(from, true); |
| } |
| |
| public NavigableSet<D> tailSet(D from, boolean inclusive) |
| { |
| return new DescendingSet(set.headSet(from, inclusive)); |
| } |
| |
| public Object[] toArray() |
| { |
| D[] array = (D[]) set.toArray(); |
| Arrays.sort(array, comparator()); |
| return array; |
| } |
| |
| public <T> T[] toArray(T[] a) |
| { |
| T[] array = set.toArray(a); |
| Arrays.sort(array, (Comparator<? super T>) comparator()); |
| return array; |
| } |
| |
| public String toString() |
| { |
| StringBuilder r = new StringBuilder("["); |
| final Iterator<D> it = iterator(); |
| while (it.hasNext()) |
| { |
| final D o = it.next(); |
| if (o == this) |
| r.append("<this>"); |
| else |
| r.append(o); |
| r.append(", "); |
| } |
| r.replace(r.length() - 2, r.length(), "]"); |
| return r.toString(); |
| } |
| |
| } // class DescendingSet |
| |
| private class EntrySet |
| extends AbstractSet<Entry<K,V>> |
| { |
| public int size() |
| { |
| return size; |
| } |
| |
| public Iterator<Map.Entry<K,V>> iterator() |
| { |
| return new TreeIterator(ENTRIES); |
| } |
| |
| public void clear() |
| { |
| TreeMap.this.clear(); |
| } |
| |
| public boolean contains(Object o) |
| { |
| if (! (o instanceof Map.Entry)) |
| return false; |
| Map.Entry<K,V> me = (Map.Entry<K,V>) o; |
| Node<K,V> n = getNode(me.getKey()); |
| return n != nil && AbstractSet.equals(me.getValue(), n.value); |
| } |
| |
| public boolean remove(Object o) |
| { |
| if (! (o instanceof Map.Entry)) |
| return false; |
| Map.Entry<K,V> me = (Map.Entry<K,V>) o; |
| Node<K,V> n = getNode(me.getKey()); |
| if (n != nil && AbstractSet.equals(me.getValue(), n.value)) |
| { |
| removeNode(n); |
| return true; |
| } |
| return false; |
| } |
| } |
| |
| private final class NavigableEntrySet |
| extends EntrySet |
| implements NavigableSet<Entry<K,V>> |
| { |
| |
| public Entry<K,V> ceiling(Entry<K,V> e) |
| { |
| return ceilingEntry(e.getKey()); |
| } |
| |
| public Comparator<? super Entry<K,V>> comparator() |
| { |
| return new Comparator<Entry<K,V>>() |
| { |
| public int compare(Entry<K,V> t1, Entry<K,V> t2) |
| { |
| return comparator.compare(t1.getKey(), t2.getKey()); |
| } |
| }; |
| } |
| |
| public Iterator<Entry<K,V>> descendingIterator() |
| { |
| return descendingSet().iterator(); |
| } |
| |
| public NavigableSet<Entry<K,V>> descendingSet() |
| { |
| return new DescendingSet(this); |
| } |
| |
| public Entry<K,V> first() |
| { |
| return firstEntry(); |
| } |
| |
| public Entry<K,V> floor(Entry<K,V> e) |
| { |
| return floorEntry(e.getKey()); |
| } |
| |
| public SortedSet<Entry<K,V>> headSet(Entry<K,V> to) |
| { |
| return headSet(to, false); |
| } |
| |
| public NavigableSet<Entry<K,V>> headSet(Entry<K,V> to, boolean inclusive) |
| { |
| return (NavigableSet<Entry<K,V>>) headMap(to.getKey(), inclusive).entrySet(); |
| } |
| |
| public Entry<K,V> higher(Entry<K,V> e) |
| { |
| return higherEntry(e.getKey()); |
| } |
| |
| public Entry<K,V> last() |
| { |
| return lastEntry(); |
| } |
| |
| public Entry<K,V> lower(Entry<K,V> e) |
| { |
| return lowerEntry(e.getKey()); |
| } |
| |
| public Entry<K,V> pollFirst() |
| { |
| return pollFirstEntry(); |
| } |
| |
| public Entry<K,V> pollLast() |
| { |
| return pollLastEntry(); |
| } |
| |
| public SortedSet<Entry<K,V>> subSet(Entry<K,V> from, Entry<K,V> to) |
| { |
| return subSet(from, true, to, false); |
| } |
| |
| public NavigableSet<Entry<K,V>> subSet(Entry<K,V> from, boolean fromInclusive, |
| Entry<K,V> to, boolean toInclusive) |
| { |
| return (NavigableSet<Entry<K,V>>) subMap(from.getKey(), fromInclusive, |
| to.getKey(), toInclusive).entrySet(); |
| } |
| |
| public SortedSet<Entry<K,V>> tailSet(Entry<K,V> from) |
| { |
| return tailSet(from, true); |
| } |
| |
| public NavigableSet<Entry<K,V>> tailSet(Entry<K,V> from, boolean inclusive) |
| { |
| return (NavigableSet<Entry<K,V>>) tailMap(from.getKey(), inclusive).navigableKeySet(); |
| } |
| |
| } // class NavigableEntrySet |
| |
| } // class TreeMap |