| /* |
| * Copyright 2008 Google Inc. |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); you may not |
| * use this file except in compliance with the License. You may obtain a copy of |
| * the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT |
| * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the |
| * License for the specific language governing permissions and limitations under |
| * the License. |
| */ |
| package java.util; |
| |
| import static javaemul.internal.InternalPreconditions.checkNotNull; |
| |
| import java.io.Serializable; |
| |
| /** |
| * Implements a TreeMap using a red-black tree. This guarantees O(log n) |
| * performance on lookups, inserts, and deletes while maintaining linear |
| * in-order traversal time. Null keys and values are fully supported if the |
| * comparator supports them (the default comparator does not). |
| * |
| * @param <K> key type |
| * @param <V> value type |
| */ |
| public class TreeMap<K, V> extends AbstractNavigableMap<K, V> implements Serializable { |
| /* |
| * Implementation derived from public domain C implementation as of 5 |
| * September 2007 at: |
| * http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx |
| * written by Julienne Walker. |
| * |
| * This version does not require a parent pointer kept in each node. |
| */ |
| |
| /** |
| * Iterator for <code>descendingMap().entrySet()</code>. |
| */ |
| private final class DescendingEntryIterator implements Iterator<Entry<K, V>> { |
| private final ListIterator<Entry<K, V>> iter; |
| private Entry<K, V> last; |
| |
| /** |
| * Constructor for <code>DescendingEntryIterator</code>. |
| */ |
| public DescendingEntryIterator() { |
| this(SubMapType.All, null, false, null, false); |
| } |
| |
| /** |
| * Create an iterator which may return only a restricted range. |
| * |
| * @param fromKey the first key to return in the iterator. |
| * @param toKey the upper bound of keys to return. |
| */ |
| public DescendingEntryIterator(SubMapType type, |
| K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) { |
| List<Entry<K, V>> list = new ArrayList<Entry<K, V>>(); |
| inOrderAdd(list, type, TreeMap.this.root, |
| fromKey, fromInclusive, toKey, toInclusive); |
| this.iter = list.listIterator(list.size()); |
| } |
| |
| @Override |
| public boolean hasNext() { |
| return iter.hasPrevious(); |
| } |
| |
| @Override |
| public Entry<K, V> next() { |
| return last = iter.previous(); |
| } |
| |
| @Override |
| public void remove() { |
| iter.remove(); |
| removeEntry(last); |
| last = null; |
| } |
| } |
| |
| /** |
| * Iterator for <code>EntrySet</code>. |
| */ |
| private final class EntryIterator implements Iterator<Entry<K, V>> { |
| private final ListIterator<Entry<K, V>> iter; |
| private Entry<K, V> last; |
| |
| /** |
| * Constructor for <code>EntrySetIterator</code>. |
| */ |
| public EntryIterator() { |
| this(SubMapType.All, null, false, null, false); |
| } |
| |
| /** |
| * Create an iterator which may return only a restricted range. |
| * |
| * @param fromKey the first key to return in the iterator. |
| * @param toKey the upper bound of keys to return. |
| */ |
| public EntryIterator(SubMapType type, |
| K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) { |
| List<Entry<K, V>> list = new ArrayList<Entry<K, V>>(); |
| inOrderAdd(list, type, TreeMap.this.root, |
| fromKey, fromInclusive, toKey, toInclusive); |
| this.iter = list.listIterator(); |
| } |
| |
| @Override |
| public boolean hasNext() { |
| return iter.hasNext(); |
| } |
| |
| @Override |
| public Entry<K, V> next() { |
| return last = iter.next(); |
| } |
| |
| @Override |
| public void remove() { |
| iter.remove(); |
| removeEntry(last); |
| last = null; |
| } |
| } |
| |
| private final class EntrySet extends AbstractNavigableMap.EntrySet { |
| @Override |
| public void clear() { |
| TreeMap.this.clear(); |
| } |
| } |
| |
| /** |
| * Tree node. |
| * |
| * @param <K> key type |
| * @param <V> value type |
| */ |
| private static class Node<K, V> extends SimpleEntry<K, V> { |
| /* |
| * The children are kept in an array to minimize the normal duplication of |
| * code. |
| */ |
| @SuppressWarnings("unchecked") |
| protected final Node<K, V>[] child = new Node[2]; |
| protected boolean isRed; |
| |
| /** |
| * Create a red node. |
| * |
| * @param key |
| * @param value |
| */ |
| public Node(K key, V value) { |
| this(key, value, true); |
| } |
| |
| /** |
| * Create a node of the specified color. |
| * |
| * @param key |
| * @param value |
| * @param isRed true if this should be a red node, false for black |
| */ |
| public Node(K key, V value, boolean isRed) { |
| super(key, value); |
| this.isRed = isRed; |
| } |
| } |
| |
| /** |
| * A state object which is passed down the tree for both insert and remove. |
| * All uses make use of the done flag to indicate when no further rebalancing |
| * of the tree is required. Remove methods use the found flag to indicate when |
| * the desired key has been found. value is used both to return the value of a |
| * removed node as well as to pass in a value which must match (used for |
| * entrySet().remove(entry)), and the matchValue flag is used to request this |
| * behavior. |
| * |
| * @param <V> value type |
| */ |
| private static class State<V> { |
| public boolean done; |
| public boolean found; |
| public boolean matchValue; |
| public V value; |
| |
| @Override |
| public String toString() { |
| return "State: mv=" + matchValue + " value=" + value + " done=" + done + " found=" + found; |
| } |
| } |
| |
| private class SubMap extends AbstractNavigableMap<K, V> { |
| private final boolean fromInclusive; |
| |
| // valid only if type is Range or Tail |
| private final K fromKey; |
| |
| private final boolean toInclusive; |
| |
| // valid only if type is Range or Head |
| private final K toKey; |
| |
| private final SubMapType type; |
| |
| SubMap(SubMapType type, |
| K fromKey, boolean fromInclusive, |
| K toKey, boolean toInclusive) { |
| switch (type) { |
| case Range: |
| if (cmp.compare(toKey, fromKey) < 0) { |
| throw new IllegalArgumentException("subMap: " + toKey |
| + " less than " + fromKey); |
| } |
| break; |
| case Head: |
| // check key for compatibility with comparator |
| cmp.compare(toKey, toKey); |
| break; |
| case Tail: |
| // check key for compatibility with comparator |
| cmp.compare(fromKey, fromKey); |
| break; |
| case All: |
| // no checks are needed |
| break; |
| } |
| this.type = type; |
| this.fromKey = fromKey; |
| this.fromInclusive = fromInclusive; |
| this.toKey = toKey; |
| this.toInclusive = toInclusive; |
| } |
| |
| @Override |
| public Comparator<? super K> comparator() { |
| return TreeMap.this.comparator(); |
| } |
| |
| @Override |
| public Set<Entry<K, V>> entrySet() { |
| return new SubMap.EntrySet(); |
| } |
| |
| @Override |
| public NavigableMap<K, V> headMap(K toKey, boolean toInclusive) { |
| if (type.toKeyValid() && cmp.compare(toKey, this.toKey) > 0) { |
| throw new IllegalArgumentException("subMap: " + toKey + |
| " greater than " + this.toKey); |
| } |
| if (type.fromKeyValid()) { |
| return TreeMap.this.subMap(fromKey, fromInclusive, toKey, toInclusive); |
| } else { |
| return TreeMap.this.headMap(toKey, toInclusive); |
| } |
| } |
| |
| @Override |
| public V put(K key, V value) { |
| if (!inRange(key)) { |
| throw new IllegalArgumentException(key + " outside the range " |
| + fromKey + " to " + toKey); |
| } |
| return TreeMap.this.put(key, value); |
| } |
| |
| @SuppressWarnings("unchecked") |
| @Override |
| public V remove(Object k) { |
| K key = (K) k; |
| if (!inRange(key)) { |
| return null; |
| } |
| return TreeMap.this.remove(key); |
| } |
| |
| @Override |
| public int size() { |
| if (getFirstEntry() == null) { |
| return 0; |
| } |
| |
| // TODO(jat): more efficient way to do this? |
| int count = 0; |
| for (Iterator<Entry<K, V>> it = entryIterator(); it.hasNext(); it.next()) { |
| count++; |
| } |
| return count; |
| } |
| |
| @Override |
| public NavigableMap<K, V> subMap(K newFromKey, boolean newFromInclusive, |
| K newToKey, boolean newToInclusive) { |
| if (type.fromKeyValid() && cmp.compare(newFromKey, fromKey) < 0) { |
| throw new IllegalArgumentException("subMap: " + newFromKey + |
| " less than " + fromKey); |
| } |
| if (type.toKeyValid() && cmp.compare(newToKey, toKey) > 0) { |
| throw new IllegalArgumentException("subMap: " + newToKey + |
| " greater than " + toKey); |
| } |
| return TreeMap.this.subMap(newFromKey, newFromInclusive, newToKey, newToInclusive); |
| } |
| |
| @Override |
| public NavigableMap<K, V> tailMap(K fromKey, boolean fromInclusive) { |
| if (type.fromKeyValid() && cmp.compare(fromKey, this.fromKey) < 0) { |
| throw new IllegalArgumentException("subMap: " + fromKey + |
| " less than " + this.fromKey); |
| } |
| if (type.toKeyValid()) { |
| return TreeMap.this.subMap(fromKey, fromInclusive, toKey, toInclusive); |
| } else { |
| return TreeMap.this.tailMap(fromKey, fromInclusive); |
| } |
| } |
| |
| @Override |
| Iterator<Entry<K, V>> descendingEntryIterator() { |
| return new DescendingEntryIterator(type, fromKey, fromInclusive, toKey, toInclusive); |
| } |
| |
| @Override |
| Iterator<Entry<K, V>> entryIterator() { |
| return new EntryIterator(type, fromKey, fromInclusive, toKey, toInclusive); |
| } |
| |
| @Override |
| Entry<K, V> getEntry(K key) { |
| return guardInRange(TreeMap.this.getEntry(key)); |
| } |
| |
| @Override |
| Entry<K, V> getFirstEntry() { |
| Entry<K, V> entry; |
| if (type.fromKeyValid()) { |
| if (fromInclusive) { |
| entry = TreeMap.this.getCeilingEntry(fromKey); |
| } else { |
| entry = TreeMap.this.getHigherEntry(fromKey); |
| } |
| } else { |
| entry = TreeMap.this.getFirstEntry(); |
| } |
| // The map is empty if the first key after fromKey is out of range. |
| return guardInRange(entry); |
| } |
| |
| @Override |
| Entry<K, V> getLastEntry() { |
| Entry<K, V> entry; |
| if (type.toKeyValid()) { |
| if (toInclusive) { |
| entry = TreeMap.this.getFloorEntry(toKey); |
| } else { |
| entry = TreeMap.this.getLowerEntry(toKey); |
| } |
| } else { |
| entry = TreeMap.this.getLastEntry(); |
| } |
| // The map is empty if the last key before toKey is out of range. |
| return guardInRange(entry); |
| } |
| |
| @Override |
| Entry<K, V> getCeilingEntry(K key) { |
| return guardInRange(TreeMap.this.getCeilingEntry(key)); |
| } |
| |
| @Override |
| Entry<K, V> getFloorEntry(K key) { |
| return guardInRange(TreeMap.this.getFloorEntry(key)); |
| } |
| |
| @Override |
| Entry<K, V> getHigherEntry(K key) { |
| return guardInRange(TreeMap.this.getHigherEntry(key)); |
| } |
| |
| @Override |
| Entry<K, V> getLowerEntry(K key) { |
| return guardInRange(TreeMap.this.getLowerEntry(key)); |
| } |
| |
| @Override |
| boolean removeEntry(Entry<K, V> entry) { |
| return inRange(entry.getKey()) && TreeMap.this.removeEntry(entry); |
| } |
| |
| private Entry<K, V> guardInRange(Entry<K, V> entry) { |
| return entry != null && inRange(entry.getKey()) ? entry : null; |
| } |
| |
| private boolean inRange(K key) { |
| return TreeMap.this.inRange(type, key, fromKey, fromInclusive, toKey, toInclusive); |
| } |
| } |
| |
| private enum SubMapType { |
| All, |
| |
| Head { |
| @Override |
| public boolean toKeyValid() { |
| return true; |
| } |
| }, |
| |
| Range { |
| @Override |
| public boolean fromKeyValid() { |
| return true; |
| } |
| |
| @Override |
| public boolean toKeyValid() { |
| return true; |
| } |
| }, |
| |
| Tail { |
| @Override |
| public boolean fromKeyValid() { |
| return true; |
| } |
| }; |
| |
| /** |
| * Returns true if this submap type uses a from-key. |
| */ |
| public boolean fromKeyValid() { |
| return false; |
| } |
| |
| /** |
| * Returns true if this submap type uses a to-key. |
| */ |
| public boolean toKeyValid() { |
| return false; |
| } |
| } |
| |
| private static final int LEFT = 0; |
| private static final int RIGHT = 1; |
| |
| private static int otherChild(int child) { |
| assert (child == 0 || child == 1); |
| return 1 - child; |
| } |
| |
| // The comparator to use. |
| private Comparator<? super K> cmp; |
| |
| /* |
| * These two fields are just hints to STOB so that it generates serializers |
| * for K and V |
| */ |
| @SuppressWarnings("unused") |
| private K exposeKeyType; |
| |
| @SuppressWarnings("unused") |
| private V exposeValueType; |
| |
| // The root of the tree. |
| private transient Node<K, V> root; |
| |
| // The number of nodes in the tree. |
| private int size = 0; |
| |
| public TreeMap() { |
| this((Comparator<? super K>) null); |
| } |
| |
| @SuppressWarnings("unchecked") |
| public TreeMap(Comparator<? super K> c) { |
| root = null; |
| cmp = Comparators.nullToNaturalOrder(c); |
| } |
| |
| public TreeMap(Map<? extends K, ? extends V> map) { |
| this(); |
| putAll(map); |
| } |
| |
| @SuppressWarnings("unchecked") |
| public TreeMap(SortedMap<K, ? extends V> map) { |
| this(checkNotNull(map).comparator()); |
| putAll(map); // TODO(jat): more efficient init from sorted map |
| } |
| |
| @Override |
| public void clear() { |
| root = null; |
| size = 0; |
| } |
| |
| @Override |
| public Comparator<? super K> comparator() { |
| return Comparators.naturalOrderToNull(cmp); |
| } |
| |
| @Override |
| public Set<Entry<K, V>> entrySet() { |
| return new EntrySet(); |
| } |
| |
| @Override |
| public NavigableMap<K, V> headMap(K toKey, boolean inclusive) { |
| return new SubMap(SubMapType.Head, null, false, toKey, inclusive); |
| } |
| |
| @Override |
| public V put(K key, V value) { |
| Node<K, V> node = new Node<K, V>(key, value); |
| State<V> state = new State<V>(); |
| root = insert(root, node, state); |
| if (!state.found) { |
| ++size; |
| } |
| root.isRed = false; |
| return state.value; |
| } |
| |
| @Override |
| @SuppressWarnings("unchecked") |
| public V remove(Object k) { |
| K key = (K) k; |
| State<V> state = new State<V>(); |
| removeWithState(key, state); |
| return state.value; |
| } |
| |
| @Override |
| public int size() { |
| return size; |
| } |
| |
| @Override |
| public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, |
| K toKey, boolean toInclusive) { |
| return new SubMap(SubMapType.Range, fromKey, fromInclusive, toKey, toInclusive); |
| } |
| |
| @Override |
| public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) { |
| return new SubMap(SubMapType.Tail, fromKey, inclusive, null, false); |
| } |
| |
| /** |
| * Returns the first node which compares greater than the given key. |
| * |
| * @param key the key to search for |
| * @return the next node, or null if there is none |
| */ |
| private Node<K, V> getNodeAfter(K key, boolean inclusive) { |
| Node<K, V> foundNode = null; |
| Node<K, V> node = root; |
| while (node != null) { |
| int c = cmp.compare(key, node.getKey()); |
| if (inclusive && c == 0) { |
| return node; |
| } |
| if (c >= 0) { |
| node = node.child[RIGHT]; |
| } else { |
| foundNode = node; |
| node = node.child[LEFT]; |
| } |
| } |
| return foundNode; |
| } |
| |
| /** |
| * Returns the last node which is strictly less than the given key. |
| * |
| * @param key the key to search for |
| * @return the previous node, or null if there is none |
| */ |
| private Node<K, V> getNodeBefore(K key, boolean inclusive) { |
| Node<K, V> foundNode = null; |
| Node<K, V> node = root; |
| while (node != null) { |
| int c = cmp.compare(key, node.getKey()); |
| if (inclusive && c == 0) { |
| return node; |
| } |
| if (c <= 0) { |
| node = node.child[LEFT]; |
| } else { |
| foundNode = node; |
| node = node.child[RIGHT]; |
| } |
| } |
| return foundNode; |
| } |
| |
| /** |
| * Used for testing. Validate that the tree meets all red-black correctness |
| * requirements. These include: |
| * |
| * <pre> |
| * - root is black |
| * - no children of a red node may be red |
| * - the black height of every path through the three to a leaf is exactly the same |
| * </pre> |
| * |
| * @throws RuntimeException if any correctness errors are detected. |
| */ |
| void assertCorrectness() { |
| assertCorrectness(root, true); |
| } |
| |
| @Override |
| Iterator<Entry<K, V>> descendingEntryIterator() { |
| return new DescendingEntryIterator(); |
| } |
| |
| @Override |
| Iterator<Entry<K, V>> entryIterator() { |
| return new EntryIterator(); |
| } |
| |
| /** |
| * Internal helper function for public {@link #assertCorrectness()}. |
| * |
| * @param tree the subtree to validate. |
| * @param isRed true if the parent of this node is red. |
| * @return the black height of this subtree. |
| * @throws RuntimeException if this RB-tree is not valid. |
| */ |
| private int assertCorrectness(Node<K, V> tree, boolean isRed) { |
| if (tree == null) { |
| return 0; |
| } |
| if (isRed && tree.isRed) { |
| throw new RuntimeException("Two red nodes adjacent"); |
| } |
| |
| Node<K, V> leftNode = tree.child[LEFT]; |
| if (leftNode != null |
| && cmp.compare(leftNode.getKey(), tree.getKey()) > 0) { |
| throw new RuntimeException("Left child " + leftNode |
| + " larger than " + tree); |
| } |
| |
| Node<K, V> rightNode = tree.child[RIGHT]; |
| if (rightNode != null |
| && cmp.compare(rightNode.getKey(), tree.getKey()) < 0) { |
| throw new RuntimeException("Right child " + rightNode |
| + " smaller than " + tree); |
| } |
| |
| int leftHeight = assertCorrectness(leftNode, tree.isRed); |
| int rightHeight = assertCorrectness(rightNode, tree.isRed); |
| if (leftHeight != 0 && rightHeight != 0 && leftHeight != rightHeight) { |
| throw new RuntimeException("Black heights don't match"); |
| } |
| return tree.isRed ? leftHeight : leftHeight + 1; |
| } |
| |
| /** |
| * Finds an entry given a key and returns the node. |
| * |
| * @param key the search key |
| * @return the node matching the key or null |
| */ |
| @Override |
| Entry<K, V> getEntry(K key) { |
| Node<K, V> tree = root; |
| while (tree != null) { |
| int c = cmp.compare(key, tree.getKey()); |
| if (c == 0) { |
| return tree; |
| } |
| int childNum = c < 0 ? LEFT : RIGHT; |
| tree = tree.child[childNum]; |
| } |
| return null; |
| } |
| |
| /** |
| * Returns the left-most node of the tree, or null if empty. |
| */ |
| @Override |
| Entry<K, V> getFirstEntry() { |
| if (root == null) { |
| return null; |
| } |
| Node<K, V> node = root; |
| Node<K, V> nextNode; |
| while ((nextNode = node.child[LEFT]) != null) { |
| node = nextNode; |
| } |
| return node; |
| } |
| |
| /** |
| * Returns the right-most node of the tree, or null if empty. |
| */ |
| @Override |
| Entry<K, V> getLastEntry() { |
| if (root == null) { |
| return null; |
| } |
| Node<K, V> node = root; |
| Node<K, V> nextNode; |
| while ((nextNode = node.child[RIGHT]) != null) { |
| node = nextNode; |
| } |
| return node; |
| } |
| |
| @Override |
| Entry<K, V> getCeilingEntry(K key) { |
| return getNodeAfter(key, true); |
| } |
| |
| @Override |
| Entry<K, V> getFloorEntry(K key) { |
| return getNodeBefore(key, true); |
| } |
| |
| @Override |
| Entry<K, V> getHigherEntry(K key) { |
| return getNodeAfter(key, false); |
| } |
| |
| @Override |
| Entry<K, V> getLowerEntry(K key) { |
| return getNodeBefore(key, false); |
| } |
| |
| @Override |
| boolean removeEntry(Entry<K, V> entry) { |
| State<V> state = new State<V>(); |
| state.matchValue = true; |
| state.value = entry.getValue(); |
| return removeWithState(entry.getKey(), state); |
| } |
| |
| private void inOrderAdd(List<Entry<K, V>> list, SubMapType type, Node<K, V> current, |
| K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) { |
| if (current == null) { |
| return; |
| } |
| // TODO: truncate this recursion if the whole subtree is known to be |
| // outside of bounds? |
| Node<K, V> leftNode = current.child[LEFT]; |
| if (leftNode != null) { |
| inOrderAdd(list, type, leftNode, |
| fromKey, fromInclusive, toKey, toInclusive); |
| } |
| if (inRange(type, current.getKey(), fromKey, fromInclusive, toKey, toInclusive)) { |
| list.add(current); |
| } |
| Node<K, V> rightNode = current.child[RIGHT]; |
| if (rightNode != null) { |
| inOrderAdd(list, type, rightNode, fromKey, fromInclusive, toKey, toInclusive); |
| } |
| } |
| |
| private boolean inRange(SubMapType type, K key, |
| K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) { |
| if (type.fromKeyValid() && smaller(key, fromKey, !fromInclusive)) { |
| return false; |
| } |
| if (type.toKeyValid() && larger(key, toKey, !toInclusive)) { |
| return false; |
| } |
| return true; |
| } |
| |
| /** |
| * Insert a node into a subtree, collecting state about the insertion. |
| * |
| * If the same key already exists, the value of the node is overwritten with |
| * the value from the new node instead. |
| * |
| * @param tree subtree to insert into |
| * @param newNode new node to insert |
| * @param state result of the insertion: state.found true if the key already |
| * existed in the tree state.value the old value if the key existed |
| * @return the new subtree root |
| */ |
| private Node<K, V> insert(Node<K, V> tree, Node<K, V> newNode, State<V> state) { |
| if (tree == null) { |
| return newNode; |
| } else { |
| int c = cmp.compare(newNode.getKey(), tree.getKey()); |
| if (c == 0) { |
| state.value = tree.setValue(newNode.getValue()); |
| state.found = true; |
| return tree; |
| } |
| int childNum = c < 0 ? LEFT : RIGHT; |
| tree.child[childNum] = insert(tree.child[childNum], newNode, state); |
| if (isRed(tree.child[childNum])) { |
| if (isRed(tree.child[otherChild(childNum)])) { |
| // both children are red (nulls are black), make both black and me red |
| tree.isRed = true; |
| tree.child[LEFT].isRed = false; |
| tree.child[RIGHT].isRed = false; |
| } else { |
| // |
| if (isRed(tree.child[childNum].child[childNum])) { |
| tree = rotateSingle(tree, otherChild(childNum)); |
| } else if (isRed(tree.child[childNum].child[otherChild(childNum)])) { |
| tree = rotateDouble(tree, otherChild(childNum)); |
| } |
| } |
| } |
| } |
| return tree; |
| } |
| |
| /** |
| * Returns true if <code>node</code> is red. Note that null pointers are |
| * considered black. |
| */ |
| private boolean isRed(Node<K, V> node) { |
| return node != null && node.isRed; |
| } |
| |
| /** |
| * Returns true if <code>a</code> is greater than or equal to <code>b</code>. |
| */ |
| private boolean larger(K a, K b, boolean orEqual) { |
| int compare = cmp.compare(a, b); |
| return compare > 0 || (orEqual && compare == 0); |
| } |
| |
| /** |
| * Returns true if <code>a</code> is less than or equal to <code>b</code>. |
| */ |
| private boolean smaller(K a, K b, boolean orEqual) { |
| int compare = cmp.compare(a, b); |
| return compare < 0 || (orEqual && compare == 0); |
| } |
| |
| /** |
| * Remove a key from the tree, returning whether it was found and its value. |
| * |
| * @param key key to remove |
| * @param state return state, not null |
| * @return true if the value was found |
| */ |
| private boolean removeWithState(K key, State<V> state) { |
| if (root == null) { |
| return false; |
| } |
| Node<K, V> found = null; |
| Node<K, V> parent = null; |
| |
| // create a fake tree root to minimize special cases for changing the root |
| Node<K, V> head = new Node<K, V>(null, null); |
| int dir = RIGHT; |
| head.child[RIGHT] = root; |
| |
| Node<K, V> node = head; |
| while (node.child[dir] != null) { |
| int last = dir; |
| Node<K, V> grandparent = parent; |
| parent = node; |
| node = node.child[dir]; |
| int c = cmp.compare(key, node.getKey()); |
| dir = c < 0 ? LEFT : RIGHT; |
| if (c == 0 && (!state.matchValue || Objects.equals(node.getValue(), state.value))) { |
| found = node; |
| } |
| if (!isRed(node) && !isRed(node.child[dir])) { |
| if (isRed(node.child[otherChild(dir)])) { |
| parent = parent.child[last] = rotateSingle(node, dir); |
| } else if (!isRed(node.child[otherChild(dir)])) { |
| Node<K, V> sibling = parent.child[otherChild(last)]; |
| if (sibling != null) { |
| if (!isRed(sibling.child[otherChild(last)]) |
| && !isRed(sibling.child[last])) { |
| parent.isRed = false; |
| sibling.isRed = true; |
| node.isRed = true; |
| } else { |
| assert grandparent != null; |
| int dir2 = grandparent.child[RIGHT] == parent ? RIGHT : LEFT; |
| if (isRed(sibling.child[last])) { |
| grandparent.child[dir2] = rotateDouble(parent, last); |
| } else if (isRed(sibling.child[otherChild(last)])) { |
| grandparent.child[dir2] = rotateSingle(parent, last); |
| } |
| node.isRed = grandparent.child[dir2].isRed = true; |
| grandparent.child[dir2].child[LEFT].isRed = false; |
| grandparent.child[dir2].child[RIGHT].isRed = false; |
| } |
| } |
| } |
| } |
| } |
| |
| if (found != null) { |
| state.found = true; |
| state.value = found.getValue(); |
| /** |
| * put the "node" values in "found" (the node with key K) and cut "node" |
| * out. However, we do not want to corrupt "found" -- issue 3423. So |
| * create a new node "newNode" to replace the "found" node. |
| * |
| * TODO: (jat's suggestion) Consider using rebalance to move the deleted |
| * node to a leaf to avoid the extra traversal in replaceNode. |
| */ |
| if (node != found) { |
| Node<K, V> newNode = new Node<K, V>(node.getKey(), node.getValue()); |
| replaceNode(head, found, newNode); |
| if (parent == found) { |
| parent = newNode; |
| } |
| } |
| |
| // cut "node" out |
| parent.child[parent.child[RIGHT] == node ? RIGHT : LEFT] = node.child[node.child[LEFT] == null |
| ? RIGHT : LEFT]; |
| size--; |
| } |
| |
| root = head.child[RIGHT]; |
| if (root != null) { |
| root.isRed = false; |
| } |
| return state.found; |
| } |
| |
| /** |
| * replace 'node' with 'newNode' in the tree rooted at 'head'. Could have |
| * avoided this traversal if each node maintained a parent pointer. |
| */ |
| private void replaceNode(Node<K, V> head, Node<K, V> node, Node<K, V> newNode) { |
| Node<K, V> parent = head; |
| int direction = (parent.getKey() == null || cmp.compare(node.getKey(), parent.getKey()) > 0) |
| ? RIGHT : LEFT; // parent.key == null handles the fake root node |
| while (parent.child[direction] != node) { |
| parent = parent.child[direction]; |
| assert parent != null; |
| direction = cmp.compare(node.getKey(), parent.getKey()) > 0 ? RIGHT : LEFT; |
| } |
| // replace node with newNode |
| parent.child[direction] = newNode; |
| newNode.isRed = node.isRed; |
| newNode.child[LEFT] = node.child[LEFT]; |
| newNode.child[RIGHT] = node.child[RIGHT]; |
| node.child[LEFT] = null; |
| node.child[RIGHT] = null; |
| } |
| |
| /** |
| * Perform a double rotation, first rotating the child which will become the |
| * root in the opposite direction, then rotating the root in the specified |
| * direction. |
| * |
| * <pre> |
| * A F |
| * B C becomes (with rotateDirection=0) A C |
| * D E F G B E G |
| * D |
| * </pre> |
| * |
| * @param tree root of the subtree to rotate |
| * @param rotateDirection the direction to rotate: 0=left, 1=right |
| * @return the new root of the rotated subtree |
| */ |
| private Node<K, V> rotateDouble(Node<K, V> tree, int rotateDirection) { |
| // free the pointer of the new root |
| int otherChildDir = otherChild(rotateDirection); |
| tree.child[otherChildDir] = rotateSingle(tree.child[otherChildDir], otherChildDir); |
| return rotateSingle(tree, rotateDirection); |
| } |
| |
| /** |
| * Perform a single rotation, pushing the root of the subtree to the specified |
| * direction. |
| * |
| * <pre> |
| * A B |
| * B C becomes (with rotateDirection=1) D A |
| * D E E C |
| * </pre> |
| * |
| * @param tree the root of the subtree to rotate |
| * @param rotateDirection the direction to rotate: 0=left rotation, 1=right |
| * @return the new root of the rotated subtree |
| */ |
| private Node<K, V> rotateSingle(Node<K, V> tree, int rotateDirection) { |
| int otherChildDir = otherChild(rotateDirection); |
| Node<K, V> save = tree.child[otherChildDir]; |
| tree.child[otherChildDir] = save.child[rotateDirection]; |
| save.child[rotateDirection] = tree; |
| tree.isRed = true; |
| save.isRed = false; |
| return save; |
| } |
| } |
