| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You 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.ObjectOutputStream; |
| import java.io.Serializable; |
| |
| /** |
| * TreeMap is an implementation of SortedMap. All optional operations (adding |
| * and removing) are supported. 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. |
| * |
| * @since Android 1.0 |
| */ |
| public class TreeMap<K, V> extends AbstractMap<K, V> implements SortedMap<K, V>, Cloneable, |
| Serializable { |
| private static final long serialVersionUID = 919286545866124006L; |
| |
| transient int size; |
| |
| transient Entry<K, V> root; |
| |
| private 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; |
| |
| boolean color; |
| |
| Entry(K key) { |
| super(key); |
| } |
| |
| Entry(K key, V value) { |
| super(key, value); |
| } |
| |
| @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) { |
| clone.left = left.clone(clone); |
| } |
| if (right != null) { |
| clone.right = right.clone(clone); |
| } |
| return clone; |
| } |
| } |
| |
| @SuppressWarnings("unchecked") |
| private static <T> Comparable<T> toComparable(T obj) { |
| return (Comparable<T>)obj; |
| } |
| |
| private static class AbstractMapIterator <K,V> { |
| TreeMap<K, V> backingMap; |
| 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; |
| } |
| |
| public boolean hasNext() { |
| return node != null; |
| } |
| |
| final public void remove() { |
| if (expectedModCount == backingMap.modCount) { |
| if (lastNode != null) { |
| backingMap.rbDelete(lastNode); |
| lastNode = null; |
| expectedModCount++; |
| } else { |
| throw new IllegalStateException(); |
| } |
| } else { |
| throw new ConcurrentModificationException(); |
| } |
| } |
| |
| final void makeNext() { |
| if (expectedModCount != backingMap.modCount) { |
| throw new ConcurrentModificationException(); |
| } else if (node == null) { |
| throw new NoSuchElementException(); |
| } |
| lastNode = node; |
| node = TreeMap.successor(node); |
| } |
| } |
| |
| 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); |
| } |
| |
| UnboundedEntryIterator(TreeMap<K, V> map) { |
| super(map, map.root == null ? null : TreeMap.minimum(map.root)); |
| } |
| |
| public Map.Entry<K, V> next() { |
| makeNext(); |
| return lastNode; |
| } |
| } |
| |
| 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); |
| } |
| |
| public UnboundedKeyIterator(TreeMap<K, V> map) { |
| super(map, map.root == null ? null : TreeMap.minimum(map.root)); |
| } |
| |
| public K next() { |
| makeNext(); |
| return lastNode.key; |
| } |
| } |
| |
| 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; |
| } |
| } |
| |
| private static class ComparatorBoundedIterator<K, V> extends AbstractMapIterator<K, V> { |
| private final K endKey; |
| |
| private final Comparator<? super K> cmp; |
| |
| ComparatorBoundedIterator(TreeMap<K, V> map, Entry<K, V> startNode, K end) { |
| super(map, startNode); |
| endKey = end; |
| cmp = map.comparator(); |
| } |
| |
| final void cleanNext() { |
| if (node != null && cmp.compare(endKey, node.key) <= 0) { |
| node = null; |
| } |
| } |
| |
| @Override |
| public boolean hasNext() { |
| return (node != null && endKey != null) && (cmp.compare(node.key, endKey) < 0); |
| } |
| } |
| |
| private static class ComparatorBoundedEntryIterator<K, V> extends |
| ComparatorBoundedIterator<K, V> implements Iterator<Map.Entry<K, V>> { |
| |
| ComparatorBoundedEntryIterator(TreeMap<K, V> map, Entry<K, V> startNode, K end) { |
| super(map, startNode, end); |
| } |
| |
| public Map.Entry<K, V> next() { |
| makeNext(); |
| cleanNext(); |
| return lastNode; |
| } |
| } |
| |
| private static class ComparatorBoundedKeyIterator<K, V> extends |
| ComparatorBoundedIterator<K, V> implements Iterator<K> { |
| |
| ComparatorBoundedKeyIterator(TreeMap<K, V> map, Entry<K, V> startNode, K end) { |
| super(map, startNode, end); |
| } |
| |
| public K next() { |
| makeNext(); |
| cleanNext(); |
| return lastNode.key; |
| } |
| } |
| |
| private static class ComparatorBoundedValueIterator<K, V> extends |
| ComparatorBoundedIterator<K, V> implements Iterator<V> { |
| |
| ComparatorBoundedValueIterator(TreeMap<K, V> map, Entry<K, V> startNode, K end) { |
| super(map, startNode, end); |
| } |
| |
| public V next() { |
| makeNext(); |
| cleanNext(); |
| return lastNode.value; |
| } |
| } |
| |
| private static class ComparableBoundedIterator<K, V> extends AbstractMapIterator<K, V> { |
| private final Comparable<K> endKey; |
| |
| public ComparableBoundedIterator(TreeMap<K, V> treeMap, Entry<K, V> entry, |
| Comparable<K> endKey) { |
| super(treeMap, entry); |
| this.endKey = endKey; |
| } |
| |
| final void cleanNext() { |
| if ((node != null) && (endKey.compareTo(node.key) <= 0)) { |
| node = null; |
| } |
| } |
| |
| @Override |
| public boolean hasNext() { |
| return (node != null) && (endKey.compareTo(node.key) > 0); |
| } |
| } |
| |
| 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); |
| } |
| |
| public Map.Entry<K, V> next() { |
| makeNext(); |
| cleanNext(); |
| return lastNode; |
| } |
| |
| } |
| |
| private static class ComparableBoundedKeyIterator<K, V> extends |
| ComparableBoundedIterator<K, V> implements Iterator<K> { |
| |
| ComparableBoundedKeyIterator(TreeMap<K, V> map, Entry<K, V> startNode, Comparable<K> end) { |
| super(map, startNode, end); |
| } |
| |
| public K next() { |
| makeNext(); |
| cleanNext(); |
| return lastNode.key; |
| } |
| } |
| |
| private static class ComparableBoundedValueIterator<K, V> extends |
| ComparableBoundedIterator<K, V> implements Iterator<V> { |
| |
| ComparableBoundedValueIterator(TreeMap<K, V> map, Entry<K, V> startNode, |
| Comparable<K> end) { |
| super(map, startNode, end); |
| } |
| |
| public V next() { |
| makeNext(); |
| cleanNext(); |
| return lastNode.value; |
| } |
| } |
| |
| static final class SubMap<K,V> extends AbstractMap<K,V> implements SortedMap<K,V>, Serializable { |
| private static final long serialVersionUID = -6520786458950516097L; |
| |
| private TreeMap<K,V> backingMap; |
| |
| boolean hasStart, hasEnd; |
| |
| K startKey, endKey; |
| |
| transient Set<Map.Entry<K,V>> entrySet = null; |
| |
| SubMap(K start, TreeMap<K,V> map) { |
| backingMap = map; |
| hasStart = true; |
| startKey = start; |
| } |
| |
| 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; |
| } |
| |
| 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(); |
| } |
| } |
| } |
| |
| 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; |
| } |
| |
| 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; |
| } |
| |
| 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 Comparator<? super K> comparator() { |
| return backingMap.comparator(); |
| } |
| |
| @SuppressWarnings("unchecked") |
| @Override |
| public boolean containsKey(Object key) { |
| if (isInRange((K)key)) { |
| return backingMap.containsKey(key); |
| } |
| return false; |
| } |
| |
| @Override |
| public Set<Map.Entry<K,V>> entrySet() { |
| if(entrySet==null) { |
| entrySet = new SubMapEntrySet<K,V>(this); |
| } |
| return entrySet; |
| } |
| |
| public K firstKey() { |
| TreeMap.Entry<K,V> node = firstEntry(); |
| if (node != null ) { |
| return node.key; |
| } |
| throw new NoSuchElementException(); |
| } |
| |
| 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; |
| } |
| |
| @SuppressWarnings("unchecked") |
| @Override |
| public V get(Object key) { |
| if (isInRange((K)key)) { |
| return backingMap.get(key); |
| } |
| return null; |
| } |
| |
| 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); |
| } |
| |
| @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; |
| } |
| |
| @Override |
| public Set<K> keySet() { |
| if (keySet == null) { |
| keySet = new SubMapKeySet<K,V>(this); |
| } |
| return keySet; |
| } |
| |
| 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(); |
| } |
| |
| @Override |
| public V put(K key, V value) { |
| if (isInRange(key)) { |
| return backingMap.put(key, value); |
| } |
| throw new IllegalArgumentException(); |
| } |
| |
| @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(); |
| } |
| |
| 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); |
| } |
| |
| @Override |
| public Collection<V> values() { |
| if(valuesCollection==null) { |
| valuesCollection = new SubMapValuesCollection<K,V>(this); |
| } |
| return valuesCollection; |
| } |
| } |
| |
| static class SubMapEntrySet<K,V> extends AbstractSet<Map.Entry<K,V>> implements Set<Map.Entry<K,V>> { |
| SubMap<K,V> subMap; |
| |
| SubMapEntrySet(SubMap<K,V> map) { |
| subMap = map; |
| } |
| |
| @Override |
| public boolean isEmpty() { |
| return subMap.isEmpty(); |
| } |
| |
| @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); |
| } |
| |
| @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; |
| } |
| |
| } |
| |
| static class SubMapKeySet<K,V> extends AbstractSet<K> implements Set<K> { |
| SubMap<K,V> subMap; |
| |
| SubMapKeySet(SubMap<K,V> map) { |
| subMap = map; |
| } |
| |
| @Override |
| public boolean contains(Object object) { |
| return subMap.containsKey(object); |
| } |
| |
| @Override |
| public boolean isEmpty() { |
| return subMap.isEmpty(); |
| } |
| |
| @Override |
| public int size() { |
| int size = 0; |
| Iterator<K> it = iterator(); |
| while (it.hasNext()) { |
| size++; |
| it.next(); |
| } |
| return size; |
| } |
| |
| @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); |
| } |
| } |
| |
| static class SubMapValuesCollection<K,V> extends AbstractCollection<V> { |
| SubMap<K,V> subMap; |
| |
| public SubMapValuesCollection(SubMap<K,V> subMap) { |
| this.subMap = subMap; |
| } |
| |
| @Override |
| public boolean isEmpty() { |
| return subMap.isEmpty(); |
| } |
| |
| @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); |
| } |
| |
| @Override |
| public int size() { |
| int cnt = 0; |
| for (Iterator<V> it = iterator(); it.hasNext();) { |
| it.next(); |
| cnt++; |
| } |
| return cnt; |
| } |
| } |
| |
| /** |
| * Constructs a new empty {@code TreeMap} instance. |
| * |
| * @since Android 1.0 |
| */ |
| public TreeMap() { |
| super(); |
| } |
| |
| /** |
| * Constructs a new empty {@code TreeMap} instance with the specified |
| * comparator. |
| * |
| * @param comparator |
| * the comparator to compare keys with. |
| * @since Android 1.0 |
| */ |
| public TreeMap(Comparator<? super K> comparator) { |
| this.comparator = comparator; |
| } |
| |
| /** |
| * Constructs a new {@code TreeMap} instance containing the mappings from |
| * the specified map and using natural ordering. |
| * |
| * @param map |
| * the mappings to add. |
| * @throws ClassCastException |
| * if a key in the specified map does not implement the |
| * Comparable interface, or if the keys in the map cannot be |
| * compared. |
| * @since Android 1.0 |
| */ |
| public TreeMap(Map<? extends K,? extends V> map) { |
| this(); |
| putAll(map); |
| } |
| |
| /** |
| * Constructs a new {@code TreeMap} instance containing the mappings from |
| * the specified SortedMap and using the same comparator. |
| * |
| * @param map |
| * the mappings to add. |
| * @since Android 1.0 |
| */ |
| 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 { |
| 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() |
| * @since Android 1.0 |
| */ |
| @Override |
| public void clear() { |
| root = null; |
| size = 0; |
| modCount++; |
| } |
| |
| /** |
| * Returns a new {@code TreeMap} with the same mappings, size and comparator |
| * as this instance. |
| * |
| * @return a shallow copy of this instance. |
| * @see java.lang.Cloneable |
| * @since Android 1.0 |
| */ |
| @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); |
| } |
| return clone; |
| } catch (CloneNotSupportedException e) { |
| return null; |
| } |
| } |
| |
| /** |
| * Returns the comparator used to compare elements in this map. |
| * |
| * @return the comparator or {@code null} if the natural ordering is used. |
| * @since Android 1.0 |
| */ |
| public Comparator<? super K> comparator() { |
| return comparator; |
| } |
| |
| /** |
| * Returns whether this map contains the specified key. |
| * |
| * @param key |
| * the key to search for. |
| * @return {@code true} if this map contains the specified key, |
| * {@code false} otherwise. |
| * @since Android 1.0 |
| */ |
| @Override |
| public boolean containsKey(Object key) { |
| return find(key) != null; |
| } |
| |
| /** |
| * Returns whether this map contains the specified value. |
| * |
| * @param value |
| * the value to search for. |
| * @return {@code true} if this map contains the specified value, |
| * {@code false} otherwise. |
| * @since Android 1.0 |
| */ |
| @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; |
| } |
| |
| /** |
| * Returns a set containing all of the mappings in this map. Each mapping is |
| * an instance of {@link Map.Entry}. As the set is backed by this map, |
| * changes in one will be reflected in the other. It does not support adding |
| * operations. |
| * |
| * @return a set of the mappings. |
| * @since Android 1.0 |
| */ |
| @Override |
| public Set<Map.Entry<K, V>> entrySet() { |
| if (entrySet == null) { |
| entrySet = new AbstractSet<Map.Entry<K, V>>() { |
| @Override |
| public int size() { |
| return size; |
| } |
| |
| @Override |
| public void clear() { |
| TreeMap.this.clear(); |
| } |
| |
| @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; |
| } |
| |
| @Override |
| public Iterator<Map.Entry<K, V>> iterator() { |
| return new UnboundedEntryIterator<K, V>(TreeMap.this); |
| } |
| }; |
| } |
| 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 != null ? object.compareTo(x.key) : comparator |
| .compare(key, x.key); |
| if (result == 0) { |
| return x; |
| } |
| x = result < 0 ? x.left : x.right; |
| } |
| 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; |
| } |
| } |
| return last; |
| } |
| |
| 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; |
| } else { |
| last = x; |
| x = x.right; |
| } |
| } |
| return last; |
| } |
| |
| /** |
| * Returns the first key in this map. |
| * |
| * @return the first key in this map. |
| * @exception NoSuchElementException |
| * if this sorted map is empty. |
| * @since Android 1.0 |
| */ |
| 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; |
| } |
| |
| /** |
| * Returns the value of the mapping with the specified key. |
| * |
| * @param key |
| * the key. |
| * @return the value of the mapping with the specified key. |
| * @throws ClassCastException |
| * if the key cannot be compared with the keys in this map. |
| * @throws NullPointerException |
| * if the key is {@code null} and the comparator cannot handle |
| * {@code null}. |
| * @since Android 1.0 |
| */ |
| @Override |
| public V get(Object key) { |
| Entry<K, V> node = find(key); |
| if (node != null) { |
| return node.value; |
| } |
| return null; |
| } |
| |
| /** |
| * Returns a sorted map over a range of this sorted map with all keys that |
| * are less than the specified {@code endKey}. Changes to the returned |
| * sorted map are reflected in this sorted map and vice versa. |
| * <p> |
| * Note: The returned map will not allow an insertion of a key outside the |
| * specified range. |
| * </p> |
| * |
| * @param endKey |
| * the high boundary of the range specified. |
| * @return a sorted map where the keys are less than {@code endKey}. |
| * @throws ClassCastException |
| * if the specified key cannot be compared with the keys in this |
| * map. |
| * @throws NullPointerException |
| * if the specified key is {@code null} and the comparator |
| * cannot handle {@code null} keys. |
| * @throws IllegalArgumentException |
| * if this map is itself a sorted map over a range of another |
| * map and the specified key is outside of its range. |
| * @since Android 1.0 |
| */ |
| 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); |
| } |
| |
| /** |
| * Returns a set of the keys contained in this map. The set is backed by |
| * this map so changes to one are reflected by the other. The set does not |
| * support adding. |
| * |
| * @return a set of the keys. |
| * @since Android 1.0 |
| */ |
| @Override |
| public Set<K> keySet() { |
| if (keySet == null) { |
| keySet = new AbstractSet<K>() { |
| @Override |
| public boolean contains(Object object) { |
| return containsKey(object); |
| } |
| |
| @Override |
| public int size() { |
| return size; |
| } |
| |
| @Override |
| public void clear() { |
| TreeMap.this.clear(); |
| } |
| |
| @Override |
| public Iterator<K> iterator() { |
| return new UnboundedKeyIterator<K,V> (TreeMap.this); |
| } |
| }; |
| } |
| return keySet; |
| } |
| |
| /** |
| * Returns the last key in this map. |
| * |
| * @return the last key in this map. |
| * @throws NoSuchElementException |
| * if this map is empty. |
| * @since Android 1.0 |
| */ |
| public K lastKey() { |
| if (root != null) { |
| return maximum(root).key; |
| } |
| throw new NoSuchElementException(); |
| } |
| |
| 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) { |
| x.parent.left = y; |
| } else { |
| x.parent.right = y; |
| } |
| } |
| y.left = x; |
| x.parent = y; |
| } |
| |
| static <K, V> Entry<K, V> maximum(Entry<K, V> x) { |
| while (x.right != null) { |
| x = x.right; |
| } |
| return x; |
| } |
| |
| static <K, V> Entry<K, V> minimum(Entry<K, V> x) { |
| while (x.left != null) { |
| x = x.left; |
| } |
| return x; |
| } |
| |
| static <K, V> Entry<K, V> predecessor(Entry<K, V> x) { |
| if (x.left != null) { |
| return maximum(x.left); |
| } |
| Entry<K, V> y = x.parent; |
| while (y != null && x == y.left) { |
| x = y; |
| y = y.parent; |
| } |
| return y; |
| } |
| |
| /** |
| * Maps the specified key to the specified value. |
| * |
| * @param key |
| * the key. |
| * @param value |
| * the value. |
| * @return the value of any previous mapping with the specified key or |
| * {@code null} if there was no mapping. |
| * @throws ClassCastException |
| * if the specified key cannot be compared with the keys in this |
| * map. |
| * @throws NullPointerException |
| * if the specified key is {@code null} and the comparator |
| * cannot handle {@code null} keys. |
| * @since Android 1.0 |
| */ |
| @Override |
| public V put(K key, V value) { |
| MapEntry<K, V> entry = rbInsert(key); |
| V result = entry.value; |
| entry.value = value; |
| return result; |
| } |
| |
| /** |
| * Copies all the mappings in the given map to this map. These mappings will |
| * replace all mappings that this map had for any of the keys currently in |
| * the given map. |
| * |
| * @param map |
| * the map to copy mappings from. |
| * @throws ClassCastException |
| * if a key in the specified map cannot be compared with the |
| * keys in this map. |
| * @throws NullPointerException |
| * if a key in the specified map is {@code null} and the |
| * comparator cannot handle {@code null} keys. |
| * @since Android 1.0 |
| */ |
| @Override |
| public void putAll(Map<? extends K, ? extends V> map) { |
| super.putAll(map); |
| } |
| |
| void rbDelete(Entry<K, V> z) { |
| Entry<K, V> y = z.left == null || z.right == null ? z : successor(z); |
| Entry<K, V> x = y.left != null ? y.left : y.right; |
| if (x != null) { |
| x.parent = y.parent; |
| } |
| if (y.parent == null) { |
| root = x; |
| } else if (y == y.parent.left) { |
| y.parent.left = x; |
| } else { |
| y.parent.right = x; |
| } |
| modCount++; |
| if (y != z) { |
| z.key = y.key; |
| z.value = y.value; |
| } |
| if (!y.color && root != null) { |
| if (x == null) { |
| fixup(y.parent); |
| } else { |
| fixup(x); |
| } |
| } |
| size--; |
| } |
| |
| private Entry<K, V> rbInsert(K object) { |
| int result = 0; |
| Entry<K, V> y = null; |
| if (size != 0) { |
| Comparable<K> key = null; |
| if (comparator == null) { |
| key = toComparable(object); |
| } |
| Entry<K, V> x = root; |
| while (x != null) { |
| y = x; |
| result = key != null ? key.compareTo(x.key) : comparator |
| .compare(object, x.key); |
| if (result == 0) { |
| return x; |
| } |
| x = result < 0 ? x.left : x.right; |
| } |
| } |
| |
| size++; |
| modCount++; |
| Entry<K, V> z = new Entry<K, V>(object); |
| if (y == null) { |
| return root = z; |
| } |
| z.parent = y; |
| if (result < 0) { |
| y.left = z; |
| } else { |
| y.right = z; |
| } |
| balance(z); |
| return z; |
| } |
| |
| /** |
| * Removes the mapping with the specified key from this map. |
| * |
| * @param key |
| * the key of the mapping to remove. |
| * @return the value of the removed mapping or {@code null} if no mapping |
| * for the specified key was found. |
| * @throws ClassCastException |
| * if the specified key cannot be compared with the keys in this |
| * map. |
| * @throws NullPointerException |
| * if the specified key is {@code null} and the comparator |
| * cannot handle {@code null} keys. |
| * @since Android 1.0 |
| */ |
| @Override |
| public V remove(Object key) { |
| if (size == 0) { |
| return null; |
| } |
| Entry<K, V> node = find(key); |
| if (node == null) { |
| return null; |
| } |
| V result = node.value; |
| rbDelete(node); |
| return result; |
| } |
| |
| private void rightRotate(Entry<K, V> x) { |
| Entry<K, V> y = x.left; |
| x.left = y.right; |
| if (y.right != null) { |
| y.right.parent = x; |
| } |
| y.parent = x.parent; |
| if (x.parent == null) { |
| root = y; |
| } else { |
| if (x == x.parent.right) { |
| x.parent.right = y; |
| } else { |
| x.parent.left = y; |
| } |
| } |
| y.right = x; |
| x.parent = y; |
| } |
| |
| /** |
| * Returns the number of mappings in this map. |
| * |
| * @return the number of mappings in this map. |
| * @since Android 1.0 |
| */ |
| @Override |
| public int size() { |
| return size; |
| } |
| |
| /** |
| * Returns a sorted map over a range of this sorted map with all keys |
| * greater than or equal to the specified {@code startKey} and less than the |
| * specified {@code endKey}. Changes to the returned sorted map are |
| * reflected in this sorted map and vice versa. |
| * <p> |
| * Note: The returned map will not allow an insertion of a key outside the |
| * specified range. |
| * </p> |
| * |
| * @param startKey |
| * the low boundary of the range (inclusive). |
| * @param endKey |
| * the high boundary of the range (exclusive), |
| * @return a sorted map with the key from the specified range. |
| * @throws ClassCastException |
| * if the start or end key cannot be compared with the keys in |
| * this map. |
| * @throws NullPointerException |
| * if the start or end key is {@code null} and the comparator |
| * cannot handle {@code null} keys. |
| * @throws IllegalArgumentException |
| * if the start key is greater than the end key, or if this map |
| * is itself a sorted map over a range of another sorted map and |
| * the specified range is outside of its range. |
| * @since Android 1.0 |
| */ |
| public SortedMap<K, V> subMap(K startKey, K endKey) { |
| if (comparator == null) { |
| if (toComparable(startKey).compareTo(endKey) <= 0) { |
| return new SubMap<K, V>(startKey, this, endKey); |
| } |
| } else { |
| if (comparator.compare(startKey, endKey) <= 0) { |
| return new SubMap<K, V>(startKey, this, endKey); |
| } |
| } |
| throw new IllegalArgumentException(); |
| } |
| |
| static <K, V> Entry<K, V> successor(Entry<K, V> x) { |
| if (x.right != null) { |
| return minimum(x.right); |
| } |
| Entry<K, V> y = x.parent; |
| while (y != null && x == y.right) { |
| x = y; |
| y = y.parent; |
| } |
| return y; |
| } |
| |
| /** |
| * Returns a sorted map over a range of this sorted map with all keys that |
| * are greater than or equal to the specified {@code startKey}. Changes to |
| * the returned sorted map are reflected in this sorted map and vice versa. |
| * <p> |
| * Note: The returned map will not allow an insertion of a key outside the |
| * specified range. |
| * </p> |
| * |
| * @param startKey |
| * the low boundary of the range specified. |
| * @return a sorted map where the keys are greater or equal to |
| * {@code startKey}. |
| * @throws ClassCastException |
| * if the specified key cannot be compared with the keys in this |
| * map. |
| * @throws NullPointerException |
| * if the specified key is {@code null} and the comparator |
| * cannot handle {@code null} keys. |
| * @throws IllegalArgumentException |
| * if this map itself a sorted map over a range of another map |
| * and the specified key is outside of its range. |
| * @since Android 1.0 |
| */ |
| public SortedMap<K, V> tailMap(K startKey) { |
| // Check for errors |
| if (comparator == null) { |
| toComparable(startKey).compareTo(startKey); |
| } else { |
| comparator.compare(startKey, startKey); |
| } |
| return new SubMap<K, V>(startKey, this); |
| } |
| |
| /** |
| * Returns a collection of the values contained in this map. The collection |
| * is backed by this map so changes to one are reflected by the other. The |
| * collection supports remove, removeAll, retainAll and clear operations, |
| * and it does not support add or addAll operations. |
| * <p> |
| * This method returns a collection which is the subclass of |
| * AbstractCollection. The iterator method of this subclass returns a |
| * "wrapper object" over the iterator of map's entrySet(). The {@code size} |
| * method wraps the map's size method and the {@code contains} method wraps |
| * the map's containsValue method. |
| * </p> |
| * <p> |
| * The collection is created when this method is called for the first time |
| * and returned in response to all subsequent calls. This method may return |
| * different collections when multiple concurrent calls occur, since no |
| * synchronization is performed. |
| * </p> |
| * |
| * @return a collection of the values contained in this map. |
| * @since Android 1.0 |
| */ |
| @Override |
| public Collection<V> values() { |
| if (valuesCollection == null) { |
| valuesCollection = new AbstractCollection<V>() { |
| @Override |
| public boolean contains(Object object) { |
| return containsValue(object); |
| } |
| |
| @Override |
| public int size() { |
| return size; |
| } |
| |
| @Override |
| public void clear() { |
| TreeMap.this.clear(); |
| } |
| |
| @Override |
| public Iterator<V> iterator() { |
| return new UnboundedValueIterator<K,V> (TreeMap.this); |
| } |
| }; |
| } |
| return valuesCollection; |
| } |
| |
| private void writeObject(ObjectOutputStream stream) throws IOException { |
| stream.defaultWriteObject(); |
| stream.writeInt(size); |
| if (size > 0) { |
| Entry<K, V> node = minimum(root); |
| while (node != null) { |
| stream.writeObject(node.key); |
| stream.writeObject(node.value); |
| node = successor(node); |
| } |
| } |
| } |
| |
| @SuppressWarnings("unchecked") |
| private void readObject(ObjectInputStream stream) throws IOException, |
| ClassNotFoundException { |
| stream.defaultReadObject(); |
| size = stream.readInt(); |
| Entry<K, V> last = null; |
| for (int i = size; --i >= 0;) { |
| Entry<K, V> node = new Entry<K, V>((K)stream.readObject()); |
| node.value = (V)stream.readObject(); |
| if (last == null) { |
| root = node; |
| } else { |
| node.parent = last; |
| last.right = node; |
| balance(node); |
| } |
| last = node; |
| } |
| } |
| } |
