~ubuntu-branches/debian/squeeze/libcommons-collections-java/squeeze

/*
 * Copyright 1999-2004 The Apache Software Foundation
 *
 * 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 org.apache.commons.collections;



import java.util.AbstractCollection;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;


/**
* Red-Black tree-based implementation of Map. This class guarantees
* that the map will be in both ascending key order and ascending
* value order, sorted according to the natural order for the key's
* and value's classes.<p>
*
* This Map is intended for applications that need to be able to look
* up a key-value pairing by either key or value, and need to do so
* with equal efficiency.<p>
*
* While that goal could be accomplished by taking a pair of TreeMaps
* and redirecting requests to the appropriate TreeMap (e.g.,
* containsKey would be directed to the TreeMap that maps values to
* keys, containsValue would be directed to the TreeMap that maps keys
* to values), there are problems with that implementation,
* particularly when trying to keep the two TreeMaps synchronized with
* each other. And if the data contained in the TreeMaps is large, the
* cost of redundant storage becomes significant.<p>
*
* This solution keeps the data properly synchronized and minimizes
* the data storage. The red-black algorithm is based on TreeMap's,
* but has been modified to simultaneously map a tree node by key and
* by value. This doubles the cost of put operations (but so does
* using two TreeMaps), and nearly doubles the cost of remove
* operations (there is a savings in that the lookup of the node to be
* removed only has to be performed once). And since only one node
* contains the key and value, storage is significantly less than that
* required by two TreeMaps.<p>
*
* There are some limitations placed on data kept in this Map. The
* biggest one is this:<p>
*
* When performing a put operation, neither the key nor the value may
* already exist in the Map. In the java.util Map implementations
* (HashMap, TreeMap), you can perform a put with an already mapped
* key, and neither cares about duplicate values at all ... but this
* implementation's put method with throw an IllegalArgumentException
* if either the key or the value is already in the Map.<p>
*
* Obviously, that same restriction (and consequence of failing to
* heed that restriction) applies to the putAll method.<p>
*
* The Map.Entry instances returned by the appropriate methods will
* not allow setValue() and will throw an
* UnsupportedOperationException on attempts to call that method.<p>
*
* New methods are added to take advantage of the fact that values are
* kept sorted independently of their keys:<p>
*
* Object getKeyForValue(Object value) is the opposite of get; it
* takes a value and returns its key, if any.<p>
*
* Object removeValue(Object value) finds and removes the specified
* value and returns the now un-used key.<p>
*
* Set entrySetByValue() returns the Map.Entry's in a Set whose
* iterator will iterate over the Map.Entry's in ascending order by
* their corresponding values.<p>
*
* Set keySetByValue() returns the keys in a Set whose iterator will
* iterate over the keys in ascending order by their corresponding
* values.<p>
*
* Collection valuesByValue() returns the values in a Collection whose
* iterator will iterate over the values in ascending order.<p>
*
* @since 2.0
* @author Marc Johnson (marcj at users dot sourceforge dot net)
*/

// final for performance
public final class DoubleOrderedMap extends AbstractMap {

