/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.openjpa.lib.util.collections;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.AbstractSet;
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 BidiMap where all objects added
 * implement the <code>Comparable</code> interface.
 * <p>
 * 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>
 * <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>
 * <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.
 * If the data contained in the TreeMaps is large, the cost of redundant
 * storage becomes significant. The {@link DualTreeBidiMap} and
 * {@link DualHashBidiMap} implementations use this approach.
 * </p>
 * <p>
 * This solution keeps minimizes the data storage by holding data only once.
 * The red-black algorithm is based on {@link java.util.TreeMap}, 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>
 * <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>
 *
 * @param <K> the type of the keys in this map
 * @param <V> the type of the values in this map
 *
 * @since 3.0 (previously DoubleOrderedMap v2.0)
 */
public class TreeBidiMap<K extends Comparable<K>, V extends Comparable<V>>
    implements OrderedBidiMap<K, V>, Serializable {

    enum DataElement {
        KEY("key"), VALUE("value");

        private final String description;

        /**
         * Create a new TreeBidiMap.DataElement.
         *
         * @param description  the description for the element
         */
        DataElement(final String description) {
            this.description = description;
        }

        @Override
        public String toString() {
            return description;
        }
    }

    private static final long serialVersionUID = 721969328361807L;

    private transient Node<K, V>[] rootNode;
    private transient int nodeCount = 0;
    private transient int modifications = 0;
    private transient Set<K> keySet;
    private transient Set<V> valuesSet;
    private transient Set<Entry<K, V>> entrySet;
    private transient Inverse inverse = null;

    //-----------------------------------------------------------------------
    /**
     * Constructs a new empty TreeBidiMap.
     */
    @SuppressWarnings("unchecked")
    public TreeBidiMap() {
        super();
        rootNode = new Node[2];
    }

    /**
     * Constructs a new TreeBidiMap by copying an existing Map.
     *
     * @param map  the map to copy
     * @throws ClassCastException if the keys/values in the map are
     *  not Comparable or are not mutually comparable
     * @throws NullPointerException if any key or value in the map is null
     */
    public TreeBidiMap(final Map<? extends K, ? extends V> map) {
        this();
        putAll(map);
    }

    //-----------------------------------------------------------------------
    /**
     * Returns the number of key-value mappings in this map.
     *
     * @return the number of key-value mappings in this map
     */
    @Override
    public int size() {
        return nodeCount;
    }

    /**
     * Checks whether the map is empty or not.
     *
     * @return true if the map is empty
     */
    @Override
    public boolean isEmpty() {
        return nodeCount == 0;
    }

    /**
     * Checks whether this map contains the a mapping for the specified key.
     * <p>
     * The key must implement <code>Comparable</code>.
     *
     * @param key  key whose presence in this map is to be tested
     * @return true if this map contains a mapping for the specified key
     * @throws ClassCastException if the key is of an inappropriate type
     * @throws NullPointerException if the key is null
     */
    @Override
    public boolean containsKey(final Object key) {
        checkKey(key);
        return lookupKey(key) != null;
    }

    /**
     * Checks whether this map contains the a mapping for the specified value.
     * <p>
     * The value must implement <code>Comparable</code>.
     *
     * @param value  value whose presence in this map is to be tested
     * @return true if this map contains a mapping for the specified value
     * @throws ClassCastException if the value is of an inappropriate type
     * @throws NullPointerException if the value is null
     */
    @Override
    public boolean containsValue(final Object value) {
        checkValue(value);
        return lookupValue(value) != null;
    }

    /**
     * Gets the value to which this map maps the specified key.
     * Returns null if the map contains no mapping for this key.
     * <p>
     * The key must implement <code>Comparable</code>.
     *
     * @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
     * @throws ClassCastException if the key is of an inappropriate type
     * @throws NullPointerException if the key is null
     */
    @Override
    public V get(final Object key) {
        checkKey(key);
        final Node<K, V> node = lookupKey(key);
        return node == null ? null : node.getValue();
    }

    /**
     * Puts the key-value pair into the map, replacing any previous pair.
     * <p>
     * When adding a key-value pair, the value may already exist in the map
     * against a different key. That mapping is removed, to ensure that the
     * value only occurs once in the inverse map.
     * <pre>
     *  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
     * </pre>
     * <p>
     * Both key and value must implement <code>Comparable</code>.
     *
     * @param key  key with which the specified value is to be  associated
     * @param value  value to be associated with the specified key
     * @return the previous value for the key
     * @throws ClassCastException if the key is of an inappropriate type
     * @throws NullPointerException if the key is null
     */
    @Override
    public V put(final K key, final V value) {
        final 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
     */
    @Override
    public void putAll(final Map<? extends K, ? extends V> map) {
        for (final 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>
     * The key must implement <code>Comparable</code>.
     *
     * @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.
     * @throws ClassCastException if the key is of an inappropriate type
     * @throws NullPointerException if the key is null
     */
    @Override
    public V remove(final Object key) {
        return doRemoveKey(key);
    }

    /**
     * Removes all mappings from this map.
     */
    @Override
    public void clear() {
        modify();

        nodeCount = 0;
        rootNode[DataElement.KEY.ordinal()] = null;
        rootNode[DataElement.VALUE.ordinal()] = null;
    }

    //-----------------------------------------------------------------------
    /**
     * Returns the key to which this map maps the specified value.
     * Returns null if the map contains no mapping for this value.
     * <p>
     * The value must implement <code>Comparable</code>.
     *
     * @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.
     * @throws ClassCastException if the value is of an inappropriate type
     * @throws NullPointerException if the value is null
     */
    @Override
    public K getKey(final Object value) {
        checkValue(value);
        final Node<K, V> node = lookupValue(value);
        return node == null ? null : node.getKey();
    }

    /**
     * Removes the mapping for this value from this map if present.
     * <p>
     * The value must implement <code>Comparable</code>.
     *
     * @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.
     * @throws ClassCastException if the value is of an inappropriate type
     * @throws NullPointerException if the value is null
     */
    @Override
    public K removeValue(final Object value) {
        return doRemoveValue(value);
    }

    //-----------------------------------------------------------------------
    /**
     * Gets the first (lowest) key currently in this map.
     *
     * @return the first (lowest) key currently in this sorted map
     * @throws NoSuchElementException if this map is empty
     */
    @Override
    public K firstKey() {
        if (nodeCount == 0) {
            throw new NoSuchElementException("Map is empty");
        }
        return leastNode(rootNode[DataElement.KEY.ordinal()], DataElement.KEY).getKey();
    }

    /**
     * Gets the last (highest) key currently in this map.
     *
     * @return the last (highest) key currently in this sorted map
     * @throws NoSuchElementException if this map is empty
     */
    @Override
    public K lastKey() {
        if (nodeCount == 0) {
            throw new NoSuchElementException("Map is empty");
        }
        return greatestNode(rootNode[DataElement.KEY.ordinal()], DataElement.KEY).getKey();
    }

    /**
     * Gets the next key after the one specified.
     * <p>
     * The key must implement <code>Comparable</code>.
     *
     * @param key the key to search for next from
     * @return the next key, null if no match or at end
     */
    @Override
    public K nextKey(final K key) {
        checkKey(key);
        final Node<K, V> node = nextGreater(lookupKey(key), DataElement.KEY);
        return node == null ? null : node.getKey();
    }

    /**
     * Gets the previous key before the one specified.
     * <p>
     * The key must implement <code>Comparable</code>.
     *
     * @param key the key to search for previous from
     * @return the previous key, null if no match or at start
     */
    @Override
    public K previousKey(final K key) {
        checkKey(key);
        final Node<K, V> node = nextSmaller(lookupKey(key), DataElement.KEY);
        return node == null ? null : node.getKey();
    }

    //-----------------------------------------------------------------------
    /**
     * Returns a set view of the keys contained in this map in key order.
     * <p>
     * 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.
     * <p>
     * The set supports element removal, which removes the corresponding mapping
     * from the map. It does not support the add or addAll operations.
     *
     * @return a set view of the keys contained in this map.
     */
    @Override
    public Set<K> keySet() {
        if (keySet == null) {
            keySet = new KeyView(DataElement.KEY);
        }
        return keySet;
    }

    //-----------------------------------------------------------------------
    /**
     * Returns a set view of the values contained in this map in key order.
     * The returned object can be cast to a Set.
     * <p>
     * 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.
     * <p>
     * The set supports element removal, which removes the corresponding mapping
     * from the map. It does not support the add or addAll operations.
     *
     * @return a set view of the values contained in this map.
     */
    @Override
    public Set<V> values() {
        if (valuesSet == null) {
            valuesSet = new ValueView(DataElement.KEY);
        }
        return valuesSet;
    }

    //-----------------------------------------------------------------------
    /**
     * Returns a set view of the entries contained in this map in key order.
     * For simple iteration through the map, the MapIterator is quicker.
     * <p>
     * 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.
     * <p>
     * The set supports element removal, which removes the corresponding mapping
     * from the map. It does not support the add or addAll operations.
     * The returned MapEntry objects do not support setValue.
     *
     * @return a set view of the values contained in this map.
     */
    @Override
    public Set<Entry<K, V>> entrySet() {
        if (entrySet == null) {
            entrySet = new EntryView();
        }
        return entrySet;
    }

    //-----------------------------------------------------------------------
    @Override
    public OrderedMapIterator<K, V> mapIterator() {
        if (isEmpty()) {
            return EmptyOrderedMapIterator.<K, V>emptyOrderedMapIterator();
        }
        return new ViewMapIterator(DataElement.KEY);
    }

    //-----------------------------------------------------------------------
    /**
     * Gets the inverse map for comparison.
     *
     * @return the inverse map
     */
    @Override
    public OrderedBidiMap<V, K> inverseBidiMap() {
        if (inverse == null) {
            inverse = new Inverse();
        }
        return inverse;
    }

    //-----------------------------------------------------------------------
    /**
     * Compares for equals as per the API.
     *
     * @param obj  the object to compare to
     * @return true if equal
     */
    @Override
    public boolean equals(final Object obj) {
        return this.doEquals(obj, DataElement.KEY);
    }

    /**
     * Gets the hash code value for this map as per the API.
     *
     * @return the hash code value for this map
     */
    @Override
    public int hashCode() {
        return this.doHashCode(DataElement.KEY);
    }

    /**
     * Returns a string version of this Map in standard format.
     *
     * @return a standard format string version of the map
     */
    @Override
    public String toString() {
        return this.doToString(DataElement.KEY);
    }

    //-----------------------------------------------------------------------
    /**
     * Put logic.
     *
     * @param key  the key, always the main map key
     * @param value  the value, always the main map value
     */
    private void doPut(final K key, final V value) {
        checkKeyAndValue(key, value);

        // store previous and remove previous mappings
        doRemoveKey(key);
        doRemoveValue(value);

        Node<K, V> node = rootNode[DataElement.KEY.ordinal()];
        if (node == null) {
            // map is empty
            final Node<K, V> root = new Node<>(key, value);
            rootNode[DataElement.KEY.ordinal()] = root;
            rootNode[DataElement.VALUE.ordinal()] = root;
            grow();

        } else {
            // add new mapping
            while (true) {
                final int cmp = compare(key, node.getKey());

                if (cmp == 0) {
                    // shouldn't happen
                    throw new IllegalArgumentException("Cannot store a duplicate key (\"" + key + "\") in this Map");
                } else if (cmp < 0) {
                    if (node.getLeft(DataElement.KEY) != null) {
                        node = node.getLeft(DataElement.KEY);
                    } else {
                        final Node<K, V> newNode = new Node<>(key, value);

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

                        break;
                    }
                } else { // cmp > 0
                    if (node.getRight(DataElement.KEY) != null) {
                        node = node.getRight(DataElement.KEY);
                    } else {
                        final Node<K, V> newNode = new Node<>(key, value);

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

                        break;
                    }
                }
            }
        }
    }

    private V doRemoveKey(final Object key) {
        final Node<K, V> node = lookupKey(key);
        if (node == null) {
            return null;
        }
        doRedBlackDelete(node);
        return node.getValue();
    }

    private K doRemoveValue(final Object value) {
        final Node<K, V> node = lookupValue(value);
        if (node == null) {
            return null;
        }
        doRedBlackDelete(node);
        return node.getKey();
    }

    /**
     * do the actual lookup of a piece of data
     *
     * @param data the key or value to be looked up
     * @param dataElement  either {@link DataElement#KEY} key}
     *                     or the {@link DataElement#VALUE value}.
     * @return the desired Node, or null if there is no mapping of the
     *         specified data
     */
    @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) {
            final int cmp = compare((T) data, (T) node.getData(dataElement));
            if (cmp == 0) {
                rval = node;
                break;
            }
            node = cmp < 0 ? node.getLeft(dataElement) : node.getRight(dataElement);
        }

        return rval;
    }

    private Node<K, V> lookupKey(final Object key) {
        return this.<K>lookup(key, DataElement.KEY);
    }

    private Node<K, V> lookupValue(final Object value) {
        return this.<V>lookup(value, DataElement.VALUE);
    }

    /**
     * get the next larger node from the specified node
     *
     * @param node the node to be searched from
     * @param dataElement  either {@link DataElement#KEY} key}
     *                     or the {@link DataElement#VALUE value}.
     * @return the specified node
     */
    private Node<K, V> nextGreater(final Node<K, V> node, final DataElement dataElement) {
        Node<K, V> rval;
        if (node == null) {
            rval = 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(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
            // 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<K, V> parent = node.getParent(dataElement);
            Node<K, V> child = node;

            while (parent != null && child == parent.getRight(dataElement)) {
                child = parent;
                parent = parent.getParent(dataElement);
            }
            rval = parent;
        }
        return rval;
    }

    /**
     * get the next larger node from the specified node
     *
     * @param node the node to be searched from
     * @param dataElement  either {@link DataElement#KEY} key}
     *                     or the {@link DataElement#VALUE value}.
     * @return the specified node
     */
    private Node<K, V> nextSmaller(final Node<K, V> node, final DataElement dataElement) {
        Node<K, V> rval;
        if (node == null) {
            rval = 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(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
            // 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 right
            // ... and that ancestor is the next greatest node
            Node<K, V> parent = node.getParent(dataElement);
            Node<K, V> child = node;

            while (parent != null && child == parent.getLeft(dataElement)) {
                child = parent;
                parent = parent.getParent(dataElement);
            }
            rval = parent;
        }
        return rval;
    }

    //-----------------------------------------------------------------------

    /**
     * Compare two objects
     *
     * @param o1  the first object
     * @param o2  the second object
     *
     * @return negative value if o1 &lt; o2; 0 if o1 == o2; positive
     *         value if o1 &gt; o2
     */
    private static <T extends Comparable<T>> int compare(final T o1, final T o2) {
        return o1.compareTo(o2);
    }

    /**
     * Find the least node from a given node.
     *
     * @param node  the node from which we will start searching
     * @param dataElement  either {@link DataElement#KEY} key}
     *                     or the {@link DataElement#VALUE value}.
     * @return the smallest node, from the specified node, in the
     *         specified mapping
     */
    private Node<K, V> leastNode(final Node<K, V> node, final DataElement dataElement) {
        Node<K, V> rval = node;
        if (rval != null) {
            while (rval.getLeft(dataElement) != null) {
                rval = rval.getLeft(dataElement);
            }
        }
        return rval;
    }

    /**
     * Find the greatest node from a given node.
     *
     * @param node  the node from which we will start searching
     * @param dataElement  either {@link DataElement#KEY} key}
     *                     or the {@link DataElement#VALUE value}.
     * @return the greatest node, from the specified 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(dataElement) != null) {
                rval = rval.getRight(dataElement);
            }
        }
        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 dataElement  either {@link DataElement#KEY} key}
     *                     or the {@link DataElement#VALUE value}.
     */
    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(dataElement);
            } else {
                to.copyColor(from, dataElement);
            }
        }
    }

    /**
     * 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 dataElement  either {@link DataElement#KEY} key}
     *                     or the {@link DataElement#VALUE value}.
     */
    private static boolean isRed(final Node<?, ?> node, final DataElement dataElement) {
        return node != null && node.isRed(dataElement);
    }

    /**
     * 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 dataElement  either {@link DataElement#KEY} key}
     *                     or the {@link DataElement#VALUE value}.
     */
    private static boolean isBlack(final Node<?, ?> node, final DataElement dataElement) {
        return node == null || node.isBlack(dataElement);
    }

    /**
     * force a node (if it exists) red
     *
     * @param node the node (may be null) in question
     * @param dataElement  either {@link DataElement#KEY} key}
     *                     or the {@link DataElement#VALUE value}.
     */
    private static void makeRed(final Node<?, ?> node, final DataElement dataElement) {
        if (node != null) {
            node.setRed(dataElement);
        }
    }

    /**
     * force a node (if it exists) black
     *
     * @param node the node (may be null) in question
     * @param dataElement  either {@link DataElement#KEY} key}
     *                     or the {@link DataElement#VALUE value}.
     */
    private static void makeBlack(final Node<?, ?> node, final DataElement dataElement) {
        if (node != null) {
            node.setBlack(dataElement);
        }
    }

    /**
     * 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 dataElement  either {@link DataElement#KEY} key}
     *                     or the {@link DataElement#VALUE value}.
     */
    private Node<K, V> getGrandParent(final Node<K, V> node, final DataElement dataElement) {
        return getParent(getParent(node, dataElement), dataElement);
    }

    /**
     * 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 dataElement  either {@link DataElement#KEY} key}
     *                     or the {@link DataElement#VALUE value}.
     */
    private Node<K, V> getParent(final Node<K, V> node, final DataElement dataElement) {
        return node == null ? null : node.getParent(dataElement);
    }

    /**
     * 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 dataElement  either {@link DataElement#KEY} key}
     *                     or the {@link DataElement#VALUE value}.
     */
    private Node<K, V> getRightChild(final Node<K, V> node, final DataElement dataElement) {
        return node == null ? null : node.getRight(dataElement);
    }

    /**
     * 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 dataElement  either {@link DataElement#KEY} key}
     *                     or the {@link DataElement#VALUE value}.
     */
    private Node<K, V> getLeftChild(final Node<K, V> node, final DataElement dataElement) {
        return node == null ? null : node.getLeft(dataElement);
    }

    /**
     * do a rotate left. standard fare in the world of balanced trees
     *
     * @param node the node to be rotated
     * @param dataElement  either {@link DataElement#KEY} key}
     *                     or the {@link DataElement#VALUE value}.
     */
    private void rotateLeft(final Node<K, V> node, final DataElement dataElement) {
        final Node<K, V> rightChild = node.getRight(dataElement);
        node.setRight(rightChild.getLeft(dataElement), dataElement);

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

        if (node.getParent(dataElement) == null) {
            // node was the root ... now its right child is the root
            rootNode[dataElement.ordinal()] = rightChild;
        } else if (node.getParent(dataElement).getLeft(dataElement) == node) {
            node.getParent(dataElement).setLeft(rightChild, dataElement);
        } else {
            node.getParent(dataElement).setRight(rightChild, dataElement);
        }

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

    /**
     * do a rotate right. standard fare in the world of balanced trees
     *
     * @param node the node to be rotated
     * @param dataElement  either {@link DataElement#KEY} key}
     *                     or the {@link DataElement#VALUE value}.
     */
    private void rotateRight(final Node<K, V> node, final DataElement dataElement) {
        final 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(dataElement), dataElement);

        if (node.getParent(dataElement) == null) {
            // node was the root ... now its left child is the root
            rootNode[dataElement.ordinal()] = leftChild;
        } else if (node.getParent(dataElement).getRight(dataElement) == node) {
            node.getParent(dataElement).setRight(leftChild, dataElement);
        } else {
            node.getParent(dataElement).setLeft(leftChild, dataElement);
        }

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

    /**
     * complicated red-black insert stuff. Based on Sun's TreeMap
     * implementation, though it's barely recognizable any more
     *
     * @param insertedNode the node to be inserted
