/* * Copyright (C) 2010 The Android Open Source Project * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ package java.util; import java.io.IOException; import java.io.ObjectInputStream; import java.io.ObjectInputStream.GetField; import java.io.ObjectOutputStream; import java.io.ObjectStreamException; import java.io.Serializable; import static java.util.TreeMap.Bound.*; import static java.util.TreeMap.Relation.*; import libcore.util.Objects; /** * A map whose entries are sorted by their keys. All optional operations such as * {@link #put} and {@link #remove} are supported. * *

This map sorts keys using either a user-supplied comparator or the key's * natural order: *

* With either a comparator or a natural ordering, comparisons should be * consistent with equals. An ordering is consistent with equals if for * every pair of keys {@code a} and {@code b}, {@code a.equals(b)} if and only * if {@code compare(a, b) == 0}. * *

When the ordering is not consistent with equals the behavior of this * class is well defined but does not honor the contract specified by {@link * Map}. Consider a tree map of case-insensitive strings, an ordering that is * not consistent with equals:

   {@code
 *   TreeMap map = new TreeMap(String.CASE_INSENSITIVE_ORDER);
 *   map.put("a", "android");
 *
 *   // The Map API specifies that the next line should print "null" because
 *   // "a".equals("A") is false and there is no mapping for upper case "A".
 *   // But the case insensitive ordering says compare("a", "A") == 0. TreeMap
 *   // uses only comparators/comparable on keys and so this prints "android".
 *   System.out.println(map.get("A"));
 * }
* * @since 1.2 */ public class TreeMap extends AbstractMap implements SortedMap, NavigableMap, Cloneable, Serializable { @SuppressWarnings("unchecked") // to avoid Comparable>> private static final Comparator NATURAL_ORDER = new Comparator() { public int compare(Comparable a, Comparable b) { return a.compareTo(b); } }; Comparator comparator; Node root; int size = 0; int modCount = 0; /** * Create a natural order, empty tree map whose keys must be mutually * comparable and non-null. */ @SuppressWarnings("unchecked") // unsafe! this assumes K is comparable public TreeMap() { this.comparator = (Comparator) NATURAL_ORDER; } /** * Create a natural order tree map populated with the key/value pairs of * {@code copyFrom}. This map's keys must be mutually comparable and * non-null. * *

Even if {@code copyFrom} is a {@code SortedMap}, the constructed map * will not use {@code copyFrom}'s ordering. This * constructor always creates a naturally-ordered map. Because the {@code * TreeMap} constructor overloads are ambiguous, prefer to construct a map * and populate it in two steps:

   {@code
     *   TreeMap customOrderedMap
     *       = new TreeMap(copyFrom.comparator());
     *   customOrderedMap.putAll(copyFrom);
     * }
*/ public TreeMap(Map copyFrom) { this(); for (Map.Entry entry : copyFrom.entrySet()) { putInternal(entry.getKey(), entry.getValue()); } } /** * Create a tree map ordered by {@code comparator}. This map's keys may only * be null if {@code comparator} permits. * * @param comparator the comparator to order elements with, or {@code null} to use the natural * ordering. */ @SuppressWarnings("unchecked") // unsafe! if comparator is null, this assumes K is comparable public TreeMap(Comparator comparator) { if (comparator != null) { this.comparator = comparator; } else { this.comparator = (Comparator) NATURAL_ORDER; } } /** * Create a tree map with the ordering and key/value pairs of {@code * copyFrom}. This map's keys may only be null if the {@code copyFrom}'s * ordering permits. * *

The constructed map will always use {@code * copyFrom}'s ordering. Because the {@code TreeMap} constructor overloads * are ambiguous, prefer to construct a map and populate it in two steps: *

   {@code
     *   TreeMap customOrderedMap
     *       = new TreeMap(copyFrom.comparator());
     *   customOrderedMap.putAll(copyFrom);
     * }
*/ @SuppressWarnings("unchecked") // if copyFrom's keys are comparable this map's keys must be also public TreeMap(SortedMap copyFrom) { Comparator sourceComparator = copyFrom.comparator(); if (sourceComparator != null) { this.comparator = sourceComparator; } else { this.comparator = (Comparator) NATURAL_ORDER; } for (Map.Entry entry : copyFrom.entrySet()) { putInternal(entry.getKey(), entry.getValue()); } } @Override public Object clone() { try { @SuppressWarnings("unchecked") // super.clone() must return the same type TreeMap map = (TreeMap) super.clone(); map.root = root != null ? root.copy(null) : null; map.entrySet = null; map.keySet = null; return map; } catch (CloneNotSupportedException e) { throw new AssertionError(); } } @Override public int size() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public V get(Object key) { Entry entry = findByObject(key); return entry != null ? entry.getValue() : null; } @Override public boolean containsKey(Object key) { return findByObject(key) != null; } @Override public V put(K key, V value) { return putInternal(key, value); } @Override public void clear() { root = null; size = 0; modCount++; } @Override public V remove(Object key) { Node node = removeInternalByKey(key); return node != null ? node.value : null; } /* * AVL methods */ enum Relation { LOWER, FLOOR, EQUAL, CREATE, CEILING, HIGHER; /** * Returns a possibly-flipped relation for use in descending views. * * @param ascending false to flip; true to return this. */ Relation forOrder(boolean ascending) { if (ascending) { return this; } switch (this) { case LOWER: return HIGHER; case FLOOR: return CEILING; case EQUAL: return EQUAL; case CEILING: return FLOOR; case HIGHER: return LOWER; default: throw new IllegalStateException(); } } } V putInternal(K key, V value) { Node created = find(key, Relation.CREATE); V result = created.value; created.value = value; return result; } /** * Returns the node at or adjacent to the given key, creating it if requested. * * @throws ClassCastException if {@code key} and the tree's keys aren't mutually comparable. */ Node find(K key, Relation relation) { if (root == null) { if (comparator == NATURAL_ORDER && !(key instanceof Comparable)) { throw new ClassCastException(key.getClass().getName() + " is not Comparable"); // NullPointerException ok } if (relation == Relation.CREATE) { root = new Node(null, key); size = 1; modCount++; return root; } else { return null; } } /* * Micro-optimization: avoid polymorphic calls to Comparator.compare(). * This is 10% faster for naturally ordered trees. */ @SuppressWarnings("unchecked") // will throw a ClassCastException below if there's trouble Comparable comparableKey = (comparator == NATURAL_ORDER) ? (Comparable) key : null; Node nearest = root; while (true) { int comparison = (comparableKey != null) ? comparableKey.compareTo(nearest.key) : comparator.compare(key, nearest.key); /* * We found the requested key. */ if (comparison == 0) { switch (relation) { case LOWER: return nearest.prev(); case FLOOR: case EQUAL: case CREATE: case CEILING: return nearest; case HIGHER: return nearest.next(); } } Node child = (comparison < 0) ? nearest.left : nearest.right; if (child != null) { nearest = child; continue; } /* * We found a nearest node. Every key not in the tree has up to two * nearest nodes, one lower and one higher. */ if (comparison < 0) { // nearest.key is higher switch (relation) { case LOWER: case FLOOR: return nearest.prev(); case CEILING: case HIGHER: return nearest; case EQUAL: return null; case CREATE: Node created = new Node(nearest, key); nearest.left = created; size++; modCount++; rebalance(nearest, true); return created; } } else { // comparison > 0, nearest.key is lower switch (relation) { case LOWER: case FLOOR: return nearest; case CEILING: case HIGHER: return nearest.next(); case EQUAL: return null; case CREATE: Node created = new Node(nearest, key); nearest.right = created; size++; modCount++; rebalance(nearest, true); return created; } } } } @SuppressWarnings("unchecked") // this method throws ClassCastExceptions! Node findByObject(Object key) { return find((K) key, EQUAL); } /** * Returns this map's entry that has the same key and value as {@code * entry}, or null if this map has no such entry. * *

This method uses the comparator for key equality rather than {@code * equals}. If this map's comparator isn't consistent with equals (such as * {@code String.CASE_INSENSITIVE_ORDER}), then {@code remove()} and {@code * contains()} will violate the collections API. */ Node findByEntry(Entry entry) { Node mine = findByObject(entry.getKey()); boolean valuesEqual = mine != null && Objects.equal(mine.value, entry.getValue()); return valuesEqual ? mine : null; } /** * Removes {@code node} from this tree, rearranging the tree's structure as * necessary. */ void removeInternal(Node node) { Node left = node.left; Node right = node.right; Node originalParent = node.parent; if (left != null && right != null) { /* * To remove a node with both left and right subtrees, move an * adjacent node from one of those subtrees into this node's place. * * Removing the adjacent node may change this node's subtrees. This * node may no longer have two subtrees once the adjacent node is * gone! */ Node adjacent = (left.height > right.height) ? left.last() : right.first(); removeInternal(adjacent); // takes care of rebalance and size-- int leftHeight = 0; left = node.left; if (left != null) { leftHeight = left.height; adjacent.left = left; left.parent = adjacent; node.left = null; } int rightHeight = 0; right = node.right; if (right != null) { rightHeight = right.height; adjacent.right = right; right.parent = adjacent; node.right = null; } adjacent.height = Math.max(leftHeight, rightHeight) + 1; replaceInParent(node, adjacent); return; } else if (left != null) { replaceInParent(node, left); node.left = null; } else if (right != null) { replaceInParent(node, right); node.right = null; } else { replaceInParent(node, null); } rebalance(originalParent, false); size--; modCount++; } Node removeInternalByKey(Object key) { Node node = findByObject(key); if (node != null) { removeInternal(node); } return node; } private void replaceInParent(Node node, Node replacement) { Node parent = node.parent; node.parent = null; if (replacement != null) { replacement.parent = parent; } if (parent != null) { if (parent.left == node) { parent.left = replacement; } else { assert (parent.right == node); parent.right = replacement; } } else { root = replacement; } } /** * Rebalances the tree by making any AVL rotations necessary between the * newly-unbalanced node and the tree's root. * * @param insert true if the node was unbalanced by an insert; false if it * was by a removal. */ private void rebalance(Node unbalanced, boolean insert) { for (Node node = unbalanced; node != null; node = node.parent) { Node left = node.left; Node right = node.right; int leftHeight = left != null ? left.height : 0; int rightHeight = right != null ? right.height : 0; int delta = leftHeight - rightHeight; if (delta == -2) { Node rightLeft = right.left; Node rightRight = right.right; int rightRightHeight = rightRight != null ? rightRight.height : 0; int rightLeftHeight = rightLeft != null ? rightLeft.height : 0; int rightDelta = rightLeftHeight - rightRightHeight; if (rightDelta == -1 || (rightDelta == 0 && !insert)) { rotateLeft(node); // AVL right right } else { assert (rightDelta == 1); rotateRight(right); // AVL right left rotateLeft(node); } if (insert) { break; // no further rotations will be necessary } } else if (delta == 2) { Node leftLeft = left.left; Node leftRight = left.right; int leftRightHeight = leftRight != null ? leftRight.height : 0; int leftLeftHeight = leftLeft != null ? leftLeft.height : 0; int leftDelta = leftLeftHeight - leftRightHeight; if (leftDelta == 1 || (leftDelta == 0 && !insert)) { rotateRight(node); // AVL left left } else { assert (leftDelta == -1); rotateLeft(left); // AVL left right rotateRight(node); } if (insert) { break; // no further rotations will be necessary } } else if (delta == 0) { node.height = leftHeight + 1; // leftHeight == rightHeight if (insert) { break; // the insert caused balance, so rebalancing is done! } } else { assert (delta == -1 || delta == 1); node.height = Math.max(leftHeight, rightHeight) + 1; if (!insert) { break; // the height hasn't changed, so rebalancing is done! } } } } /** * Rotates the subtree so that its root's right child is the new root. */ private void rotateLeft(Node root) { Node left = root.left; Node pivot = root.right; Node pivotLeft = pivot.left; Node pivotRight = pivot.right; // move the pivot's left child to the root's right root.right = pivotLeft; if (pivotLeft != null) { pivotLeft.parent = root; } replaceInParent(root, pivot); // move the root to the pivot's left pivot.left = root; root.parent = pivot; // fix heights root.height = Math.max(left != null ? left.height : 0, pivotLeft != null ? pivotLeft.height : 0) + 1; pivot.height = Math.max(root.height, pivotRight != null ? pivotRight.height : 0) + 1; } /** * Rotates the subtree so that its root's left child is the new root. */ private void rotateRight(Node root) { Node pivot = root.left; Node right = root.right; Node pivotLeft = pivot.left; Node pivotRight = pivot.right; // move the pivot's right child to the root's left root.left = pivotRight; if (pivotRight != null) { pivotRight.parent = root; } replaceInParent(root, pivot); // move the root to the pivot's right pivot.right = root; root.parent = pivot; // fixup heights root.height = Math.max(right != null ? right.height : 0, pivotRight != null ? pivotRight.height : 0) + 1; pivot.height = Math.max(root.height, pivotLeft != null ? pivotLeft.height : 0) + 1; } /* * Navigable methods. */ /** * Returns an immutable version of {@param entry}. Need this because we allow entry to be null, * in which case we return a null SimpleImmutableEntry. */ private SimpleImmutableEntry immutableCopy(Entry entry) { return entry == null ? null : new SimpleImmutableEntry(entry); } public Entry firstEntry() { return immutableCopy(root == null ? null : root.first()); } private Entry internalPollFirstEntry() { if (root == null) { return null; } Node result = root.first(); removeInternal(result); return result; } public Entry pollFirstEntry() { return immutableCopy(internalPollFirstEntry()); } public K firstKey() { if (root == null) { throw new NoSuchElementException(); } return root.first().getKey(); } public Entry lastEntry() { return immutableCopy(root == null ? null : root.last()); } private Entry internalPollLastEntry() { if (root == null) { return null; } Node result = root.last(); removeInternal(result); return result; } public Entry pollLastEntry() { return immutableCopy(internalPollLastEntry()); } public K lastKey() { if (root == null) { throw new NoSuchElementException(); } return root.last().getKey(); } public Entry lowerEntry(K key) { return immutableCopy(find(key, LOWER)); } public K lowerKey(K key) { Entry entry = find(key, LOWER); return entry != null ? entry.getKey() : null; } public Entry floorEntry(K key) { return immutableCopy(find(key, FLOOR)); } public K floorKey(K key) { Entry entry = find(key, FLOOR); return entry != null ? entry.getKey() : null; } public Entry ceilingEntry(K key) { return immutableCopy(find(key, CEILING)); } public K ceilingKey(K key) { Entry entry = find(key, CEILING); return entry != null ? entry.getKey() : null; } public Entry higherEntry(K key) { return immutableCopy(find(key, HIGHER)); } public K higherKey(K key) { Entry entry = find(key, HIGHER); return entry != null ? entry.getKey() : null; } public Comparator comparator() { return comparator != NATURAL_ORDER ? comparator : null; } /* * View factory methods. */ private EntrySet entrySet; private KeySet keySet; @Override public Set> entrySet() { EntrySet result = entrySet; return result != null ? result : (entrySet = new EntrySet()); } @Override public Set keySet() { KeySet result = keySet; return result != null ? result : (keySet = new KeySet()); } public NavigableSet navigableKeySet() { KeySet result = keySet; return result != null ? result : (keySet = new KeySet()); } public NavigableMap subMap(K from, boolean fromInclusive, K to, boolean toInclusive) { Bound fromBound = fromInclusive ? INCLUSIVE : EXCLUSIVE; Bound toBound = toInclusive ? INCLUSIVE : EXCLUSIVE; return new BoundedMap(true, from, fromBound, to, toBound); } public SortedMap subMap(K fromInclusive, K toExclusive) { return new BoundedMap(true, fromInclusive, INCLUSIVE, toExclusive, EXCLUSIVE); } public NavigableMap headMap(K to, boolean inclusive) { Bound toBound = inclusive ? INCLUSIVE : EXCLUSIVE; return new BoundedMap(true, null, NO_BOUND, to, toBound); } public SortedMap headMap(K toExclusive) { return new BoundedMap(true, null, NO_BOUND, toExclusive, EXCLUSIVE); } public NavigableMap tailMap(K from, boolean inclusive) { Bound fromBound = inclusive ? INCLUSIVE : EXCLUSIVE; return new BoundedMap(true, from, fromBound, null, NO_BOUND); } public SortedMap tailMap(K fromInclusive) { return new BoundedMap(true, fromInclusive, INCLUSIVE, null, NO_BOUND); } public NavigableMap descendingMap() { return new BoundedMap(false, null, NO_BOUND, null, NO_BOUND); } public NavigableSet descendingKeySet() { return new BoundedMap(false, null, NO_BOUND, null, NO_BOUND).navigableKeySet(); } static class Node implements Map.Entry { Node parent; Node left; Node right; final K key; V value; int height; Node(Node parent, K key) { this.parent = parent; this.key = key; this.height = 1; } Node copy(Node parent) { Node result = new Node(parent, key); if (left != null) { result.left = left.copy(result); } if (right != null) { result.right = right.copy(result); } result.value = value; result.height = height; return result; } public K getKey() { return key; } public V getValue() { return value; } public V setValue(V value) { V oldValue = this.value; this.value = value; return oldValue; } @Override public boolean equals(Object o) { if (o instanceof Map.Entry) { Map.Entry other = (Map.Entry) o; return (key == null ? other.getKey() == null : key.equals(other.getKey())) && (value == null ? other.getValue() == null : value.equals(other.getValue())); } return false; } @Override public int hashCode() { return (key == null ? 0 : key.hashCode()) ^ (value == null ? 0 : value.hashCode()); } @Override public String toString() { return key + "=" + value; } /** * Returns the next node in an inorder traversal, or null if this is the * last node in the tree. */ Node next() { if (right != null) { return right.first(); } Node node = this; Node parent = node.parent; while (parent != null) { if (parent.left == node) { return parent; } node = parent; parent = node.parent; } return null; } /** * Returns the previous node in an inorder traversal, or null if this is * the first node in the tree. */ public Node prev() { if (left != null) { return left.last(); } Node node = this; Node parent = node.parent; while (parent != null) { if (parent.right == node) { return parent; } node = parent; parent = node.parent; } return null; } /** * Returns the first node in this subtree. */ public Node first() { Node node = this; Node child = node.left; while (child != null) { node = child; child = node.left; } return node; } /** * Returns the last node in this subtree. */ public Node last() { Node node = this; Node child = node.right; while (child != null) { node = child; child = node.right; } return node; } } /** * Walk the nodes of the tree left-to-right or right-to-left. Note that in * descending iterations, {@code next} will return the previous node. */ abstract class MapIterator implements Iterator { protected Node next; protected Node last; protected int expectedModCount = modCount; MapIterator(Node next) { this.next = next; } public boolean hasNext() { return next != null; } protected Node stepForward() { if (next == null) { throw new NoSuchElementException(); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } last = next; next = next.next(); return last; } protected Node stepBackward() { if (next == null) { throw new NoSuchElementException(); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } last = next; next = next.prev(); return last; } public void remove() { if (last == null) { throw new IllegalStateException(); } removeInternal(last); expectedModCount = modCount; last = null; } } /* * View implementations. */ class EntrySet extends AbstractSet> { @Override public int size() { return size; } @Override public Iterator> iterator() { return new MapIterator>(root == null ? null : root.first()) { public Entry next() { return stepForward(); } }; } @Override public boolean contains(Object o) { return o instanceof Entry && findByEntry((Entry) o) != null; } @Override public boolean remove(Object o) { if (!(o instanceof Entry)) { return false; } Node node = findByEntry((Entry) o); if (node == null) { return false; } removeInternal(node); return true; } @Override public void clear() { TreeMap.this.clear(); } } class KeySet extends AbstractSet implements NavigableSet { @Override public int size() { return size; } @Override public Iterator iterator() { return new MapIterator(root == null ? null : root.first()) { public K next() { return stepForward().key; } }; } public Iterator descendingIterator() { return new MapIterator(root == null ? null : root.last()) { public K next() { return stepBackward().key; } }; } @Override public boolean contains(Object o) { return containsKey(o); } @Override public boolean remove(Object key) { return removeInternalByKey(key) != null; } @Override public void clear() { TreeMap.this.clear(); } public Comparator comparator() { return TreeMap.this.comparator(); } /* * Navigable methods. */ public K first() { return firstKey(); } public K last() { return lastKey(); } public K lower(K key) { return lowerKey(key); } public K floor(K key) { return floorKey(key); } public K ceiling(K key) { return ceilingKey(key); } public K higher(K key) { return higherKey(key); } public K pollFirst() { Entry entry = internalPollFirstEntry(); return entry != null ? entry.getKey() : null; } public K pollLast() { Entry entry = internalPollLastEntry(); return entry != null ? entry.getKey() : null; } /* * View factory methods. */ public NavigableSet subSet(K from, boolean fromInclusive, K to, boolean toInclusive) { return TreeMap.this.subMap(from, fromInclusive, to, toInclusive).navigableKeySet(); } public SortedSet subSet(K fromInclusive, K toExclusive) { return TreeMap.this.subMap(fromInclusive, true, toExclusive, false).navigableKeySet(); } public NavigableSet headSet(K to, boolean inclusive) { return TreeMap.this.headMap(to, inclusive).navigableKeySet(); } public SortedSet headSet(K toExclusive) { return TreeMap.this.headMap(toExclusive, false).navigableKeySet(); } public NavigableSet tailSet(K from, boolean inclusive) { return TreeMap.this.tailMap(from, inclusive).navigableKeySet(); } public SortedSet tailSet(K fromInclusive) { return TreeMap.this.tailMap(fromInclusive, true).navigableKeySet(); } public NavigableSet descendingSet() { return new BoundedMap(false, null, NO_BOUND, null, NO_BOUND).navigableKeySet(); } } /* * Bounded views implementations. */ enum Bound { INCLUSIVE { @Override public String leftCap(Object from) { return "[" + from; } @Override public String rightCap(Object to) { return to + "]"; } }, EXCLUSIVE { @Override public String leftCap(Object from) { return "(" + from; } @Override public String rightCap(Object to) { return to + ")"; } }, NO_BOUND { @Override public String leftCap(Object from) { return "."; } @Override public String rightCap(Object to) { return "."; } }; public abstract String leftCap(Object from); public abstract String rightCap(Object to); } /** * A map with optional limits on its range. */ final class BoundedMap extends AbstractMap implements NavigableMap, Serializable { private final transient boolean ascending; private final transient K from; private final transient Bound fromBound; private final transient K to; private final transient Bound toBound; BoundedMap(boolean ascending, K from, Bound fromBound, K to, Bound toBound) { /* * Validate the bounds. In addition to checking that from <= to, we * verify that the comparator supports our bound objects. */ if (fromBound != NO_BOUND && toBound != NO_BOUND) { if (comparator.compare(from, to) > 0) { throw new IllegalArgumentException(from + " > " + to); } } else if (fromBound != NO_BOUND) { comparator.compare(from, from); } else if (toBound != NO_BOUND) { comparator.compare(to, to); } this.ascending = ascending; this.from = from; this.fromBound = fromBound; this.to = to; this.toBound = toBound; } @Override public int size() { return count(entrySet().iterator()); } @Override public boolean isEmpty() { return endpoint(true) == null; } @Override public V get(Object key) { return isInBounds(key) ? TreeMap.this.get(key) : null; } @Override public boolean containsKey(Object key) { return isInBounds(key) && TreeMap.this.containsKey(key); } @Override public V put(K key, V value) { if (!isInBounds(key)) { throw outOfBounds(key, fromBound, toBound); } return putInternal(key, value); } @Override public V remove(Object key) { return isInBounds(key) ? TreeMap.this.remove(key) : null; } /** * Returns true if the key is in bounds. */ @SuppressWarnings("unchecked") // this method throws ClassCastExceptions! private boolean isInBounds(Object key) { return isInBounds((K) key, fromBound, toBound); } /** * Returns true if the key is in bounds. Use this overload with * NO_BOUND to skip bounds checking on either end. */ private boolean isInBounds(K key, Bound fromBound, Bound toBound) { if (fromBound == INCLUSIVE) { if (comparator.compare(key, from) < 0) { return false; // less than from } } else if (fromBound == EXCLUSIVE) { if (comparator.compare(key, from) <= 0) { return false; // less than or equal to from } } if (toBound == INCLUSIVE) { if (comparator.compare(key, to) > 0) { return false; // greater than 'to' } } else if (toBound == EXCLUSIVE) { if (comparator.compare(key, to) >= 0) { return false; // greater than or equal to 'to' } } return true; } /** * Returns the entry if it is in bounds, or null if it is out of bounds. */ private Node bound(Node node, Bound fromBound, Bound toBound) { return node != null && isInBounds(node.getKey(), fromBound, toBound) ? node : null; } /* * Navigable methods. */ public Entry firstEntry() { return immutableCopy(endpoint(true)); } public Entry pollFirstEntry() { Node result = endpoint(true); if (result != null) { removeInternal(result); } return immutableCopy(result); } public K firstKey() { Entry entry = endpoint(true); if (entry == null) { throw new NoSuchElementException(); } return entry.getKey(); } public Entry lastEntry() { return immutableCopy(endpoint(false)); } public Entry pollLastEntry() { Node result = endpoint(false); if (result != null) { removeInternal(result); } return immutableCopy(result); } public K lastKey() { Entry entry = endpoint(false); if (entry == null) { throw new NoSuchElementException(); } return entry.getKey(); } /** * @param first true for the first element, false for the last. */ private Node endpoint(boolean first) { Node node; if (ascending == first) { switch (fromBound) { case NO_BOUND: node = root == null ? null : root.first(); break; case INCLUSIVE: node = find(from, CEILING); break; case EXCLUSIVE: node = find(from, HIGHER); break; default: throw new AssertionError(); } return bound(node, NO_BOUND, toBound); } else { switch (toBound) { case NO_BOUND: node = root == null ? null : root.last(); break; case INCLUSIVE: node = find(to, FLOOR); break; case EXCLUSIVE: node = find(to, LOWER); break; default: throw new AssertionError(); } return bound(node, fromBound, NO_BOUND); } } /** * Performs a find on the underlying tree after constraining it to the * bounds of this view. Examples: * * bound is (A..C) * findBounded(B, FLOOR) stays source.find(B, FLOOR) * * bound is (A..C) * findBounded(C, FLOOR) becomes source.find(C, LOWER) * * bound is (A..C) * findBounded(D, LOWER) becomes source.find(C, LOWER) * * bound is (A..C] * findBounded(D, FLOOR) becomes source.find(C, FLOOR) * * bound is (A..C] * findBounded(D, LOWER) becomes source.find(C, FLOOR) */ private Entry findBounded(K key, Relation relation) { relation = relation.forOrder(ascending); Bound fromBoundForCheck = fromBound; Bound toBoundForCheck = toBound; if (toBound != NO_BOUND && (relation == LOWER || relation == FLOOR)) { int comparison = comparator.compare(to, key); if (comparison <= 0) { key = to; if (toBound == EXCLUSIVE) { relation = LOWER; // 'to' is too high } else if (comparison < 0) { relation = FLOOR; // we already went lower } } toBoundForCheck = NO_BOUND; // we've already checked the upper bound } if (fromBound != NO_BOUND && (relation == CEILING || relation == HIGHER)) { int comparison = comparator.compare(from, key); if (comparison >= 0) { key = from; if (fromBound == EXCLUSIVE) { relation = HIGHER; // 'from' is too low } else if (comparison > 0) { relation = CEILING; // we already went higher } } fromBoundForCheck = NO_BOUND; // we've already checked the lower bound } return bound(find(key, relation), fromBoundForCheck, toBoundForCheck); } public Entry lowerEntry(K key) { return immutableCopy(findBounded(key, LOWER)); } public K lowerKey(K key) { Entry entry = findBounded(key, LOWER); return entry != null ? entry.getKey() : null; } public Entry floorEntry(K key) { return immutableCopy(findBounded(key, FLOOR)); } public K floorKey(K key) { Entry entry = findBounded(key, FLOOR); return entry != null ? entry.getKey() : null; } public Entry ceilingEntry(K key) { return immutableCopy(findBounded(key, CEILING)); } public K ceilingKey(K key) { Entry entry = findBounded(key, CEILING); return entry != null ? entry.getKey() : null; } public Entry higherEntry(K key) { return immutableCopy(findBounded(key, HIGHER)); } public K higherKey(K key) { Entry entry = findBounded(key, HIGHER); return entry != null ? entry.getKey() : null; } public Comparator comparator() { Comparator forward = TreeMap.this.comparator(); if (ascending) { return forward; } else { return Collections.reverseOrder(forward); } } /* * View factory methods. */ private transient BoundedEntrySet entrySet; private transient BoundedKeySet keySet; @Override public Set> entrySet() { BoundedEntrySet result = entrySet; return result != null ? result : (entrySet = new BoundedEntrySet()); } @Override public Set keySet() { return navigableKeySet(); } public NavigableSet navigableKeySet() { BoundedKeySet result = keySet; return result != null ? result : (keySet = new BoundedKeySet()); } public NavigableMap descendingMap() { return new BoundedMap(!ascending, from, fromBound, to, toBound); } public NavigableSet descendingKeySet() { return new BoundedMap(!ascending, from, fromBound, to, toBound).navigableKeySet(); } public NavigableMap subMap(K from, boolean fromInclusive, K to, boolean toInclusive) { Bound fromBound = fromInclusive ? INCLUSIVE : EXCLUSIVE; Bound toBound = toInclusive ? INCLUSIVE : EXCLUSIVE; return subMap(from, fromBound, to, toBound); } public NavigableMap subMap(K fromInclusive, K toExclusive) { return subMap(fromInclusive, INCLUSIVE, toExclusive, EXCLUSIVE); } public NavigableMap headMap(K to, boolean inclusive) { Bound toBound = inclusive ? INCLUSIVE : EXCLUSIVE; return subMap(null, NO_BOUND, to, toBound); } public NavigableMap headMap(K toExclusive) { return subMap(null, NO_BOUND, toExclusive, EXCLUSIVE); } public NavigableMap tailMap(K from, boolean inclusive) { Bound fromBound = inclusive ? INCLUSIVE : EXCLUSIVE; return subMap(from, fromBound, null, NO_BOUND); } public NavigableMap tailMap(K fromInclusive) { return subMap(fromInclusive, INCLUSIVE, null, NO_BOUND); } private NavigableMap subMap(K from, Bound fromBound, K to, Bound toBound) { if (!ascending) { K fromTmp = from; Bound fromBoundTmp = fromBound; from = to; fromBound = toBound; to = fromTmp; toBound = fromBoundTmp; } /* * If both the current and requested bounds are exclusive, the isInBounds check must be * inclusive. For example, to create (C..F) from (A..F), the bound 'F' is in bounds. */ if (fromBound == NO_BOUND) { from = this.from; fromBound = this.fromBound; } else { Bound fromBoundToCheck = fromBound == this.fromBound ? INCLUSIVE : this.fromBound; if (!isInBounds(from, fromBoundToCheck, this.toBound)) { throw outOfBounds(to, fromBoundToCheck, this.toBound); } } if (toBound == NO_BOUND) { to = this.to; toBound = this.toBound; } else { Bound toBoundToCheck = toBound == this.toBound ? INCLUSIVE : this.toBound; if (!isInBounds(to, this.fromBound, toBoundToCheck)) { throw outOfBounds(to, this.fromBound, toBoundToCheck); } } return new BoundedMap(ascending, from, fromBound, to, toBound); } private IllegalArgumentException outOfBounds(Object value, Bound fromBound, Bound toBound) { return new IllegalArgumentException(value + " not in range " + fromBound.leftCap(from) + ".." + toBound.rightCap(to)); } /* * Bounded view implementations. */ abstract class BoundedIterator extends MapIterator { protected BoundedIterator(Node next) { super(next); } @Override protected Node stepForward() { Node result = super.stepForward(); if (next != null && !isInBounds(next.key, NO_BOUND, toBound)) { next = null; } return result; } @Override protected Node stepBackward() { Node result = super.stepBackward(); if (next != null && !isInBounds(next.key, fromBound, NO_BOUND)) { next = null; } return result; } } final class BoundedEntrySet extends AbstractSet> { @Override public int size() { return BoundedMap.this.size(); } @Override public boolean isEmpty() { return BoundedMap.this.isEmpty(); } @Override public Iterator> iterator() { return new BoundedIterator>(endpoint(true)) { public Entry next() { return ascending ? stepForward() : stepBackward(); } }; } @Override public boolean contains(Object o) { if (!(o instanceof Entry)) { return false; } Entry entry = (Entry) o; return isInBounds(entry.getKey()) && findByEntry(entry) != null; } @Override public boolean remove(Object o) { if (!(o instanceof Entry)) { return false; } Entry entry = (Entry) o; return isInBounds(entry.getKey()) && TreeMap.this.entrySet().remove(entry); } } final class BoundedKeySet extends AbstractSet implements NavigableSet { @Override public int size() { return BoundedMap.this.size(); } @Override public boolean isEmpty() { return BoundedMap.this.isEmpty(); } @Override public Iterator iterator() { return new BoundedIterator(endpoint(true)) { public K next() { return (ascending ? stepForward() : stepBackward()).key; } }; } public Iterator descendingIterator() { return new BoundedIterator(endpoint(false)) { public K next() { return (ascending ? stepBackward() : stepForward()).key; } }; } @Override public boolean contains(Object key) { return isInBounds(key) && findByObject(key) != null; } @Override public boolean remove(Object key) { return isInBounds(key) && removeInternalByKey(key) != null; } /* * Navigable methods. */ public K first() { return firstKey(); } public K pollFirst() { Entry entry = pollFirstEntry(); return entry != null ? entry.getKey() : null; } public K last() { return lastKey(); } public K pollLast() { Entry entry = pollLastEntry(); return entry != null ? entry.getKey() : null; } public K lower(K key) { return lowerKey(key); } public K floor(K key) { return floorKey(key); } public K ceiling(K key) { return ceilingKey(key); } public K higher(K key) { return higherKey(key); } public Comparator comparator() { return BoundedMap.this.comparator(); } /* * View factory methods. */ public NavigableSet subSet(K from, boolean fromInclusive, K to, boolean toInclusive) { return subMap(from, fromInclusive, to, toInclusive).navigableKeySet(); } public SortedSet subSet(K fromInclusive, K toExclusive) { return subMap(fromInclusive, toExclusive).navigableKeySet(); } public NavigableSet headSet(K to, boolean inclusive) { return headMap(to, inclusive).navigableKeySet(); } public SortedSet headSet(K toExclusive) { return headMap(toExclusive).navigableKeySet(); } public NavigableSet tailSet(K from, boolean inclusive) { return tailMap(from, inclusive).navigableKeySet(); } public SortedSet tailSet(K fromInclusive) { return tailMap(fromInclusive).navigableKeySet(); } public NavigableSet descendingSet() { return new BoundedMap(!ascending, from, fromBound, to, toBound).navigableKeySet(); } } Object writeReplace() throws ObjectStreamException { return ascending ? new AscendingSubMap(TreeMap.this, from, fromBound, to, toBound) : new DescendingSubMap(TreeMap.this, from, fromBound, to, toBound); } } /** * Returns the number of elements in the iteration. */ static int count(Iterator iterator) { int count = 0; while (iterator.hasNext()) { iterator.next(); count++; } return count; } /* * Serialization */ private static final long serialVersionUID = 919286545866124006L; private void writeObject(ObjectOutputStream stream) throws IOException { stream.putFields().put("comparator", comparator()); stream.writeFields(); stream.writeInt(size); for (Map.Entry entry : entrySet()) { stream.writeObject(entry.getKey()); stream.writeObject(entry.getValue()); } } @SuppressWarnings("unchecked") // we have to trust that keys are Ks and values are Vs private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { GetField fields = stream.readFields(); comparator = (Comparator) fields.get("comparator", null); if (comparator == null) { comparator = (Comparator) NATURAL_ORDER; } int size = stream.readInt(); for (int i = 0; i < size; i++) { putInternal((K) stream.readObject(), (V) stream.readObject()); } } static abstract class NavigableSubMap extends AbstractMap implements Serializable { private static final long serialVersionUID = -2102997345730753016L; TreeMap m; Object lo; Object hi; boolean fromStart; boolean toEnd; boolean loInclusive; boolean hiInclusive; NavigableSubMap(TreeMap delegate, K from, Bound fromBound, K to, Bound toBound) { this.m = delegate; this.lo = from; this.hi = to; this.fromStart = fromBound == NO_BOUND; this.toEnd = toBound == NO_BOUND; this.loInclusive = fromBound == INCLUSIVE; this.hiInclusive = toBound == INCLUSIVE; } @Override public Set> entrySet() { throw new UnsupportedOperationException(); } @SuppressWarnings("unchecked") // we have to trust that the bounds are Ks protected Object readResolve() throws ObjectStreamException { Bound fromBound = fromStart ? NO_BOUND : (loInclusive ? INCLUSIVE : EXCLUSIVE); Bound toBound = toEnd ? NO_BOUND : (hiInclusive ? INCLUSIVE : EXCLUSIVE); boolean ascending = !(this instanceof DescendingSubMap); return m.new BoundedMap(ascending, (K) lo, fromBound, (K) hi, toBound); } } static class DescendingSubMap extends NavigableSubMap { private static final long serialVersionUID = 912986545866120460L; Comparator reverseComparator; DescendingSubMap(TreeMap delegate, K from, Bound fromBound, K to, Bound toBound) { super(delegate, from, fromBound, to, toBound); } } static class AscendingSubMap extends NavigableSubMap { private static final long serialVersionUID = 912986545866124060L; AscendingSubMap(TreeMap delegate, K from, Bound fromBound, K to, Bound toBound) { super(delegate, from, fromBound, to, toBound); } } class SubMap extends AbstractMap implements Serializable { private static final long serialVersionUID = -6520786458950516097L; Object fromKey; Object toKey; boolean fromStart; boolean toEnd; @Override public Set> entrySet() { throw new UnsupportedOperationException(); } @SuppressWarnings("unchecked") // we have to trust that the bounds are Ks protected Object readResolve() throws ObjectStreamException { Bound fromBound = fromStart ? NO_BOUND : INCLUSIVE; Bound toBound = toEnd ? NO_BOUND : EXCLUSIVE; return new BoundedMap(true, (K) fromKey, fromBound, (K) toKey, toBound); } } }