    private Node[]                rootNode           = new Node[]{ null,
                                                           null };
    private int                   nodeCount          = 0;
    private int                   modifications      = 0;
    private Set[]                 setOfKeys          = new Set[]{ null,
                                                           null };
    private Set[]                 setOfEntries       = new Set[]{ null,
                                                           null };
    private Collection[]          collectionOfValues = new Collection[]{ 
null,
                                                                         
null };
    private static final int      KEY                = 0;
    private static final int      VALUE              = 1;
    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" 
};

    /**
     * Construct a new DoubleOrderedMap
     */
    public DoubleOrderedMap() {}

    /**
     * Constructs a new DoubleOrderedMap from an existing Map, with keys and
     * values sorted
     *
     * @param map the map whose mappings are to be placed in this map.
     *
     * @exception ClassCastException if the keys in the map are not
     *                               Comparable, or are not mutually
     *                               comparable; also if the values in
     *                               the map are not Comparable, or
     *                               are not mutually Comparable
     * @exception NullPointerException if any key or value in the map
     *                                 is null
     * @exception IllegalArgumentException if there are duplicate keys
     *                                     or duplicate values in the
     *                                     map
     */
    public DoubleOrderedMap(final Map map)
            throws ClassCastException, NullPointerException,
                   IllegalArgumentException {
        putAll(map);
    }

    /**
     * Returns the key to which this map maps the specified value.
     * Returns null if the map contains no mapping for this value.
     *
     * @param value value whose associated key is to be returned.
     *
     * @return the key to which this map maps the specified value, or
     *         null if the map contains no mapping for this value.
     *
     * @exception ClassCastException if the value is of an
     *                               inappropriate type for this map.
     * @exception NullPointerException if the value is null
     */
    public Object getKeyForValue(final Object value)
            throws ClassCastException, NullPointerException {
        return doGet((Comparable) value, VALUE);
    }

    /**
     * Removes the mapping for this value from this map if present
     *
     * @param value value whose mapping is to be removed from the map.
     *
     * @return previous key associated with specified value, or null
     *         if there was no mapping for value.
     */
    public Object removeValue(final Object value) {
        return doRemove((Comparable) value, VALUE);
    }

    /**
     * Returns a set view of the mappings contained in this map. Each
     * element in the returned set is a Map.Entry. The set is backed
     * by the map, so changes to the map are reflected in the set, and
     * vice-versa.  If the map is modified while an iteration over the
     * set is in progress, the results of the iteration are
     * undefined. The set supports element removal, which removes the
     * corresponding mapping from the map, via the Iterator.remove,
     * Set.remove, removeAll, retainAll and clear operations.  It does
     * not support the add or addAll operations.<p>
     *
     * The difference between this method and entrySet is that
     * entrySet's iterator() method returns an iterator that iterates
     * over the mappings in ascending order by key. This method's
     * iterator method iterates over the mappings in ascending order
     * by value.
     *
     * @return a set view of the mappings contained in this map.
     */
    public Set entrySetByValue() {

        if (setOfEntries[VALUE] == null) {
            setOfEntries[VALUE] = new AbstractSet() {

                public Iterator iterator() {

                    return new DoubleOrderedMapIterator(VALUE) {

                        protected Object doGetNext() {
                            return lastReturnedNode;
                        }
                    };
                }

                public boolean contains(Object o) {

                    if (!(o instanceof Map.Entry)) {
                        return false;
                    }

                    Map.Entry entry = (Map.Entry) o;
                    Object    key   = entry.getKey();
                    Node      node  = lookup((Comparable) entry.getValue(),
                                             VALUE);

                    return (node != null) && node.getData(KEY).equals(key);
                }

                public boolean remove(Object o) {

                    if (!(o instanceof Map.Entry)) {
                        return false;
                    }

                    Map.Entry entry = (Map.Entry) o;
                    Object    key   = entry.getKey();
                    Node      node  = lookup((Comparable) entry.getValue(),
                                             VALUE);

                    if ((node != null) && node.getData(KEY).equals(key)) {
                        doRedBlackDelete(node);

                        return true;
                    }

                    return false;
                }

                public int size() {
                    return DoubleOrderedMap.this.size();
                }

                public void clear() {
                    DoubleOrderedMap.this.clear();
                }
            };
        }

        return setOfEntries[VALUE];
    }

    /**
     * Returns a set view of the keys contained in this map.  The set
     * is backed by the map, so changes to the map are reflected in
     * the set, and vice-versa. If the map is modified while an
     * iteration over the set is in progress, the results of the
     * iteration are undefined. The set supports element removal,
     * which removes the corresponding mapping from the map, via the
     * Iterator.remove, Set.remove, removeAll, retainAll, and clear
     * operations. It does not support the add or addAll
     * operations.<p>
     *
     * The difference between this method and keySet is that keySet's
     * iterator() method returns an iterator that iterates over the
     * keys in ascending order by key. This method's iterator method
     * iterates over the keys in ascending order by value.
     *
     * @return a set view of the keys contained in this map.
     */
    public Set keySetByValue() {

        if (setOfKeys[VALUE] == null) {
            setOfKeys[VALUE] = new AbstractSet() {

                public Iterator iterator() {

                    return new DoubleOrderedMapIterator(VALUE) {

                        protected Object doGetNext() {
                            return lastReturnedNode.getData(KEY);
                        }
                    };
                }

                public int size() {
                    return DoubleOrderedMap.this.size();
                }

                public boolean contains(Object o) {
                    return containsKey(o);
                }

                public boolean remove(Object o) {

                    int oldnodeCount = nodeCount;

                    DoubleOrderedMap.this.remove(o);

                    return nodeCount != oldnodeCount;
                }

                public void clear() {
                    DoubleOrderedMap.this.clear();
                }
            };
        }

        return setOfKeys[VALUE];
    }

    /**
     * Returns a collection view of the values contained in this
     * map. The collection is backed by the map, so changes to the map
     * are reflected in the collection, and vice-versa. If the map is
     * modified while an iteration over the collection is in progress,
     * the results of the iteration are undefined. The collection
     * supports element removal, which removes the corresponding
     * mapping from the map, via the Iterator.remove,
     * Collection.remove, removeAll, retainAll and clear operations.
     * It does not support the add or addAll operations.<p>
     *
     * The difference between this method and values is that values's
     * iterator() method returns an iterator that iterates over the
     * values in ascending order by key. This method's iterator method
     * iterates over the values in ascending order by key.
     *
     * @return a collection view of the values contained in this map.
     */
    public Collection valuesByValue() {

        if (collectionOfValues[VALUE] == null) {
            collectionOfValues[VALUE] = new AbstractCollection() {

                public Iterator iterator() {

                    return new DoubleOrderedMapIterator(VALUE) {

                        protected Object doGetNext() {
                            return lastReturnedNode.getData(VALUE);
                        }
                    };
                }

                public int size() {
                    return DoubleOrderedMap.this.size();
                }

                public boolean contains(Object o) {
                    return containsValue(o);
                }

                public boolean remove(Object o) {

                    int oldnodeCount = nodeCount;

                    removeValue(o);

                    return nodeCount != oldnodeCount;
                }

                public boolean removeAll(Collection c) {

                    boolean  modified = false;
                    Iterator iter     = c.iterator();

                    while (iter.hasNext()) {
                        if (removeValue(iter.next()) != null) {
                            modified = true;
                        }
                    }

                    return modified;
                }

                public void clear() {
                    DoubleOrderedMap.this.clear();
                }
            };
        }

        return collectionOfValues[VALUE];
    }

    /**
     * common remove logic (remove by key or remove by value)
     *
     * @param o the key, or value, that we're looking for
     * @param index KEY or VALUE
     *
     * @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);
        }

        return rval;
    }

    /**
     * common get logic, used to get by key or get by value
     *
     * @param o the key or value that we're looking for
     * @param index KEY or VALUE
     *
     * @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 o, final int index) {

        checkNonNullComparable(o, index);

        Node node = lookup(o, index);

        return ((node == null)
                ? null
                : node.getData(oppositeIndex(index)));
    }

    /**
     * Get the opposite index of the specified index
     *
     * @param index KEY or VALUE
     *
     * @return VALUE (if KEY was specified), else KEY
     */
    private 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;
    }

    /**
     * do the actual lookup of a piece of data
     *
     * @param data the key or value to be looked up
     * @param index KEY or VALUE
     *
     * @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];

        while (node != null) {
            int cmp = compare(data, node.getData(index));

            if (cmp == 0) {
                rval = node;

                break;
            } else {
                node = (cmp < 0)
                       ? node.getLeft(index)
                       : node.getRight(index);
            }
        }

        return rval;
    }

    /**
     * Compare two objects
     *
     * @param o1 the first object
     * @param o2 the second object
     *
     * @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) {
        return ((Comparable) o1).compareTo(o2);
    }

    /**
     * find the least node from a given node. very useful for starting
     * a sorting iterator ...
     *
     * @param node the node from which we will start searching
     * @param index KEY or VALUE
     *
     * @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;

        if (rval != null) {
            while (rval.getLeft(index) != null) {
                rval = rval.getLeft(index);
            }
        }

        return rval;
    }

    /**
     * get the next larger node from the specified node
     *
     * @param node the node to be searched from
     * @param index KEY or VALUE
     *
     * @return the specified node
     */
    private Node nextGreater(final Node node, final int index) {

        Node rval = null;

        if (node == null) {
            rval = null;
        } else if (node.getRight(index) != null) {

            // everything to the node's right is larger. The least of
            // the right node's descendents is the next larger node
            rval = leastNode(node.getRight(index), index);
        } else {

            // traverse up our ancestry until we find an ancestor that
            // is null or one whose left child is our ancestor. If we
            // find a null, then this node IS the largest node in the
            // 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;

            while ((parent != null) && (child == parent.getRight(index))) {
                child  = parent;
                parent = parent.getParent(index);
            }

            rval = parent;
        }

        return rval;
    }

    /**
     * copy the color from one node to another, dealing with the fact
     * that one or both nodes may, in fact, be null
     *
     * @param from the node whose color we're copying; may be null
     * @param to the node whose color we're changing; may be null
     * @param index KEY or VALUE
     */
    private static void copyColor(final Node from, final Node to,
                                  final int index) {

        if (to != null) {
            if (from == null) {

                // by default, make it black
                to.setBlack(index);
            } else {
                to.copyColor(from, index);
            }
        }
    }

    /**
     * is the specified node red? if the node does not exist, no, it's
     * black, thank you
     *
     * @param node the node (may be null) in question
     * @param index KEY or VALUE
     */
    private static boolean isRed(final Node node, final int index) {

        return ((node == null)
                ? false
                : node.isRed(index));
    }

    /**
     * is the specified black red? if the node does not exist, sure,
     * it's black, thank you
     *
     * @param node the node (may be null) in question
     * @param index KEY or VALUE
     */
    private static boolean isBlack(final Node node, final int index) {

        return ((node == null)
                ? true
                : node.isBlack(index));
    }

    /**
     * force a node (if it exists) red
     *
     * @param node the node (may be null) in question
     * @param index KEY or VALUE
     */
    private static void makeRed(final Node node, final int index) {

        if (node != null) {
            node.setRed(index);
        }
    }

    /**
     * force a node (if it exists) black
     *
     * @param node the node (may be null) in question
     * @param index KEY or VALUE
     */
    private static void makeBlack(final Node node, final int index) {

        if (node != null) {
            node.setBlack(index);
        }
    }

    /**
     * get a node's grandparent. mind you, the node, its parent, or
     * its grandparent may not exist. no problem
     *
     * @param node the node (may be null) in question
     * @param index KEY or VALUE
     */
    private static Node getGrandParent(final Node node, final int index) {
        return getParent(getParent(node, index), index);
    }

    /**
     * get a node's parent. mind you, the node, or its parent, may not
     * exist. no problem
     *
     * @param node the node (may be null) in question
     * @param index KEY or VALUE
     */
    private static Node getParent(final Node node, final int index) {

        return ((node == null)
                ? null
                : node.getParent(index));
    }

    /**
     * get a node's right child. mind you, the node may not exist. no
     * problem
     *
     * @param node the node (may be null) in question
     * @param index KEY or VALUE
     */
    private static Node getRightChild(final Node node, final int index) {

        return (node == null)
               ? null
               : node.getRight(index);
    }

    /**
     * get a node's left child. mind you, the node may not exist. no
     * problem
     *
     * @param node the node (may be null) in question
     * @param index KEY or VALUE
     */
    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 KEY or VALUE
     */
    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 KEY or VALUE
     */
    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)));
    }

    /**
     * do a rotate left. standard fare in the world of balanced trees
     *
     * @param node the node to be rotated
     * @param index KEY or VALUE
     */
    private void rotateLeft(final Node node, final int index) {

        Node rightChild = node.getRight(index);

        node.setRight(rightChild.getLeft(index), index);

        if (rightChild.getLeft(index) != null) {
            rightChild.getLeft(index).setParent(node, index);
        }

        rightChild.setParent(node.getParent(index), index);

        if (node.getParent(index) == 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);
        } else {
            node.getParent(index).setRight(rightChild, index);
        }

        rightChild.setLeft(node, index);
        node.setParent(rightChild, index);
    }

    /**
     * do a rotate right. standard fare in the world of balanced trees
     *
     * @param node the node to be rotated
     * @param index KEY or VALUE
     */
    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);
        }

        leftChild.setParent(node.getParent(index), index);

        if (node.getParent(index) == 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);
        } else {
            node.getParent(index).setLeft(leftChild, index);
        }

        leftChild.setRight(node, index);
        node.setParent(leftChild, index);
    }

    /**
     * complicated red-black insert stuff. Based on Sun's TreeMap
     * implementation, though it's barely recognizeable any more
     *
     * @param insertedNode the node to be inserted
     * @param index KEY or VALUE
     */
    private void doRedBlackInsert(final Node insertedNode, final int index) 
{

        Node currentNode = insertedNode;

        makeRed(currentNode, index);

        while ((currentNode != null) && (currentNode != rootNode[index])
                && (isRed(currentNode.getParent(index), index))) {
            if (isLeftChild(getParent(currentNode, index), index)) {
                Node y = getRightChild(getGrandParent(currentNode, index),
                                       index);

                if (isRed(y, index)) {
                    makeBlack(getParent(currentNode, index), index);
                    makeBlack(y, index);
                    makeRed(getGrandParent(currentNode, index), index);

                    currentNode = getGrandParent(currentNode, index);
                } else {
                    if (isRightChild(currentNode, index)) {
                        currentNode = getParent(currentNode, index);

                        rotateLeft(currentNode, index);
                    }

                    makeBlack(getParent(currentNode, index), index);
                    makeRed(getGrandParent(currentNode, index), index);

                    if (getGrandParent(currentNode, index) != null) {
                        rotateRight(getGrandParent(currentNode, index),
                                    index);
                    }
                }
            } else {

                // just like clause above, except swap left for right
                Node y = getLeftChild(getGrandParent(currentNode, index),
                                      index);

                if (isRed(y, index)) {
                    makeBlack(getParent(currentNode, index), index);
                    makeBlack(y, index);
                    makeRed(getGrandParent(currentNode, index), index);

                    currentNode = getGrandParent(currentNode, index);
                } else {
                    if (isLeftChild(currentNode, index)) {
                        currentNode = getParent(currentNode, index);

                        rotateRight(currentNode, index);
                    }

                    makeBlack(getParent(currentNode, index), index);
                    makeRed(getGrandParent(currentNode, index), index);

                    if (getGrandParent(currentNode, index) != null) {
                        rotateLeft(getGrandParent(currentNode, index), 
index);
                    }
                }
            }
        }

        makeBlack(rootNode[index], index);
    }

    /**
     * complicated red-black delete stuff. Based on Sun's TreeMap
     * implementation, though it's barely recognizeable any more
     *
     * @param deletedNode the node to be deleted
     */
    private void doRedBlackDelete(final Node deletedNode) {

        for (int index = FIRST_INDEX; index < NUMBER_OF_INDICES; index++) {

            // 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);
            }

            Node replacement = ((deletedNode.getLeft(index) != null)
                                ? deletedNode.getLeft(index)
                                : deletedNode.getRight(index));

            if (replacement != null) {
                replacement.setParent(deletedNode.getParent(index), index);

                if (deletedNode.getParent(index) == null) {
                    rootNode[index] = replacement;
                } else if (deletedNode
                           == deletedNode.getParent(index).getLeft(index)) {
                    deletedNode.getParent(index).setLeft(replacement, 
index);
                } else {
                    deletedNode.getParent(index).setRight(replacement, 
index);
                }

                deletedNode.setLeft(null, index);
                deletedNode.setRight(null, index);
                deletedNode.setParent(null, index);

                if (isBlack(deletedNode, index)) {
                    doRedBlackDeleteFixup(replacement, index);
                }
            } else {

                // replacement is null
                if (deletedNode.getParent(index) == null) {

                    // empty tree
                    rootNode[index] = null;
                } else {

                    // deleted node had no children
                    if (isBlack(deletedNode, index)) {
                        doRedBlackDeleteFixup(deletedNode, index);
                    }

                    if (deletedNode.getParent(index) != null) {
                        if (deletedNode
                                == deletedNode.getParent(index)
                                    .getLeft(index)) {
                            deletedNode.getParent(index).setLeft(null, 
index);
                        } else {
                            deletedNode.getParent(index).setRight(null,
                                                  index);
                        }

                        deletedNode.setParent(null, index);
                    }
                }
            }
        }

        shrink();
    }

    /**
     * complicated red-black delete stuff. Based on Sun's TreeMap
     * implementation, though it's barely recognizeable any more. This
     * rebalances the tree (somewhat, as red-black trees are not
     * perfectly balanced -- perfect balancing takes longer)
     *
     * @param replacementNode the node being replaced
     * @param index KEY or VALUE
     */
    private void doRedBlackDeleteFixup(final Node replacementNode,
                                       final int index) {

        Node currentNode = replacementNode;

        while ((currentNode != rootNode[index])
                && (isBlack(currentNode, index))) {
            if (isLeftChild(currentNode, index)) {
                Node siblingNode =
                    getRightChild(getParent(currentNode, index), index);

                if (isRed(siblingNode, index)) {
                    makeBlack(siblingNode, index);
                    makeRed(getParent(currentNode, index), index);
                    rotateLeft(getParent(currentNode, index), index);

                    siblingNode = getRightChild(getParent(currentNode, 
index),
                                                index);
                }

                if (isBlack(getLeftChild(siblingNode, index), index)
                        && isBlack(getRightChild(siblingNode, index),
                                   index)) {
                    makeRed(siblingNode, index);

                    currentNode = getParent(currentNode, index);
                } else {
                    if (isBlack(getRightChild(siblingNode, index), index)) {
                        makeBlack(getLeftChild(siblingNode, index), index);
                        makeRed(siblingNode, index);
                        rotateRight(siblingNode, index);

                        siblingNode =
                            getRightChild(getParent(currentNode, index),
                                          index);
                    }

                    copyColor(getParent(currentNode, index), siblingNode,
                              index);
                    makeBlack(getParent(currentNode, index), index);
                    makeBlack(getRightChild(siblingNode, index), index);
                    rotateLeft(getParent(currentNode, index), index);

                    currentNode = rootNode[index];
                }
            } else {
                Node siblingNode = getLeftChild(getParent(currentNode, 
index),
                                                index);

                if (isRed(siblingNode, index)) {
                    makeBlack(siblingNode, index);
                    makeRed(getParent(currentNode, index), index);
                    rotateRight(getParent(currentNode, index), index);

                    siblingNode = getLeftChild(getParent(currentNode, 
index),
                                               index);
                }

                if (isBlack(getRightChild(siblingNode, index), index)
                        && isBlack(getLeftChild(siblingNode, index), index)) 
{
                    makeRed(siblingNode, index);

                    currentNode = getParent(currentNode, index);
                } else {
                    if (isBlack(getLeftChild(siblingNode, index), index)) {
                        makeBlack(getRightChild(siblingNode, index), index);
                        makeRed(siblingNode, index);
                        rotateLeft(siblingNode, index);

                        siblingNode =
                            getLeftChild(getParent(currentNode, index),
                                         index);
                    }

                    copyColor(getParent(currentNode, index), siblingNode,
                              index);
                    makeBlack(getParent(currentNode, index), index);
                    makeBlack(getLeftChild(siblingNode, index), index);
                    rotateRight(getParent(currentNode, index), index);

                    currentNode = rootNode[index];
                }
            }
        }

        makeBlack(currentNode, index);
    }

    /**
     * swap two nodes (except for their content), taking care of
     * special cases where one is the other's parent ... hey, it
     * happens.
     *
     * @param x one node
     * @param y another node
     * @param index KEY or VALUE
     */
    private void swapPosition(final Node x, final Node y, final int index) {

        // 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));

        // Swap, handling special cases of one being the other's parent.
        if (x == yFormerParent) {    // x was y's parent
            x.setParent(y, index);

            if (yWasLeftChild) {
                y.setLeft(x, index);
                y.setRight(xFormerRightChild, index);
            } else {
                y.setRight(x, index);
                y.setLeft(xFormerLeftChild, index);
            }
        } else {
            x.setParent(yFormerParent, index);

            if (yFormerParent != null) {
                if (yWasLeftChild) {
                    yFormerParent.setLeft(x, index);
                } else {
                    yFormerParent.setRight(x, index);
                }
            }

            y.setLeft(xFormerLeftChild, index);
            y.setRight(xFormerRightChild, index);
        }

        if (y == xFormerParent) {    // y was x's parent
            y.setParent(x, index);

            if (xWasLeftChild) {
                x.setLeft(y, index);
                x.setRight(yFormerRightChild, index);
            } else {
                x.setRight(y, index);
                x.setLeft(yFormerLeftChild, index);
            }
        } else {
            y.setParent(xFormerParent, index);

            if (xFormerParent != null) {
                if (xWasLeftChild) {
                    xFormerParent.setLeft(y, index);
                } else {
                    xFormerParent.setRight(y, index);
                }
            }

            x.setLeft(yFormerLeftChild, index);
            x.setRight(yFormerRightChild, index);
        }

        // Fix children's parent pointers
        if (x.getLeft(index) != null) {
            x.getLeft(index).setParent(x, index);
        }

        if (x.getRight(index) != null) {
            x.getRight(index).setParent(x, index);
        }

        if (y.getLeft(index) != null) {
            y.getLeft(index).setParent(y, index);
        }

        if (y.getRight(index) != null) {
            y.getRight(index).setParent(y, index);
        }

        x.swapColors(y, index);

        // Check if root changed
        if (rootNode[index] == x) {
            rootNode[index] = y;
        } else if (rootNode[index] == y) {
            rootNode[index] = x;
        }
    }

    /**
     * check if an object is fit to be proper input ... has to be
     * Comparable and non-null
     *
     * @param o the object being checked
     * @param index KEY or VALUE (used to put the right word in the
     *              exception message)
     *
     * @exception NullPointerException if o is null
     * @exception ClassCastException if o is not Comparable
     */
    private static void checkNonNullComparable(final Object o,
                                               final int index) {

        if (o == null) {
            throw new NullPointerException(dataName[index]
                                           + " cannot be null");
        }

        if (!(o instanceof Comparable)) {
            throw new ClassCastException(dataName[index]
                                         + " must be Comparable");
        }
    }

    /**
     * check a key for validity (non-null and implements Comparable)
     *
     * @param key the key to be checked
     *
     * @exception NullPointerException if key is null
     * @exception ClassCastException if key is not Comparable
     */
    private static void checkKey(final Object key) {
        checkNonNullComparable(key, KEY);
    }

    /**
     * check a value for validity (non-null and implements Comparable)
     *
     * @param value the value to be checked
     *
     * @exception NullPointerException if value is null
     * @exception ClassCastException if value is not Comparable
     */
    private static void checkValue(final Object value) {
        checkNonNullComparable(value, VALUE);
    }

    /**
     * check a key and a value for validity (non-null and implements
     * Comparable)
     *
     * @param key the key to be checked
     * @param value the value to be checked
     *
     * @exception NullPointerException if key or value is null
     * @exception ClassCastException if key or value is not Comparable
     */
    private static void checkKeyAndValue(final Object key,
                                         final Object value) {
        checkKey(key);
        checkValue(value);
    }

    /**
     * increment the modification count -- used to check for
     * concurrent modification of the map through the map and through
     * an Iterator from one of its Set or Collection views
     */
    private void modify() {
        modifications++;
    }

    /**
     * bump up the size and note that the map has changed
     */
    private void grow() {

        modify();

        nodeCount++;
    }

    /**
     * decrement the size and note that the map has changed
     */
    private void shrink() {

        modify();

        nodeCount--;
    }

    /**
     * insert a node by its value
     *
     * @param newNode the node to be inserted
     *
     * @exception IllegalArgumentException if the node already exists
     *                                     in the value mapping
     */
    private void insertValue(final Node newNode)
            throws IllegalArgumentException {

        Node node = rootNode[VALUE];

        while (true) {
            int cmp = compare(newNode.getData(VALUE), node.getData(VALUE));

            if (cmp == 0) {
                throw new IllegalArgumentException(
                    "Cannot store a duplicate value (\""
                    + newNode.getData(VALUE) + "\") in this Map");
            } else if (cmp < 0) {
                if (node.getLeft(VALUE) != null) {
                    node = node.getLeft(VALUE);
                } else {
                    node.setLeft(newNode, VALUE);
                    newNode.setParent(node, VALUE);
                    doRedBlackInsert(newNode, VALUE);

                    break;
                }
            } else {    // cmp > 0
                if (node.getRight(VALUE) != null) {
                    node = node.getRight(VALUE);
                } else {
                    node.setRight(newNode, VALUE);
                    newNode.setParent(node, VALUE);
                    doRedBlackInsert(newNode, VALUE);

                    break;
                }
            }
        }
    }

    /* ********** START implementation of Map ********** */

    /**
     * Returns the number of key-value mappings in this map. If the
     * map contains more than Integer.MAXVALUE elements, returns
     * Integer.MAXVALUE.
     *
     * @return the number of key-value mappings in this map.
     */
    public int size() {
        return nodeCount;
    }

    /**
     * Returns true if this map contains a mapping for the specified
     * key.
     *
     * @param key key whose presence in this map is to be tested.
     *
     * @return true if this map contains a mapping for the specified
     *         key.
     *
     * @exception ClassCastException if the key is of an inappropriate
     *                               type for this map.
     * @exception NullPointerException if the key is null
     */
    public boolean containsKey(final Object key)
            throws ClassCastException, NullPointerException {

        checkKey(key);

        return lookup((Comparable) key, KEY) != null;
    }

    /**
     * Returns true if this map maps one or more keys to the
     * specified value.
     *
     * @param value value whose presence in this map is to be tested.
     *
     * @return true if this map maps one or more keys to the specified
     *         value.
     */
    public boolean containsValue(final Object value) {

        checkValue(value);

        return lookup((Comparable) value, VALUE) != null;
    }

    /**
     * Returns the value to which this map maps the specified
     * key. Returns null if the map contains no mapping for this key.
     *
     * @param key key whose associated value is to be returned.
     *
     * @return the value to which this map maps the specified key, or
     *         null if the map contains no mapping for this key.
     *
     * @exception ClassCastException if the key is of an inappropriate
     *                               type for this map.
     * @exception NullPointerException if the key is null
     */
    public Object get(final Object key)
            throws ClassCastException, NullPointerException {
        return doGet((Comparable) key, KEY);
    }

    /**
     * Associates the specified value with the specified key in this
     * map.
     *
     * @param key key with which the specified value is to be
     *            associated.
     * @param value value to be associated with the specified key.
     *
     * @return null
     *
     * @exception ClassCastException if the class of the specified key
     *                               or value prevents it from being
     *                               stored in this map.
     * @exception NullPointerException if the specified key or value
     *                                 is null
     * @exception IllegalArgumentException if the key duplicates an
     *                                     existing key, or if the
     *                                     value duplicates an
     *                                     existing value
     */
    public Object put(final Object key, final Object value)
            throws ClassCastException, NullPointerException,
                   IllegalArgumentException {

        checkKeyAndValue(key, value);

        Node node = rootNode[KEY];

        if (node == null) {
            Node root = new Node((Comparable) key, (Comparable) value);

            rootNode[KEY]   = root;
            rootNode[VALUE] = root;

            grow();
        } else {
            while (true) {
                int cmp = compare((Comparable) key, node.getData(KEY));

                if (cmp == 0) {
                    throw new IllegalArgumentException(
                        "Cannot store a duplicate key (\"" + key
                        + "\") in this Map");
                } else if (cmp < 0) {
                    if (node.getLeft(KEY) != null) {
                        node = node.getLeft(KEY);
                    } else {
                        Node newNode = new Node((Comparable) key,
                                                (Comparable) 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((Comparable) key,
                                                (Comparable) value);

                        insertValue(newNode);
                        node.setRight(newNode, KEY);
                        newNode.setParent(node, KEY);
                        doRedBlackInsert(newNode, KEY);
                        grow();

                        break;
                    }
                }
            }
        }

        return null;
    }

    /**
     * Removes the mapping for this key from this map if present
     *
     * @param key key whose mapping is to be removed from the map.
     *
     * @return previous value associated with specified key, or null
     *         if there was no mapping for key.
     */
    public Object remove(final Object key) {
        return doRemove((Comparable) key, KEY);
    }

    /**
     * Removes all mappings from this map
     */
    public void clear() {

        modify();

        nodeCount   = 0;
        rootNode[KEY]   = null;
        rootNode[VALUE] = null;
    }

    /**
     * Returns a set view of the keys contained in this map.  The set
     * is backed by the map, so changes to the map are reflected in
     * the set, and vice-versa. If the map is modified while an
     * iteration over the set is in progress, the results of the
     * iteration are undefined. The set supports element removal,
     * which removes the corresponding mapping from the map, via the
     * Iterator.remove, Set.remove, removeAll, retainAll, and clear
     * operations.  It does not support the add or addAll operations.
     *
     * @return a set view of the keys contained in this map.
     */
    public Set keySet() {

        if (setOfKeys[KEY] == null) {
            setOfKeys[KEY] = new AbstractSet() {

                public Iterator iterator() {

                    return new DoubleOrderedMapIterator(KEY) {

                        protected Object doGetNext() {
                            return lastReturnedNode.getData(KEY);
                        }
                    };
                }

                public int size() {
                    return DoubleOrderedMap.this.size();
                }

                public boolean contains(Object o) {
                    return containsKey(o);
                }

                public boolean remove(Object o) {

                    int oldNodeCount = nodeCount;

                    DoubleOrderedMap.this.remove(o);

                    return nodeCount != oldNodeCount;
                }

                public void clear() {
                    DoubleOrderedMap.this.clear();
                }
            };
        }

        return setOfKeys[KEY];
    }

    /**
     * Returns a collection view of the values contained in this
     * map. The collection is backed by the map, so changes to the map
     * are reflected in the collection, and vice-versa. If the map is
     * modified while an iteration over the collection is in progress,
     * the results of the iteration are undefined. The collection
     * supports element removal, which removes the corresponding
     * mapping from the map, via the Iterator.remove,
     * Collection.remove, removeAll, retainAll and clear operations.
     * It does not support the add or addAll operations.
     *
     * @return a collection view of the values contained in this map.
     */
    public Collection values() {

        if (collectionOfValues[KEY] == null) {
            collectionOfValues[KEY] = new AbstractCollection() {

                public Iterator iterator() {

                    return new DoubleOrderedMapIterator(KEY) {

                        protected Object doGetNext() {
                            return lastReturnedNode.getData(VALUE);
                        }
                    };
                }

                public int size() {
                    return DoubleOrderedMap.this.size();
                }

                public boolean contains(Object o) {
                    return containsValue(o);
                }

                public boolean remove(Object o) {

                    int oldNodeCount = nodeCount;

                    removeValue(o);

                    return nodeCount != oldNodeCount;
                }

                public boolean removeAll(Collection c) {

                    boolean  modified = false;
                    Iterator iter     = c.iterator();

                    while (iter.hasNext()) {
                        if (removeValue(iter.next()) != null) {
                            modified = true;
                        }
                    }

                    return modified;
                }

                public void clear() {
                    DoubleOrderedMap.this.clear();
                }
            };
        }

        return collectionOfValues[KEY];
    }

    /**
     * Returns a set view of the mappings contained in this map. Each
     * element in the returned set is a Map.Entry. The set is backed
     * by the map, so changes to the map are reflected in the set, and
     * vice-versa.  If the map is modified while an iteration over the
     * set is in progress, the results of the iteration are
     * undefined. The set supports element removal, which removes the
     * corresponding mapping from the map, via the Iterator.remove,
     * Set.remove, removeAll, retainAll and clear operations.  It does
     * not support the add or addAll operations.
     *
     * @return a set view of the mappings contained in this map.
     */
    public Set entrySet() {

        if (setOfEntries[KEY] == null) {
            setOfEntries[KEY] = new AbstractSet() {

                public Iterator iterator() {

                    return new DoubleOrderedMapIterator(KEY) {

                        protected Object doGetNext() {
                            return lastReturnedNode;
                        }
                    };
                }

                public boolean contains(Object o) {

                    if (!(o instanceof Map.Entry)) {
                        return false;
                    }

                    Map.Entry entry = (Map.Entry) o;
                    Object    value = entry.getValue();
                    Node      node  = lookup((Comparable) entry.getKey(),
                                             KEY);

                    return (node != null)
                           && node.getData(VALUE).equals(value);
                }

                public boolean remove(Object o) {

                    if (!(o instanceof Map.Entry)) {
                        return false;
                    }

                    Map.Entry entry = (Map.Entry) o;
                    Object    value = entry.getValue();
                    Node      node  = lookup((Comparable) entry.getKey(),
                                             KEY);

                    if ((node != null) && node.getData(VALUE).equals(value)) 
{
                        doRedBlackDelete(node);

                        return true;
                    }

                    return false;
                }

                public int size() {
                    return DoubleOrderedMap.this.size();
                }

                public void clear() {
                    DoubleOrderedMap.this.clear();
                }
            };
        }

        return setOfEntries[KEY];
    }

    /* **********  END  implementation of Map ********** */
    private abstract class DoubleOrderedMapIterator implements Iterator {

        private int    expectedModifications;
        protected Node lastReturnedNode;
        private Node   nextNode;
        private int    iteratorType;

        /**
         * Constructor
         *
         * @param type
         */
        DoubleOrderedMapIterator(final int type) {

            iteratorType          = type;
            expectedModifications = DoubleOrderedMap.this.modifications;
            lastReturnedNode      = null;
            nextNode              = leastNode(rootNode[iteratorType],
                                              iteratorType);
        }

        /**
         * @return 'next', whatever that means for a given kind of
         *         DoubleOrderedMapIterator
         */
        protected abstract Object doGetNext();

        /* ********** START implementation of Iterator ********** */

        /**
         * @return true if the iterator has more elements.
         */
        public final boolean hasNext() {
            return nextNode != null;
        }

        /**
         * @return the next element in the iteration.
         *
         * @exception NoSuchElementException if iteration has no more
         *                                   elements.
         * @exception ConcurrentModificationException if the
         *                                            DoubleOrderedMap is
         *                                            modified behind
         *                                            the iterator's
         *                                            back
         */
        public final Object next()
                throws NoSuchElementException,
                       ConcurrentModificationException {

            if (nextNode == null) {
                throw new NoSuchElementException();
            }

            if (modifications != expectedModifications) {
                throw new ConcurrentModificationException();
            }

            lastReturnedNode = nextNode;
            nextNode         = nextGreater(nextNode, iteratorType);

            return doGetNext();
        }

        /**
         * Removes from the underlying collection the last element
         * returned by the iterator. This method can be called only
         * once per call to next. The behavior of an iterator is
         * unspecified if the underlying collection is modified while
         * the iteration is in progress in any way other than by
         * calling this method.
         *
         * @exception IllegalStateException if the next method has not
         *                                  yet been called, or the
         *                                  remove method has already
         *                                  been called after the last
         *                                  call to the next method.
         * @exception ConcurrentModificationException if the
         *                                            DoubleOrderedMap is
         *                                            modified behind
         *                                            the iterator's
         *                                            back
         */
        public final void remove()
                throws IllegalStateException,
                       ConcurrentModificationException {

            if (lastReturnedNode == null) {
                throw new IllegalStateException();
            }

            if (modifications != expectedModifications) {
                throw new ConcurrentModificationException();
            }

            doRedBlackDelete(lastReturnedNode);

            expectedModifications++;

            lastReturnedNode = null;
        }

        /* **********  END  implementation of Iterator ********** */
    }    // end private abstract class DoubleOrderedMapIterator

    // final for performance
    private static final class Node implements Map.Entry {

        private Comparable[] data;
        private Node[]       leftNode;
        private Node[]       rightNode;
        private Node[]       parentNode;
        private boolean[]    blackColor;
        private int          hashcodeValue;
        private boolean      calculatedHashCode;

        /**
         * Make a new cell with given key and value, and with null
         * links, and black (true) colors.
         *
         * @param key
         * @param value
         */
        Node(final Comparable key, final Comparable value) {

            data               = new Comparable[]{ key, value };
            leftNode           = new Node[]{ null, null };
            rightNode          = new Node[]{ null, null };
            parentNode         = new Node[]{ null, null };
            blackColor         = new boolean[]{ true, true };
            calculatedHashCode = false;
        }

        /**
         * get the specified data
         *
         * @param index KEY or VALUE
         *
         * @return the key or value
         */
        private Comparable getData(final int index) {
            return data[index];
        }

        /**
         * Set this node's left node
         *
         * @param node the new left node
         * @param index KEY or VALUE
         */
        private void setLeft(final Node node, final int index) {
            leftNode[index] = node;
        }

        /**
         * get the left node
         *
         * @param index KEY or VALUE
         *
         * @return the left node -- may be null
         */
        private Node getLeft(final int index) {
            return leftNode[index];
        }

        /**
         * Set this node's right node
         *
         * @param node the new right node
         * @param index KEY or VALUE
         */
        private void setRight(final Node node, final int index) {
            rightNode[index] = node;
        }

        /**
         * get the right node
         *
         * @param index KEY or VALUE
         *
         * @return the right node -- may be null
         */
        private Node getRight(final int index) {
            return rightNode[index];
        }

        /**
         * Set this node's parent node
         *
         * @param node the new parent node
         * @param index KEY or VALUE
         */
        private void setParent(final Node node, final int index) {
            parentNode[index] = node;
        }

        /**
         * get the parent node
         *
         * @param index KEY or VALUE
         *
         * @return the parent node -- may be null
         */
        private Node getParent(final int index) {
            return parentNode[index];
        }

        /**
         * exchange colors with another node
         *
         * @param node the node to swap with
         * @param index KEY or VALUE
         */
        private void swapColors(final Node node, final int index) {

            // Swap colors -- old hacker's trick
            blackColor[index]      ^= node.blackColor[index];
            node.blackColor[index] ^= blackColor[index];
            blackColor[index]      ^= node.blackColor[index];
        }

        /**
         * is this node black?
         *
         * @param index KEY or VALUE
         *
         * @return true if black (which is represented as a true boolean)
         */
        private boolean isBlack(final int index) {
            return blackColor[index];
        }

        /**
         * is this node red?
         *
         * @param index KEY or VALUE
         *
         * @return true if non-black
         */
        private boolean isRed(final int index) {
            return !blackColor[index];
        }

        /**
         * make this node black
         *
         * @param index KEY or VALUE
         */
        private void setBlack(final int index) {
            blackColor[index] = true;
        }

        /**
         * make this node red
         *
         * @param index KEY or VALUE
         */
        private void setRed(final int index) {
            blackColor[index] = false;
        }

        /**
         * make this node the same color as another
         *
         * @param node the node whose color we're adopting
         * @param index KEY or VALUE
         */
        private void copyColor(final Node node, final int index) {
            blackColor[index] = node.blackColor[index];
        }

        /* ********** START implementation of Map.Entry ********** */

        /**
         * @return the key corresponding to this entry.
         */
        public Object getKey() {
            return data[KEY];
        }

        /**
         * @return the value corresponding to this entry.
         */
        public Object getValue() {
            return data[VALUE];
        }

        /**
         * Optional operation that is not permitted in this
         * implementation
         *
         * @param ignored
         *
         * @return does not return
         *
         * @exception UnsupportedOperationException
         */
        public Object setValue(Object ignored)
                throws UnsupportedOperationException {
            throw new UnsupportedOperationException(
                "Map.Entry.setValue is not supported");
        }

        /**
         * Compares the specified object with this entry for equality.
         * Returns true if the given object is also a map entry and
         * the two entries represent the same mapping.
         *
         * @param o object to be compared for equality with this map
         *          entry.
         * @return true if the specified object is equal to this map
         *         entry.
         */
        public boolean equals(Object o) {

            if (this == o) {
                return true;
            }

            if (!(o instanceof Map.Entry)) {
                return false;
            }

            Map.Entry e = (Map.Entry) o;

            return data[KEY].equals(e.getKey())
                   && data[VALUE].equals(e.getValue());
        }

        /**
         * @return the hash code value for this map entry.
         */
        public int hashCode() {

            if (!calculatedHashCode) {
                hashcodeValue      = data[KEY].hashCode()
                                     ^ data[VALUE].hashCode();
                calculatedHashCode = true;
            }

            return hashcodeValue;
        }

        /* **********  END  implementation of Map.Entry ********** */
    }
}    // end public class DoubleOrderedMap