| /* |
| * 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 1.2 |
| */ |
| public class TreeMap <K, V> extends AbstractMap<K, V> implements SortedMap<K, V>, |
| Cloneable, Serializable { |
| private static final long serialVersionUID = 919286545866124006L; |
| |
| transient int size; |
| |
| private Comparator<? super K> comparator; |
| |
| transient int modCount; |
| |
| transient Set<Map.Entry<K, V>> entrySet; |
| |
| transient Node<K, V> root; |
| |
| class MapEntry implements Map.Entry<K, V>, Cloneable { |
| |
| final int offset; |
| final Node<K, V> node; |
| final K key; |
| |
| MapEntry(Node<K, V> node, int offset) { |
| this.node = node; |
| this.offset = offset; |
| key = node.keys[offset]; |
| } |
| |
| @Override |
| public Object clone() { |
| try { |
| return super.clone(); |
| } catch (CloneNotSupportedException e) { |
| return null; |
| } |
| } |
| |
| @Override |
| public boolean equals(Object object) { |
| if (this == object) { |
| return true; |
| } |
| if (object instanceof Map.Entry) { |
| Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object; |
| V value = getValue(); |
| return (key == null ? entry.getKey() == null : key.equals(entry |
| .getKey())) |
| && (value == null ? entry.getValue() == null : value |
| .equals(entry.getValue())); |
| } |
| return false; |
| } |
| |
| public K getKey() { |
| return key; |
| } |
| |
| public V getValue() { |
| if (node.keys[offset] == key) { |
| return node.values[offset]; |
| } |
| if (containsKey(key)) { |
| return get(key); |
| } |
| throw new IllegalStateException(); |
| } |
| |
| @Override |
| public int hashCode() { |
| V value = getValue(); |
| return (key == null ? 0 : key.hashCode()) |
| ^ (value == null ? 0 : value.hashCode()); |
| } |
| |
| public V setValue(V object) { |
| if (node.keys[offset] == key) { |
| V res = node.values[offset]; |
| node.values[offset] = object; |
| return res; |
| } |
| if (containsKey(key)) { |
| return put(key, object); |
| } |
| throw new IllegalStateException(); |
| } |
| |
| @Override |
| public String toString() { |
| return key + "=" + getValue(); |
| } |
| } |
| |
| static class Node <K,V> implements Cloneable { |
| static final int NODE_SIZE = 64; |
| Node<K, V> prev, next; |
| Node<K, V> parent, left, right; |
| V[] values; |
| K[] keys; |
| int left_idx = 0; |
| int right_idx = -1; |
| int size = 0; |
| boolean color; |
| |
| public Node() { |
| keys = (K[]) new Object[NODE_SIZE]; |
| values = (V[]) new Object[NODE_SIZE]; |
| } |
| |
| @SuppressWarnings("unchecked") |
| Node<K, V> clone(Node<K, V> parent) throws CloneNotSupportedException { |
| Node<K, V> clone = (Node<K, V>) super.clone(); |
| clone.keys = (K[]) new Object[NODE_SIZE]; |
| clone.values = (V[]) new Object[NODE_SIZE]; |
| System.arraycopy(keys, 0, clone.keys, 0, keys.length); |
| System.arraycopy(values, 0, clone.values, 0, values.length); |
| clone.left_idx = left_idx; |
| clone.right_idx = right_idx; |
| clone.parent = parent; |
| if (left != null) { |
| clone.left = left.clone(clone); |
| } |
| if (right != null) { |
| clone.right = right.clone(clone); |
| } |
| clone.prev = null; |
| clone.next = null; |
| return clone; |
| } |
| } |
| |
| @SuppressWarnings("unchecked") |
| private static <T> Comparable<T> toComparable(T obj) { |
| if (obj == null) { |
| throw new NullPointerException(); |
| } |
| return (Comparable) obj; |
| } |
| |
| static class AbstractMapIterator <K,V> { |
| TreeMap<K, V> backingMap; |
| int expectedModCount; |
| Node<K, V> node; |
| Node<K, V> lastNode; |
| int offset; |
| int lastOffset; |
| |
| AbstractMapIterator(TreeMap<K, V> map, Node<K, V> startNode, int startOffset) { |
| backingMap = map; |
| expectedModCount = map.modCount; |
| node = startNode; |
| offset = startOffset; |
| } |
| |
| AbstractMapIterator(TreeMap<K, V> map, Node<K, V> startNode) { |
| this(map, startNode, startNode != null ? |
| startNode.right_idx - startNode.left_idx : 0); |
| } |
| |
| AbstractMapIterator(TreeMap<K, V> map) { |
| this(map, minimum(map.root)); |
| } |
| |
| public boolean hasNext() { |
| return node != null; |
| } |
| |
| final void makeNext() { |
| if (expectedModCount != backingMap.modCount) { |
| throw new ConcurrentModificationException(); |
| } else if (node == null) { |
| throw new NoSuchElementException(); |
| } |
| lastNode = node; |
| lastOffset = offset; |
| if (offset != 0) { |
| offset--; |
| } else { |
| node = node.next; |
| if (node != null) { |
| offset = node.right_idx - node.left_idx; |
| } |
| } |
| } |
| |
| final public void remove() { |
| if (expectedModCount == backingMap.modCount) { |
| if (lastNode != null) { |
| int idx = lastNode.right_idx - lastOffset; |
| backingMap.removeFromIterator(lastNode, idx); |
| lastNode = null; |
| expectedModCount++; |
| } else { |
| throw new IllegalStateException(); |
| } |
| } else { |
| throw new ConcurrentModificationException(); |
| } |
| } |
| } |
| |
| static class UnboundedEntryIterator <K, V> extends AbstractMapIterator<K, V> |
| implements Iterator<Map.Entry<K, V>> { |
| |
| UnboundedEntryIterator(TreeMap<K, V> map, Node<K, V> startNode, int startOffset) { |
| super(map, startNode, startOffset); |
| } |
| |
| UnboundedEntryIterator(TreeMap<K, V> map) { |
| super(map); |
| } |
| |
| public Map.Entry<K, V> next() { |
| makeNext(); |
| int idx = lastNode.right_idx - lastOffset; |
| return backingMap.new MapEntry(lastNode, idx); |
| } |
| } |
| |
| static class UnboundedKeyIterator <K, V> extends AbstractMapIterator<K, V> |
| implements Iterator<K> { |
| |
| UnboundedKeyIterator(TreeMap<K, V> map, Node<K, V> startNode, int startOffset) { |
| super(map, startNode, startOffset); |
| } |
| |
| UnboundedKeyIterator(TreeMap<K, V> map) { |
| super(map); |
| } |
| |
| public K next() { |
| makeNext(); |
| return lastNode.keys[lastNode.right_idx - lastOffset]; |
| } |
| } |
| |
| static class UnboundedValueIterator <K, V> extends AbstractMapIterator<K, V> |
| implements Iterator<V> { |
| |
| UnboundedValueIterator(TreeMap<K, V> map, Node<K, V> startNode, int startOffset) { |
| super(map, startNode, startOffset); |
| } |
| |
| UnboundedValueIterator(TreeMap<K, V> map) { |
| super(map); |
| } |
| |
| public V next() { |
| makeNext(); |
| return lastNode.values[lastNode.right_idx - lastOffset]; |
| } |
| } |
| |
| static class BoundedMapIterator <K, V> extends AbstractMapIterator<K, V> { |
| |
| Node<K, V> finalNode; |
| int finalOffset; |
| |
| BoundedMapIterator(Node<K, V> startNode, int startOffset, TreeMap<K, V> map, |
| Node<K, V> finalNode, int finalOffset) { |
| super(map, finalNode==null? null : startNode, startOffset); |
| this.finalNode = finalNode; |
| this.finalOffset = finalOffset; |
| } |
| |
| BoundedMapIterator(Node<K, V> startNode, TreeMap<K, V> map, |
| Node<K, V> finalNode, int finalOffset) { |
| this(startNode, startNode != null ? |
| startNode.right_idx - startNode.left_idx : 0, |
| map, finalNode, finalOffset); |
| } |
| |
| BoundedMapIterator(Node<K, V> startNode, int startOffset, |
| TreeMap<K, V> map, Node<K, V> finalNode) { |
| this(startNode, startOffset, map, finalNode, |
| finalNode.right_idx - finalNode.left_idx); |
| } |
| |
| void makeBoundedNext() { |
| makeNext(); |
| if (lastNode == finalNode && lastOffset == finalOffset) { |
| node = null; |
| } |
| } |
| } |
| |
| static class BoundedEntryIterator <K, V> extends BoundedMapIterator<K, V> |
| implements Iterator<Map.Entry<K, V>> { |
| |
| public BoundedEntryIterator(Node<K, V> startNode, int startOffset, TreeMap<K, V> map, |
| Node<K, V> finalNode, int finalOffset) { |
| super(startNode, startOffset, map, finalNode, finalOffset); |
| } |
| |
| public Map.Entry<K, V> next() { |
| makeBoundedNext(); |
| int idx = lastNode.right_idx - lastOffset; |
| return backingMap.new MapEntry(lastNode, idx); |
| } |
| } |
| |
| static class BoundedKeyIterator <K, V> extends BoundedMapIterator<K, V> |
| implements Iterator<K> { |
| |
| public BoundedKeyIterator(Node<K, V> startNode, int startOffset, TreeMap<K, V> map, |
| Node<K, V> finalNode, int finalOffset) { |
| super(startNode, startOffset, map, finalNode, finalOffset); |
| } |
| |
| public K next() { |
| makeBoundedNext(); |
| return lastNode.keys[lastNode.right_idx - lastOffset]; |
| } |
| } |
| |
| static class BoundedValueIterator <K, V> extends BoundedMapIterator<K, V> |
| implements Iterator<V> { |
| |
| public BoundedValueIterator(Node<K, V> startNode, int startOffset, TreeMap<K, V> map, |
| Node<K, V> finalNode, int finalOffset) { |
| super(startNode, startOffset, map, finalNode, finalOffset); |
| } |
| |
| public V next() { |
| makeBoundedNext(); |
| return lastNode.values[lastNode.right_idx - lastOffset]; |
| } |
| } |
| |
| 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; |
| transient int firstKeyModCount = -1; |
| transient int lastKeyModCount = -1; |
| transient Node<K, V> firstKeyNode; |
| transient int firstKeyIndex; |
| transient Node<K, V> lastKeyNode; |
| transient int lastKeyIndex; |
| |
| 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 void clear() { |
| keySet().clear(); |
| } |
| |
| @Override |
| public boolean containsValue(Object value) { |
| Iterator<V> it = values().iterator(); |
| if (value != null) { |
| while (it.hasNext()) { |
| if (value.equals(it.next())) { |
| return true; |
| } |
| } |
| } else { |
| while (it.hasNext()) { |
| if (it.next() == null) { |
| return true; |
| } |
| } |
| } |
| return false; |
| } |
| |
| @Override |
| public Set<Map.Entry<K, V>> entrySet() { |
| if (entrySet == null) { |
| entrySet = new SubMapEntrySet<K, V>(this); |
| } |
| return entrySet; |
| } |
| |
| private void setFirstKey() { |
| if (firstKeyModCount == backingMap.modCount) { |
| return; |
| } |
| Comparable<K> object = backingMap.comparator == null ? |
| toComparable((K) startKey) : null; |
| K key = (K) startKey; |
| Node<K, V> node = backingMap.root; |
| Node<K, V> foundNode = null; |
| int foundIndex = -1; |
| TOP_LOOP: |
| while (node != null) { |
| K[] keys = node.keys; |
| int left_idx = node.left_idx; |
| int result = backingMap.cmp(object, key, keys[left_idx]); |
| if (result < 0) { |
| foundNode = node; |
| foundIndex = left_idx; |
| node = node.left; |
| } else if (result == 0) { |
| foundNode = node; |
| foundIndex = left_idx; |
| break; |
| } else { |
| int right_idx = node.right_idx; |
| if (left_idx != right_idx) { |
| result = backingMap.cmp(object, key, keys[right_idx]); |
| } |
| if (result > 0) { |
| node = node.right; |
| } else if (result == 0) { |
| foundNode = node; |
| foundIndex = right_idx; |
| break; |
| } else { /*search in node*/ |
| foundNode = node; |
| foundIndex = right_idx; |
| int low = left_idx + 1, mid = 0, high = right_idx - 1; |
| while (low <= high) { |
| mid = (low + high) >>> 1; |
| result = backingMap.cmp(object, key, keys[mid]); |
| if (result > 0) { |
| low = mid + 1; |
| } else if (result == 0) { |
| foundNode = node; |
| foundIndex = mid; |
| break TOP_LOOP; |
| } else { |
| foundNode = node; |
| foundIndex = mid; |
| high = mid - 1; |
| } |
| } |
| break TOP_LOOP; |
| } |
| } |
| } |
| if (foundNode != null && !checkUpperBound(foundNode.keys[foundIndex])) { |
| foundNode = null; |
| } |
| firstKeyNode = foundNode; |
| firstKeyIndex = foundIndex; |
| firstKeyModCount = backingMap.modCount; |
| } |
| |
| public K firstKey() { |
| if (backingMap.size > 0) { |
| if (!hasStart) { |
| Node<K, V> node = minimum(backingMap.root); |
| if (node != null && checkUpperBound(node.keys[node.left_idx])) { |
| return node.keys[node.left_idx]; |
| } |
| } else { |
| setFirstKey(); |
| if (firstKeyNode != null) { |
| return firstKeyNode.keys[firstKeyIndex]; |
| } |
| } |
| } |
| throw new NoSuchElementException(); |
| } |
| |
| |
| @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) { |
| setFirstKey(); |
| return firstKeyNode == null; |
| } else { |
| setLastKey(); |
| return lastKeyNode == null; |
| } |
| } |
| |
| @Override |
| public Set<K> keySet() { |
| if (keySet == null) { |
| keySet = new SubMapKeySet<K, V>(this); |
| } |
| return keySet; |
| } |
| |
| private void setLastKey() { |
| if (lastKeyModCount == backingMap.modCount) { |
| return; |
| } |
| Comparable<K> object = backingMap.comparator == null ? |
| toComparable((K) endKey) : null; |
| K key = (K) endKey; |
| Node<K, V> node = backingMap.root; |
| Node<K, V> foundNode = null; |
| int foundIndex = -1; |
| TOP_LOOP: |
| while (node != null) { |
| K[] keys = node.keys; |
| int left_idx = node.left_idx; |
| int result = backingMap.cmp(object, key, keys[left_idx]); |
| if (result <= 0) { |
| node = node.left; |
| } else { |
| int right_idx = node.right_idx; |
| if (left_idx != right_idx) { |
| result = backingMap.cmp(object, key, keys[right_idx]); |
| } |
| if (result > 0) { |
| foundNode = node; |
| foundIndex = right_idx; |
| node = node.right; |
| } else if (result == 0) { |
| if (node.left_idx == node.right_idx) { |
| foundNode = node.prev; |
| if (foundNode != null) { |
| foundIndex = foundNode.right_idx - 1; |
| } |
| } else { |
| foundNode = node; |
| foundIndex = right_idx - 1; |
| } |
| break; |
| } else { /*search in node*/ |
| foundNode = node; |
| foundIndex = left_idx; |
| int low = left_idx + 1, mid = 0, high = right_idx - 1; |
| while (low <= high) { |
| mid = (low + high) >>> 1; |
| result = backingMap.cmp(object, key, keys[mid]); |
| if (result > 0) { |
| foundNode = node; |
| foundIndex = mid; |
| low = mid + 1; |
| } else if (result == 0) { |
| foundNode = node; |
| foundIndex = mid - 1; |
| break TOP_LOOP; |
| } else { |
| high = mid - 1; |
| } |
| } |
| break TOP_LOOP; |
| } |
| } |
| } |
| if (foundNode != null && !checkLowerBound(foundNode.keys[foundIndex])) { |
| foundNode = null; |
| } |
| lastKeyNode = foundNode; |
| lastKeyIndex = foundIndex; |
| lastKeyModCount = backingMap.modCount; |
| } |
| |
| public K lastKey() { |
| if (backingMap.size > 0) { |
| if (!hasEnd) { |
| Node<K, V> node = maximum(backingMap.root); |
| if (node != null && checkLowerBound(node.keys[node.right_idx])) { |
| return node.keys[node.right_idx]; |
| } |
| } else { |
| setLastKey(); |
| if (lastKeyNode != null) { |
| return lastKeyNode.keys[lastKeyIndex]; |
| } |
| } |
| } |
| 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; |
| } |
| |
| public int size() { |
| Node<K, V> from, to; |
| int fromIndex, toIndex; |
| if (hasStart) { |
| setFirstKey(); |
| from = firstKeyNode; |
| fromIndex = firstKeyIndex; |
| } else { |
| from = minimum(backingMap.root); |
| fromIndex = from == null ? 0 : from.left_idx; |
| } |
| if (from == null) { |
| return 0; |
| } |
| if (hasEnd) { |
| setLastKey(); |
| to = lastKeyNode; |
| toIndex = lastKeyIndex; |
| } else { |
| to = maximum(backingMap.root); |
| toIndex = to == null ? 0 : to.right_idx; |
| } |
| if (to == null) { |
| return 0; |
| } |
| if (from == to) { |
| return toIndex - fromIndex + 1; |
| } |
| int sum = 0; |
| while (from != to) { |
| sum += (from.right_idx - fromIndex + 1); |
| from = from.next; |
| fromIndex = from.left_idx; |
| } |
| return sum + toIndex - fromIndex + 1; |
| } |
| |
| private void readObject(ObjectInputStream stream) throws IOException, |
| ClassNotFoundException { |
| stream.defaultReadObject(); |
| firstKeyModCount = -1; |
| lastKeyModCount = -1; |
| } |
| } |
| |
| 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(); |
| } |
| |
| public Iterator<Map.Entry<K, V>> iterator() { |
| Node<K, V> from; |
| int fromIndex; |
| if (subMap.hasStart) { |
| subMap.setFirstKey(); |
| from = subMap.firstKeyNode; |
| fromIndex = subMap.firstKeyIndex; |
| } else { |
| from = minimum(subMap.backingMap.root); |
| fromIndex = from != null ? from.left_idx : 0; |
| } |
| if (!subMap.hasEnd) { |
| return new UnboundedEntryIterator<K, V>(subMap.backingMap, from, from == null ? 0 : from.right_idx - fromIndex); |
| } |
| subMap.setLastKey(); |
| Node<K, V> to = subMap.lastKeyNode; |
| int toIndex = subMap.lastKeyIndex; |
| return new BoundedEntryIterator<K, V>(from, from == null ? 0 : from.right_idx - fromIndex, subMap.backingMap, to, to == null ? 0 : to.right_idx - toIndex); |
| } |
| |
| @Override |
| public int size() { |
| return subMap.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 && subMap.containsKey(key) ) : v1.equals(v2); |
| } |
| } |
| return false; |
| } |
| |
| @Override |
| public boolean remove(Object object) { |
| if (contains(object)) { |
| Map.Entry<K, V> entry = (Map.Entry<K, V>) object; |
| K key = entry.getKey(); |
| subMap.remove(key); |
| return true; |
| } |
| 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() { |
| return subMap.size(); |
| } |
| |
| @Override |
| public boolean remove(Object object) { |
| if (subMap.containsKey(object)) { |
| subMap.remove(object); |
| return true; |
| } |
| return false; |
| } |
| |
| public Iterator<K> iterator() { |
| Node<K, V> from; |
| int fromIndex; |
| if (subMap.hasStart) { |
| subMap.setFirstKey(); |
| from = subMap.firstKeyNode; |
| fromIndex = subMap.firstKeyIndex; |
| } else { |
| from = minimum(subMap.backingMap.root); |
| fromIndex = from != null ? from.left_idx : 0; |
| } |
| if (!subMap.hasEnd) { |
| return new UnboundedKeyIterator<K, V>(subMap.backingMap, from, |
| from == null ? 0 : from.right_idx - fromIndex); |
| } |
| subMap.setLastKey(); |
| Node<K, V> to = subMap.lastKeyNode; |
| int toIndex = subMap.lastKeyIndex; |
| return new BoundedKeyIterator<K, V>(from, |
| from == null ? 0 : from.right_idx - fromIndex, subMap.backingMap, to, |
| to == null ? 0 : to.right_idx - toIndex); |
| } |
| } |
| |
| 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() { |
| Node<K, V> from; |
| int fromIndex; |
| if (subMap.hasStart) { |
| subMap.setFirstKey(); |
| from = subMap.firstKeyNode; |
| fromIndex = subMap.firstKeyIndex; |
| } else { |
| from = minimum(subMap.backingMap.root); |
| fromIndex = from != null ? from.left_idx : 0; |
| } |
| if (!subMap.hasEnd) { |
| return new UnboundedValueIterator<K, V>(subMap.backingMap, from, |
| from == null ? 0 : from.right_idx - fromIndex); |
| } |
| subMap.setLastKey(); |
| Node<K, V> to = subMap.lastKeyNode; |
| int toIndex = subMap.lastKeyIndex; |
| return new BoundedValueIterator<K, V>(from, |
| from == null ? 0 : from.right_idx - fromIndex, subMap.backingMap, to, |
| to == null ? 0 : to.right_idx - toIndex); |
| } |
| |
| @Override |
| public int size() { |
| return subMap.size(); |
| } |
| } |
| |
| /** |
| * Constructs a new empty {@code TreeMap} instance. |
| */ |
| public TreeMap() { |
| } |
| |
| /** |
| * Constructs a new empty {@code TreeMap} instance with the specified |
| * comparator. |
| * |
| * @param comparator |
| * the comparator to compare keys with. |
| */ |
| 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. |
| */ |
| public TreeMap(Map<? extends K, ? extends V> map) { |
| 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. |
| */ |
| public TreeMap(SortedMap<K, ? extends V> map) { |
| this(map.comparator()); |
| Node<K, V> lastNode = null; |
| Iterator<? extends Map.Entry<K, ? extends V>> it = map.entrySet().iterator(); |
| while (it.hasNext()) { |
| Map.Entry<K, ? extends V> entry = it.next(); |
| lastNode = addToLast(lastNode, entry.getKey(), entry.getValue()); |
| } |
| } |
| |
| Node<K, V> addToLast(Node<K, V> last, K key, V value) { |
| if (last == null) { |
| root = last = createNode(key, value); |
| size = 1; |
| } else if (last.size == Node.NODE_SIZE) { |
| Node<K, V> newNode = createNode(key, value); |
| attachToRight(last, newNode); |
| balance(newNode); |
| size++; |
| last = newNode; |
| } else { |
| appendFromRight(last, key, value); |
| size++; |
| } |
| return last; |
| } |
| |
| /** |
| * Removes all mappings from this TreeMap, leaving it empty. |
| * |
| * @see Map#isEmpty() |
| * @see #size() |
| */ |
| @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 |
| */ |
| @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); |
| // restore prev/next chain |
| Node<K, V> node = minimum(clone.root); |
| while (true) { |
| Node<K, V> nxt = successor(node); |
| if (nxt == null) { |
| break; |
| } |
| nxt.prev = node; |
| node.next = nxt; |
| node = nxt; |
| } |
| } |
| return clone; |
| } catch (CloneNotSupportedException e) { |
| return null; |
| } |
| } |
| |
| static private <K, V> Node<K, V> successor(Node<K, V> x) { |
| if (x.right != null) { |
| return minimum(x.right); |
| } |
| Node<K, V> y = x.parent; |
| while (y != null && x == y.right) { |
| x = y; |
| y = y.parent; |
| } |
| return y; |
| } |
| |
| /** |
| * Returns the comparator used to compare elements in this map. |
| * |
| * @return the comparator or {@code null} if the natural ordering is used. |
| */ |
| 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. |
| * @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. |
| */ |
| @Override |
| public boolean containsKey(Object key) { |
| Comparable<K> object = comparator == null ? toComparable((K) key) : null; |
| K keyK = (K) key; |
| Node<K, V> node = root; |
| while (node != null) { |
| K[] keys = node.keys; |
| int left_idx = node.left_idx; |
| int result = cmp(object, keyK, keys[left_idx]); |
| if (result < 0) { |
| node = node.left; |
| } else if (result == 0) { |
| return true; |
| } else { |
| int right_idx = node.right_idx; |
| if (left_idx != right_idx) { |
| result = cmp(object, keyK, keys[right_idx]); |
| } |
| if (result > 0) { |
| node = node.right; |
| } else if (result == 0) { |
| return true; |
| } else { /*search in node*/ |
| int low = left_idx + 1, mid = 0, high = right_idx - 1; |
| while (low <= high) { |
| mid = (low + high) >>> 1; |
| result = cmp(object, keyK, keys[mid]); |
| if (result > 0) { |
| low = mid + 1; |
| } else if (result == 0) { |
| return true; |
| } else { |
| high = mid - 1; |
| } |
| } |
| return false; |
| } |
| } |
| } |
| return false; |
| } |
| |
| /** |
| * 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. |
| */ |
| @Override |
| public boolean containsValue(Object value) { |
| if (root == null) { |
| return false; |
| } |
| Node<K, V> node = minimum(root); |
| if (value != null) { |
| while (node != null) { |
| int to = node.right_idx; |
| V[] values = node.values; |
| for (int i = node.left_idx; i <= to; i++) { |
| if (value.equals(values[i])) { |
| return true; |
| } |
| } |
| node = node.next; |
| } |
| } else { |
| while (node != null) { |
| int to = node.right_idx; |
| V[] values = node.values; |
| for (int i = node.left_idx; i <= to; i++) { |
| if (values[i] == null) { |
| return true; |
| } |
| } |
| node = node.next; |
| } |
| } |
| 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. |
| */ |
| @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; |
| K key = entry.getKey(); |
| Object v1 = TreeMap.this.get(key), v2 = entry.getValue(); |
| return v1 == null ? ( v2 == null && TreeMap.this.containsKey(key) ) : v1.equals(v2); |
| } |
| return false; |
| } |
| |
| @Override |
| public boolean remove(Object object) { |
| if (contains(object)) { |
| Map.Entry<K, V> entry = (Map.Entry<K, V>) object; |
| K key = entry.getKey(); |
| TreeMap.this.remove(key); |
| return true; |
| } |
| return false; |
| } |
| |
| @Override |
| public Iterator<Map.Entry<K, V>> iterator() { |
| return new UnboundedEntryIterator<K, V>(TreeMap.this); |
| } |
| }; |
| } |
| return entrySet; |
| } |
| |
| /** |
| * Returns the first key in this map. |
| * |
| * @return the first key in this map. |
| * @throws NoSuchElementException |
| * if this map is empty. |
| */ |
| public K firstKey() { |
| if (root != null) { |
| Node<K, V> node = minimum(root); |
| return node.keys[node.left_idx]; |
| } |
| throw new NoSuchElementException(); |
| } |
| |
| |
| /** |
| * 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}. |
| */ |
| @Override |
| public V get(Object key) { |
| Comparable<K> object = comparator == null ? toComparable((K) key) : null; |
| K keyK = (K) key; |
| Node<K, V> node = root; |
| while (node != null) { |
| K[] keys = node.keys; |
| int left_idx = node.left_idx; |
| int result = cmp(object, keyK, keys[left_idx]); |
| if (result < 0) { |
| node = node.left; |
| } else if (result == 0) { |
| return node.values[left_idx]; |
| } else { |
| int right_idx = node.right_idx; |
| if (left_idx != right_idx) { |
| result = cmp(object, keyK, keys[right_idx]); |
| } |
| if (result > 0) { |
| node = node.right; |
| } else if (result == 0) { |
| return node.values[right_idx]; |
| } else { /*search in node*/ |
| int low = left_idx + 1, mid = 0, high = right_idx - 1; |
| while (low <= high) { |
| mid = (low + high) >>> 1; |
| result = cmp(object, keyK, keys[mid]); |
| if (result > 0) { |
| low = mid + 1; |
| } else if (result == 0) { |
| return node.values[mid]; |
| } else { |
| high = mid - 1; |
| } |
| } |
| return null; |
| } |
| } |
| } |
| return null; |
| } |
| |
| private int cmp(Comparable<K> object, K key1, K key2) { |
| return object != null ? |
| object.compareTo(key2) : comparator.compare(key1, key2); |
| } |
| |
| /** |
| * 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. |
| * |
| * @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. |
| */ |
| 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. |
| */ |
| @Override |
| public Set<K> keySet() { |
| if (keySet == null) { |
| keySet = new AbstractSet<K>() { |
| @Override |
| public boolean contains(Object object) { |
| return TreeMap.this.containsKey(object); |
| } |
| |
| @Override |
| public int size() { |
| return TreeMap.this.size; |
| } |
| |
| @Override |
| public void clear() { |
| TreeMap.this.clear(); |
| } |
| |
| @Override |
| public boolean remove(Object object) { |
| if (contains(object)) { |
| TreeMap.this.remove(object); |
| return true; |
| } |
| return false; |
| } |
| |
| @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. |
| */ |
| public K lastKey() { |
| if (root != null) { |
| Node<K, V> node = maximum(root); |
| return node.keys[node.right_idx]; |
| } |
| throw new NoSuchElementException(); |
| } |
| |
| static <K,V> Node<K, V> minimum(Node<K, V> x) { |
| if (x == null) { |
| return null; |
| } |
| while (x.left != null) { |
| x = x.left; |
| } |
| return x; |
| } |
| |
| static <K,V> Node<K, V> maximum(Node<K, V> x) { |
| if (x == null) { |
| return null; |
| } |
| while (x.right != null) { |
| x = x.right; |
| } |
| return x; |
| } |
| |
| /** |
| * 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. |
| */ |
| @Override |
| public V put(K key, V value) { |
| if (root == null) { |
| root = createNode(key, value); |
| size = 1; |
| modCount++; |
| return null; |
| } |
| Comparable<K> object = comparator == null ? toComparable((K) key) : null; |
| K keyK = (K) key; |
| Node<K, V> node = root; |
| Node<K, V> prevNode = null; |
| int result = 0; |
| while (node != null) { |
| prevNode = node; |
| K[] keys = node.keys; |
| int left_idx = node.left_idx; |
| result = cmp(object, keyK, keys[left_idx]); |
| if (result < 0) { |
| node = node.left; |
| } else if (result == 0) { |
| V res = node.values[left_idx]; |
| node.values[left_idx] = value; |
| return res; |
| } else { |
| int right_idx = node.right_idx; |
| if (left_idx != right_idx) { |
| result = cmp(object, keyK, keys[right_idx]); |
| } |
| if (result > 0) { |
| node = node.right; |
| } else if (result == 0) { |
| V res = node.values[right_idx]; |
| node.values[right_idx] = value; |
| return res; |
| } else { /*search in node*/ |
| int low = left_idx + 1, mid = 0, high = right_idx - 1; |
| while (low <= high) { |
| mid = (low + high) >>> 1; |
| result = cmp(object, keyK, keys[mid]); |
| if (result > 0) { |
| low = mid + 1; |
| } else if (result == 0) { |
| V res = node.values[mid]; |
| node.values[mid] = value; |
| return res; |
| } else { |
| high = mid - 1; |
| } |
| } |
| result = low; |
| break; |
| } |
| } |
| } /* while */ |
| /* |
| if(node == null) { |
| if(prevNode==null) { |
| - case of empty Tree |
| } else { |
| result < 0 - prevNode.left==null - attach here |
| result > 0 - prevNode.right==null - attach here |
| } |
| } else { |
| insert into node. |
| result - index where it should be inserted. |
| } |
| */ |
| size++; |
| modCount++; |
| if (node == null) { |
| if (prevNode == null) { |
| // case of empty Tree |
| root = createNode(key, value); |
| } else if (prevNode.size < Node.NODE_SIZE) { |
| // there is a place for insert |
| if (result < 0) { |
| appendFromLeft(prevNode, key, value); |
| } else { |
| appendFromRight(prevNode, key, value); |
| } |
| } else { |
| // create and link |
| Node<K, V> newNode = createNode(key, value); |
| if (result < 0) { |
| attachToLeft(prevNode, newNode); |
| } else { |
| attachToRight(prevNode, newNode); |
| } |
| balance(newNode); |
| } |
| } else { |
| // insert into node. |
| // result - index where it should be inserted. |
| if (node.size < Node.NODE_SIZE) { // insert and ok |
| int left_idx = node.left_idx; |
| int right_idx = node.right_idx; |
| if (left_idx == 0 || ((right_idx != Node.NODE_SIZE - 1) && (right_idx - result <= result - left_idx))) { |
| int right_idxPlus1 = right_idx + 1; |
| System.arraycopy(node.keys, result, node.keys, result + 1, right_idxPlus1 - result); |
| System.arraycopy(node.values, result, node.values, result + 1, right_idxPlus1 - result); |
| node.right_idx = right_idxPlus1; |
| node.keys[result] = key; |
| node.values[result] = value; |
| } else { |
| int left_idxMinus1 = left_idx - 1; |
| System.arraycopy(node.keys, left_idx, node.keys, left_idxMinus1, result - left_idx); |
| System.arraycopy(node.values, left_idx, node.values, left_idxMinus1, result - left_idx); |
| node.left_idx = left_idxMinus1; |
| node.keys[result - 1] = key; |
| node.values[result - 1] = value; |
| } |
| node.size++; |
| } else { |
| // there are no place here |
| // insert and push old pair |
| Node<K, V> previous = node.prev; |
| Node<K, V> nextNode = node.next; |
| boolean removeFromStart; |
| boolean attachFromLeft = false; |
| Node<K, V> attachHere = null; |
| if (previous == null) { |
| if (nextNode != null && nextNode.size < Node.NODE_SIZE) { |
| // move last pair to next |
| removeFromStart = false; |
| } else { |
| // next node doesn't exist or full |
| // left==null |
| // drop first pair to new node from left |
| removeFromStart = true; |
| attachFromLeft = true; |
| attachHere = node; |
| } |
| } else if (nextNode == null) { |
| if (previous.size < Node.NODE_SIZE) { |
| // move first pair to prev |
| removeFromStart = true; |
| } else { |
| // right == null; |
| // drop last pair to new node from right |
| removeFromStart = false; |
| attachFromLeft = false; |
| attachHere = node; |
| } |
| } else { |
| if (previous.size < Node.NODE_SIZE) { |
| if (nextNode.size < Node.NODE_SIZE) { |
| // choose prev or next for moving |
| removeFromStart = previous.size < nextNode.size; |
| } else { |
| // move first pair to prev |
| removeFromStart = true; |
| } |
| } else { |
| if (nextNode.size < Node.NODE_SIZE) { |
| // move last pair to next |
| removeFromStart = false; |
| } else { |
| // prev & next are full |
| // if node.right!=null then node.next.left==null |
| // if node.left!=null then node.prev.right==null |
| if (node.right == null) { |
| attachHere = node; |
| attachFromLeft = false; |
| removeFromStart = false; |
| } else { |
| attachHere = nextNode; |
| attachFromLeft = true; |
| removeFromStart = false; |
| } |
| } |
| } |
| } |
| K movedKey; |
| V movedValue; |
| if (removeFromStart) { |
| // node.left_idx == 0 |
| movedKey = node.keys[0]; |
| movedValue = node.values[0]; |
| int resMunus1 = result - 1; |
| System.arraycopy(node.keys, 1, node.keys, 0, resMunus1); |
| System.arraycopy(node.values, 1, node.values, 0, resMunus1); |
| node.keys [resMunus1] = key; |
| node.values[resMunus1] = value; |
| } else { |
| // node.right_idx == Node.NODE_SIZE - 1 |
| movedKey = node.keys[Node.NODE_SIZE - 1]; |
| movedValue = node.values[Node.NODE_SIZE - 1]; |
| System.arraycopy(node.keys, result, node.keys, result + 1, Node.NODE_SIZE - 1 - result); |
| System.arraycopy(node.values, result, node.values, result + 1, Node.NODE_SIZE - 1 - result); |
| node.keys[result] = key; |
| node.values[result] = value; |
| } |
| if (attachHere == null) { |
| if (removeFromStart) { |
| appendFromRight(previous, movedKey, movedValue); |
| } else { |
| appendFromLeft(nextNode, movedKey, movedValue); |
| } |
| } else { |
| Node<K, V> newNode = createNode(movedKey, movedValue); |
| if (attachFromLeft) { |
| attachToLeft(attachHere, newNode); |
| } else { |
| attachToRight(attachHere, newNode); |
| } |
| balance(newNode); |
| } |
| } |
| } |
| return null; |
| } |
| |
| private void appendFromLeft(Node<K, V> node, K keyObj, V value) { |
| if (node.left_idx == 0) { |
| int new_right = node.right_idx + 1; |
| System.arraycopy(node.keys, 0, node.keys, 1, new_right); |
| System.arraycopy(node.values, 0, node.values, 1, new_right); |
| node.right_idx = new_right; |
| } else { |
| node.left_idx--; |
| } |
| node.size++; |
| node.keys[node.left_idx] = keyObj; |
| node.values[node.left_idx] = value; |
| } |
| |
| private void attachToLeft(Node<K, V> node, Node<K, V> newNode) { |
| newNode.parent = node; |
| // node.left==null - attach here |
| node.left = newNode; |
| Node<K, V> predecessor = node.prev; |
| newNode.prev = predecessor; |
| newNode.next = node; |
| if (predecessor != null) { |
| predecessor.next = newNode; |
| } |
| node.prev = newNode; |
| } |
| |
| /* add pair into node; existence free room in the node should be checked |
| * before call |
| */ |
| private void appendFromRight(Node<K, V> node, K keyObj, V value) { |
| if (node.right_idx == Node.NODE_SIZE - 1) { |
| int left_idx = node.left_idx; |
| int left_idxMinus1 = left_idx - 1; |
| System.arraycopy(node.keys, left_idx, node.keys, left_idxMinus1, Node.NODE_SIZE - left_idx); |
| System.arraycopy(node.values, left_idx, node.values, left_idxMinus1, Node.NODE_SIZE - left_idx); |
| node.left_idx = left_idxMinus1; |
| } else { |
| node.right_idx++; |
| } |
| node.size++; |
| node.keys[node.right_idx] = keyObj; |
| node.values[node.right_idx] = value; |
| } |
| |
| private void attachToRight(Node<K, V> node, Node<K, V> newNode) { |
| newNode.parent = node; |
| // - node.right==null - attach here |
| node.right = newNode; |
| newNode.prev = node; |
| Node<K, V> successor = node.next; |
| newNode.next = successor; |
| if (successor != null) { |
| successor.prev = newNode; |
| } |
| node.next = newNode; |
| } |
| |
| private Node<K, V> createNode(K keyObj, V value) { |
| Node<K, V> node = new Node<K, V>(); |
| node.keys[0] = keyObj; |
| node.values[0] = value; |
| node.left_idx = 0; |
| node.right_idx = 0; |
| node.size = 1; |
| return node; |
| } |
| |
| void balance(Node<K, V> x) { |
| Node<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; |
| } |
| |
| private void rightRotate(Node<K, V> x) { |
| Node<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; |
| } |
| |
| |
| private void leftRotate(Node<K, V> x) { |
| Node<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; |
| } |
| |
| |
| /** |
| * 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. |
| */ |
| @Override |
| public void putAll(Map<? extends K, ? extends V> map) { |
| super.putAll(map); |
| } |
| |
| /** |
| * 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. |
| */ |
| @Override |
| public V remove(Object key) { |
| if (size == 0) { |
| return null; |
| } |
| Comparable<K> object = comparator == null ? toComparable((K) key) : null; |
| K keyK = (K) key; |
| Node<K, V> node = root; |
| while (node != null) { |
| K[] keys = node.keys; |
| int left_idx = node.left_idx; |
| int result = cmp(object, keyK, keys[left_idx]); |
| if (result < 0) { |
| node = node.left; |
| } else if (result == 0) { |
| V value = node.values[left_idx]; |
| removeLeftmost(node); |
| return value; |
| } else { |
| int right_idx = node.right_idx; |
| if (left_idx != right_idx) { |
| result = cmp(object, keyK, keys[right_idx]); |
| } |
| if (result > 0) { |
| node = node.right; |
| } else if (result == 0) { |
| V value = node.values[right_idx]; |
| removeRightmost(node); |
| return value; |
| } else { /*search in node*/ |
| int low = left_idx + 1, mid = 0, high = right_idx - 1; |
| while (low <= high) { |
| mid = (low + high) >>> 1; |
| result = cmp(object, keyK, keys[mid]); |
| if (result > 0) { |
| low = mid + 1; |
| } else if (result == 0) { |
| V value = node.values[mid]; |
| removeMiddleElement(node, mid); |
| return value; |
| } else { |
| high = mid - 1; |
| } |
| } |
| return null; |
| } |
| } |
| } |
| return null; |
| } |
| |
| void removeLeftmost(Node<K, V> node) { |
| int index = node.left_idx; |
| if (node.size == 1) { |
| deleteNode(node); |
| } else if (node.prev != null && (Node.NODE_SIZE - 1 - node.prev.right_idx) > node.size) { |
| // move all to prev node and kill it |
| Node<K, V> prev = node.prev; |
| int size = node.right_idx - index; |
| System.arraycopy(node.keys, index + 1, prev.keys, prev.right_idx + 1, size); |
| System.arraycopy(node.values, index + 1, prev.values, prev.right_idx + 1, size); |
| prev.right_idx += size; |
| prev.size += size; |
| deleteNode(node); |
| } else if (node.next != null && (node.next.left_idx) > node.size) { |
| // move all to next node and kill it |
| Node<K, V> next = node.next; |
| int size = node.right_idx - index; |
| int next_new_left = next.left_idx - size; |
| next.left_idx = next_new_left; |
| System.arraycopy(node.keys, index + 1, next.keys, next_new_left, size); |
| System.arraycopy(node.values, index + 1, next.values, next_new_left, size); |
| next.size += size; |
| deleteNode(node); |
| } else { |
| node.keys[index] = null; |
| node.values[index] = null; |
| node.left_idx++; |
| node.size--; |
| Node<K, V> prev = node.prev; |
| if (prev != null && prev.size == 1) { |
| node.size++; |
| node.left_idx--; |
| node.keys [node.left_idx] = prev.keys [prev.left_idx]; |
| node.values[node.left_idx] = prev.values[prev.left_idx]; |
| deleteNode(prev); |
| } |
| } |
| modCount++; |
| size--; |
| } |
| |
| void removeRightmost(Node<K, V> node) { |
| int index = node.right_idx; |
| if (node.size == 1) { |
| deleteNode(node); |
| } else if (node.prev != null && (Node.NODE_SIZE - 1 - node.prev.right_idx) > node.size) { |
| // move all to prev node and kill it |
| Node<K, V> prev = node.prev; |
| int left_idx = node.left_idx; |
| int size = index - left_idx; |
| System.arraycopy(node.keys, left_idx, prev.keys, prev.right_idx + 1, size); |
| System.arraycopy(node.values, left_idx, prev.values, prev.right_idx + 1, size); |
| prev.right_idx += size; |
| prev.size += size; |
| deleteNode(node); |
| } else if (node.next != null && (node.next.left_idx) > node.size) { |
| // move all to next node and kill it |
| Node<K, V> next = node.next; |
| int left_idx = node.left_idx; |
| int size = index - left_idx; |
| int next_new_left = next.left_idx - size; |
| next.left_idx = next_new_left; |
| System.arraycopy(node.keys, left_idx, next.keys, next_new_left, size); |
| System.arraycopy(node.values, left_idx, next.values, next_new_left, size); |
| next.size += size; |
| deleteNode(node); |
| } else { |
| node.keys[index] = null; |
| node.values[index] = null; |
| node.right_idx--; |
| node.size--; |
| Node<K, V> next = node.next; |
| if (next != null && next.size == 1) { |
| node.size++; |
| node.right_idx++; |
| node.keys[node.right_idx] = next.keys[next.left_idx]; |
| node.values[node.right_idx] = next.values[next.left_idx]; |
| deleteNode(next); |
| } |
| } |
| modCount++; |
| size--; |
| } |
| |
| void removeMiddleElement(Node<K, V> node, int index) { |
| // this function is called iff index if some middle element; |
| // so node.left_idx < index < node.right_idx |
| // condition above assume that node.size > 1 |
| if (node.prev != null && (Node.NODE_SIZE - 1 - node.prev.right_idx) > node.size) { |
| // move all to prev node and kill it |
| Node<K, V> prev = node.prev; |
| int left_idx = node.left_idx; |
| int size = index - left_idx; |
| System.arraycopy(node.keys, left_idx, prev.keys, prev.right_idx + 1, size); |
| System.arraycopy(node.values, left_idx, prev.values, prev.right_idx + 1, size); |
| prev.right_idx += size; |
| size = node.right_idx - index; |
| System.arraycopy(node.keys, index + 1, prev.keys, prev.right_idx + 1, size); |
| System.arraycopy(node.values, index + 1, prev.values, prev.right_idx + 1, size); |
| prev.right_idx += size; |
| prev.size += (node.size - 1); |
| deleteNode(node); |
| } else if (node.next != null && (node.next.left_idx) > node.size) { |
| // move all to next node and kill it |
| Node<K, V> next = node.next; |
| int left_idx = node.left_idx; |
| int next_new_left = next.left_idx - node.size + 1; |
| next.left_idx = next_new_left; |
| int size = index - left_idx; |
| System.arraycopy(node.keys, left_idx, next.keys, next_new_left, size); |
| System.arraycopy(node.values, left_idx, next.values, next_new_left, size); |
| next_new_left += size; |
| size = node.right_idx - index; |
| System.arraycopy(node.keys, index + 1, next.keys, next_new_left, size); |
| System.arraycopy(node.values, index + 1, next.values, next_new_left, size); |
| next.size += (node.size - 1); |
| deleteNode(node); |
| } else { |
| int moveFromRight = node.right_idx - index; |
| int left_idx = node.left_idx; |
| int moveFromLeft = index - left_idx ; |
| if (moveFromRight <= moveFromLeft) { |
| System.arraycopy(node.keys, index + 1, node.keys, index, moveFromRight); |
| System.arraycopy(node.values, index + 1, node.values, index, moveFromRight); |
| Node<K, V> next = node.next; |
| if (next != null && next.size == 1) { |
| node.keys [node.right_idx] = next.keys [next.left_idx]; |
| node.values[node.right_idx] = next.values[next.left_idx]; |
| deleteNode(next); |
| } else { |
| node.keys [node.right_idx] = null; |
| node.values[node.right_idx] = null; |
| node.right_idx--; |
| node.size--; |
| } |
| } else { |
| System.arraycopy(node.keys, left_idx , node.keys, left_idx + 1, moveFromLeft); |
| System.arraycopy(node.values, left_idx , node.values, left_idx + 1, moveFromLeft); |
| Node<K, V> prev = node.prev; |
| if (prev != null && prev.size == 1) { |
| node.keys [left_idx ] = prev.keys [prev.left_idx]; |
| node.values[left_idx ] = prev.values[prev.left_idx]; |
| deleteNode(prev); |
| } else { |
| node.keys [left_idx ] = null; |
| node.values[left_idx ] = null; |
| node.left_idx++; |
| node.size--; |
| } |
| } |
| } |
| modCount++; |
| size--; |
| } |
| |
| void removeFromIterator(Node<K, V> node, int index) { |
| if (node.size == 1) { |
| // it is safe to delete the whole node here. |
| // iterator already moved to the next node; |
| deleteNode(node); |
| } else { |
| int left_idx = node.left_idx; |
| if (index == left_idx) { |
| Node<K, V> prev = node.prev; |
| if (prev != null && prev.size == 1) { |
| node.keys [left_idx] = prev.keys [prev.left_idx]; |
| node.values[left_idx] = prev.values[prev.left_idx]; |
| deleteNode(prev); |
| } else { |
| node.keys [left_idx] = null; |
| node.values[left_idx] = null; |
| node.left_idx++; |
| node.size--; |
| } |
| } else if (index == node.right_idx) { |
| node.keys [index] = null; |
| node.values[index] = null; |
| node.right_idx--; |
| node.size--; |
| } else { |
| int moveFromRight = node.right_idx - index; |
| int moveFromLeft = index - left_idx; |
| if (moveFromRight <= moveFromLeft) { |
| System.arraycopy(node.keys, index + 1, node.keys, index, moveFromRight ); |
| System.arraycopy(node.values, index + 1, node.values, index, moveFromRight ); |
| node.keys [node.right_idx] = null; |
| node.values[node.right_idx] = null; |
| node.right_idx--; |
| node.size--; |
| } else { |
| System.arraycopy(node.keys, left_idx, node.keys, left_idx+ 1, moveFromLeft); |
| System.arraycopy(node.values, left_idx, node.values, left_idx+ 1, moveFromLeft); |
| node.keys [left_idx] = null; |
| node.values[left_idx] = null; |
| node.left_idx++; |
| node.size--; |
| } |
| } |
| } |
| modCount++; |
| size--; |
| } |
| |
| private void deleteNode(Node<K, V> node) { |
| if (node.right == null) { |
| if (node.left != null) { |
| attachToParent(node, node.left); |
| } else { |
| attachNullToParent(node); |
| } |
| fixNextChain(node); |
| } else if(node.left == null) { // node.right != null |
| attachToParent(node, node.right); |
| fixNextChain(node); |
| } else { |
| // Here node.left!=nul && node.right!=null |
| // node.next should replace node in tree |
| // node.next!=null by tree logic. |
| // node.next.left==null by tree logic. |
| // node.next.right may be null or non-null |
| Node<K, V> toMoveUp = node.next; |
| fixNextChain(node); |
| if(toMoveUp.right==null){ |
| attachNullToParent(toMoveUp); |
| } else { |
| attachToParent(toMoveUp, toMoveUp.right); |
| } |
| // Here toMoveUp is ready to replace node |
| toMoveUp.left = node.left; |
| if (node.left != null) { |
| node.left.parent = toMoveUp; |
| } |
| toMoveUp.right = node.right; |
| if (node.right != null) { |
| node.right.parent = toMoveUp; |
| } |
| attachToParentNoFixup(node,toMoveUp); |
| toMoveUp.color = node.color; |
| } |
| } |
| |
| private void attachToParentNoFixup(Node<K, V> toDelete, Node<K, V> toConnect) { |
| // assert toConnect!=null |
| Node<K,V> parent = toDelete.parent; |
| toConnect.parent = parent; |
| if (parent == null) { |
| root = toConnect; |
| } else if (toDelete == parent.left) { |
| parent.left = toConnect; |
| } else { |
| parent.right = toConnect; |
| } |
| } |
| |
| private void attachToParent(Node<K, V> toDelete, Node<K, V> toConnect) { |
| // assert toConnect!=null |
| attachToParentNoFixup(toDelete,toConnect); |
| if (!toDelete.color) { |
| fixup(toConnect); |
| } |
| } |
| |
| private void attachNullToParent(Node<K, V> toDelete) { |
| Node<K, V> parent = toDelete.parent; |
| if (parent == null) { |
| root = null; |
| } else { |
| if (toDelete == parent.left) { |
| parent.left = null; |
| } else { |
| parent.right = null; |
| } |
| if (!toDelete.color) { |
| fixup(parent); |
| } |
| } |
| } |
| |
| private void fixNextChain(Node<K, V> node) { |
| if (node.prev != null) { |
| node.prev.next = node.next; |
| } |
| if (node.next != null) { |
| node.next.prev = node.prev; |
| } |
| } |
| |
| private void fixup(Node<K, V> x) { |
| Node<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 number of mappings in this map. |
| * |
| * @return the number of mappings in this map. |
| */ |
| @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. |
| * |
| * @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. |
| */ |
| 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(); |
| } |
| |
| /** |
| * 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. |
| * |
| * @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. |
| */ |
| 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> |
| * 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. |
| * |
| * @return a collection of the values contained in this map. |
| */ |
| @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) { |
| Node<K, V> node = minimum(root); |
| while (node != null) { |
| int to = node.right_idx; |
| for (int i = node.left_idx; i <= to; i++) { |
| stream.writeObject(node.keys[i]); |
| stream.writeObject(node.values[i]); |
| } |
| node = node.next; |
| } |
| } |
| } |
| |
| @SuppressWarnings("unchecked") |
| private void readObject(ObjectInputStream stream) throws IOException, |
| ClassNotFoundException { |
| stream.defaultReadObject(); |
| int size = stream.readInt(); |
| Node<K, V> lastNode = null; |
| for (int i = 0; i < size; i++) { |
| lastNode = addToLast(lastNode, (K) stream.readObject(), (V) stream.readObject()); |
| } |
| } |
| } |
