http://git-wip-us.apache.org/repos/asf/commons-collections/blob/884baf0d/src/java/org/apache/commons/collections/bidimap/TreeBidiMap.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/commons/collections/bidimap/TreeBidiMap.java b/src/java/org/apache/commons/collections/bidimap/TreeBidiMap.java index 08684f9..b1192fd 100644 --- a/src/java/org/apache/commons/collections/bidimap/TreeBidiMap.java +++ b/src/java/org/apache/commons/collections/bidimap/TreeBidiMap.java @@ -5,9 +5,9 @@ * 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. @@ -24,7 +24,6 @@ import java.util.Map; import java.util.NoSuchElementException; import java.util.Set; -import org.apache.commons.collections.BidiMap; import org.apache.commons.collections.KeyValue; import org.apache.commons.collections.MapIterator; import org.apache.commons.collections.OrderedBidiMap; @@ -32,6 +31,7 @@ import org.apache.commons.collections.OrderedIterator; import org.apache.commons.collections.OrderedMapIterator; import org.apache.commons.collections.iterators.EmptyOrderedMapIterator; import org.apache.commons.collections.keyvalue.UnmodifiableMapEntry; +import static org.apache.commons.collections.bidimap.TreeBidiMap.DataElement.*; /** * Red-Black tree-based implementation of BidiMap where all objects added @@ -69,35 +69,50 @@ import org.apache.commons.collections.keyvalue.UnmodifiableMapEntry; * * @since Commons Collections 3.0 (previously DoubleOrderedMap v2.0) * @version $Revision$ $Date$ - * + * * @author Marc Johnson * @author Stephen Colebourne + * @author Matt Benson */ -public class TreeBidiMap implements OrderedBidiMap { - - private static final int KEY = 0; - private static final int VALUE = 1; - private static final int MAPENTRY = 2; - private static final int INVERSEMAPENTRY = 3; - private static final int SUM_OF_INDICES = KEY + VALUE; - private static final int FIRST_INDEX = 0; - private static final int NUMBER_OF_INDICES = 2; - private static final String[] dataName = new String[] { "key", "value" }; - - private Node[] rootNode = new Node[2]; +public class TreeBidiMap<K extends Comparable<K>, V extends Comparable<V>> implements OrderedBidiMap<K, V> { + + static enum DataElement { + KEY("key"), VALUE("value"); + + private final String description; + + /** + * Create a new TreeBidiMap.DataElement. + */ + private DataElement(String description) { + this.description = description; + } + + /** + * {@inheritDoc} + */ + @Override + public String toString() { + return description; + } + } + + private Node<K, V>[] rootNode; private int nodeCount = 0; private int modifications = 0; - private Set keySet; - private Set valuesSet; - private Set entrySet; - private TreeBidiMap.Inverse inverse = null; + private Set<K> keySet; + private Set<V> valuesSet; + private Set<Map.Entry<K, V>> entrySet; + private Inverse inverse = null; //----------------------------------------------------------------------- /** * Constructs a new empty TreeBidiMap. */ + @SuppressWarnings("unchecked") public TreeBidiMap() { super(); + rootNode = new Node[2]; } /** @@ -108,8 +123,8 @@ public class TreeBidiMap implements OrderedBidiMap { * not Comparable or are not mutually comparable * @throws NullPointerException if any key or value in the map is null */ - public TreeBidiMap(final Map map) { - super(); + public TreeBidiMap(final Map<K, V> map) { + this(); putAll(map); } @@ -144,7 +159,7 @@ public class TreeBidiMap implements OrderedBidiMap { */ public boolean containsKey(final Object key) { checkKey(key); - return (lookup((Comparable) key, KEY) != null); + return (lookupKey(key) != null); } /** @@ -159,7 +174,7 @@ public class TreeBidiMap implements OrderedBidiMap { */ public boolean containsValue(final Object value) { checkValue(value); - return (lookup((Comparable) value, VALUE) != null); + return (lookupValue(value) != null); } /** @@ -174,8 +189,10 @@ public class TreeBidiMap implements OrderedBidiMap { * @throws ClassCastException if the key is of an inappropriate type * @throws NullPointerException if the key is null */ - public Object get(final Object key) { - return doGet((Comparable) key, KEY); + public V get(final Object key) { + checkKey(key); + Node<K, V> node = lookupKey(key); + return node == null ? null : node.getValue(); } /** @@ -188,7 +205,7 @@ public class TreeBidiMap implements OrderedBidiMap { * BidiMap map1 = new TreeBidiMap(); * map.put("A","B"); // contains A mapped to B, as per Map * map.put("A","C"); // contains A mapped to C, as per Map - * + * * BidiMap map2 = new TreeBidiMap(); * map.put("A","B"); // contains A mapped to B, as per Map * map.put("C","B"); // contains C mapped to B, key A is removed @@ -202,25 +219,25 @@ public class TreeBidiMap implements OrderedBidiMap { * @throws ClassCastException if the key is of an inappropriate type * @throws NullPointerException if the key is null */ - public Object put(final Object key, final Object value) { - return doPut((Comparable) key, (Comparable) value, KEY); + public V put(final K key, final V value) { + V result = get(key); + doPut(key, value); + return result; } /** * Puts all the mappings from the specified map into this map. * <p> * All keys and values must implement <code>Comparable</code>. - * + * * @param map the map to copy from */ - public void putAll(Map map) { - Iterator it = map.entrySet().iterator(); - while (it.hasNext()) { - Map.Entry entry = (Map.Entry) it.next(); - put(entry.getKey(), entry.getValue()); + public void putAll(Map<? extends K, ? extends V> map) { + for (Map.Entry<? extends K, ? extends V> e : map.entrySet()) { + put(e.getKey(), e.getValue()); } } - + /** * Removes the mapping for this key from this map if present. * <p> @@ -232,8 +249,8 @@ public class TreeBidiMap implements OrderedBidiMap { * @throws ClassCastException if the key is of an inappropriate type * @throws NullPointerException if the key is null */ - public Object remove(final Object key) { - return doRemove((Comparable) key, KEY); + public V remove(final Object key) { + return doRemoveKey(key); } /** @@ -243,8 +260,8 @@ public class TreeBidiMap implements OrderedBidiMap { modify(); nodeCount = 0; - rootNode[KEY] = null; - rootNode[VALUE] = null; + rootNode[KEY.ordinal()] = null; + rootNode[VALUE.ordinal()] = null; } //----------------------------------------------------------------------- @@ -260,8 +277,10 @@ public class TreeBidiMap implements OrderedBidiMap { * @throws ClassCastException if the value is of an inappropriate type * @throws NullPointerException if the value is null */ - public Object getKey(final Object value) { - return doGet((Comparable) value, VALUE); + public K getKey(final Object value) { + checkValue(value); + Node<K, V> node = lookupValue(value); + return node == null ? null : node.getKey(); } /** @@ -275,8 +294,8 @@ public class TreeBidiMap implements OrderedBidiMap { * @throws ClassCastException if the value is of an inappropriate type * @throws NullPointerException if the value is null */ - public Object removeValue(final Object value) { - return doRemove((Comparable) value, VALUE); + public K removeValue(final Object value) { + return doRemoveValue(value); } //----------------------------------------------------------------------- @@ -286,11 +305,11 @@ public class TreeBidiMap implements OrderedBidiMap { * @return the first (lowest) key currently in this sorted map * @throws NoSuchElementException if this map is empty */ - public Object firstKey() { + public K firstKey() { if (nodeCount == 0) { throw new NoSuchElementException("Map is empty"); } - return leastNode(rootNode[KEY], KEY).getKey(); + return leastNode(rootNode[KEY.ordinal()], KEY).getKey(); } /** @@ -299,13 +318,13 @@ public class TreeBidiMap implements OrderedBidiMap { * @return the last (highest) key currently in this sorted map * @throws NoSuchElementException if this map is empty */ - public Object lastKey() { + public K lastKey() { if (nodeCount == 0) { throw new NoSuchElementException("Map is empty"); } - return greatestNode(rootNode[KEY], KEY).getKey(); + return greatestNode(rootNode[KEY.ordinal()], KEY).getKey(); } - + /** * Gets the next key after the one specified. * <p> @@ -314,10 +333,10 @@ public class TreeBidiMap implements OrderedBidiMap { * @param key the key to search for next from * @return the next key, null if no match or at end */ - public Object nextKey(Object key) { + public K nextKey(K key) { checkKey(key); - Node node = nextGreater(lookup((Comparable) key, KEY), KEY); - return (node == null ? null : node.getKey()); + Node<K, V> node = nextGreater(lookupKey(key), KEY); + return node == null ? null : node.getKey(); } /** @@ -328,12 +347,12 @@ public class TreeBidiMap implements OrderedBidiMap { * @param key the key to search for previous from * @return the previous key, null if no match or at start */ - public Object previousKey(Object key) { + public K previousKey(K key) { checkKey(key); - Node node = nextSmaller(lookup((Comparable) key, KEY), KEY); - return (node == null ? null : node.getKey()); + Node<K, V> node = nextSmaller(lookupKey(key), KEY); + return node == null ? null : node.getKey(); } - + //----------------------------------------------------------------------- /** * Returns a set view of the keys contained in this map in key order. @@ -347,9 +366,9 @@ public class TreeBidiMap implements OrderedBidiMap { * * @return a set view of the keys contained in this map. */ - public Set keySet() { + public Set<K> keySet() { if (keySet == null) { - keySet = new View(this, KEY, KEY); + keySet = new KeyView(KEY); } return keySet; } @@ -368,9 +387,9 @@ public class TreeBidiMap implements OrderedBidiMap { * * @return a set view of the values contained in this map. */ - public Collection values() { + public Collection<V> values() { if (valuesSet == null) { - valuesSet = new View(this, KEY, VALUE); + valuesSet = new ValueView(KEY); } return valuesSet; } @@ -390,60 +409,33 @@ public class TreeBidiMap implements OrderedBidiMap { * * @return a set view of the values contained in this map. */ - public Set entrySet() { + public Set<Map.Entry<K, V>> entrySet() { if (entrySet == null) { - return new EntryView(this, KEY, MAPENTRY); + return new EntryView(); } return entrySet; } //----------------------------------------------------------------------- /** - * Gets an iterator over the map entries. - * <p> - * For this map, this iterator is the fastest way to iterate over the entries. - * - * @return an iterator + * {@inheritDoc} */ - public MapIterator mapIterator() { + public OrderedMapIterator<K, V> mapIterator() { if (isEmpty()) { - return EmptyOrderedMapIterator.INSTANCE; + return EmptyOrderedMapIterator.<K, V>getInstance(); } - return new ViewMapIterator(this, KEY); - } - - /** - * Gets an ordered iterator over the map entries. - * <p> - * This iterator allows both forward and reverse iteration over the entries. - * - * @return an iterator - */ - public OrderedMapIterator orderedMapIterator() { - if (isEmpty()) { - return EmptyOrderedMapIterator.INSTANCE; - } - return new ViewMapIterator(this, KEY); + return new ViewMapIterator(KEY); } //----------------------------------------------------------------------- /** * Gets the inverse map for comparison. - * - * @return the inverse map - */ - public BidiMap inverseBidiMap() { - return inverseOrderedBidiMap(); - } - - /** - * Gets the inverse map for comparison. - * + * * @return the inverse map */ - public OrderedBidiMap inverseOrderedBidiMap() { + public OrderedBidiMap<V, K> inverseBidiMap() { if (inverse == null) { - inverse = new Inverse(this); + inverse = new Inverse(); } return inverse; } @@ -458,7 +450,7 @@ public class TreeBidiMap implements OrderedBidiMap { public boolean equals(Object obj) { return this.doEquals(obj, KEY); } - + /** * Gets the hash code value for this map as per the API. * @@ -467,61 +459,43 @@ public class TreeBidiMap implements OrderedBidiMap { public int hashCode() { return this.doHashCode(KEY); } - + /** * Returns a string version of this Map in standard format. - * + * * @return a standard format string version of the map */ public String toString() { return this.doToString(KEY); } - + //----------------------------------------------------------------------- /** - * Common get logic, used to get by key or get by value + * Put logic. * - * @param obj the key or value that we're looking for - * @param index the KEY or VALUE int - * @return the key (if the value was mapped) or the value (if the - * key was mapped); null if we couldn't find the specified - * object - */ - private Object doGet(final Comparable obj, final int index) { - checkNonNullComparable(obj, index); - Node node = lookup(obj, index); - return ((node == null) ? null : node.getData(oppositeIndex(index))); - } - - /** - * Common put logic, differing only in the return value. - * * @param key the key, always the main map key * @param value the value, always the main map value - * @param index the KEY or VALUE int, for the return value only - * @return the previously mapped value */ - private Object doPut(final Comparable key, final Comparable value, final int index) { + private void doPut(final K key, final V value) { checkKeyAndValue(key, value); - + // store previous and remove previous mappings - Object prev = (index == KEY ? doGet(key, KEY) : doGet(value, VALUE)); - doRemove(key, KEY); - doRemove(value, VALUE); - - Node node = rootNode[KEY]; + doRemoveKey(key); + doRemoveValue(value); + + Node<K, V> node = rootNode[KEY.ordinal()]; if (node == null) { // map is empty - Node root = new Node(key, value); - rootNode[KEY] = root; - rootNode[VALUE] = root; + Node<K, V> root = new Node<K, V>(key, value); + rootNode[KEY.ordinal()] = root; + rootNode[VALUE.ordinal()] = root; grow(); - + } else { // add new mapping while (true) { - int cmp = compare(key, node.getData(KEY)); - + int cmp = compare(key, node.getKey()); + if (cmp == 0) { // shouldn't happen throw new IllegalArgumentException("Cannot store a duplicate key (\"" + key + "\") in this Map"); @@ -529,54 +503,51 @@ public class TreeBidiMap implements OrderedBidiMap { if (node.getLeft(KEY) != null) { node = node.getLeft(KEY); } else { - Node newNode = new Node(key, value); - + Node<K, V> newNode = new Node<K, V>(key, value); + insertValue(newNode); node.setLeft(newNode, KEY); newNode.setParent(node, KEY); doRedBlackInsert(newNode, KEY); grow(); - + break; } } else { // cmp > 0 if (node.getRight(KEY) != null) { node = node.getRight(KEY); } else { - Node newNode = new Node(key, value); - + Node<K, V> newNode = new Node<K, V>(key, value); + insertValue(newNode); node.setRight(newNode, KEY); newNode.setParent(node, KEY); doRedBlackInsert(newNode, KEY); grow(); - + break; } } } } - return prev; } - /** - * Remove by object (remove by key or remove by value) - * - * @param o the key, or value, that we're looking for - * @param index the KEY or VALUE int - * - * @return the key, if remove by value, or the value, if remove by - * key. null if the specified key or value could not be - * found - */ - private Object doRemove(final Comparable o, final int index) { - Node node = lookup(o, index); - Object rval = null; - if (node != null) { - rval = node.getData(oppositeIndex(index)); - doRedBlackDelete(node); + private V doRemoveKey(Object key) { + Node<K, V> node = lookupKey(key); + if (node == null) { + return null; } - return rval; + doRedBlackDelete(node); + return node.getValue(); + } + + private K doRemoveValue(Object value) { + Node<K, V> node = lookupValue(value); + if (node == null) { + return null; + } + doRedBlackDelete(node); + return node.getKey(); } /** @@ -587,23 +558,32 @@ public class TreeBidiMap implements OrderedBidiMap { * @return the desired Node, or null if there is no mapping of the * specified data */ - private Node lookup(final Comparable data, final int index) { - Node rval = null; - Node node = rootNode[index]; + @SuppressWarnings("unchecked") + private <T extends Comparable<T>> Node<K, V> lookup(final Object data, final DataElement dataElement) { + Node<K, V> rval = null; + Node<K, V> node = rootNode[dataElement.ordinal()]; while (node != null) { - int cmp = compare(data, node.getData(index)); + int cmp = compare((T) data, (T) node.getData(dataElement)); if (cmp == 0) { rval = node; break; } else { - node = (cmp < 0) ? node.getLeft(index) : node.getRight(index); + node = (cmp < 0) ? node.getLeft(dataElement) : node.getRight(dataElement); } } return rval; } + private Node<K, V> lookupKey(Object key) { + return this.<K>lookup(key, KEY); + } + + private Node<K, V> lookupValue(Object value) { + return this.<V>lookup(value, VALUE); + } + /** * get the next larger node from the specified node * @@ -611,14 +591,14 @@ public class TreeBidiMap implements OrderedBidiMap { * @param index the KEY or VALUE int * @return the specified node */ - private Node nextGreater(final Node node, final int index) { - Node rval = null; + private Node<K, V> nextGreater(final Node<K, V> node, final DataElement dataElement) { + Node<K, V> rval = null; if (node == null) { rval = null; - } else if (node.getRight(index) != null) { + } else if (node.getRight(dataElement) != null) { // everything to the node's right is larger. The least of // the right node's descendants is the next larger node - rval = leastNode(node.getRight(index), index); + rval = leastNode(node.getRight(dataElement), dataElement); } else { // traverse up our ancestry until we find an ancestor that // is null or one whose left child is our ancestor. If we @@ -626,12 +606,12 @@ public class TreeBidiMap implements OrderedBidiMap { // tree, and there is no greater node. Otherwise, we are // the largest node in the subtree on that ancestor's left // ... and that ancestor is the next greatest node - Node parent = node.getParent(index); - Node child = node; + Node<K, V> parent = node.getParent(dataElement); + Node<K, V> child = node; - while ((parent != null) && (child == parent.getRight(index))) { + while ((parent != null) && (child == parent.getRight(dataElement))) { child = parent; - parent = parent.getParent(index); + parent = parent.getParent(dataElement); } rval = parent; } @@ -645,14 +625,14 @@ public class TreeBidiMap implements OrderedBidiMap { * @param index the KEY or VALUE int * @return the specified node */ - private Node nextSmaller(final Node node, final int index) { - Node rval = null; + private Node<K, V> nextSmaller(final Node<K, V> node, final DataElement dataElement) { + Node<K, V> rval = null; if (node == null) { rval = null; - } else if (node.getLeft(index) != null) { + } else if (node.getLeft(dataElement) != null) { // everything to the node's left is smaller. The greatest of // the left node's descendants is the next smaller node - rval = greatestNode(node.getLeft(index), index); + rval = greatestNode(node.getLeft(dataElement), dataElement); } else { // traverse up our ancestry until we find an ancestor that // is null or one whose right child is our ancestor. If we @@ -660,12 +640,12 @@ public class TreeBidiMap implements OrderedBidiMap { // tree, and there is no greater node. Otherwise, we are // the largest node in the subtree on that ancestor's right // ... and that ancestor is the next greatest node - Node parent = node.getParent(index); - Node child = node; + Node<K, V> parent = node.getParent(dataElement); + Node<K, V> child = node; - while ((parent != null) && (child == parent.getLeft(index))) { + while ((parent != null) && (child == parent.getLeft(dataElement))) { child = parent; - parent = parent.getParent(index); + parent = parent.getParent(dataElement); } rval = parent; } @@ -673,18 +653,6 @@ public class TreeBidiMap implements OrderedBidiMap { } //----------------------------------------------------------------------- - /** - * Get the opposite index of the specified index - * - * @param index the KEY or VALUE int - * @return VALUE (if KEY was specified), else KEY - */ - private static int oppositeIndex(final int index) { - // old trick ... to find the opposite of a value, m or n, - // subtract the value from the sum of the two possible - // values. (m + n) - m = n; (m + n) - n = m - return SUM_OF_INDICES - index; - } /** * Compare two objects @@ -695,7 +663,7 @@ public class TreeBidiMap implements OrderedBidiMap { * @return negative value if o1 < o2; 0 if o1 == o2; positive * value if o1 > o2 */ - private static int compare(final Comparable o1, final Comparable o2) { + private static <T extends Comparable<T>> int compare(final T o1, final T o2) { return o1.compareTo(o2); } @@ -707,11 +675,11 @@ public class TreeBidiMap implements OrderedBidiMap { * @return the smallest node, from the specified node, in the * specified mapping */ - private static Node leastNode(final Node node, final int index) { - Node rval = node; + private Node<K, V> leastNode(final Node<K, V> node, final DataElement dataElement) { + Node<K, V> rval = node; if (rval != null) { - while (rval.getLeft(index) != null) { - rval = rval.getLeft(index); + while (rval.getLeft(dataElement) != null) { + rval = rval.getLeft(dataElement); } } return rval; @@ -724,11 +692,11 @@ public class TreeBidiMap implements OrderedBidiMap { * @param index the KEY or VALUE int * @return the greatest node, from the specified node */ - private static Node greatestNode(final Node node, final int index) { - Node rval = node; + private Node<K, V> greatestNode(final Node<K, V> node, final DataElement dataElement) { + Node<K, V> rval = node; if (rval != null) { - while (rval.getRight(index) != null) { - rval = rval.getRight(index); + while (rval.getRight(dataElement) != null) { + rval = rval.getRight(dataElement); } } return rval; @@ -742,13 +710,13 @@ public class TreeBidiMap implements OrderedBidiMap { * @param to the node whose color we're changing; may be null * @param index the KEY or VALUE int */ - private static void copyColor(final Node from, final Node to, final int index) { + private void copyColor(final Node<K, V> from, final Node<K, V> to, final DataElement dataElement) { if (to != null) { if (from == null) { // by default, make it black - to.setBlack(index); + to.setBlack(dataElement); } else { - to.copyColor(from, index); + to.copyColor(from, dataElement); } } } @@ -760,8 +728,8 @@ public class TreeBidiMap implements OrderedBidiMap { * @param node the node (may be null) in question * @param index the KEY or VALUE int */ - private static boolean isRed(final Node node, final int index) { - return ((node == null) ? false : node.isRed(index)); + private static boolean isRed(final Node<?, ?> node, final DataElement dataElement) { + return node != null && node.isRed(dataElement); } /** @@ -771,8 +739,8 @@ public class TreeBidiMap implements OrderedBidiMap { * @param node the node (may be null) in question * @param index the KEY or VALUE int */ - private static boolean isBlack(final Node node, final int index) { - return ((node == null) ? true : node.isBlack(index)); + private static boolean isBlack(final Node<?, ?> node, final DataElement dataElement) { + return node == null || node.isBlack(dataElement); } /** @@ -781,9 +749,9 @@ public class TreeBidiMap implements OrderedBidiMap { * @param node the node (may be null) in question * @param index the KEY or VALUE int */ - private static void makeRed(final Node node, final int index) { + private static void makeRed(final Node<?, ?> node, final DataElement dataElement) { if (node != null) { - node.setRed(index); + node.setRed(dataElement); } } @@ -793,9 +761,9 @@ public class TreeBidiMap implements OrderedBidiMap { * @param node the node (may be null) in question * @param index the KEY or VALUE int */ - private static void makeBlack(final Node node, final int index) { + private static void makeBlack(final Node<?, ?> node, final DataElement dataElement) { if (node != null) { - node.setBlack(index); + node.setBlack(dataElement); } } @@ -806,8 +774,8 @@ public class TreeBidiMap implements OrderedBidiMap { * @param node the node (may be null) in question * @param index the KEY or VALUE int */ - private static Node getGrandParent(final Node node, final int index) { - return getParent(getParent(node, index), index); + private Node<K, V> getGrandParent(final Node<K, V> node, final DataElement dataElement) { + return getParent(getParent(node, dataElement), dataElement); } /** @@ -817,8 +785,8 @@ public class TreeBidiMap implements OrderedBidiMap { * @param node the node (may be null) in question * @param index the KEY or VALUE int */ - private static Node getParent(final Node node, final int index) { - return ((node == null) ? null : node.getParent(index)); + private Node<K, V> getParent(final Node<K, V> node, final DataElement dataElement) { + return node == null ? null : node.getParent(dataElement); } /** @@ -828,8 +796,8 @@ public class TreeBidiMap implements OrderedBidiMap { * @param node the node (may be null) in question * @param index the KEY or VALUE int */ - private static Node getRightChild(final Node node, final int index) { - return (node == null) ? null : node.getRight(index); + private Node<K, V> getRightChild(final Node<K, V> node, final DataElement dataElement) { + return node == null ? null : node.getRight(dataElement); } /** @@ -839,44 +807,8 @@ public class TreeBidiMap implements OrderedBidiMap { * @param node the node (may be null) in question * @param index the KEY or VALUE int */ - private static Node getLeftChild(final Node node, final int index) { - return (node == null) ? null : node.getLeft(index); - } - - /** - * is this node its parent's left child? mind you, the node, or - * its parent, may not exist. no problem. if the node doesn't - * exist ... it's its non-existent parent's left child. If the - * node does exist but has no parent ... no, we're not the - * non-existent parent's left child. Otherwise (both the specified - * node AND its parent exist), check. - * - * @param node the node (may be null) in question - * @param index the KEY or VALUE int - */ - private static boolean isLeftChild(final Node node, final int index) { - return (node == null) - ? true - : ((node.getParent(index) == null) ? - false : (node == node.getParent(index).getLeft(index))); - } - - /** - * is this node its parent's right child? mind you, the node, or - * its parent, may not exist. no problem. if the node doesn't - * exist ... it's its non-existent parent's right child. If the - * node does exist but has no parent ... no, we're not the - * non-existent parent's right child. Otherwise (both the - * specified node AND its parent exist), check. - * - * @param node the node (may be null) in question - * @param index the KEY or VALUE int - */ - private static boolean isRightChild(final Node node, final int index) { - return (node == null) - ? true - : ((node.getParent(index) == null) ? - false : (node == node.getParent(index).getRight(index))); + private Node<K, V> getLeftChild(final Node<K, V> node, final DataElement dataElement) { + return node == null ? null : node.getLeft(dataElement); } /** @@ -885,26 +817,26 @@ public class TreeBidiMap implements OrderedBidiMap { * @param node the node to be rotated * @param index the KEY or VALUE int */ - private void rotateLeft(final Node node, final int index) { - Node rightChild = node.getRight(index); - node.setRight(rightChild.getLeft(index), index); + private void rotateLeft(final Node<K, V> node, final DataElement dataElement) { + Node<K, V> rightChild = node.getRight(dataElement); + node.setRight(rightChild.getLeft(dataElement), dataElement); - if (rightChild.getLeft(index) != null) { - rightChild.getLeft(index).setParent(node, index); + if (rightChild.getLeft(dataElement) != null) { + rightChild.getLeft(dataElement).setParent(node, dataElement); } - rightChild.setParent(node.getParent(index), index); - - if (node.getParent(index) == null) { + rightChild.setParent(node.getParent(dataElement), dataElement); + + if (node.getParent(dataElement) == null) { // node was the root ... now its right child is the root - rootNode[index] = rightChild; - } else if (node.getParent(index).getLeft(index) == node) { - node.getParent(index).setLeft(rightChild, index); + rootNode[dataElement.ordinal()] = rightChild; + } else if (node.getParent(dataElement).getLeft(dataElement) == node) { + node.getParent(dataElement).setLeft(rightChild, dataElement); } else { - node.getParent(index).setRight(rightChild, index); + node.getParent(dataElement).setRight(rightChild, dataElement); } - rightChild.setLeft(node, index); - node.setParent(rightChild, index); + rightChild.setLeft(node, dataElement); + node.setParent(rightChild, dataElement); } /** @@ -913,25 +845,25 @@ public class TreeBidiMap implements OrderedBidiMap { * @param node the node to be rotated * @param index the KEY or VALUE int */ - private void rotateRight(final Node node, final int index) { - Node leftChild = node.getLeft(index); - node.setLeft(leftChild.getRight(index), index); - if (leftChild.getRight(index) != null) { - leftChild.getRight(index).setParent(node, index); + private void rotateRight(final Node<K, V> node, final DataElement dataElement) { + Node<K, V> leftChild = node.getLeft(dataElement); + node.setLeft(leftChild.getRight(dataElement), dataElement); + if (leftChild.getRight(dataElement) != null) { + leftChild.getRight(dataElement).setParent(node, dataElement); } - leftChild.setParent(node.getParent(index), index); + leftChild.setParent(node.getParent(dataElement), dataElement); - if (node.getParent(index) == null) { + if (node.getParent(dataElement) == null) { // node was the root ... now its left child is the root - rootNode[index] = leftChild; - } else if (node.getParent(index).getRight(index) == node) { - node.getParent(index).setRight(leftChild, index); + rootNode[dataElement.ordinal()] = leftChild; + } else if (node.getParent(dataElement).getRight(dataElement) == node) { + node.getParent(dataElement).setRight(leftChild, dataElement); } else { - node.getParent(index).setLeft(leftChild, index); + node.getParent(dataElement).setLeft(leftChild, dataElement); } - leftChild.setRight(node, index); - node.setParent(leftChild, index); + leftChild.setRight(node, dataElement); + node.setParent(leftChild, dataElement); } /** @@ -939,67 +871,69 @@ public class TreeBidiMap implements OrderedBidiMap { * implementation, though it's barely recognizable any more * * @param insertedNode the node to be inserted - * @param index the KEY or VALUE int + * @param dataElement the KEY or VALUE int */ - private void doRedBlackInsert(final Node insertedNode, final int index) { - Node currentNode = insertedNode; - makeRed(currentNode, index); + private void doRedBlackInsert(final Node<K, V> insertedNode, final DataElement dataElement) { + Node<K, V> currentNode = insertedNode; + makeRed(currentNode, dataElement); while ((currentNode != null) - && (currentNode != rootNode[index]) - && (isRed(currentNode.getParent(index), index))) { - if (isLeftChild(getParent(currentNode, index), index)) { - Node y = getRightChild(getGrandParent(currentNode, index), index); + && (currentNode != rootNode[dataElement.ordinal()]) + && (isRed(currentNode.getParent(dataElement), dataElement))) { + if (currentNode.isLeftChild(dataElement)) { + Node<K, V> y = getRightChild(getGrandParent(currentNode, dataElement), dataElement); - if (isRed(y, index)) { - makeBlack(getParent(currentNode, index), index); - makeBlack(y, index); - makeRed(getGrandParent(currentNode, index), index); + if (isRed(y, dataElement)) { + makeBlack(getParent(currentNode, dataElement), dataElement); + makeBlack(y, dataElement); + makeRed(getGrandParent(currentNode, dataElement), dataElement); - currentNode = getGrandParent(currentNode, index); + currentNode = getGrandParent(currentNode, dataElement); } else { - if (isRightChild(currentNode, index)) { - currentNode = getParent(currentNode, index); + //dead code? + if (currentNode.isRightChild(dataElement)) { + currentNode = getParent(currentNode, dataElement); - rotateLeft(currentNode, index); + rotateLeft(currentNode, dataElement); } - makeBlack(getParent(currentNode, index), index); - makeRed(getGrandParent(currentNode, index), index); + makeBlack(getParent(currentNode, dataElement), dataElement); + makeRed(getGrandParent(currentNode, dataElement), dataElement); - if (getGrandParent(currentNode, index) != null) { - rotateRight(getGrandParent(currentNode, index), index); + if (getGrandParent(currentNode, dataElement) != null) { + rotateRight(getGrandParent(currentNode, dataElement), dataElement); } } } else { // just like clause above, except swap left for right - Node y = getLeftChild(getGrandParent(currentNode, index), index); + Node<K, V> y = getLeftChild(getGrandParent(currentNode, dataElement), dataElement); - if (isRed(y, index)) { - makeBlack(getParent(currentNode, index), index); - makeBlack(y, index); - makeRed(getGrandParent(currentNode, index), index); + if (isRed(y, dataElement)) { + makeBlack(getParent(currentNode, dataElement), dataElement); + makeBlack(y, dataElement); + makeRed(getGrandParent(currentNode, dataElement), dataElement); - currentNode = getGrandParent(currentNode, index); + currentNode = getGrandParent(currentNode, dataElement); } else { - if (isLeftChild(currentNode, index)) { - currentNode = getParent(currentNode, index); + //dead code? + if (currentNode.isLeftChild(dataElement)) { + currentNode = getParent(currentNode, dataElement); - rotateRight(currentNode, index); + rotateRight(currentNode, dataElement); } - makeBlack(getParent(currentNode, index), index); - makeRed(getGrandParent(currentNode, index), index); + makeBlack(getParent(currentNode, dataElement), dataElement); + makeRed(getGrandParent(currentNode, dataElement), dataElement); - if (getGrandParent(currentNode, index) != null) { - rotateLeft(getGrandParent(currentNode, index), index); + if (getGrandParent(currentNode, dataElement) != null) { + rotateLeft(getGrandParent(currentNode, dataElement), dataElement); } } } } - makeBlack(rootNode[index], index); + makeBlack(rootNode[dataElement.ordinal()], dataElement); } /** @@ -1008,57 +942,57 @@ public class TreeBidiMap implements OrderedBidiMap { * * @param deletedNode the node to be deleted */ - private void doRedBlackDelete(final Node deletedNode) { - for (int index = FIRST_INDEX; index < NUMBER_OF_INDICES; index++) { + private void doRedBlackDelete(final Node<K, V> deletedNode) { + for (DataElement dataElement : DataElement.values()) { // if deleted node has both left and children, swap with // the next greater node - if ((deletedNode.getLeft(index) != null) && (deletedNode.getRight(index) != null)) { - swapPosition(nextGreater(deletedNode, index), deletedNode, index); + if ((deletedNode.getLeft(dataElement) != null) && (deletedNode.getRight(dataElement) != null)) { + swapPosition(nextGreater(deletedNode, dataElement), deletedNode, dataElement); } - Node replacement = - ((deletedNode.getLeft(index) != null) ? deletedNode.getLeft(index) : deletedNode.getRight(index)); + Node<K, V> replacement = + ((deletedNode.getLeft(dataElement) != null) ? deletedNode.getLeft(dataElement) : deletedNode.getRight(dataElement)); if (replacement != null) { - replacement.setParent(deletedNode.getParent(index), index); + replacement.setParent(deletedNode.getParent(dataElement), dataElement); - if (deletedNode.getParent(index) == null) { - rootNode[index] = replacement; - } else if (deletedNode == deletedNode.getParent(index).getLeft(index)) { - deletedNode.getParent(index).setLeft(replacement, index); + if (deletedNode.getParent(dataElement) == null) { + rootNode[dataElement.ordinal()] = replacement; + } else if (deletedNode == deletedNode.getParent(dataElement).getLeft(dataElement)) { + deletedNode.getParent(dataElement).setLeft(replacement, dataElement); } else { - deletedNode.getParent(index).setRight(replacement, index); + deletedNode.getParent(dataElement).setRight(replacement, dataElement); } - deletedNode.setLeft(null, index); - deletedNode.setRight(null, index); - deletedNode.setParent(null, index); + deletedNode.setLeft(null, dataElement); + deletedNode.setRight(null, dataElement); + deletedNode.setParent(null, dataElement); - if (isBlack(deletedNode, index)) { - doRedBlackDeleteFixup(replacement, index); + if (isBlack(deletedNode, dataElement)) { + doRedBlackDeleteFixup(replacement, dataElement); } } else { // replacement is null - if (deletedNode.getParent(index) == null) { + if (deletedNode.getParent(dataElement) == null) { // empty tree - rootNode[index] = null; + rootNode[dataElement.ordinal()] = null; } else { // deleted node had no children - if (isBlack(deletedNode, index)) { - doRedBlackDeleteFixup(deletedNode, index); + if (isBlack(deletedNode, dataElement)) { + doRedBlackDeleteFixup(deletedNode, dataElement); } - if (deletedNode.getParent(index) != null) { - if (deletedNode == deletedNode.getParent(index).getLeft(index)) { - deletedNode.getParent(index).setLeft(null, index); + if (deletedNode.getParent(dataElement) != null) { + if (deletedNode == deletedNode.getParent(dataElement).getLeft(dataElement)) { + deletedNode.getParent(dataElement).setLeft(null, dataElement); } else { - deletedNode.getParent(index).setRight(null, index); + deletedNode.getParent(dataElement).setRight(null, dataElement); } - deletedNode.setParent(null, index); + deletedNode.setParent(null, dataElement); } } } @@ -1073,80 +1007,80 @@ public class TreeBidiMap implements OrderedBidiMap { * perfectly balanced -- perfect balancing takes longer) * * @param replacementNode the node being replaced - * @param index the KEY or VALUE int + * @param dataElement the KEY or VALUE int */ - private void doRedBlackDeleteFixup(final Node replacementNode, final int index) { - Node currentNode = replacementNode; + private void doRedBlackDeleteFixup(final Node<K, V> replacementNode, final DataElement dataElement) { + Node<K, V> currentNode = replacementNode; - while ((currentNode != rootNode[index]) && (isBlack(currentNode, index))) { - if (isLeftChild(currentNode, index)) { - Node siblingNode = getRightChild(getParent(currentNode, index), index); + while ((currentNode != rootNode[dataElement.ordinal()]) && (isBlack(currentNode, dataElement))) { + if (currentNode.isLeftChild(dataElement)) { + Node<K, V> siblingNode = getRightChild(getParent(currentNode, dataElement), dataElement); - if (isRed(siblingNode, index)) { - makeBlack(siblingNode, index); - makeRed(getParent(currentNode, index), index); - rotateLeft(getParent(currentNode, index), index); + if (isRed(siblingNode, dataElement)) { + makeBlack(siblingNode, dataElement); + makeRed(getParent(currentNode, dataElement), dataElement); + rotateLeft(getParent(currentNode, dataElement), dataElement); - siblingNode = getRightChild(getParent(currentNode, index), index); + siblingNode = getRightChild(getParent(currentNode, dataElement), dataElement); } - if (isBlack(getLeftChild(siblingNode, index), index) - && isBlack(getRightChild(siblingNode, index), index)) { - makeRed(siblingNode, index); + if (isBlack(getLeftChild(siblingNode, dataElement), dataElement) + && isBlack(getRightChild(siblingNode, dataElement), dataElement)) { + makeRed(siblingNode, dataElement); - currentNode = getParent(currentNode, index); + currentNode = getParent(currentNode, dataElement); } else { - if (isBlack(getRightChild(siblingNode, index), index)) { - makeBlack(getLeftChild(siblingNode, index), index); - makeRed(siblingNode, index); - rotateRight(siblingNode, index); + if (isBlack(getRightChild(siblingNode, dataElement), dataElement)) { + makeBlack(getLeftChild(siblingNode, dataElement), dataElement); + makeRed(siblingNode, dataElement); + rotateRight(siblingNode, dataElement); - siblingNode = getRightChild(getParent(currentNode, index), index); + siblingNode = getRightChild(getParent(currentNode, dataElement), dataElement); } - copyColor(getParent(currentNode, index), siblingNode, index); - makeBlack(getParent(currentNode, index), index); - makeBlack(getRightChild(siblingNode, index), index); - rotateLeft(getParent(currentNode, index), index); + copyColor(getParent(currentNode, dataElement), siblingNode, dataElement); + makeBlack(getParent(currentNode, dataElement), dataElement); + makeBlack(getRightChild(siblingNode, dataElement), dataElement); + rotateLeft(getParent(currentNode, dataElement), dataElement); - currentNode = rootNode[index]; + currentNode = rootNode[dataElement.ordinal()]; } } else { - Node siblingNode = getLeftChild(getParent(currentNode, index), index); + Node<K, V> siblingNode = getLeftChild(getParent(currentNode, dataElement), dataElement); - if (isRed(siblingNode, index)) { - makeBlack(siblingNode, index); - makeRed(getParent(currentNode, index), index); - rotateRight(getParent(currentNode, index), index); + if (isRed(siblingNode, dataElement)) { + makeBlack(siblingNode, dataElement); + makeRed(getParent(currentNode, dataElement), dataElement); + rotateRight(getParent(currentNode, dataElement), dataElement); - siblingNode = getLeftChild(getParent(currentNode, index), index); + siblingNode = getLeftChild(getParent(currentNode, dataElement), dataElement); } - if (isBlack(getRightChild(siblingNode, index), index) - && isBlack(getLeftChild(siblingNode, index), index)) { - makeRed(siblingNode, index); + if (isBlack(getRightChild(siblingNode, dataElement), dataElement) + && isBlack(getLeftChild(siblingNode, dataElement), dataElement)) { + makeRed(siblingNode, dataElement); - currentNode = getParent(currentNode, index); + currentNode = getParent(currentNode, dataElement); } else { - if (isBlack(getLeftChild(siblingNode, index), index)) { - makeBlack(getRightChild(siblingNode, index), index); - makeRed(siblingNode, index); - rotateLeft(siblingNode, index); + if (isBlack(getLeftChild(siblingNode, dataElement), dataElement)) { + makeBlack(getRightChild(siblingNode, dataElement), dataElement); + makeRed(siblingNode, dataElement); + rotateLeft(siblingNode, dataElement); - siblingNode = getLeftChild(getParent(currentNode, index), index); + siblingNode = getLeftChild(getParent(currentNode, dataElement), dataElement); } - copyColor(getParent(currentNode, index), siblingNode, index); - makeBlack(getParent(currentNode, index), index); - makeBlack(getLeftChild(siblingNode, index), index); - rotateRight(getParent(currentNode, index), index); + copyColor(getParent(currentNode, dataElement), siblingNode, dataElement); + makeBlack(getParent(currentNode, dataElement), dataElement); + makeBlack(getLeftChild(siblingNode, dataElement), dataElement); + rotateRight(getParent(currentNode, dataElement), dataElement); - currentNode = rootNode[index]; + currentNode = rootNode[dataElement.ordinal()]; } } } - makeBlack(currentNode, index); + makeBlack(currentNode, dataElement); } /** @@ -1156,94 +1090,94 @@ public class TreeBidiMap implements OrderedBidiMap { * * @param x one node * @param y another node - * @param index the KEY or VALUE int + * @param dataElement the KEY or VALUE int */ - private void swapPosition(final Node x, final Node y, final int index) { + private void swapPosition(final Node<K, V> x, final Node<K, V> y, final DataElement dataElement) { // Save initial values. - Node xFormerParent = x.getParent(index); - Node xFormerLeftChild = x.getLeft(index); - Node xFormerRightChild = x.getRight(index); - Node yFormerParent = y.getParent(index); - Node yFormerLeftChild = y.getLeft(index); - Node yFormerRightChild = y.getRight(index); - boolean xWasLeftChild = (x.getParent(index) != null) && (x == x.getParent(index).getLeft(index)); - boolean yWasLeftChild = (y.getParent(index) != null) && (y == y.getParent(index).getLeft(index)); + Node<K, V> xFormerParent = x.getParent(dataElement); + Node<K, V> xFormerLeftChild = x.getLeft(dataElement); + Node<K, V> xFormerRightChild = x.getRight(dataElement); + Node<K, V> yFormerParent = y.getParent(dataElement); + Node<K, V> yFormerLeftChild = y.getLeft(dataElement); + Node<K, V> yFormerRightChild = y.getRight(dataElement); + boolean xWasLeftChild = (x.getParent(dataElement) != null) && (x == x.getParent(dataElement).getLeft(dataElement)); + boolean yWasLeftChild = (y.getParent(dataElement) != null) && (y == y.getParent(dataElement).getLeft(dataElement)); // Swap, handling special cases of one being the other's parent. if (x == yFormerParent) { // x was y's parent - x.setParent(y, index); + x.setParent(y, dataElement); if (yWasLeftChild) { - y.setLeft(x, index); - y.setRight(xFormerRightChild, index); + y.setLeft(x, dataElement); + y.setRight(xFormerRightChild, dataElement); } else { - y.setRight(x, index); - y.setLeft(xFormerLeftChild, index); + y.setRight(x, dataElement); + y.setLeft(xFormerLeftChild, dataElement); } } else { - x.setParent(yFormerParent, index); + x.setParent(yFormerParent, dataElement); if (yFormerParent != null) { if (yWasLeftChild) { - yFormerParent.setLeft(x, index); + yFormerParent.setLeft(x, dataElement); } else { - yFormerParent.setRight(x, index); + yFormerParent.setRight(x, dataElement); } } - y.setLeft(xFormerLeftChild, index); - y.setRight(xFormerRightChild, index); + y.setLeft(xFormerLeftChild, dataElement); + y.setRight(xFormerRightChild, dataElement); } if (y == xFormerParent) { // y was x's parent - y.setParent(x, index); + y.setParent(x, dataElement); if (xWasLeftChild) { - x.setLeft(y, index); - x.setRight(yFormerRightChild, index); + x.setLeft(y, dataElement); + x.setRight(yFormerRightChild, dataElement); } else { - x.setRight(y, index); - x.setLeft(yFormerLeftChild, index); + x.setRight(y, dataElement); + x.setLeft(yFormerLeftChild, dataElement); } } else { - y.setParent(xFormerParent, index); + y.setParent(xFormerParent, dataElement); if (xFormerParent != null) { if (xWasLeftChild) { - xFormerParent.setLeft(y, index); + xFormerParent.setLeft(y, dataElement); } else { - xFormerParent.setRight(y, index); + xFormerParent.setRight(y, dataElement); } } - x.setLeft(yFormerLeftChild, index); - x.setRight(yFormerRightChild, index); + x.setLeft(yFormerLeftChild, dataElement); + x.setRight(yFormerRightChild, dataElement); } // Fix children's parent pointers - if (x.getLeft(index) != null) { - x.getLeft(index).setParent(x, index); + if (x.getLeft(dataElement) != null) { + x.getLeft(dataElement).setParent(x, dataElement); } - if (x.getRight(index) != null) { - x.getRight(index).setParent(x, index); + if (x.getRight(dataElement) != null) { + x.getRight(dataElement).setParent(x, dataElement); } - if (y.getLeft(index) != null) { - y.getLeft(index).setParent(y, index); + if (y.getLeft(dataElement) != null) { + y.getLeft(dataElement).setParent(y, dataElement); } - if (y.getRight(index) != null) { - y.getRight(index).setParent(y, index); + if (y.getRight(dataElement) != null) { + y.getRight(dataElement).setParent(y, dataElement); } - x.swapColors(y, index); + x.swapColors(y, dataElement); // Check if root changed - if (rootNode[index] == x) { - rootNode[index] = y; - } else if (rootNode[index] == y) { - rootNode[index] = x; + if (rootNode[dataElement.ordinal()] == x) { + rootNode[dataElement.ordinal()] = y; + } else if (rootNode[dataElement.ordinal()] == y) { + rootNode[dataElement.ordinal()] = x; } } @@ -1258,12 +1192,12 @@ public class TreeBidiMap implements OrderedBidiMap { * @throws NullPointerException if o is null * @throws ClassCastException if o is not Comparable */ - private static void checkNonNullComparable(final Object o, final int index) { + private static void checkNonNullComparable(final Object o, final DataElement dataElement) { if (o == null) { - throw new NullPointerException(dataName[index] + " cannot be null"); + throw new NullPointerException(dataElement + " cannot be null"); } if (!(o instanceof Comparable)) { - throw new ClassCastException(dataName[index] + " must be Comparable"); + throw new ClassCastException(dataElement + " must be Comparable"); } } @@ -1339,11 +1273,11 @@ public class TreeBidiMap implements OrderedBidiMap { * @throws IllegalArgumentException if the node already exists * in the value mapping */ - private void insertValue(final Node newNode) throws IllegalArgumentException { - Node node = rootNode[VALUE]; + private void insertValue(final Node<K, V> newNode) throws IllegalArgumentException { + Node<K, V> node = rootNode[VALUE.ordinal()]; while (true) { - int cmp = compare(newNode.getData(VALUE), node.getData(VALUE)); + int cmp = compare(newNode.getValue(), node.getValue()); if (cmp == 0) { throw new IllegalArgumentException( @@ -1371,7 +1305,7 @@ public class TreeBidiMap implements OrderedBidiMap { } } } - + //----------------------------------------------------------------------- /** * Compares for equals as per the API. @@ -1380,21 +1314,21 @@ public class TreeBidiMap implements OrderedBidiMap { * @param type the KEY or VALUE int * @return true if equal */ - private boolean doEquals(Object obj, final int type) { + private boolean doEquals(Object obj, DataElement dataElement) { if (obj == this) { return true; } if (obj instanceof Map == false) { return false; } - Map other = (Map) obj; + Map<?, ?> other = (Map<?, ?>) obj; if (other.size() != size()) { return false; } if (nodeCount > 0) { try { - for (MapIterator it = new ViewMapIterator(this, type); it.hasNext(); ) { + for (MapIterator<?, ?> it = getMapIterator(dataElement); it.hasNext(); ) { Object key = it.next(); Object value = it.getValue(); if (value.equals(other.get(key)) == false) { @@ -1416,10 +1350,10 @@ public class TreeBidiMap implements OrderedBidiMap { * @param type the KEY or VALUE int * @return the hash code value for this map */ - private int doHashCode(final int type) { + private int doHashCode(DataElement dataElement) { int total = 0; if (nodeCount > 0) { - for (MapIterator it = new ViewMapIterator(this, type); it.hasNext(); ) { + for (MapIterator<?, ?> it = getMapIterator(dataElement); it.hasNext(); ) { Object key = it.next(); Object value = it.getValue(); total += (key.hashCode() ^ value.hashCode()); @@ -1427,20 +1361,20 @@ public class TreeBidiMap implements OrderedBidiMap { } return total; } - + /** * Gets the string form of this map as per AbstractMap. * * @param type the KEY or VALUE int * @return the string form of this map */ - private String doToString(final int type) { + private String doToString(DataElement dataElement) { if (nodeCount == 0) { return "{}"; } StringBuffer buf = new StringBuffer(nodeCount * 32); buf.append('{'); - MapIterator it = new ViewMapIterator(this, type); + MapIterator<?, ?> it = getMapIterator(dataElement); boolean hasNext = it.hasNext(); while (hasNext) { Object key = it.next(); @@ -1459,52 +1393,174 @@ public class TreeBidiMap implements OrderedBidiMap { return buf.toString(); } + private MapIterator<?, ?> getMapIterator(DataElement dataElement) { + switch (dataElement) { + case KEY: + return new ViewMapIterator(KEY); + case VALUE: + return new InverseViewMapIterator(VALUE); + default: + throw new IllegalArgumentException(); + } + } + //----------------------------------------------------------------------- /** * A view of this map. */ - static class View extends AbstractSet { - - /** The parent map. */ - protected final TreeBidiMap main; + abstract class View<E> extends AbstractSet<E> { + /** Whether to return KEY or VALUE order. */ - protected final int orderType; - /** Whether to return KEY, VALUE, MAPENTRY or INVERSEMAPENTRY data. */ - protected final int dataType; + protected final DataElement orderType; /** * Constructor. - * - * @param main the main map * @param orderType the KEY or VALUE int for the order - * @param dataType the KEY, VALUE, MAPENTRY or INVERSEMAPENTRY int + * @param main the main map */ - View(final TreeBidiMap main, final int orderType, final int dataType) { + View(final DataElement orderType) { super(); - this.main = main; this.orderType = orderType; - this.dataType = dataType; - } - - public Iterator iterator() { - return new ViewIterator(main, orderType, dataType); } public int size() { - return main.size(); + return TreeBidiMap.this.size(); + } + + public void clear() { + TreeBidiMap.this.clear(); + } + } + + class KeyView extends View<K> { + + /** + * Create a new TreeBidiMap.KeyView. + */ + public KeyView(DataElement orderType) { + super(orderType); + } + + @Override + public Iterator<K> iterator() { + return new ViewMapIterator(orderType); } + @Override public boolean contains(final Object obj) { - checkNonNullComparable(obj, dataType); - return (main.lookup((Comparable) obj, dataType) != null); + checkNonNullComparable(obj, KEY); + return (lookupKey(obj) != null); } - public boolean remove(final Object obj) { - return (main.doRemove((Comparable) obj, dataType) != null); + @Override + public boolean remove(Object o) { + return doRemoveKey(o) != null; } - public void clear() { - main.clear(); + } + + class ValueView extends View<V> { + + /** + * Create a new TreeBidiMap.ValueView. + */ + public ValueView(DataElement orderType) { + super(orderType); + } + + @Override + public Iterator<V> iterator() { + return new InverseViewMapIterator(orderType); + } + + @Override + public boolean contains(final Object obj) { + checkNonNullComparable(obj, VALUE); + return (lookupValue(obj) != null); + } + + @Override + public boolean remove(Object o) { + return doRemoveValue(o) != null; + } + + } + + /** + * A view of this map. + */ + class EntryView extends View<Map.Entry<K, V>> { + + EntryView() { + super(KEY); + } + + public boolean contains(Object obj) { + if (obj instanceof Map.Entry == false) { + return false; + } + Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj; + Object value = entry.getValue(); + Node<K, V> node = lookupKey(entry.getKey()); + return node != null && node.getValue().equals(value); + } + + public boolean remove(Object obj) { + if (obj instanceof Map.Entry == false) { + return false; + } + Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj; + Object value = entry.getValue(); + Node<K, V> node = lookupKey(entry.getKey()); + if (node != null && node.getValue().equals(value)) { + doRedBlackDelete(node); + return true; + } + return false; + } + + @Override + public Iterator<java.util.Map.Entry<K, V>> iterator() { + return new ViewMapEntryIterator(); + } + } + + /** + * A view of this map. + */ + class InverseEntryView extends View<Map.Entry<V, K>> { + + InverseEntryView() { + super(VALUE); + } + + public boolean contains(Object obj) { + if (obj instanceof Map.Entry == false) { + return false; + } + Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj; + Object value = entry.getValue(); + Node<K, V> node = lookupValue(entry.getKey()); + return node != null && node.getKey().equals(value); + } + + public boolean remove(Object obj) { + if (obj instanceof Map.Entry == false) { + return false; + } + Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj; + Object value = entry.getValue(); + Node<K, V> node = lookupValue(entry.getKey()); + if (node != null && node.getKey().equals(value)) { + doRedBlackDelete(node); + return true; + } + return false; + } + + @Override + public Iterator<java.util.Map.Entry<V, K>> iterator() { + return new InverseViewMapEntryIterator(); } } @@ -1512,110 +1568,84 @@ public class TreeBidiMap implements OrderedBidiMap { /** * An iterator over the map. */ - static class ViewIterator implements OrderedIterator { + abstract class ViewIterator { - /** The parent map. */ - protected final TreeBidiMap main; /** Whether to return KEY or VALUE order. */ - protected final int orderType; - /** Whether to return KEY, VALUE, MAPENTRY or INVERSEMAPENTRY data. */ - protected final int dataType; + protected final DataElement orderType; /** The last node returned by the iterator. */ - protected Node lastReturnedNode; + protected Node<K, V> lastReturnedNode; /** The next node to be returned by the iterator. */ - protected Node nextNode; + protected Node<K, V> nextNode; /** The previous node in the sequence returned by the iterator. */ - protected Node previousNode; + protected Node<K, V> previousNode; /** The modification count. */ private int expectedModifications; /** * Constructor. - * - * @param main the main map * @param orderType the KEY or VALUE int for the order - * @param dataType the KEY, VALUE, MAPENTRY or INVERSEMAPENTRY int + * @param main the main map */ - ViewIterator(final TreeBidiMap main, final int orderType, final int dataType) { + ViewIterator(final DataElement orderType) { super(); - this.main = main; this.orderType = orderType; - this.dataType = dataType; - expectedModifications = main.modifications; - nextNode = leastNode(main.rootNode[orderType], orderType); + expectedModifications = modifications; + nextNode = leastNode(rootNode[orderType.ordinal()], orderType); lastReturnedNode = null; previousNode = null; } public final boolean hasNext() { - return (nextNode != null); + return nextNode != null; } - public final Object next() { + protected Node<K, V> navigateNext() { if (nextNode == null) { throw new NoSuchElementException(); } - if (main.modifications != expectedModifications) { + if (modifications != expectedModifications) { throw new ConcurrentModificationException(); } lastReturnedNode = nextNode; previousNode = nextNode; - nextNode = main.nextGreater(nextNode, orderType); - return doGetData(); + nextNode = nextGreater(nextNode, orderType); + return lastReturnedNode; } public boolean hasPrevious() { - return (previousNode != null); + return previousNode != null; } - public Object previous() { + protected Node<K, V> navigatePrevious() { if (previousNode == null) { throw new NoSuchElementException(); } - if (main.modifications != expectedModifications) { + if (modifications != expectedModifications) { throw new ConcurrentModificationException(); } nextNode = lastReturnedNode; if (nextNode == null) { - nextNode = main.nextGreater(previousNode, orderType); + nextNode = nextGreater(previousNode, orderType); } lastReturnedNode = previousNode; - previousNode = main.nextSmaller(previousNode, orderType); - return doGetData(); - } - - /** - * Gets the data value for the lastReturnedNode field. - * @return the data value - */ - protected Object doGetData() { - switch (dataType) { - case KEY: - return lastReturnedNode.getKey(); - case VALUE: - return lastReturnedNode.getValue(); - case MAPENTRY: - return lastReturnedNode; - case INVERSEMAPENTRY: - return new UnmodifiableMapEntry(lastReturnedNode.getValue(), lastReturnedNode.getKey()); - } - return null; + previousNode = nextSmaller(previousNode, orderType); + return lastReturnedNode; } public final void remove() { if (lastReturnedNode == null) { throw new IllegalStateException(); } - if (main.modifications != expectedModifications) { + if (modifications != expectedModifications) { throw new ConcurrentModificationException(); } - main.doRedBlackDelete(lastReturnedNode); + doRedBlackDelete(lastReturnedNode); expectedModifications++; lastReturnedNode = null; if (nextNode == null) { - previousNode = TreeBidiMap.greatestNode(main.rootNode[orderType], orderType); + previousNode = greatestNode(rootNode[orderType.ordinal()], orderType); } else { - previousNode = main.nextSmaller(nextNode, orderType); + previousNode = nextSmaller(nextNode, orderType); } } } @@ -1624,95 +1654,139 @@ public class TreeBidiMap implements OrderedBidiMap { /** * An iterator over the map. */ - static class ViewMapIterator extends ViewIterator implements OrderedMapIterator { + class ViewMapIterator extends ViewIterator implements OrderedMapIterator<K, V> { - private final int oppositeType; - /** * Constructor. - * - * @param main the main map - * @param orderType the KEY or VALUE int for the order */ - ViewMapIterator(final TreeBidiMap main, final int orderType) { - super(main, orderType, orderType); - this.oppositeType = oppositeIndex(dataType); + ViewMapIterator(DataElement orderType) { + super(orderType); } - - public Object getKey() { + + public K getKey() { if (lastReturnedNode == null) { throw new IllegalStateException("Iterator getKey() can only be called after next() and before remove()"); } - return lastReturnedNode.getData(dataType); + return lastReturnedNode.getKey(); } - public Object getValue() { + public V getValue() { if (lastReturnedNode == null) { throw new IllegalStateException("Iterator getValue() can only be called after next() and before remove()"); } - return lastReturnedNode.getData(oppositeType); + return lastReturnedNode.getValue(); } - public Object setValue(final Object obj) { + public V setValue(final V obj) { throw new UnsupportedOperationException(); } + + public K next() { + return navigateNext().getKey(); + } + + public K previous() { + return navigatePrevious().getKey(); + } } - //----------------------------------------------------------------------- /** - * A view of this map. + * An iterator over the map. */ - static class EntryView extends View { - - private final int oppositeType; - + class InverseViewMapIterator extends ViewIterator implements OrderedMapIterator<V, K> { + /** - * Constructor. - * - * @param main the main map - * @param orderType the KEY or VALUE int for the order - * @param dataType the MAPENTRY or INVERSEMAPENTRY int for the returned data + * Create a new TreeBidiMap.InverseViewMapIterator. */ - EntryView(final TreeBidiMap main, final int orderType, final int dataType) { - super(main, orderType, dataType); - this.oppositeType = TreeBidiMap.oppositeIndex(orderType); + public InverseViewMapIterator(DataElement orderType) { + super(orderType); } - - public boolean contains(Object obj) { - if (obj instanceof Map.Entry == false) { - return false; + + public V getKey() { + if (lastReturnedNode == null) { + throw new IllegalStateException("Iterator getKey() can only be called after next() and before remove()"); } - Map.Entry entry = (Map.Entry) obj; - Object value = entry.getValue(); - Node node = main.lookup((Comparable) entry.getKey(), orderType); - return (node != null && node.getData(oppositeType).equals(value)); + return lastReturnedNode.getValue(); } - public boolean remove(Object obj) { - if (obj instanceof Map.Entry == false) { - return false; - } - Map.Entry entry = (Map.Entry) obj; - Object value = entry.getValue(); - Node node = main.lookup((Comparable) entry.getKey(), orderType); - if (node != null && node.getData(oppositeType).equals(value)) { - main.doRedBlackDelete(node); - return true; + public K getValue() { + if (lastReturnedNode == null) { + throw new IllegalStateException("Iterator getValue() can only be called after next() and before remove()"); } - return false; + return lastReturnedNode.getKey(); + } + + public K setValue(final K obj) { + throw new UnsupportedOperationException(); + } + + public V next() { + return navigateNext().getValue(); + } + + public V previous() { + return navigatePrevious().getValue(); + } + } + + /** + * An iterator over the map entries. + */ + class ViewMapEntryIterator extends ViewIterator implements OrderedIterator<Map.Entry<K, V>> { + + /** + * Constructor. + */ + ViewMapEntryIterator() { + super(KEY); + } + + public Map.Entry<K, V> next() { + return navigateNext(); + } + + public Map.Entry<K, V> previous() { + return navigatePrevious(); + } + } + + /** + * An iterator over the inverse map entries. + */ + class InverseViewMapEntryIterator extends ViewIterator implements OrderedIterator<Map.Entry<V, K>> { + + /** + * Constructor. + */ + InverseViewMapEntryIterator() { + super(VALUE); + } + + public Map.Entry<V, K> next() { + return createEntry(navigateNext()); + } + + public Map.Entry<V, K> previous() { + return createEntry(navigatePrevious()); + } + + private Map.Entry<V, K> createEntry(Node<K, V> node) { + return new UnmodifiableMapEntry<V, K>(node.getValue(), node.getKey()); } } //----------------------------------------------------------------------- + //----------------------------------------------------------------------- /** * A node used to store the data. */ - static class Node implements Map.Entry, KeyValue { + static class Node<K extends Comparable<K>, V extends Comparable<V>> implements Map.Entry<K, V>, KeyValue<K, V> { - private Comparable[] data; - private Node[] leftNode; - private Node[] rightNode; - private Node[] parentNode; + private K key; + private V value; + private Node<K, V>[] leftNode; + private Node<K, V>[] rightNode; + private Node<K, V>[] parentNode; private boolean[] blackColor; private int hashcodeValue; private boolean calculatedHashCode; @@ -1724,9 +1798,11 @@ public class TreeBidiMap implements OrderedBidiMap { * @param key * @param value */ - Node(final Comparable key, final Comparable value) { + @SuppressWarnings("unchecked") + Node(final K key, final V value) { super(); - data = new Comparable[] { key, value }; + this.key = key; + this.value = value; leftNode = new Node[2]; rightNode = new Node[2]; parentNode = new Node[2]; @@ -1734,54 +1810,31 @@ public class TreeBidiMap implements OrderedBidiMap { calculatedHashCode = false; } - /** - * Get the specified data. - * - * @param index the KEY or VALUE int - * @return the key or value - */ - private Comparable getData(final int index) { - return data[index]; + private Object getData(final DataElement dataElement) { + switch (dataElement) { + case KEY: + return getKey(); + case VALUE: + return getValue(); + default: + throw new IllegalArgumentException(); + } } - /** - * Set this node's left node. - * - * @param node the new left node - * @param index the KEY or VALUE int - */ - private void setLeft(final Node node, final int index) { - leftNode[index] = node; + private void setLeft(final Node<K, V> node, final DataElement dataElement) { + leftNode[dataElement.ordinal()] = node; } - /** - * Get the left node. - * - * @param index the KEY or VALUE int - * @return the left node, may be null - */ - private Node getLeft(final int index) { - return leftNode[index]; + private Node<K, V> getLeft(final DataElement dataElement) { + return leftNode[dataElement.ordinal()]; } - /** - * Set this node's right node. - * - * @param node the new right node - * @param index the KEY or VALUE int - */ - private void setRight(final Node node, final int index) { - rightNode[index] = node; + private void setRight(final Node<K, V> node, final DataElement dataElement) { + rightNode[dataElement.ordinal()] = node; } - /** - * Get the right node. - * - * @param index the KEY or VALUE int - * @return the right node, may be null - */ - private Node getRight(final int index) { - return rightNode[index]; + private Node<K, V> getRight(final DataElement dataElement) { + return rightNode[dataElement.ordinal()]; } /** @@ -1790,8 +1843,8 @@ public class TreeBidiMap implements OrderedBidiMap { * @param node the new parent node * @param index the KEY or VALUE int */ - private void setParent(final Node node, final int index) { - parentNode[index] = node; + private void setParent(final Node<K, V> node, final DataElement dataElement) { + parentNode[dataElement.ordinal()] = node; } /** @@ -1800,8 +1853,8 @@ public class TreeBidiMap implements OrderedBidiMap { * @param index the KEY or VALUE int * @return the parent node, may be null */ - private Node getParent(final int index) { - return parentNode[index]; + private Node<K, V> getParent(final DataElement dataElement) { + return parentNode[dataElement.ordinal()]; } /** @@ -1810,11 +1863,11 @@ public class TreeBidiMap implements OrderedBidiMap { * @param node the node to swap with * @param index the KEY or VALUE int */ - private void swapColors(final Node node, final int index) { + private void swapColors(final Node<K, V> node, final DataElement dataElement) { // Swap colors -- old hacker's trick - blackColor[index] ^= node.blackColor[index]; - node.blackColor[index] ^= blackColor[index]; - blackColor[index] ^= node.blackColor[index]; + blackColor[dataElement.ordinal()] ^= node.blackColor[dataElement.ordinal()]; + node.blackColor[dataElement.ordinal()] ^= blackColor[dataElement.ordinal()]; + blackColor[dataElement.ordinal()] ^= node.blackColor[dataElement.ordinal()]; } /** @@ -1823,8 +1876,8 @@ public class TreeBidiMap implements OrderedBidiMap { * @param index the KEY or VALUE int * @return true if black (which is represented as a true boolean) */ - private boolean isBlack(final int index) { - return blackColor[index]; + private boolean isBlack(final DataElement dataElement) { + return blackColor[dataElement.ordinal()]; } /** @@ -1833,8 +1886,8 @@ public class TreeBidiMap implements OrderedBidiMap { * @param index the KEY or VALUE int * @return true if non-black */ - private boolean isRed(final int index) { - return !blackColor[index]; + private boolean isRed(final DataElement dataElement) { + return !blackColor[dataElement.ordinal()]; } /** @@ -1842,8 +1895,8 @@ public class TreeBidiMap implements OrderedBidiMap { * * @param index the KEY or VALUE int */ - private void setBlack(final int index) { - blackColor[index] = true; + private void setBlack(final DataElement dataElement) { + blackColor[dataElement.ordinal()] = true; } /** @@ -1851,8 +1904,8 @@ public class TreeBidiMap implements OrderedBidiMap { * * @param index the KEY or VALUE int */ - private void setRed(final int index) { - blackColor[index] = false; + private void setRed(final DataElement dataElement) { + blackColor[dataElement.ordinal()] = false; } /** @@ -1861,27 +1914,37 @@ public class TreeBidiMap implements OrderedBidiMap { * @param node the node whose color we're adopting * @param index the KEY or VALUE int */ - private void copyColor(final Node node, final int index) { - blackColor[index] = node.blackColor[index]; + private void copyColor(final Node<K, V> node, final DataElement dataElement) { + blackColor[dataElement.ordinal()] = node.blackColor[dataElement.ordinal()]; + } + + private boolean isLeftChild(final DataElement dataElement) { + return parentNode[dataElement.ordinal()] != null + && parentNode[dataElement.ordinal()].leftNode[dataElement.ordinal()] == this; + } + + private boolean isRightChild(final DataElement dataElement) { + return parentNode[dataElement.ordinal()] != null + && parentNode[dataElement.ordinal()].rightNode[dataElement.ordinal()] == this; } //------------------------------------------------------------------- /** * Gets the key. - * + * * @return the key corresponding to this entry. */ - public Object getKey() { - return data[KEY]; + public K getKey() { + return key; } /** * Gets the value. - * + * * @return the value corresponding to this entry. */ - public Object getValue() { - return data[VALUE]; + public V getValue() { + return value; } /** @@ -1891,10 +1954,8 @@ public class TreeBidiMap impleme
<TRUNCATED>
