You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by le...@apache.org on 2007/06/22 09:32:13 UTC
svn commit: r549743 [2/3] - in
/harmony/enhanced/classlib/branches/java6/modules/luni/src:
main/java/java/util/ test/api/common/tests/api/java/util/
Modified: harmony/enhanced/classlib/branches/java6/modules/luni/src/main/java/java/util/TreeMap.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/branches/java6/modules/luni/src/main/java/java/util/TreeMap.java?view=diff&rev=549743&r1=549742&r2=549743
==============================================================================
--- harmony/enhanced/classlib/branches/java6/modules/luni/src/main/java/java/util/TreeMap.java (original)
+++ harmony/enhanced/classlib/branches/java6/modules/luni/src/main/java/java/util/TreeMap.java Fri Jun 22 00:32:12 2007
@@ -23,82 +23,125 @@
import java.io.Serializable;
/**
- * TreeMap is an implementation of SortedMap. All optional operations are
+ * TreeMap is an implementation of NavigableMap. All optional operations are
* supported, adding and removing. The values can be any objects. The keys can
* be any objects which are comparable to each other either using their natural
* order or a specified Comparator.
+ *
+ * @param <K>
+ * type of key
+ * @param <V>
+ * type of value
+ *
* @since 1.2
*/
-public class TreeMap<K, V> extends AbstractMap<K, V> implements SortedMap<K, V>, Cloneable,
- Serializable {
- private static final long serialVersionUID = 919286545866124006L;
+public class TreeMap<K, V> extends AbstractMap<K, V> implements
+ NavigableMap<K, V>, Cloneable, Serializable {
+ private static final long serialVersionUID = 919286545866124006L;
- transient int size;
+ transient int size;
transient Entry<K, V> root;
- private Comparator<? super K> comparator;
+ Comparator<? super K> comparator;
transient int modCount;
transient Set<Map.Entry<K, V>> entrySet;
- /**
- * Entry is an internal class which is used to hold the entries of a
- * TreeMap.
- */
- static class Entry<K, V> extends MapEntry<K, V> {
- Entry<K, V> parent, left, right;
+ transient NavigableMap<K, V> descendingMap;
- boolean color;
+ transient NavigableSet<K> navigableKeySet;
- Entry(K key) {
- super(key);
- }
+ /**
+ * Entry is an internal class which is used to hold the entries of a
+ * TreeMap.
+ */
+ static class Entry<K, V> extends MapEntry<K, V> {
+ Entry<K, V> parent, left, right;
- Entry(K key, V value) {
- super(key, value);
- }
+ boolean color;
+
+ Entry(K theKey) {
+ super(theKey);
+ }
+
+ Entry(K theKey, V theValue) {
+ super(theKey, theValue);
+ }
- @SuppressWarnings("unchecked")
- Entry<K, V> clone(Entry<K, V> parent) {
- Entry<K, V> clone = (Entry<K, V>) super.clone();
- clone.parent = parent;
- if (left != null) {
+ @SuppressWarnings("unchecked")
+ Entry<K, V> clone(Entry<K, V> theParent) {
+ Entry<K, V> clone = (Entry<K, V>) super.clone();
+ clone.parent = theParent;
+ if (left != null) {
clone.left = left.clone(clone);
}
- if (right != null) {
+ if (right != null) {
clone.right = right.clone(clone);
}
- return clone;
- }
- }
-
- @SuppressWarnings("unchecked")
- private static <T> Comparable<T> toComparable(T obj) {
- return (Comparable<T>)obj;
+ return clone;
+ }
}
- private static class AbstractMapIterator <K,V> {
- TreeMap<K, V> backingMap;
+ /*
+ * It is a "work-around" method because of a RI's bug. The RI's bug is that:
+ * if the TreeMap has no comparator or its comparator is not null-tolerable,
+ * it can not put a null-key entry into this TreeMap.But RI can do it when
+ * the TreeMap is empty, and can not do it when the TreeMap is not empty.It
+ * is best for Harmony to follow RI's behavior for legacy reason. This
+ * method is to check if this TreeMap is constructed by that bug.It can be
+ * easily removed when the bug is fixed in the future.
+ */
+ boolean isRootWithIllegalNullKey() {
+ if (null != root) {
+ if (null == root.key && null == comparator) {
+ return true;
+ } else if (null != comparator) {
+ try {
+ comparator.compare(root.key, root.key);
+ } catch (NullPointerException e) {
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ private static abstract class AbstractSubMapIterator<K, V> {
+ final NavigableSubMap<K, V> subMap;
+
int expectedModCount;
- TreeMap.Entry<K, V> node;
- TreeMap.Entry<K, V> lastNode;
- AbstractMapIterator(TreeMap<K, V> map, Entry<K, V> startNode) {
- backingMap = map;
- expectedModCount = map.modCount;
- node = startNode;
- }
+ TreeMap.Entry<K, V> node;
- public boolean hasNext() {
- return node != null;
+ TreeMap.Entry<K, V> lastNode;
+
+ TreeMap.Entry<K, V> boundaryNode;
+
+ boolean getToEnd = false;
+
+ AbstractSubMapIterator(final NavigableSubMap<K, V> map) {
+ subMap = map;
+ expectedModCount = subMap.backingMap.modCount;
+ node = getStartNode();
+
+ boundaryNode = getBoundaryNode();
+ if (null == boundaryNode) {
+ node = null;
+ }
}
- final public void remove() {
- if (expectedModCount == backingMap.modCount) {
+ public final void remove() {
+ if (expectedModCount == subMap.backingMap.modCount) {
if (lastNode != null) {
- backingMap.rbDelete(lastNode);
+ if (lastNode.key == this.boundaryNode.key) {
+ node = null;
+ }
+ subMap.backingMap.rbDelete(lastNode);
+ if( null != node && node.key == lastNode.key) {
+ node = lastNode;
+ }
lastNode = null;
expectedModCount++;
} else {
@@ -109,1176 +152,1765 @@
}
}
- final void makeNext() {
- if (expectedModCount != backingMap.modCount) {
+ TreeMap.Entry<K, V> getNext() {
+ if (hasNext()) {
+ if (expectedModCount == subMap.backingMap.modCount) {
+ lastNode = node;
+ if (node.key == this.boundaryNode.key) {
+ node = null;
+ } else {
+ node = getRealNext(node);
+ }
+ return lastNode;
+ }
throw new ConcurrentModificationException();
- } else if (node == null) {
- throw new NoSuchElementException();
- }
- lastNode = node;
- node = TreeMap.successor(node);
}
+ throw new NoSuchElementException();
}
- private static class UnboundedEntryIterator <K, V> extends AbstractMapIterator<K, V> implements Iterator<Map.Entry<K, V>> {
-
- UnboundedEntryIterator(TreeMap<K, V> map, Entry<K, V> startNode) {
- super(map, startNode);
- }
+ abstract TreeMap.Entry<K, V> getStartNode();
- UnboundedEntryIterator(TreeMap<K, V> map) {
- super(map, map.root == null ? null : TreeMap.minimum(map.root));
- }
+ abstract TreeMap.Entry<K, V> getRealNext(TreeMap.Entry<K, V> entry);
- public Map.Entry<K, V> next() {
- makeNext();
- return lastNode;
- }
- }
+ abstract boolean hasNext();
+
+ abstract TreeMap.Entry<K, V> getBoundaryNode();
+ }
- static class UnboundedKeyIterator <K, V> extends AbstractMapIterator<K, V> implements Iterator<K> {
- public UnboundedKeyIterator(TreeMap<K, V> treeMap, Entry<K, V> entry) {
- super(treeMap, entry);
- }
+ private abstract static class AscendingSubMapIterator<K, V> extends
+ AbstractSubMapIterator<K, V> {
+
+ AscendingSubMapIterator(NavigableSubMap<K, V> map) {
+ super(map);
+ }
+
+ final TreeMap.Entry<K, V> getBoundaryNode() {
+ if (subMap.hasEnd) {
+ return subMap.endInclusive ? subMap
+ .smallerOrEqualEntry(subMap.endKey) : subMap
+ .smallerEntry(subMap.endKey);
+ }
+ return subMap.theBiggestEntry();
+ }
- public UnboundedKeyIterator(TreeMap<K, V> map) {
- super(map, map.root == null ? null : TreeMap.minimum(map.root));
+ @Override
+ final TreeMap.Entry<K, V> getStartNode() {
+ if (subMap.hasStart) {
+ return subMap.startInclusive ? subMap
+ .biggerOrEqualEntry(subMap.startKey) : subMap
+ .biggerEntry(subMap.startKey);
}
+ return subMap.theSmallestEntry();
+ }
- public K next() {
- makeNext();
- return lastNode.key;
- }
+ @Override
+ final Entry<K, V> getRealNext(Entry<K, V> entry) {
+ return TreeMap.successor(entry);
}
- static class UnboundedValueIterator <K, V> extends AbstractMapIterator<K, V> implements Iterator<V> {
-
- public UnboundedValueIterator(TreeMap<K, V> treeMap, Entry<K, V> startNode) {
- super(treeMap, startNode);
- }
-
- public UnboundedValueIterator(TreeMap<K, V> map) {
- super(map, map.root == null ? null : TreeMap.minimum(map.root));
- }
-
- public V next() {
- makeNext();
- return lastNode.value;
- }
+ @Override
+ public final boolean hasNext() {
+// if (null != node) {
+// if (subMap.backingMap.root == node
+// && subMap.backingMap.isRootWithIllegalNullKey()) {
+// return true;
+// }
+// return subMap.checkUpperBound(node.key);
+// }
+// return false;
+ return null!=node;
}
- private static class ComparatorBoundedIterator<K, V> extends AbstractMapIterator<K, V> {
- private final K endKey;
+ }
- private final Comparator<? super K> cmp;
+ static class AscendingSubMapEntryIterator<K, V> extends
+ AscendingSubMapIterator<K, V> implements Iterator<Map.Entry<K, V>> {
- ComparatorBoundedIterator(TreeMap<K, V> map, Entry<K, V> startNode, K end) {
- super(map, startNode);
- endKey = end;
- cmp = map.comparator();
+ AscendingSubMapEntryIterator(NavigableSubMap<K, V> map) {
+ super(map);
}
- final void cleanNext() {
- if (node != null && cmp.compare(endKey, node.key) <= 0) {
- node = null;
- }
+ public final Map.Entry<K, V> next() {
+ return getNext();
}
+ }
- @Override
- public boolean hasNext() {
- return (node != null && endKey != null) && (cmp.compare(node.key, endKey) < 0);
+ static class AscendingSubMapKeyIterator<K, V> extends
+ AscendingSubMapIterator<K, V> implements Iterator<K> {
+
+ AscendingSubMapKeyIterator(NavigableSubMap<K, V> map) {
+ super(map);
+ }
+
+ public final K next() {
+ return getNext().key;
}
}
- private static class ComparatorBoundedEntryIterator<K, V> extends
- ComparatorBoundedIterator<K, V> implements Iterator<Map.Entry<K, V>> {
+ private abstract static class DescendingSubMapIterator<K, V> extends
+ AbstractSubMapIterator<K, V> {
+
+ DescendingSubMapIterator(NavigableSubMap<K, V> map) {
+ super(map);
+ }
+
+ @Override
+ final TreeMap.Entry<K, V> getStartNode() {
+ if (subMap.hasEnd) {
+ return subMap.endInclusive ? subMap
+ .smallerOrEqualEntry(subMap.endKey) : subMap
+ .smallerEntry(subMap.endKey);
+ }
+ return subMap.theBiggestEntry();
+ }
+
+ final TreeMap.Entry<K, V> getBoundaryNode() {
+ if (subMap.hasStart) {
+ return subMap.startInclusive ? subMap
+ .biggerOrEqualEntry(subMap.startKey) : subMap
+ .biggerEntry(subMap.startKey);
+ }
+ return subMap.theSmallestEntry();
+ }
- ComparatorBoundedEntryIterator(TreeMap<K, V> map, Entry<K, V> startNode, K end) {
- super(map, startNode, end);
+ @Override
+ final Entry<K, V> getRealNext(Entry<K, V> entry) {
+ return TreeMap.predecessor(entry);
}
- public Map.Entry<K, V> next() {
- makeNext();
- cleanNext();
- return lastNode;
+ @Override
+ public final boolean hasNext() {
+// if (null != node) {
+// if (subMap.backingMap.root == node
+// && subMap.backingMap.isRootWithIllegalNullKey()) {
+// return true;
+// }
+// return subMap.checkLowerBound(node.key);
+// }
+// return false;
+ return node != null;
}
}
- private static class ComparatorBoundedKeyIterator<K, V> extends
- ComparatorBoundedIterator<K, V> implements Iterator<K> {
+ static class DescendingSubMapEntryIterator<K, V> extends
+ DescendingSubMapIterator<K, V> implements Iterator<Map.Entry<K, V>> {
- ComparatorBoundedKeyIterator(TreeMap<K, V> map, Entry<K, V> startNode, K end) {
- super(map, startNode, end);
+ DescendingSubMapEntryIterator(NavigableSubMap<K, V> map) {
+ super(map);
}
- public K next() {
- makeNext();
- cleanNext();
- return lastNode.key;
+ public final Map.Entry<K, V> next() {
+ return getNext();
}
}
- private static class ComparatorBoundedValueIterator<K, V> extends
- ComparatorBoundedIterator<K, V> implements Iterator<V> {
+ static class DescendingSubMapKeyIterator<K, V> extends
+ DescendingSubMapIterator<K, V> implements Iterator<K> {
- ComparatorBoundedValueIterator(TreeMap<K, V> map, Entry<K, V> startNode, K end) {
- super(map, startNode, end);
+ DescendingSubMapKeyIterator(NavigableSubMap<K, V> map) {
+ super(map);
}
- public V next() {
- makeNext();
- cleanNext();
- return lastNode.value;
+ public final K next() {
+ return getNext().key;
}
}
- private static class ComparableBoundedIterator<K, V> extends AbstractMapIterator<K, V> {
- private final Comparable<K> endKey;
+ /*
+ * Entry set of sub-maps, must override methods which check the range. add
+ * or addAll operations are disabled by default.
+ */
+ static abstract class SubMapEntrySet<K, V> extends
+ AbstractSet<Map.Entry<K, V>> {
+ final NavigableSubMap<K, V> subMap;
- public ComparableBoundedIterator(TreeMap<K, V> treeMap, Entry<K, V> entry,
- Comparable<K> endKey) {
- super(treeMap, entry);
- this.endKey = endKey;
+ SubMapEntrySet(NavigableSubMap<K, V> map) {
+ subMap = map;
}
- final void cleanNext() {
- if ((node != null) && (endKey.compareTo(node.key) <= 0)) {
- node = null;
- }
+ @Override
+ public boolean isEmpty() {
+ return 0 == size();
}
@Override
- public boolean hasNext() {
- return (node != null) && (endKey.compareTo(node.key) > 0);
+ public int size() {
+ int size = 0;
+ Iterator<Map.Entry<K, V>> it = iterator();
+ while (it.hasNext()) {
+ size++;
+ it.next();
+ }
+ return size;
}
- }
-
- private static class ComparableBoundedEntryIterator<K, V> extends
- ComparableBoundedIterator<K, V> implements Iterator<Map.Entry<K, V>> {
- ComparableBoundedEntryIterator(TreeMap<K, V> map, Entry<K, V> startNode,
- Comparable<K> end) {
- super(map, startNode, end);
+ @SuppressWarnings("unchecked")
+ @Override
+ public boolean contains(Object object) {
+ if (object instanceof Map.Entry) {
+ Map.Entry<K, V> entry = (Map.Entry<K, V>) object;
+ K key = entry.getKey();
+ if (subMap.isInRange(key)) {
+ V v1 = subMap.get(key), v2 = entry.getValue();
+ return (v1 == null) ? v2 == null : v1.equals(v2);
+ }
+ }
+ return false;
}
- public Map.Entry<K, V> next() {
- makeNext();
- cleanNext();
- return lastNode;
+ @SuppressWarnings("unchecked")
+ @Override
+ /*
+ * Must added, because it need check the range, and used in
+ * clear(),removeAll() methods.
+ */
+ public boolean remove(Object object) {
+ if (object instanceof Map.Entry) {
+ TreeMap.Entry<K, V> entry = (TreeMap.Entry<K, V>) object;
+ K key = entry.getKey();
+ if (subMap.isInRange(key)) {
+ TreeMap.Entry<K, V> node = subMap.backingMap.find(key);
+ if (node == null) {
+ return false;
+ }
+ V v1 = node.value, v2 = entry.getValue();
+ if ((v1 == null) ? (v2 == null) : v1.equals(v2)) {
+ subMap.backingMap.rbDelete(node);
+ return true;
+ }
+ }
+ }
+ return false;
}
+ @Override
+ public abstract Iterator<Map.Entry<K, V>> iterator();
}
- private static class ComparableBoundedKeyIterator<K, V> extends
- ComparableBoundedIterator<K, V> implements Iterator<K> {
+ static class AscendingSubMapEntrySet<K, V> extends SubMapEntrySet<K, V> {
- ComparableBoundedKeyIterator(TreeMap<K, V> map, Entry<K, V> startNode, Comparable<K> end) {
- super(map, startNode, end);
+ AscendingSubMapEntrySet(NavigableSubMap<K, V> map) {
+ super(map);
}
- public K next() {
- makeNext();
- cleanNext();
- return lastNode.key;
+ @Override
+ public final Iterator<Map.Entry<K, V>> iterator() {
+ return new AscendingSubMapEntryIterator<K, V>(subMap);
}
}
- private static class ComparableBoundedValueIterator<K, V> extends
- ComparableBoundedIterator<K, V> implements Iterator<V> {
+ static class DescendingSubMapEntrySet<K, V> extends SubMapEntrySet<K, V> {
- ComparableBoundedValueIterator(TreeMap<K, V> map, Entry<K, V> startNode,
- Comparable<K> end) {
- super(map, startNode, end);
+ DescendingSubMapEntrySet(NavigableSubMap<K, V> map) {
+ super(map);
}
- public V next() {
- makeNext();
- cleanNext();
- return lastNode.value;
+ @Override
+ public final Iterator<Map.Entry<K, V>> iterator() {
+ return new DescendingSubMapEntryIterator<K, V>(subMap);
}
}
- static final class SubMap<K,V> extends AbstractMap<K,V> implements SortedMap<K,V>, Serializable {
- private static final long serialVersionUID = -6520786458950516097L;
+ static abstract class SubMapKeySet<K> extends AbstractSet<K> implements
+ NavigableSet<K> {
+ final NavigableSubMap<K, K> subMap;
- private TreeMap<K,V> backingMap;
+ NavigableSet<K> descendingSet;
- boolean hasStart, hasEnd;
+ SubMapKeySet(NavigableSubMap<K, K> map) {
+ subMap = map;
+ }
- K startKey, endKey;
+ public Comparator<? super K> comparator() {
+ return subMap.backingMap.comparator();
+ }
- transient Set<Map.Entry<K,V>> entrySet = null;
+ @Override
+ public boolean contains(Object object) {
+ return subMap.backingMap.containsKey(object);
+ }
- SubMap(K start, TreeMap<K,V> map) {
- backingMap = map;
- hasStart = true;
- startKey = start;
- }
+ @Override
+ public boolean isEmpty() {
+ return size() == 0;
+ }
- SubMap(K start, TreeMap<K,V> map, K end) {
- backingMap = map;
- hasStart = hasEnd = true;
- startKey = start;
- endKey = end;
- }
-
- SubMap(TreeMap<K,V> map, K end) {
- backingMap = map;
- hasEnd = true;
- endKey = end;
+ @Override
+ public int size() {
+ Iterator<K> it = iterator();
+ int size = 0;
+ while (it.hasNext()) {
+ it.next();
+ size++;
}
+ return size;
+ }
- private void checkRange(K key) {
- Comparator<? super K> cmp = backingMap.comparator;
- if (cmp == null) {
- Comparable<K> object = toComparable(key);
- if (hasStart && object.compareTo(startKey) < 0) {
- throw new IllegalArgumentException();
- }
- if (hasEnd && object.compareTo(endKey) > 0) {
- throw new IllegalArgumentException();
- }
- } else {
- if (hasStart
- && backingMap.comparator().compare(key, startKey) < 0) {
- throw new IllegalArgumentException();
- }
- if (hasEnd && backingMap.comparator().compare(key, endKey) > 0) {
- throw new IllegalArgumentException();
- }
- }
- }
+ @Override
+ public boolean remove(Object object) {
+ return null != subMap.remove(object);
+ }
- private boolean isInRange(K key) {
- Comparator<? super K> cmp = backingMap.comparator;
- if (cmp == null) {
- Comparable<K> object = toComparable(key);
- if (hasStart && object.compareTo(startKey) < 0) {
- return false;
- }
- if (hasEnd && object.compareTo(endKey) >= 0) {
- return false;
- }
- } else {
- if (hasStart && cmp.compare(key, startKey) < 0) {
- return false;
- }
- if (hasEnd && cmp.compare(key, endKey) >= 0) {
- return false;
- }
- }
- return true;
- }
+ @Override
+ public abstract Iterator<K> iterator();
- private boolean checkUpperBound(K key) {
- if (hasEnd) {
- Comparator<? super K> cmp = backingMap.comparator;
- if (cmp == null) {
- return (toComparable(key).compareTo(endKey) < 0);
- }
- return (cmp.compare(key, endKey) < 0);
- }
- return true;
- }
+ public abstract Iterator<K> descendingIterator();
- private boolean checkLowerBound(K key) {
- if (hasStart) {
- Comparator<? super K> cmp = backingMap.comparator;
- if (cmp == null) {
- return (toComparable(key).compareTo(startKey) >= 0);
- }
- return (cmp.compare(key, startKey) >= 0);
- }
- return true;
- }
+ public K first() {
+ return subMap.firstKey();
+ }
- public Comparator<? super K> comparator() {
- return backingMap.comparator();
- }
+ public K last() {
+ return subMap.lastKey();
+ }
- @SuppressWarnings("unchecked")
- @Override
- public boolean containsKey(Object key) {
- if (isInRange((K)key)) {
- return backingMap.containsKey(key);
- }
- return false;
- }
+ public K pollFirst() {
+ Map.Entry<K, K> entry = subMap.pollFirstEntry();
+ return (null == entry) ? null : entry.getKey();
+ }
- @Override
- public Set<Map.Entry<K,V>> entrySet() {
- if(entrySet==null) {
- entrySet = new SubMapEntrySet<K,V>(this);
- }
- return entrySet;
- }
+ public K pollLast() {
+ Map.Entry<K, K> entry = subMap.pollLastEntry();
+ return (null == entry) ? null : entry.getKey();
+ }
- public K firstKey() {
- TreeMap.Entry<K,V> node = firstEntry();
- if (node != null ) {
- return node.key;
- }
- throw new NoSuchElementException();
- }
+ public K higher(K key) {
+ return subMap.higherKey(key);
+ }
- TreeMap.Entry<K,V> firstEntry() {
- if (!hasStart) {
- TreeMap.Entry<K,V> root = backingMap.root;
- return (root == null) ? null : minimum(backingMap.root);
- }
- TreeMap.Entry<K,V> node = backingMap.findAfter(startKey);
- if (node != null && checkUpperBound(node.key)) {
- return node;
- }
- return null;
- }
+ public K lower(K key) {
+ return subMap.lowerKey(key);
+ }
- @SuppressWarnings("unchecked")
- @Override
- public V get(Object key) {
- if (isInRange((K)key)) {
- return backingMap.get(key);
- }
- return null;
- }
+ public K ceiling(K key) {
+ return subMap.ceilingKey(key);
+ }
- public SortedMap<K,V> headMap(K endKey) {
- checkRange(endKey);
- if (hasStart) {
- return new SubMap<K,V>(startKey, backingMap, endKey);
- }
- return new SubMap<K,V>(backingMap, endKey);
- }
+ public K floor(K key) {
+ return subMap.floorKey(key);
+ }
- @Override
- public boolean isEmpty() {
- if (hasStart) {
- TreeMap.Entry<K,V> node = backingMap.findAfter(startKey);
- return node == null || !checkUpperBound(node.key);
- }
- return backingMap.findBefore(endKey) == null;
- }
+ public NavigableSet<K> descendingSet() {
+ return (null != descendingSet) ? descendingSet
+ : (descendingSet = new TreeSet<K>(subMap.descendingMap()));
+ }
- @Override
- public Set<K> keySet() {
- if (keySet == null) {
- keySet = new SubMapKeySet<K,V>(this);
- }
- return keySet;
- }
+ public SortedSet<K> subSet(K start, K end) {
+ return subSet(start, true, end, false);
+ }
- public K lastKey() {
- if (!hasEnd) {
- return backingMap.lastKey();
- }
- TreeMap.Entry<K,V> node = backingMap.findBefore(endKey);
- if (node != null && checkLowerBound(node.key)) {
- return node.key;
- }
- throw new NoSuchElementException();
- }
+ public SortedSet<K> headSet(K end) {
+ return headSet(end, false);
+ }
- @Override
- public V put(K key, V value) {
- if (isInRange(key)) {
- return backingMap.put(key, value);
- }
- throw new IllegalArgumentException();
- }
+ public SortedSet<K> tailSet(K start) {
+ return tailSet(start, true);
+ }
- @SuppressWarnings("unchecked")
- @Override
- public V remove(Object key) {
- if (isInRange((K)key)) {
- return backingMap.remove(key);
- }
- return null;
- }
-
- public SortedMap<K,V> subMap(K startKey, K endKey) {
- checkRange(startKey);
- checkRange(endKey);
- Comparator<? super K> c = backingMap.comparator();
- if (c == null) {
- if (toComparable(startKey).compareTo(endKey) <= 0) {
- return new SubMap<K,V>(startKey, backingMap, endKey);
- }
- } else {
- if (c.compare(startKey, endKey) <= 0) {
- return new SubMap<K,V>(startKey, backingMap, endKey);
- }
- }
- throw new IllegalArgumentException();
+ @SuppressWarnings("unchecked")
+ public NavigableSet<K> subSet(K start, boolean startInclusive, K end,
+ boolean endInclusive) {
+ // copied from TreeSet
+ if (subMap.backingMap.keyCompare(start, end) <= 0) {
+ return new TreeSet<K>(subMap.subMap(start, startInclusive, end,
+ endInclusive));
}
+ throw new IllegalArgumentException();
+ }
- public SortedMap<K,V> tailMap(K startKey) {
- checkRange(startKey);
- if (hasEnd) {
- return new SubMap<K,V>(startKey, backingMap, endKey);
- }
- return new SubMap<K,V>(startKey, backingMap);
- }
+ @SuppressWarnings("unchecked")
+ public NavigableSet<K> headSet(K end, boolean endInclusive) {
+ // copied from TreeSet
+ // Check for errors
+ subMap.backingMap.keyCompare(end, end);
+ return new TreeSet<K>(subMap.headMap(end, endInclusive));
+ }
- @Override
- public Collection<V> values() {
- if(valuesCollection==null) {
- valuesCollection = new SubMapValuesCollection<K,V>(this);
- }
- return valuesCollection;
- }
+ @SuppressWarnings("unchecked")
+ public NavigableSet<K> tailSet(K start, boolean startInclusive) {
+ // copied from TreeSet
+ // Check for errors
+ subMap.backingMap.keyCompare(start, start);
+ return new TreeSet<K>(subMap.tailMap(start, startInclusive));
}
+ }
- static class SubMapEntrySet<K,V> extends AbstractSet<Map.Entry<K,V>> implements Set<Map.Entry<K,V>> {
- SubMap<K,V> subMap;
+ static class AscendingSubMapKeySet<K> extends SubMapKeySet<K> {
+ AscendingSubMapKeySet(NavigableSubMap<K, K> map) {
+ super(map);
+ }
- SubMapEntrySet(SubMap<K,V> map) {
- subMap = map;
- }
+ @Override
+ public final Iterator<K> iterator() {
+ return new AscendingSubMapKeyIterator<K, K>(subMap);
+ }
- @Override
- public boolean isEmpty() {
- return subMap.isEmpty();
- }
+ @Override
+ public final Iterator<K> descendingIterator() {
+ return new DescendingSubMapKeyIterator<K, K>(subMap);
+ }
+ }
- @Override
- public Iterator<Map.Entry<K,V>> iterator() {
- TreeMap.Entry<K,V> startNode = subMap.firstEntry();
- if (subMap.hasEnd) {
- Comparator<? super K> cmp = subMap.comparator();
- if (cmp == null) {
- return new ComparableBoundedEntryIterator<K,V>(subMap.backingMap, startNode, toComparable(subMap.endKey));
- }
- return new ComparatorBoundedEntryIterator<K,V>(subMap.backingMap, startNode, subMap.endKey);
- }
- return new UnboundedEntryIterator<K,V>(subMap.backingMap, startNode);
- }
+ static class DescendingSubMapKeySet<K> extends SubMapKeySet<K> {
+ DescendingSubMapKeySet(NavigableSubMap<K, K> map) {
+ super(map);
+ }
- @Override
- public int size() {
- int size = 0;
- Iterator<Map.Entry<K,V>> it = iterator();
- while (it.hasNext()) {
- size++;
- it.next();
- }
- return size;
- }
-
- @SuppressWarnings("unchecked")
- @Override
- public boolean contains(Object object) {
- if (object instanceof Map.Entry) {
- Map.Entry<K,V> entry = (Map.Entry<K,V>) object;
- K key = entry.getKey();
- if (subMap.isInRange(key)) {
- V v1 = subMap.get(key), v2 = entry.getValue();
- return v1 == null ? v2 == null : v1.equals(v2);
- }
- }
- return false;
- }
+ @Override
+ public final Iterator<K> iterator() {
+ return new DescendingSubMapKeyIterator<K, K>(subMap);
+ }
+ @Override
+ public final Iterator<K> descendingIterator() {
+ return new AscendingSubMapKeyIterator<K, K>(subMap);
}
+ }
- static class SubMapKeySet<K,V> extends AbstractSet<K> implements Set<K> {
- SubMap<K,V> subMap;
+ static abstract class NavigableSubMap<K, V> extends AbstractMap<K, V>
+ implements NavigableMap<K, V>, Serializable {
- SubMapKeySet(SubMap<K,V> map) {
- subMap = map;
- }
+ final TreeMap<K, V> backingMap;
- @Override
- public boolean contains(Object object) {
- return subMap.containsKey(object);
- }
+ final K startKey, endKey;
- @Override
- public boolean isEmpty() {
- return subMap.isEmpty();
- }
+ final boolean hasStart, hasEnd;
- @Override
- public int size() {
- int size = 0;
- Iterator<K> it = iterator();
- while (it.hasNext()) {
- size++;
- it.next();
- }
- return size;
- }
+ final boolean startInclusive, endInclusive;
- @Override
- public Iterator<K> iterator() {
- TreeMap.Entry<K,V> startNode = subMap.firstEntry();
- if (subMap.hasEnd) {
- Comparator<? super K> cmp = subMap.comparator();
- if (cmp == null) {
- return new ComparableBoundedKeyIterator<K,V>(subMap.backingMap, startNode, toComparable(subMap.endKey));
- }
- return new ComparatorBoundedKeyIterator<K,V>(subMap.backingMap, startNode, subMap.endKey);
- }
- return new UnboundedKeyIterator<K,V>(subMap.backingMap, startNode);
- }
+ NavigableSubMap(final K start, final boolean startKeyInclusive,
+ final TreeMap<K, V> map, final K end,
+ final boolean endKeyInclusive) {
+ backingMap = map;
+ hasStart = hasEnd = true;
+ startKey = start;
+ endKey = end;
+ startInclusive = startKeyInclusive;
+ endInclusive = endKeyInclusive;
+ }
+
+ NavigableSubMap(final K start, final boolean startKeyInclusive,
+ final TreeMap<K, V> map) {
+ backingMap = map;
+ hasStart = true;
+ hasEnd = false;
+ startKey = start;
+ endKey = null;
+ startInclusive = startKeyInclusive;
+ endInclusive = false;
+ }
+
+ NavigableSubMap(final TreeMap<K, V> map, final K end,
+ final boolean endKeyInclusive) {
+ backingMap = map;
+ hasStart = false;
+ hasEnd = true;
+ startKey = null;
+ endKey = end;
+ startInclusive = false;
+ endInclusive = endKeyInclusive;
+ }
+
+ // the whole TreeMap
+ NavigableSubMap(final TreeMap<K, V> map) {
+ backingMap = map;
+ hasStart = hasEnd = false;
+ startKey = endKey = null;
+ startInclusive = endInclusive = false;
}
- static class SubMapValuesCollection<K,V> extends AbstractCollection<V> {
- SubMap<K,V> subMap;
+ /*
+ * The basic public methods.
+ */
+
+ public Comparator<? super K> comparator() {
+ return backingMap.comparator();
+ }
- public SubMapValuesCollection(SubMap<K,V> subMap) {
- this.subMap = subMap;
+ @SuppressWarnings("unchecked")
+ @Override
+ public boolean containsKey(Object key) {
+ checkNull(key);
+ if (isInRange((K) key)) {
+ return backingMap.containsKey(key);
+ }
+ return false;
+ }
+
+ private void checkNull (Object key) {
+ if (null == key && null ==comparator()){
+ throw new NullPointerException();
}
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return size() == 0;
+ }
+
+ @Override
+ public int size() {
+ return entrySet().size();
+ }
- @Override
- public boolean isEmpty() {
- return subMap.isEmpty();
+ @Override
+ public V put(K key, V value) {
+ checkNull(key);
+ if (isInRange(key)) {
+ return backingMap.put(key, value);
}
+ throw new IllegalArgumentException();
+ }
- @Override
- public Iterator<V> iterator() {
- TreeMap.Entry<K,V> startNode = subMap.firstEntry();
- if (subMap.hasEnd) {
- Comparator<? super K> cmp = subMap.comparator();
- if (cmp == null) {
- return new ComparableBoundedValueIterator<K,V>(subMap.backingMap, startNode, toComparable(subMap.endKey));
- }
- return new ComparatorBoundedValueIterator<K,V>(subMap.backingMap, startNode, subMap.endKey);
- }
- return new UnboundedValueIterator<K,V>(subMap.backingMap, startNode);
+ @SuppressWarnings("unchecked")
+ @Override
+ public V get(Object key) {
+ checkNull(key);
+ if (isInRange((K) key)) {
+ return backingMap.get(key);
}
+ return null;
+ }
- @Override
- public int size() {
- int cnt = 0;
- for (Iterator<V> it = iterator(); it.hasNext();) {
- it.next();
- cnt++;
- }
- return cnt;
+ @SuppressWarnings("unchecked")
+ @Override
+ public V remove(Object key) {
+ checkNull(key);
+ if (isInRange((K) key)) {
+ return backingMap.remove(key);
}
+ return null;
}
- /**
- * Constructs a new empty instance of TreeMap.
- *
- */
- public TreeMap() {
- super();
- }
+ /*
+ * The navigable methods.
+ */
- /**
- * Constructs a new empty instance of TreeMap which uses the specified
- * Comparator.
- *
- * @param comparator
- * the Comparator
- */
- public TreeMap(Comparator<? super K> comparator) {
- this.comparator = comparator;
- }
+ public abstract Map.Entry<K, V> firstEntry();
- /**
- * Constructs a new instance of TreeMap containing the mappings from the
- * specified Map and using the natural ordering.
- *
- * @param map
- * the mappings to add
- *
- * @exception ClassCastException
- * when a key in the Map does not implement the Comparable
- * interface, or they keys in the Map cannot be compared
- */
- public TreeMap(Map<? extends K,? extends V> map) {
- this();
- putAll(map);
- }
+ public abstract Map.Entry<K, V> lastEntry();
- /**
- * Constructs a new instance of TreeMap containing the mappings from the
- * specified SortedMap and using the same Comparator.
- *
- * @param map
- * the mappings to add
- */
- public TreeMap(SortedMap<K,? extends V> map) {
- this(map.comparator());
- Iterator<? extends Map.Entry<K, ? extends V>> it = map.entrySet().iterator();
- if (it.hasNext()) {
- Map.Entry<K, ? extends V> entry = it.next();
- Entry<K, V> last = new Entry<K, V>(entry.getKey(), entry.getValue());
- root = last;
- size = 1;
- while (it.hasNext()) {
- entry = it.next();
- Entry<K, V> x = new Entry<K, V>(entry.getKey(), entry.getValue());
- x.parent = last;
- last.right = x;
- size++;
- balance(x);
- last = x;
- }
- }
- }
+ public abstract Map.Entry<K, V> pollFirstEntry();
- void balance(Entry<K, V> x) {
- Entry<K, V> y;
- x.color = true;
- while (x != root && x.parent.color) {
- if (x.parent == x.parent.parent.left) {
- y = x.parent.parent.right;
- if (y != null && y.color) {
- x.parent.color = false;
- y.color = false;
- x.parent.parent.color = true;
- x = x.parent.parent;
- } else {
- if (x == x.parent.right) {
- x = x.parent;
- leftRotate(x);
- }
- x.parent.color = false;
- x.parent.parent.color = true;
- rightRotate(x.parent.parent);
- }
- } else {
- y = x.parent.parent.left;
- if (y != null && y.color) {
- x.parent.color = false;
- y.color = false;
- x.parent.parent.color = true;
- x = x.parent.parent;
- } else {
- if (x == x.parent.left) {
- x = x.parent;
- rightRotate(x);
- }
- x.parent.color = false;
- x.parent.parent.color = true;
- leftRotate(x.parent.parent);
- }
- }
- }
- root.color = false;
- }
+ public abstract Map.Entry<K, V> pollLastEntry();
- /**
- * Removes all mappings from this TreeMap, leaving it empty.
- *
- * @see Map#isEmpty
- * @see #size
- */
- @Override
- public void clear() {
- root = null;
- size = 0;
- modCount++;
- }
+ public abstract Map.Entry<K, V> higherEntry(K key);
- /**
- * Answers a new TreeMap with the same mappings, size and comparator as this
- * TreeMap.
- *
- * @return a shallow copy of this TreeMap
- *
- * @see java.lang.Cloneable
- */
- @SuppressWarnings("unchecked")
- @Override
- public Object clone() {
- try {
- TreeMap<K, V> clone = (TreeMap<K, V>) super.clone();
- clone.entrySet = null;
- if (root != null) {
- clone.root = root.clone(null);
+ public abstract Map.Entry<K, V> lowerEntry(K key);
+
+ public abstract Map.Entry<K, V> ceilingEntry(K key);
+
+ public abstract Map.Entry<K, V> floorEntry(K key);
+
+ public K firstKey() {
+ Map.Entry<K, V> node = firstEntry();
+ if (node != null) {
+ return node.getKey();
}
- return clone;
- } catch (CloneNotSupportedException e) {
- return null;
- }
- }
+ throw new NoSuchElementException();
+ }
- /**
- * Answers the Comparator used to compare elements in this TreeMap.
- *
- * @return a Comparator or null if the natural ordering is used
- */
- public Comparator<? super K> comparator() {
- return comparator;
- }
+ public K lastKey() {
+ Map.Entry<K, V> node = lastEntry();
+ if (node != null) {
+ return node.getKey();
+ }
+ throw new NoSuchElementException();
+ }
- /**
- * Searches this TreeMap for the specified key.
- *
- * @param key
- * the object to search for
- * @return true if <code>key</code> is a key of this TreeMap, false
- * otherwise
- *
- * @exception ClassCastException
- * when the key cannot be compared with the keys in this
- * TreeMap
- * @exception NullPointerException
- * when the key is null and the comparator cannot handle null
- */
- @Override
- public boolean containsKey(Object key) {
- return find(key) != null;
- }
+ public K higherKey(K key) {
+ Map.Entry<K, V> entry = higherEntry(key);
+ return (null == entry) ? null : entry.getKey();
+ }
- /**
- * Searches this TreeMap for the specified value.
- *
- * @param value
- * the object to search for
- * @return true if <code>value</code> is a value of this TreeMap, false
- * otherwise
- */
- @Override
- public boolean containsValue(Object value) {
- if (root != null) {
- return containsValue(root, value);
+ public K lowerKey(K key) {
+ Map.Entry<K, V> entry = lowerEntry(key);
+ return (null == entry) ? null : entry.getKey();
}
- return false;
- }
- private boolean containsValue(Entry<K, V> node, Object value) {
- if (value == null ? node.value == null : value.equals(node.value)) {
+ public K ceilingKey(K key) {
+ Map.Entry<K, V> entry = ceilingEntry(key);
+ return (null == entry) ? null : entry.getKey();
+ }
+
+ public K floorKey(K key) {
+ Map.Entry<K, V> entry = floorEntry(key);
+ return (null == entry) ? null : entry.getKey();
+ }
+
+ /*
+ * The sub-collection methods.
+ */
+
+ public abstract NavigableSet<K> navigableKeySet();
+
+ @Override
+ public abstract Set<Map.Entry<K, V>> entrySet();
+
+ @Override
+ public Set<K> keySet() {
+ return navigableKeySet();
+ }
+
+ public NavigableSet<K> descendingKeySet() {
+ return descendingMap().navigableKeySet();
+ }
+
+ public SortedMap<K, V> subMap(K start, K end) {
+ return subMap(start, true, end, false);
+ }
+
+ public SortedMap<K, V> headMap(K end) {
+ return headMap(end, false);
+ }
+
+ public SortedMap<K, V> tailMap(K start) {
+ return tailMap(start, true);
+ }
+
+ public abstract NavigableMap<K, V> subMap(K start,
+ boolean startKeyInclusive, K end, boolean endKeyInclusive);
+
+ public abstract NavigableMap<K, V> headMap(K end, boolean inclusive);
+
+ public abstract NavigableMap<K, V> tailMap(K start, boolean inclusive);
+
+ /**
+ *
+ * @param key
+ * @return false if the key bigger than the end key (if any)
+ */
+ final boolean checkUpperBound(K key) {
+ if (hasEnd) {
+ int result = backingMap.keyCompare(key, endKey);
+ return endInclusive ? result <= 0 : result < 0;
+ }
return true;
}
- if (node.left != null) {
- if (containsValue(node.left, value)) {
- return true;
+
+ /**
+ *
+ * @param key
+ * @return false if the key smaller than the start key (if any)
+ */
+ final boolean checkLowerBound(K key) {
+ if (hasStart) {
+ int result = -backingMap.keyCompare(startKey, key);
+ return startInclusive ? result >= 0 : result > 0;
}
+ return true;
}
- if (node.right != null) {
- if (containsValue(node.right, value)) {
- return true;
+
+ final boolean isInRange(K key) {
+ return checkUpperBound(key) && checkLowerBound(key);
+ }
+
+ final TreeMap.Entry<K, V> theSmallestEntry() {
+ if (backingMap.isRootWithIllegalNullKey()) {
+ return backingMap.root;
}
+ TreeMap.Entry<K, V> result = null;
+ if (!hasStart) {
+ result = backingMap.findSmallestEntry();
+ } else {
+ result = startInclusive ? backingMap.findCeilingEntry(startKey)
+ : backingMap.findHigherEntry(startKey);
+ }
+ return (null != result && checkUpperBound(result.getKey())) ? result
+ : null;
}
- return false;
- }
- /**
- * Answers a Set of the mappings contained in this TreeMap. Each element in
- * the set is a Map.Entry. The set is backed by this TreeMap so changes to
- * one are reflected by the other. The set does not support adding.
- *
- * @return a Set of the mappings
- */
- @Override
- public Set<Map.Entry<K, V>> entrySet() {
- if (entrySet == null) {
- entrySet = new AbstractSet<Map.Entry<K, V>>() {
- @Override
- public int size() {
- return size;
+ final TreeMap.Entry<K, V> theBiggestEntry() {
+ if (backingMap.isRootWithIllegalNullKey()) {
+ return backingMap.root;
+ }
+ TreeMap.Entry<K, V> result = null;
+ if (!hasEnd) {
+ result = backingMap.findBiggestEntry();
+ } else {
+ result = endInclusive ? backingMap.findFloorEntry(endKey)
+ : backingMap.findLowerEntry(endKey);
+ }
+ return (null != result && checkLowerBound(result.getKey())) ? result
+ : null;
+ }
+
+ final TreeMap.Entry<K, V> smallerOrEqualEntry(K key) {
+ if (backingMap.isRootWithIllegalNullKey()) {
+ return backingMap.root;
+ }
+ TreeMap.Entry<K, V> result = findFloorEntry(key);
+ return (null != result && checkLowerBound(result.getKey())) ? result
+ : null;
+ }
+
+ TreeMap.Entry<K, V> findFloorEntry(K key) {
+ int result;
+ boolean belowUpper = false;
+ boolean aboveLower = false;
+ TreeMap.Entry<K, V> node = backingMap.root, last = null;
+ while (node != null) {
+ belowUpper = checkUpperBound(node.key);
+ aboveLower = checkLowerBound(node.key);
+ result = backingMap.keyCompare(key, node.key);
+ if (result == 0 && aboveLower && belowUpper) {
+ return node;
+ } else if (0 < result && belowUpper || result == 0 && !aboveLower) {
+ last = node;
+ node = node.right;
+ } else if( 0 > result && aboveLower || result == 0 && !belowUpper){
+ node = node.left;
+ } else {
+ node = null;
}
+ }
+ return last;
+ }
- @Override
- public void clear() {
- TreeMap.this.clear();
+ final TreeMap.Entry<K, V> biggerOrEqualEntry(K key) {
+ if (backingMap.isRootWithIllegalNullKey()) {
+ return backingMap.root;
+ }
+ TreeMap.Entry<K, V> result = findCeilingEntry(key);
+ return (null != result && checkUpperBound(result.getKey())) ? result
+ : null;
+ }
+
+ TreeMap.Entry<K, V> findCeilingEntry(K key) {
+ int result;
+ boolean belowUpper = false;
+ boolean aboveLower = false;
+ TreeMap.Entry<K, V> node = backingMap.root, last = null;
+ while (node != null) {
+ belowUpper = checkUpperBound(node.key);
+ aboveLower = checkLowerBound(node.key);
+ result = backingMap.keyCompare(key, node.key);
+ if (result == 0 && aboveLower && belowUpper) {
+ return node;
+ }
+ else if (0 > result && aboveLower || result == 0 && !belowUpper) {
+ last = node;
+ node = node.left;
}
+ else if (0 < result && belowUpper || result == 0 && !aboveLower){
+ node = node.right;
+ } else {
+ node = null;
+ }
+ }
+ return last;
+ }
- @SuppressWarnings("unchecked")
- @Override
- public boolean contains(Object object) {
- if (object instanceof Map.Entry) {
- Map.Entry<K, V> entry = (Map.Entry<K, V>) object;
- Object v1 = get(entry.getKey()), v2 = entry.getValue();
- return v1 == null ? v2 == null : v1.equals(v2);
- }
- return false;
+ final TreeMap.Entry<K, V> smallerEntry(K key) {
+ if (backingMap.isRootWithIllegalNullKey()) {
+ return backingMap.root;
+ }
+ TreeMap.Entry<K, V> result = findLowerEntry(key);
+ return (null != result && checkLowerBound(result.getKey())) ? result
+ : null;
+ }
+
+ TreeMap.Entry<K, V> findLowerEntry(K key) {
+ int result = -1;
+ boolean belowUpper = true;
+ TreeMap.Entry<K, V> node = backingMap.root, last = null;
+ while (node != null) {
+ belowUpper = checkUpperBound(node.key);
+ result = backingMap.keyCompare(key, node.key);
+ if (result > 0 && belowUpper) {
+ last = node;
+ node = node.right;
+ } else {
+ node = node.left;
}
+ }
+ return last;
+ }
- @Override
- public Iterator<Map.Entry<K, V>> iterator() {
- return new UnboundedEntryIterator<K, V>(TreeMap.this);
+ final TreeMap.Entry<K, V> biggerEntry(K key) {
+ if (backingMap.isRootWithIllegalNullKey()) {
+ return backingMap.root;
+ }
+ TreeMap.Entry<K, V> result = findHigherEntry(key);
+ return (null != result && checkUpperBound(result.getKey())) ? result
+ : null;
+ }
+
+ TreeMap.Entry<K, V> findHigherEntry(K key) {
+ int result = -1;
+ boolean aboveLower = true;
+ TreeMap.Entry<K, V> node = backingMap.root, last = null;
+ while (node != null) {
+ aboveLower = checkLowerBound(node.key);
+ result = backingMap.keyCompare(key, node.key);
+ if (result < 0 && aboveLower) {
+ last = node;
+ node = node.left;
+ } else {
+ node = node.right;
}
- };
+ }
+ return last;
}
- return entrySet;
+
}
- @SuppressWarnings("unchecked")
- private Entry<K, V> find(Object keyObj) {
- int result;
- K key = (K)keyObj;
- Comparable<K> object = null;
- if (comparator == null) {
- object = toComparable(key);
- Entry<K, V> x = root;
- while (x != null) {
- result = object.compareTo(x.key);
- if (result == 0) {
- return x;
+ static class AscendingSubMap<K, V> extends NavigableSubMap<K, V> implements
+ Serializable {
+
+ private static final long serialVersionUID = 912986545866124060L;
+
+ AscendingSubMap(K start, boolean startKeyInclusive, TreeMap<K, V> map,
+ K end, boolean endKeyInclusive) {
+ super(start, startKeyInclusive, map, end, endKeyInclusive);
+ }
+
+ AscendingSubMap(TreeMap<K, V> map, K end, boolean endKeyInclusive) {
+ super(map, end, endKeyInclusive);
+ }
+
+ AscendingSubMap(K start, boolean startKeyInclusive, TreeMap<K, V> map) {
+ super(start, startKeyInclusive, map);
+ }
+
+ AscendingSubMap(TreeMap<K, V> map) {
+ super(map);
+ }
+
+ @Override
+ public Map.Entry<K, V> firstEntry() {
+ return backingMap.newImmutableEntry(theSmallestEntry());
+ }
+
+ @Override
+ public Map.Entry<K, V> lastEntry() {
+ return backingMap.newImmutableEntry(theBiggestEntry());
+ }
+
+ @Override
+ public Map.Entry<K, V> pollFirstEntry() {
+ TreeMap.Entry<K, V> node = theSmallestEntry();
+ SimpleImmutableEntry<K, V> result = backingMap
+ .newImmutableEntry(node);
+ if (null != node) {
+ backingMap.rbDelete(node);
+ }
+ return result;
+ }
+
+ @Override
+ public Map.Entry<K, V> pollLastEntry() {
+ TreeMap.Entry<K, V> node = theBiggestEntry();
+ SimpleImmutableEntry<K, V> result = backingMap
+ .newImmutableEntry(node);
+ if (null != node) {
+ backingMap.rbDelete(node);
+ }
+ return result;
+ }
+
+ @Override
+ public Map.Entry<K, V> higherEntry(K key) {
+ return backingMap.newImmutableEntry(biggerEntry(key));
+ }
+
+ @Override
+ public Map.Entry<K, V> lowerEntry(K key) {
+ return backingMap.newImmutableEntry(smallerEntry(key));
+ }
+
+ @Override
+ public Map.Entry<K, V> ceilingEntry(K key) {
+ return backingMap.newImmutableEntry(biggerOrEqualEntry(key));
+ }
+
+ @Override
+ public Map.Entry<K, V> floorEntry(K key) {
+ return backingMap.newImmutableEntry(smallerOrEqualEntry(key));
+ }
+
+ @Override
+ public Set<Map.Entry<K, V>> entrySet() {
+ return new AscendingSubMapEntrySet<K, V>(this);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public NavigableSet<K> navigableKeySet() {
+ return new AscendingSubMapKeySet(this);
+ }
+
+ public NavigableMap<K, V> descendingMap() {
+ if (hasStart && hasEnd) {
+ return new DescendingSubMap<K, V>(startKey, startInclusive,
+ backingMap, endKey, endInclusive);
+ }
+ if (hasStart) {
+ return new DescendingSubMap<K, V>(startKey, startInclusive,
+ backingMap);
+ }
+ if (hasEnd) {
+ return new AscendingSubMap<K, V>(backingMap, endKey, endInclusive);
+ }
+ return new DescendingSubMap<K, V>(backingMap);
+ }
+
+ @Override
+ public NavigableMap<K, V> subMap(K start, boolean startKeyInclusive,
+ K end, boolean endKeyInclusive) {
+ if (backingMap.keyCompare(start, end) <= 0) {
+ if ((hasStart && backingMap.keyCompare(start, startKey) < 0)
+ || (hasEnd && backingMap.keyCompare(end, endKey) > 0)) {
+ throw new IllegalArgumentException();
+ }
+ K inclusiveStart = startKeyInclusive ? start : higherKey(start);
+ K inclusiveEnd = endKeyInclusive ? end : lowerKey(end);
+ boolean legalStart = (null == inclusiveStart)
+ || checkLowerBound(inclusiveStart);
+ boolean legalEnd = (null == inclusiveEnd)
+ || checkUpperBound(inclusiveEnd);
+ if (legalStart && legalEnd) {
+ return new AscendingSubMap<K, V>(start, startKeyInclusive,
+ backingMap, end, endKeyInclusive);
}
- x = result < 0 ? x.left : x.right;
- }
- } else {
- Entry<K, V> x = root;
- while (x != null) {
- result = comparator.compare(key, x.key);
- if (result == 0) {
- return x;
+ }
+ throw new IllegalArgumentException();
+ }
+
+ @Override
+ public NavigableMap<K, V> headMap(K end, boolean inclusive) {
+ if (hasEnd && backingMap.keyCompare(end, endKey) > 0) {
+ throw new IllegalArgumentException();
+ }
+ K inclusiveEnd = inclusive ? end : lowerKey(end);
+ if (null == inclusiveEnd || checkUpperBound(inclusiveEnd)) {
+ if (this.hasStart) {
+ return new AscendingSubMap<K, V>(this.startKey,
+ this.startInclusive, backingMap, end, inclusive);
}
- x = result < 0 ? x.left : x.right;
- }
+ return new AscendingSubMap<K, V>(backingMap, end, inclusive);
+ }
+ throw new IllegalArgumentException();
}
- return null;
- }
- @SuppressWarnings("unchecked")
- Entry<K, V> findAfter(Object keyObj) {
- K key = (K)keyObj;
- int result;
- Comparable<K> object = null;
- if (comparator == null) {
- object = toComparable(key);
- }
- Entry<K, V> x = root, last = null;
- while (x != null) {
- result = object != null ? object.compareTo(x.key) : comparator
- .compare(key, x.key);
- if (result == 0) {
- return x;
- }
- if (result < 0) {
- last = x;
- x = x.left;
- } else {
- x = x.right;
+ @Override
+ public NavigableMap<K, V> tailMap(K start, boolean inclusive) {
+ if (hasStart && backingMap.keyCompare(start, startKey) < 0) {
+ throw new IllegalArgumentException();
}
- }
- return last;
- }
+ K inclusiveStart = inclusive ? start : higherKey(start);
+ if (null == inclusiveStart || checkLowerBound(inclusiveStart)) {
+ if (this.hasEnd) {
+ return new AscendingSubMap<K, V>(start, inclusive,
+ backingMap, this.endKey, this.endInclusive);
+ }
+ return new AscendingSubMap<K, V>(start, inclusive, backingMap);
- Entry<K, V> findBefore(K key) {
- int result;
- Comparable<K> object = null;
- if (comparator == null) {
- object = toComparable(key);
- }
- Entry<K, V> x = root, last = null;
- while (x != null) {
- result = object != null ? object.compareTo(x.key) : comparator
- .compare(key, x.key);
- if (result <= 0) {
- x = x.left;
+ }
+ throw new IllegalArgumentException();
+ }
+ }
+
+ static class DescendingSubMap<K, V> extends NavigableSubMap<K, V> implements
+ Serializable {
+ private static final long serialVersionUID = 912986545866120460L;
+
+ private final Comparator<? super K> reverseComparator = Collections
+ .reverseOrder(backingMap.comparator);
+
+ DescendingSubMap(K start, boolean startKeyInclusive, TreeMap<K, V> map,
+ K end, boolean endKeyInclusive) {
+ super(start, startKeyInclusive, map, end, endKeyInclusive);
+ }
+
+ DescendingSubMap(K start, boolean startKeyInclusive, TreeMap<K, V> map) {
+ super(start, startKeyInclusive, map);
+ }
+
+ DescendingSubMap(TreeMap<K, V> map, K end, boolean endKeyInclusive) {
+ super(map, end, endKeyInclusive);
+ }
+
+ DescendingSubMap(TreeMap<K, V> map) {
+ super(map);
+ }
+
+ @Override
+ public Comparator<? super K> comparator() {
+ return reverseComparator;
+ }
+
+ @Override
+ public Map.Entry<K, V> firstEntry() {
+ return backingMap.newImmutableEntry(theBiggestEntry());
+ }
+
+ @Override
+ public Map.Entry<K, V> lastEntry() {
+ return backingMap.newImmutableEntry(theSmallestEntry());
+ }
+
+ @Override
+ public Map.Entry<K, V> pollFirstEntry() {
+ TreeMap.Entry<K, V> node = theBiggestEntry();
+ SimpleImmutableEntry<K, V> result = backingMap
+ .newImmutableEntry(node);
+ if (null != node) {
+ backingMap.rbDelete(node);
+ }
+ return result;
+ }
+
+ @Override
+ public Map.Entry<K, V> pollLastEntry() {
+ TreeMap.Entry<K, V> node = theSmallestEntry();
+ SimpleImmutableEntry<K, V> result = backingMap
+ .newImmutableEntry(node);
+ if (null != node) {
+ backingMap.rbDelete(node);
+ }
+ return result;
+ }
+
+ @Override
+ public Map.Entry<K, V> higherEntry(K key) {
+ return backingMap.newImmutableEntry(smallerEntry(key));
+ }
+
+ @Override
+ public Map.Entry<K, V> lowerEntry(K key) {
+ return backingMap.newImmutableEntry(biggerEntry(key));
+ }
+
+ @Override
+ public Map.Entry<K, V> ceilingEntry(K key) {
+ return backingMap.newImmutableEntry(smallerOrEqualEntry(key));
+ }
+
+ @Override
+ public Map.Entry<K, V> floorEntry(K key) {
+ return backingMap.newImmutableEntry(biggerOrEqualEntry(key));
+ }
+
+ @Override
+ public Set<Map.Entry<K, V>> entrySet() {
+ return new DescendingSubMapEntrySet<K, V>(this);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public NavigableSet<K> navigableKeySet() {
+ return new DescendingSubMapKeySet(this);
+ }
+
+ public NavigableMap<K, V> descendingMap() {
+ if (hasStart && hasEnd) {
+ return new AscendingSubMap<K, V>(startKey, startInclusive,
+ backingMap, endKey, endInclusive);
+ }
+ if (hasStart) {
+ return new AscendingSubMap<K, V>(startKey, startInclusive,
+ backingMap);
+ }
+ if (hasEnd) {
+ return new AscendingSubMap<K, V>(backingMap, endKey, endInclusive);
+ }
+ return new AscendingSubMap<K, V>(backingMap);
+ }
+
+ int keyCompare(K left, K right) {
+ return (null != reverseComparator) ? reverseComparator.compare(
+ left, right) : toComparable(left).compareTo(right);
+ }
+
+ @Override
+ public NavigableMap<K, V> subMap(K start, boolean startKeyInclusive,
+ K end, boolean endKeyInclusive) {
+ if (this.keyCompare(start, end) <= 0) {
+ K inclusiveStart = startKeyInclusive ? start : higherKey(start);
+ K inclusiveEnd = endKeyInclusive ? end : lowerKey(end);
+ boolean legalStart = (null == inclusiveStart)
+ || checkLowerBound(inclusiveStart);
+ boolean legalEnd = (null == inclusiveEnd)
+ || checkUpperBound(inclusiveEnd);
+ if (legalStart && legalEnd) {
+ return new DescendingSubMap<K, V>(end, endKeyInclusive,
+ backingMap, start, startKeyInclusive);
+ }
+ }
+ throw new IllegalArgumentException();
+ }
+
+ @Override
+ public NavigableMap<K, V> headMap(K end, boolean inclusive) {
+ // check for error
+ this.keyCompare(end, end);
+ K inclusiveEnd = inclusive ? end : lowerKey(end);
+ if (null == inclusiveEnd || checkLowerBound(inclusiveEnd)) {
+ if (this.hasEnd) {
+ return new DescendingSubMap<K, V>(end, inclusive,
+ backingMap, this.endKey, this.endInclusive);
+ }
+ return new DescendingSubMap<K, V>(end, inclusive, backingMap);
+ }
+ throw new IllegalArgumentException();
+ }
+
+ @Override
+ public NavigableMap<K, V> tailMap(K start, boolean inclusive) {
+ // check for error
+ this.keyCompare(start, start);
+ K inclusiveStart = inclusive ? start : higherKey(start);
+ if (null == inclusiveStart || checkUpperBound(inclusiveStart)) {
+ if (this.hasStart) {
+ return new DescendingSubMap<K, V>(this.startKey,
+ this.startInclusive, backingMap, start, inclusive);
+ }
+ return new DescendingSubMap<K, V>(backingMap, start, inclusive);
+
+ }
+ throw new IllegalArgumentException();
+ }
+ }
+
+ /**
+ * Constructs a new empty instance of TreeMap.
+ *
+ */
+ public TreeMap() {
+ super();
+ }
+
+ /**
+ * Constructs a new empty instance of TreeMap which uses the specified
+ * Comparator.
+ *
+ * @param theComparator
+ * the Comparator
+ */
+ public TreeMap(Comparator<? super K> theComparator) {
+ this.comparator = theComparator;
+ }
+
+ /**
+ * Constructs a new instance of TreeMap containing the mappings from the
+ * specified Map and using the natural ordering.
+ *
+ * @param map
+ * the mappings to add
+ *
+ * @exception ClassCastException
+ * when a key in the Map does not implement the Comparable
+ * interface, or they keys in the Map cannot be compared
+ */
+ public TreeMap(Map<? extends K, ? extends V> map) {
+ this();
+ putAll(map);
+ }
+
+ /**
+ * Constructs a new instance of TreeMap containing the mappings from the
+ * specified SortedMap and using the same Comparator.
+ *
+ * @param map
+ * the mappings to add
+ */
+ public TreeMap(SortedMap<K, ? extends V> map) {
+ this(map.comparator());
+ Iterator<? extends Map.Entry<K, ? extends V>> it = map.entrySet()
+ .iterator();
+ if (it.hasNext()) {
+ Map.Entry<K, ? extends V> entry = it.next();
+ Entry<K, V> last = new Entry<K, V>(entry.getKey(), entry.getValue());
+ root = last;
+ size = 1;
+ while (it.hasNext()) {
+ entry = it.next();
+ Entry<K, V> x = new Entry<K, V>(entry.getKey(), entry
+ .getValue());
+ x.parent = last;
+ last.right = x;
+ size++;
+ balance(x);
+ last = x;
+ }
+ }
+ }
+
+ void balance(Entry<K, V> x) {
+ Entry<K, V> y;
+ x.color = true;
+ while (x != root && x.parent.color) {
+ if (x.parent == x.parent.parent.left) {
+ y = x.parent.parent.right;
+ if (y != null && y.color) {
+ x.parent.color = false;
+ y.color = false;
+ x.parent.parent.color = true;
+ x = x.parent.parent;
+ } else {
+ if (x == x.parent.right) {
+ x = x.parent;
+ leftRotate(x);
+ }
+ x.parent.color = false;
+ x.parent.parent.color = true;
+ rightRotate(x.parent.parent);
+ }
} else {
- last = x;
- x = x.right;
+ y = x.parent.parent.left;
+ if (y != null && y.color) {
+ x.parent.color = false;
+ y.color = false;
+ x.parent.parent.color = true;
+ x = x.parent.parent;
+ } else {
+ if (x == x.parent.left) {
+ x = x.parent;
+ rightRotate(x);
+ }
+ x.parent.color = false;
+ x.parent.parent.color = true;
+ leftRotate(x.parent.parent);
+ }
+ }
+ }
+ root.color = false;
+ }
+
+ /**
+ * Removes all mappings from this TreeMap, leaving it empty.
+ *
+ * @see Map#isEmpty
+ * @see #size
+ */
+ @Override
+ public void clear() {
+ root = null;
+ size = 0;
+ modCount++;
+ }
+
+ /**
+ * Answers a new TreeMap with the same mappings, size and comparator as this
+ * TreeMap.
+ *
+ * @return a shallow copy of this TreeMap
+ *
+ * @see java.lang.Cloneable
+ */
+ @SuppressWarnings("unchecked")
+ @Override
+ public Object clone() {
+ try {
+ TreeMap<K, V> clone = (TreeMap<K, V>) super.clone();
+ clone.entrySet = null;
+ clone.navigableKeySet = null;
+ clone.descendingMap = null;
+ clone.valuesCollection = null;
+ clone.keySet = null;
+ if (root != null) {
+ clone.root = root.clone(null);
+ }
+ return clone;
+ } catch (CloneNotSupportedException e) {
+ return null;
+ }
+ }
+
+ /**
+ * Answers the Comparator used to compare elements in this TreeMap.
+ *
+ * @return a Comparator or null if the natural ordering is used
+ */
+ public Comparator<? super K> comparator() {
+ return comparator;
+ }
+
+ /**
+ * Searches this TreeMap for the specified key.
+ *
+ * @param key
+ * the object to search for
+ * @return true if <code>key</code> is a key of this TreeMap, false
+ * otherwise
+ *
+ * @exception ClassCastException
+ * when the key cannot be compared with the keys in this
+ * TreeMap
+ * @exception NullPointerException
+ * when the key is null and the comparator cannot handle null
+ */
+ @Override
+ public boolean containsKey(Object key) {
+ return find(key) != null;
+ }
+
+ /**
+ * Searches this TreeMap for the specified value.
+ *
+ * @param value
+ * the object to search for
+ * @return true if <code>value</code> is a value of this TreeMap, false
+ * otherwise
+ */
+ @Override
+ public boolean containsValue(Object value) {
+ if (root != null) {
+ return containsValue(root, value);
+ }
+ return false;
+ }
+
+ private boolean containsValue(Entry<K, V> node, Object value) {
+ if (value == null ? node.value == null : value.equals(node.value)) {
+ return true;
+ }
+ if (node.left != null) {
+ if (containsValue(node.left, value)) {
+ return true;
+ }
+ }
+ if (node.right != null) {
+ if (containsValue(node.right, value)) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ @SuppressWarnings("unchecked")
+ Entry<K, V> find(Object keyObj) {
+ int result;
+ K key = (K) keyObj;
+ Entry<K, V> x = root;
+ if (null != comparator) {
+ while (x != null) {
+ result = comparator.compare(key, x.key);
+ if (result == 0) {
+ return x;
+ }
+ x = result < 0 ? x.left : x.right;
}
+ return null;
+ } else {
+ Comparable<K> targetKey = (Comparable<K>) key;
+ while (x != null) {
+ result = targetKey.compareTo(x.key);
+ if (result == 0) {
+ return x;
+ }
+ x = result < 0 ? x.left : x.right;
+ }
+ return null;
}
- return last;
}
- /**
- * Answer the first sorted key in this TreeMap.
- *
- * @return the first sorted key
- *
- * @exception NoSuchElementException
- * when this TreeMap is empty
- */
- public K firstKey() {
- if (root != null) {
- return minimum(root).key;
- }
- throw new NoSuchElementException();
- }
+ TreeMap.Entry<K, V> findSmallestEntry() {
+ return (null == root) ? null : minimum(root);
+ }
- private void fixup(Entry<K, V> x) {
- Entry<K, V> w;
- while (x != root && !x.color) {
- if (x == x.parent.left) {
- w = x.parent.right;
- if (w == null) {
- x = x.parent;
- continue;
- }
- if (w.color) {
- w.color = false;
- x.parent.color = true;
- leftRotate(x.parent);
- w = x.parent.right;
- if (w == null) {
- x = x.parent;
- continue;
- }
+ TreeMap.Entry<K, V> findBiggestEntry() {
+ return (null == root) ? null : maximum(root);
+ }
+
+ TreeMap.Entry<K, V> findCeilingEntry(K key) {
+ int result;
+ Entry<K, V> node = root, last = null;
+ if (null != comparator) {
+ while (node != null) {
+ result = comparator.compare(key, node.key);
+ if (result == 0) {
+ return node;
}
- if ((w.left == null || !w.left.color)
- && (w.right == null || !w.right.color)) {
- w.color = true;
- x = x.parent;
+ if (result < 0) {
+ last = node;
+ node = node.left;
} else {
- if (w.right == null || !w.right.color) {
- w.left.color = false;
- w.color = true;
- rightRotate(w);
- w = x.parent.right;
- }
- w.color = x.parent.color;
- x.parent.color = false;
- w.right.color = false;
- leftRotate(x.parent);
- x = root;
- }
- } else {
- w = x.parent.left;
- if (w == null) {
- x = x.parent;
- continue;
+ node = node.right;
}
- if (w.color) {
- w.color = false;
- x.parent.color = true;
- rightRotate(x.parent);
- w = x.parent.left;
- if (w == null) {
- x = x.parent;
- continue;
- }
+ }
+ return last;
+ } else {
+ Comparable<K> targetKey = (Comparable<K>) key;
+ while (node != null) {
+ result = targetKey.compareTo(node.key);
+ if (result == 0) {
+ return node;
}
- if ((w.left == null || !w.left.color)
- && (w.right == null || !w.right.color)) {
- w.color = true;
- x = x.parent;
+ if (result < 0) {
+ last = node;
+ node = node.left;
} else {
- if (w.left == null || !w.left.color) {
- w.right.color = false;
- w.color = true;
- leftRotate(w);
- w = x.parent.left;
- }
- w.color = x.parent.color;
- x.parent.color = false;
- w.left.color = false;
- rightRotate(x.parent);
- x = root;
+ node = node.right;
}
}
+ return last;
}
- x.color = false;
- }
-
- /**
- * Answers the value of the mapping with the specified key.
- *
- * @param key
- * the key
- * @return the value of the mapping with the specified key
- *
- * @exception ClassCastException
- * when the key cannot be compared with the keys in this
- * TreeMap
- * @exception NullPointerException
- * when the key is null and the comparator cannot handle null
- */
- @Override
- public V get(Object key) {
- Entry<K, V> node = find(key);
- if (node != null) {
- return node.value;
- }
- return null;
}
- /**
- * Answers a SortedMap of the specified portion of this TreeMap which
- * contains keys less than the end key. The returned SortedMap is backed by
- * this TreeMap so changes to one are reflected by the other.
- *
- * @param endKey
- * the end key
- * @return a sub-map where the keys are less than <code>endKey</code>
- *
- * @exception ClassCastException
- * when the end key cannot be compared with the keys in this
- * TreeMap
- * @exception NullPointerException
- * when the end key is null and the comparator cannot handle
- * null
- */
- public SortedMap<K, V> headMap(K endKey) {
- // Check for errors
- if (comparator == null) {
- toComparable(endKey).compareTo(endKey);
- } else {
- comparator.compare(endKey, endKey);
- }
- return new SubMap<K, V>(this, endKey);
+ TreeMap.Entry<K, V> findFloorEntry(K key) {
+ int result;
+ Entry<K, V> node = root, last = null;
+ if (comparator != null) {
+ while (node != null) {
+ result = comparator.compare(key, node.key);
+ if (0 == result) {
+ return node;
+ } else if (0 < result) {
+ last = node;
+ node = node.right;
+ } else {
+ node = node.left;
+ }
+ }
+ return last;
+ } else {
+ Comparable<K> targetKey = (Comparable<K>) key;
+ while (node != null) {
+ result = targetKey.compareTo(node.key);
+ if (0 == result) {
+ return node;
+ } else if (0 < result) {
+ last = node;
+ node = node.right;
+ } else {
+ node = node.left;
+ }
+ }
+ return last;
+ }
}
- /**
- * Answers a Set of the keys contained in this TreeMap. The set is backed by
- * this TreeMap so changes to one are reflected by the other. The set does
- * not support adding.
- *
- * @return a Set of the keys
- */
- @Override
- public Set<K> keySet() {
- if (keySet == null) {
- keySet = new AbstractSet<K>() {
- @Override
- public boolean contains(Object object) {
- return containsKey(object);
+ TreeMap.Entry<K, V> findLowerEntry(K key) {
+ int result;
+ Entry<K, V> node = root, last = null;
+ if (comparator != null) {
+ while (node != null) {
+ result = comparator.compare(key, node.key);
+ if (result <= 0) {
+ node = node.left;
+ } else {
+ last = node;
+ node = node.right;
}
-
- @Override
- public int size() {
- return size;
+ }
+ return last;
+ } else {
+ Comparable<K> targetKey = (Comparable<K>) key;
+ while (node != null) {
+ result = targetKey.compareTo(node.key);
+ if (result <= 0) {
+ node = node.left;
+ } else {
+ last = node;
+ node = node.right;
}
+ }
+ return last;
- @Override
- public void clear() {
- TreeMap.this.clear();
- }
+ }
+ }
- @Override
- public Iterator<K> iterator() {
- return new UnboundedKeyIterator<K,V> (TreeMap.this);
+ TreeMap.Entry<K, V> findHigherEntry(K key) {
+ int result;
+ Entry<K, V> node = root, last = null;
+ if (comparator != null) {
+ while (node != null) {
+ result = comparator.compare(key, node.key);
+ if (result < 0) {
+ last = node;
+ node = node.left;
+ } else {
+ node = node.right;
}
- };
+ }
+ return last;
+ } else {
+ Comparable<K> targetKey = (Comparable<K>) key;
+ while (node != null) {
+ result = targetKey.compareTo(node.key);
+ if (result < 0) {
+ last = node;
+ node = node.left;
+ } else {
+ node = node.right;
+ }
+ }
+ return last;
}
- return keySet;
}
- /**
- * Answer the last sorted key in this TreeMap.
+ /**
+ * Answer the first sorted key in this TreeMap.
*
- * @return the last sorted key
+ * @return the first sorted key
*
* @exception NoSuchElementException
* when this TreeMap is empty
*/
- public K lastKey() {
- if (root != null) {
+ public K firstKey() {
+ if (root != null) {
+ return minimum(root).key;
+ }
+ throw new NoSuchElementException();
+ }
+
+ private void fixup(Entry<K, V> x) {
+ Entry<K, V> w;
+ while (x != root && !x.color) {
+ if (x == x.parent.left) {
+ w = x.parent.right;
+ if (w == null) {
+ x = x.parent;
+ continue;
+ }
+ if (w.color) {
+ w.color = false;
+ x.parent.color = true;
+ leftRotate(x.parent);
+ w = x.parent.right;
+ if (w == null) {
+ x = x.parent;
+ continue;
+ }
+ }
+ if ((w.left == null || !w.left.color)
+ && (w.right == null || !w.right.color)) {
+ w.color = true;
+ x = x.parent;
+ } else {
+ if (w.right == null || !w.right.color) {
+ w.left.color = false;
+ w.color = true;
+ rightRotate(w);
+ w = x.parent.right;
+ }
+ w.color = x.parent.color;
+ x.parent.color = false;
+ w.right.color = false;
+ leftRotate(x.parent);
+ x = root;
+ }
+ } else {
+ w = x.parent.left;
+ if (w == null) {
+ x = x.parent;
+ continue;
+ }
+ if (w.color) {
+ w.color = false;
+ x.parent.color = true;
+ rightRotate(x.parent);
+ w = x.parent.left;
+ if (w == null) {
+ x = x.parent;
+ continue;
+ }
+ }
+ if ((w.left == null || !w.left.color)
+ && (w.right == null || !w.right.color)) {
+ w.color = true;
+ x = x.parent;
+ } else {
+ if (w.left == null || !w.left.color) {
+ w.right.color = false;
+ w.color = true;
+ leftRotate(w);
+ w = x.parent.left;
+ }
+ w.color = x.parent.color;
+ x.parent.color = false;
+ w.left.color = false;
+ rightRotate(x.parent);
+ x = root;
+ }
+ }
+ }
+ x.color = false;
+ }
+
+ /**
+ * Answers the value of the mapping with the specified key.
+ *
+ * @param key
+ * the key
+ * @return the value of the mapping with the specified key
+ *
+ * @exception ClassCastException
+ * when the key cannot be compared with the keys in this
+ * TreeMap
+ * @exception NullPointerException
+ * when the key is null and the comparator cannot handle null
+ */
+ @Override
+ public V get(Object key) {
+ Entry<K, V> node = find(key);
+ if (node != null) {
+ return node.value;
+ }
+ return null;
+ }
+
+ /**
+ * Answers a Set of the keys contained in this TreeMap. The set is backed by
+ * this TreeMap so changes to one are reflected by the other. The set does
+ * not support adding.
+ *
+ * @return a Set of the keys
+ */
+ @Override
+ public Set<K> keySet() {
+ return navigableKeySet();
+ }
+
+ /**
+ * Answer the last sorted key in this TreeMap.
+ *
+ * @return the last sorted key
+ *
+ * @exception NoSuchElementException
+ * when this TreeMap is empty
+ */
+ public K lastKey() {
+ if (root != null) {
return maximum(root).key;
}
- throw new NoSuchElementException();
- }
+ throw new NoSuchElementException();
+ }
- private void leftRotate(Entry<K, V> x) {
- Entry<K, V> y = x.right;
- x.right = y.left;
- if (y.left != null) {
+ private void leftRotate(Entry<K, V> x) {
+ Entry<K, V> y = x.right;
+ x.right = y.left;
+ if (y.left != null) {
y.left.parent = x;
}
- y.parent = x.parent;
- if (x.parent == null) {
- root = y;
- } else {
- if (x == x.parent.left) {
+ y.parent = x.parent;
+ if (x.parent == null) {
+ root = y;
+ } else {
+ if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
- }
- y.left = x;
- x.parent = y;
- }
+ }
+ y.left = x;
+ x.parent = y;
+ }
- static <K, V> Entry<K, V> maximum(Entry<K, V> x) {
- while (x.right != null) {
+ static <K, V> Entry<K, V> maximum(Entry<K, V> x) {
+ while (x.right != null) {
x = x.right;
}
- return x;
- }
+ return x;
+ }
- static <K, V> Entry<K, V> minimum(Entry<K, V> x) {
- while (x.left != null) {
+ static <K, V> Entry<K, V> minimum(Entry<K, V> x) {
+ while (x.left != null) {
x = x.left;
}
- return x;
- }
+ return x;
+ }
- static <K, V> Entry<K, V> predecessor(Entry<K, V> x) {
- if (x.left != null) {
[... 900 lines stripped ...]