    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one or more
    003 * contributor license agreements.  See the NOTICE file distributed with
    004 * this work for additional information regarding copyright ownership.
    005 * The ASF licenses this file to You under the Apache License, Version 2.0
    006 * (the "License"); you may not use this file except in compliance with
    007 * the License.  You may obtain a copy of the License at
    008 *
    009 *      http://www.apache.org/licenses/LICENSE-2.0
    010 *
    011 * Unless required by applicable law or agreed to in writing, software
    012 * distributed under the License is distributed on an "AS IS" BASIS,
    013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014 * See the License for the specific language governing permissions and
    015 * limitations under the License.
    016 */
    017package org.apache.commons.collections4.bidimap;
    018
    019import static org.apache.commons.collections4.bidimap.TreeBidiMap.DataElement.KEY;
    020import static org.apache.commons.collections4.bidimap.TreeBidiMap.DataElement.VALUE;
    021
    022import java.io.IOException;
    023import java.io.ObjectInputStream;
    024import java.io.ObjectOutputStream;
    025import java.io.Serializable;
    026import java.util.AbstractSet;
    027import java.util.ConcurrentModificationException;
    028import java.util.Iterator;
    029import java.util.Map;
    030import java.util.NoSuchElementException;
    031import java.util.Set;
    032
    033import org.apache.commons.collections4.KeyValue;
    034import org.apache.commons.collections4.MapIterator;
    035import org.apache.commons.collections4.OrderedBidiMap;
    036import org.apache.commons.collections4.OrderedIterator;
    037import org.apache.commons.collections4.OrderedMapIterator;
    038import org.apache.commons.collections4.iterators.EmptyOrderedMapIterator;
    039import org.apache.commons.collections4.keyvalue.UnmodifiableMapEntry;
    040
    041/**
    042 * Red-Black tree-based implementation of BidiMap where all objects added
    043 * implement the <code>Comparable</code> interface.
    044 * <p>
    045 * This class guarantees that the map will be in both ascending key order
    046 * and ascending value order, sorted according to the natural order for
    047 * the key's and value's classes.
    048 * <p>
    049 * This Map is intended for applications that need to be able to look
    050 * up a key-value pairing by either key or value, and need to do so
    051 * with equal efficiency.
    052 * <p>
    053 * While that goal could be accomplished by taking a pair of TreeMaps
    054 * and redirecting requests to the appropriate TreeMap (e.g.,
    055 * containsKey would be directed to the TreeMap that maps values to
    056 * keys, containsValue would be directed to the TreeMap that maps keys
    057 * to values), there are problems with that implementation.
    058 * If the data contained in the TreeMaps is large, the cost of redundant
    059 * storage becomes significant. The {@link DualTreeBidiMap} and
    060 * {@link DualHashBidiMap} implementations use this approach.
    061 * <p>
    062 * This solution keeps minimizes the data storage by holding data only once.
    063 * The red-black algorithm is based on {@link java.util.TreeMap}, but has been modified
    064 * to simultaneously map a tree node by key and by value. This doubles the
    065 * cost of put operations (but so does using two TreeMaps), and nearly doubles
    066 * the cost of remove operations (there is a savings in that the lookup of the
    067 * node to be removed only has to be performed once). And since only one node
    068 * contains the key and value, storage is significantly less than that
    069 * required by two TreeMaps.
    070 * <p>
    071 * The Map.Entry instances returned by the appropriate methods will
    072 * not allow setValue() and will throw an
    073 * UnsupportedOperationException on attempts to call that method.
    074 *
    075 * @param <K> the type of the keys in this map
    076 * @param <V> the type of the values in this map
    077 *
    078 * @since 3.0 (previously DoubleOrderedMap v2.0)
    079 */
    080public class TreeBidiMap<K extends Comparable<K>, V extends Comparable<V>>
    081    implements OrderedBidiMap<K, V>, Serializable {
    082
    083    enum DataElement {
    084        KEY("key"), VALUE("value");
    085
    086        private final String description;
    087
    088        /**
    089         * Create a new TreeBidiMap.DataElement.
    090         *
    091         * @param description  the description for the element
    092         */
    093        private DataElement(final String description) {
    094            this.description = description;
    095        }
    096
    097        @Override
    098        public String toString() {
    099            return description;
    100        }
    101    }
    102
    103    private static final long serialVersionUID = 721969328361807L;
    104
    105    private transient Node<K, V>[] rootNode;
    106    private transient int nodeCount = 0;
    107    private transient int modifications = 0;
    108    private transient Set<K> keySet;
    109    private transient Set<V> valuesSet;
    110    private transient Set<Map.Entry<K, V>> entrySet;
    111    private transient Inverse inverse = null;
    112
    113    //-----------------------------------------------------------------------
    114    /**
    115     * Constructs a new empty TreeBidiMap.
    116     */
    117    @SuppressWarnings("unchecked")
    118    public TreeBidiMap() {
    119        super();
    120        rootNode = new Node[2];
    121    }
    122
    123    /**
    124     * Constructs a new TreeBidiMap by copying an existing Map.
    125     *
    126     * @param map  the map to copy
    127     * @throws ClassCastException if the keys/values in the map are
    128     *  not Comparable or are not mutually comparable
    129     * @throws NullPointerException if any key or value in the map is null
    130     */
    131    public TreeBidiMap(final Map<? extends K, ? extends V> map) {
    132        this();
    133        putAll(map);
    134    }
    135
    136    //-----------------------------------------------------------------------
    137    /**
    138     * Returns the number of key-value mappings in this map.
    139     *
    140     * @return the number of key-value mappings in this map
    141     */
    142    @Override
    143    public int size() {
    144        return nodeCount;
    145    }
    146
    147    /**
    148     * Checks whether the map is empty or not.
    149     *
    150     * @return true if the map is empty
    151     */
    152    @Override
    153    public boolean isEmpty() {
    154        return nodeCount == 0;
    155    }
    156
    157    /**
    158     * Checks whether this map contains the a mapping for the specified key.
    159     * <p>
    160     * The key must implement <code>Comparable</code>.
    161     *
    162     * @param key  key whose presence in this map is to be tested
    163     * @return true if this map contains a mapping for the specified key
    164     * @throws ClassCastException if the key is of an inappropriate type
    165     * @throws NullPointerException if the key is null
    166     */
    167    @Override
    168    public boolean containsKey(final Object key) {
    169        checkKey(key);
    170        return lookupKey(key) != null;
    171    }
    172
    173    /**
    174     * Checks whether this map contains the a mapping for the specified value.
    175     * <p>
    176     * The value must implement <code>Comparable</code>.
    177     *
    178     * @param value  value whose presence in this map is to be tested
    179     * @return true if this map contains a mapping for the specified value
    180     * @throws ClassCastException if the value is of an inappropriate type
    181     * @throws NullPointerException if the value is null
    182     */
    183    @Override
    184    public boolean containsValue(final Object value) {
    185        checkValue(value);
    186        return lookupValue(value) != null;
    187    }
    188
    189    /**
    190     * Gets the value to which this map maps the specified key.
    191     * Returns null if the map contains no mapping for this key.
    192     * <p>
    193     * The key must implement <code>Comparable</code>.
    194     *
    195     * @param key  key whose associated value is to be returned
    196     * @return the value to which this map maps the specified key,
    197     *  or null if the map contains no mapping for this key
    198     * @throws ClassCastException if the key is of an inappropriate type
    199     * @throws NullPointerException if the key is null
    200     */
    201    @Override
    202    public V get(final Object key) {
    203        checkKey(key);
    204        final Node<K, V> node = lookupKey(key);
    205        return node == null ? null : node.getValue();
    206    }
    207
    208    /**
    209     * Puts the key-value pair into the map, replacing any previous pair.
    210     * <p>
    211     * When adding a key-value pair, the value may already exist in the map
    212     * against a different key. That mapping is removed, to ensure that the
    213     * value only occurs once in the inverse map.
    214     * <pre>
    215     *  BidiMap map1 = new TreeBidiMap();
    216     *  map.put("A","B");  // contains A mapped to B, as per Map
    217     *  map.put("A","C");  // contains A mapped to C, as per Map
    218     *
    219     *  BidiMap map2 = new TreeBidiMap();
    220     *  map.put("A","B");  // contains A mapped to B, as per Map
    221     *  map.put("C","B");  // contains C mapped to B, key A is removed
    222     * </pre>
    223     * <p>
    224     * Both key and value must implement <code>Comparable</code>.
    225     *
    226     * @param key  key with which the specified value is to be  associated
    227     * @param value  value to be associated with the specified key
    228     * @return the previous value for the key
    229     * @throws ClassCastException if the key is of an inappropriate type
    230     * @throws NullPointerException if the key is null
    231     */
    232    @Override
    233    public V put(final K key, final V value) {
    234        final V result = get(key);
    235        doPut(key, value);
    236        return result;
    237    }
    238
    239    /**
    240     * Puts all the mappings from the specified map into this map.
    241     * <p>
    242     * All keys and values must implement <code>Comparable</code>.
    243     *
    244     * @param map  the map to copy from
    245     */
    246    @Override
    247    public void putAll(final Map<? extends K, ? extends V> map) {
    248        for (final Map.Entry<? extends K, ? extends V> e : map.entrySet()) {
    249            put(e.getKey(), e.getValue());
    250        }
    251    }
    252
    253    /**
    254     * Removes the mapping for this key from this map if present.
    255     * <p>
    256     * The key must implement <code>Comparable</code>.
    257     *
    258     * @param key  key whose mapping is to be removed from the map.
    259     * @return previous value associated with specified key,
    260     *  or null if there was no mapping for key.
    261     * @throws ClassCastException if the key is of an inappropriate type
    262     * @throws NullPointerException if the key is null
    263     */
    264    @Override
    265    public V remove(final Object key) {
    266        return doRemoveKey(key);
    267    }
    268
    269    /**
    270     * Removes all mappings from this map.
    271     */
    272    @Override
    273    public void clear() {
    274        modify();
    275
    276        nodeCount = 0;
    277        rootNode[KEY.ordinal()] = null;
    278        rootNode[VALUE.ordinal()] = null;
    279    }
    280
    281    //-----------------------------------------------------------------------
    282    /**
    283     * Returns the key to which this map maps the specified value.
    284     * Returns null if the map contains no mapping for this value.
    285     * <p>
    286     * The value must implement <code>Comparable</code>.
    287     *
    288     * @param value  value whose associated key is to be returned.
    289     * @return the key to which this map maps the specified value,
    290     *  or null if the map contains no mapping for this value.
    291     * @throws ClassCastException if the value is of an inappropriate type
    292     * @throws NullPointerException if the value is null
    293     */
    294    @Override
    295    public K getKey(final Object value) {
    296        checkValue(value);
    297        final Node<K, V> node = lookupValue(value);
    298        return node == null ? null : node.getKey();
    299    }
    300
    301    /**
    302     * Removes the mapping for this value from this map if present.
    303     * <p>
    304     * The value must implement <code>Comparable</code>.
    305     *
    306     * @param value  value whose mapping is to be removed from the map
    307     * @return previous key associated with specified value,
    308     *  or null if there was no mapping for value.
    309     * @throws ClassCastException if the value is of an inappropriate type
    310     * @throws NullPointerException if the value is null
    311     */
    312    @Override
    313    public K removeValue(final Object value) {
    314        return doRemoveValue(value);
    315    }
    316
    317    //-----------------------------------------------------------------------
    318    /**
    319     * Gets the first (lowest) key currently in this map.
    320     *
    321     * @return the first (lowest) key currently in this sorted map
    322     * @throws NoSuchElementException if this map is empty
    323     */
    324    @Override
    325    public K firstKey() {
    326        if (nodeCount == 0) {
    327            throw new NoSuchElementException("Map is empty");
    328        }
    329        return leastNode(rootNode[KEY.ordinal()], KEY).getKey();
    330    }
    331
    332    /**
    333     * Gets the last (highest) key currently in this map.
    334     *
    335     * @return the last (highest) key currently in this sorted map
    336     * @throws NoSuchElementException if this map is empty
    337     */
    338    @Override
    339    public K lastKey() {
    340        if (nodeCount == 0) {
    341            throw new NoSuchElementException("Map is empty");
    342        }
    343        return greatestNode(rootNode[KEY.ordinal()], KEY).getKey();
    344    }
    345
    346    /**
    347     * Gets the next key after the one specified.
    348     * <p>
    349     * The key must implement <code>Comparable</code>.
    350     *
    351     * @param key the key to search for next from
    352     * @return the next key, null if no match or at end
    353     */
    354    @Override
    355    public K nextKey(final K key) {
    356        checkKey(key);
    357        final Node<K, V> node = nextGreater(lookupKey(key), KEY);
    358        return node == null ? null : node.getKey();
    359    }
    360
    361    /**
    362     * Gets the previous key before the one specified.
    363     * <p>
    364     * The key must implement <code>Comparable</code>.
    365     *
    366     * @param key the key to search for previous from
    367     * @return the previous key, null if no match or at start
    368     */
    369    @Override
    370    public K previousKey(final K key) {
    371        checkKey(key);
    372        final Node<K, V> node = nextSmaller(lookupKey(key), KEY);
    373        return node == null ? null : node.getKey();
    374    }
    375
    376    //-----------------------------------------------------------------------
    377    /**
    378     * Returns a set view of the keys contained in this map in key order.
    379     * <p>
    380     * The set is backed by the map, so changes to the map are reflected in
    381     * the set, and vice-versa. If the map is modified while an iteration over
    382     * the set is in progress, the results of the iteration are undefined.
    383     * <p>
    384     * The set supports element removal, which removes the corresponding mapping
    385     * from the map. It does not support the add or addAll operations.
    386     *
    387     * @return a set view of the keys contained in this map.
    388     */
    389    @Override
    390    public Set<K> keySet() {
    391        if (keySet == null) {
    392            keySet = new KeyView(KEY);
    393        }
    394        return keySet;
    395    }
    396
    397    //-----------------------------------------------------------------------
    398    /**
    399     * Returns a set view of the values contained in this map in key order.
    400     * The returned object can be cast to a Set.
    401     * <p>
    402     * The set is backed by the map, so changes to the map are reflected in
    403     * the set, and vice-versa. If the map is modified while an iteration over
    404     * the set is in progress, the results of the iteration are undefined.
    405     * <p>
    406     * The set supports element removal, which removes the corresponding mapping
    407     * from the map. It does not support the add or addAll operations.
    408     *
    409     * @return a set view of the values contained in this map.
    410     */
    411    @Override
    412    public Set<V> values() {
    413        if (valuesSet == null) {
    414            valuesSet = new ValueView(KEY);
    415        }
    416        return valuesSet;
    417    }
    418
    419    //-----------------------------------------------------------------------
    420    /**
    421     * Returns a set view of the entries contained in this map in key order.
    422     * For simple iteration through the map, the MapIterator is quicker.
    423     * <p>
    424     * The set is backed by the map, so changes to the map are reflected in
    425     * the set, and vice-versa. If the map is modified while an iteration over
    426     * the set is in progress, the results of the iteration are undefined.
    427     * <p>
    428     * The set supports element removal, which removes the corresponding mapping
    429     * from the map. It does not support the add or addAll operations.
    430     * The returned MapEntry objects do not support setValue.
    431     *
    432     * @return a set view of the values contained in this map.
    433     */
    434    @Override
    435    public Set<Map.Entry<K, V>> entrySet() {
    436        if (entrySet == null) {
    437            entrySet = new EntryView();
    438        }
    439        return entrySet;
    440    }
    441
    442    //-----------------------------------------------------------------------
    443    @Override
    444    public OrderedMapIterator<K, V> mapIterator() {
    445        if (isEmpty()) {
    446            return EmptyOrderedMapIterator.<K, V>emptyOrderedMapIterator();
    447        }
    448        return new ViewMapIterator(KEY);
    449    }
    450
    451    //-----------------------------------------------------------------------
    452    /**
    453     * Gets the inverse map for comparison.
    454     *
    455     * @return the inverse map
    456     */
    457    @Override
    458    public OrderedBidiMap<V, K> inverseBidiMap() {
    459        if (inverse == null) {
    460            inverse = new Inverse();
    461        }
    462        return inverse;
    463    }
    464
    465    //-----------------------------------------------------------------------
    466    /**
    467     * Compares for equals as per the API.
    468     *
    469     * @param obj  the object to compare to
    470     * @return true if equal
    471     */
    472    @Override
    473    public boolean equals(final Object obj) {
    474        return this.doEquals(obj, KEY);
    475    }
    476
    477    /**
    478     * Gets the hash code value for this map as per the API.
    479     *
    480     * @return the hash code value for this map
    481     */
    482    @Override
    483    public int hashCode() {
    484        return this.doHashCode(KEY);
    485    }
    486
    487    /**
    488     * Returns a string version of this Map in standard format.
    489     *
    490     * @return a standard format string version of the map
    491     */
    492    @Override
    493    public String toString() {
    494        return this.doToString(KEY);
    495    }
    496
    497    //-----------------------------------------------------------------------
    498    /**
    499     * Put logic.
    500     *
    501     * @param key  the key, always the main map key
    502     * @param value  the value, always the main map value
    503     */
    504    private void doPut(final K key, final V value) {
    505        checkKeyAndValue(key, value);
    506
    507        // store previous and remove previous mappings
    508        doRemoveKey(key);
    509        doRemoveValue(value);
    510
    511        Node<K, V> node = rootNode[KEY.ordinal()];
    512        if (node == null) {
    513            // map is empty
    514            final Node<K, V> root = new Node<>(key, value);
    515            rootNode[KEY.ordinal()] = root;
    516            rootNode[VALUE.ordinal()] = root;
    517            grow();
    518
    519        } else {
    520            // add new mapping
    521            while (true) {
    522                final int cmp = compare(key, node.getKey());
    523
    524                if (cmp == 0) {
    525                    // shouldn't happen
    526                    throw new IllegalArgumentException("Cannot store a duplicate key (\"" + key + "\") in this Map");
    527                } else if (cmp < 0) {
    528                    if (node.getLeft(KEY) != null) {
    529                        node = node.getLeft(KEY);
    530                    } else {
    531                        final Node<K, V> newNode = new Node<>(key, value);
    532
    533                        insertValue(newNode);
    534                        node.setLeft(newNode, KEY);
    535                        newNode.setParent(node, KEY);
    536                        doRedBlackInsert(newNode, KEY);
    537                        grow();
    538
    539                        break;
    540                    }
    541                } else { // cmp > 0
    542                    if (node.getRight(KEY) != null) {
    543                        node = node.getRight(KEY);
    544                    } else {
    545                        final Node<K, V> newNode = new Node<>(key, value);
    546
    547                        insertValue(newNode);
    548                        node.setRight(newNode, KEY);
    549                        newNode.setParent(node, KEY);
    550                        doRedBlackInsert(newNode, KEY);
    551                        grow();
    552
    553                        break;
    554                    }
    555                }
    556            }
    557        }
    558    }
    559
    560    private V doRemoveKey(final Object key) {
    561        final Node<K, V> node = lookupKey(key);
    562        if (node == null) {
    563            return null;
    564        }
    565        doRedBlackDelete(node);
    566        return node.getValue();
    567    }
    568
    569    private K doRemoveValue(final Object value) {
    570        final Node<K, V> node = lookupValue(value);
    571        if (node == null) {
    572            return null;
    573        }
    574        doRedBlackDelete(node);
    575        return node.getKey();
    576    }
    577
    578    /**
    579     * do the actual lookup of a piece of data
    580     *
    581     * @param data the key or value to be looked up
    582     * @param dataElement  either {@link DataElement#KEY} key}
    583     *                     or the {@link DataElement#VALUE value}.
    584     * @return the desired Node, or null if there is no mapping of the
    585     *         specified data
    586     */
    587    @SuppressWarnings("unchecked")
    588    private <T extends Comparable<T>> Node<K, V> lookup(final Object data, final DataElement dataElement) {
    589        Node<K, V> rval = null;
    590        Node<K, V> node = rootNode[dataElement.ordinal()];
    591
    592        while (node != null) {
    593            final int cmp = compare((T) data, (T) node.getData(dataElement));
    594            if (cmp == 0) {
    595                rval = node;
    596                break;
    597            }
    598            node = cmp < 0 ? node.getLeft(dataElement) : node.getRight(dataElement);
    599        }
    600
    601        return rval;
    602    }
    603
    604    private Node<K, V> lookupKey(final Object key) {
    605        return this.<K>lookup(key, KEY);
    606    }
    607
    608    private Node<K, V> lookupValue(final Object value) {
    609        return this.<V>lookup(value, VALUE);
    610    }
    611
    612    /**
    613     * get the next larger node from the specified node
    614     *
    615     * @param node the node to be searched from
    616     * @param dataElement  either {@link DataElement#KEY} key}
    617     *                     or the {@link DataElement#VALUE value}.
    618     * @return the specified node
    619     */
    620    private Node<K, V> nextGreater(final Node<K, V> node, final DataElement dataElement) {
    621        Node<K, V> rval;
    622        if (node == null) {
    623            rval = null;
    624        } else if (node.getRight(dataElement) != null) {
    625            // everything to the node's right is larger. The least of
    626            // the right node's descendants is the next larger node
    627            rval = leastNode(node.getRight(dataElement), dataElement);
    628        } else {
    629            // traverse up our ancestry until we find an ancestor that
    630            // is null or one whose left child is our ancestor. If we
    631            // find a null, then this node IS the largest node in the
    632            // tree, and there is no greater node. Otherwise, we are
    633            // the largest node in the subtree on that ancestor's left
    634            // ... and that ancestor is the next greatest node
    635            Node<K, V> parent = node.getParent(dataElement);
    636            Node<K, V> child = node;
    637
    638            while (parent != null && child == parent.getRight(dataElement)) {
    639                child = parent;
    640                parent = parent.getParent(dataElement);
    641            }
    642            rval = parent;
    643        }
    644        return rval;
    645    }
    646
    647    /**
    648     * get the next larger node from the specified node
    649     *
    650     * @param node the node to be searched from
    651     * @param dataElement  either {@link DataElement#KEY} key}
    652     *                     or the {@link DataElement#VALUE value}.
    653     * @return the specified node
    654     */
    655    private Node<K, V> nextSmaller(final Node<K, V> node, final DataElement dataElement) {
    656        Node<K, V> rval;
    657        if (node == null) {
    658            rval = null;
    659        } else if (node.getLeft(dataElement) != null) {
    660            // everything to the node's left is smaller. The greatest of
    661            // the left node's descendants is the next smaller node
    662            rval = greatestNode(node.getLeft(dataElement), dataElement);
    663        } else {
    664            // traverse up our ancestry until we find an ancestor that
    665            // is null or one whose right child is our ancestor. If we
    666            // find a null, then this node IS the largest node in the
    667            // tree, and there is no greater node. Otherwise, we are
    668            // the largest node in the subtree on that ancestor's right
    669            // ... and that ancestor is the next greatest node
    670            Node<K, V> parent = node.getParent(dataElement);
    671            Node<K, V> child = node;
    672
    673            while (parent != null && child == parent.getLeft(dataElement)) {
    674                child = parent;
    675                parent = parent.getParent(dataElement);
    676            }
    677            rval = parent;
    678        }
    679        return rval;
    680    }
    681
    682    //-----------------------------------------------------------------------
    683
    684    /**
    685     * Compare two objects
    686     *
    687     * @param o1  the first object
    688     * @param o2  the second object
    689     *
    690     * @return negative value if o1 &lt; o2; 0 if o1 == o2; positive
    691     *         value if o1 &gt; o2
    692     */
    693    private static <T extends Comparable<T>> int compare(final T o1, final T o2) {
    694        return o1.compareTo(o2);
    695    }
    696
    697    /**
    698     * Find the least node from a given node.
    699     *
    700     * @param node  the node from which we will start searching
    701     * @param dataElement  either {@link DataElement#KEY} key}
    702     *                     or the {@link DataElement#VALUE value}.
    703     * @return the smallest node, from the specified node, in the
    704     *         specified mapping
    705     */
    706    private Node<K, V> leastNode(final Node<K, V> node, final DataElement dataElement) {
    707        Node<K, V> rval = node;
    708        if (rval != null) {
    709            while (rval.getLeft(dataElement) != null) {
    710                rval = rval.getLeft(dataElement);
    711            }
    712        }
    713        return rval;
    714    }
    715
    716    /**
    717     * Find the greatest node from a given node.
    718     *
    719     * @param node  the node from which we will start searching
    720     * @param dataElement  either {@link DataElement#KEY} key}
    721     *                     or the {@link DataElement#VALUE value}.
    722     * @return the greatest node, from the specified node
    723     */
    724    private Node<K, V> greatestNode(final Node<K, V> node, final DataElement dataElement) {
    725        Node<K, V> rval = node;
    726        if (rval != null) {
    727            while (rval.getRight(dataElement) != null) {
    728                rval = rval.getRight(dataElement);
    729            }
    730        }
    731        return rval;
    732    }
    733
    734    /**
    735     * copy the color from one node to another, dealing with the fact
    736     * that one or both nodes may, in fact, be null
    737     *
    738     * @param from the node whose color we're copying; may be null
    739     * @param to the node whose color we're changing; may be null
    740     * @param dataElement  either {@link DataElement#KEY} key}
    741     *                     or the {@link DataElement#VALUE value}.
    742     */
    743    private void copyColor(final Node<K, V> from, final Node<K, V> to, final DataElement dataElement) {
    744        if (to != null) {
    745            if (from == null) {
    746                // by default, make it black
    747                to.setBlack(dataElement);
    748            } else {
    749                to.copyColor(from, dataElement);
    750            }
    751        }
    752    }
    753
    754    /**
    755     * is the specified node red? if the node does not exist, no, it's
    756     * black, thank you
    757     *
    758     * @param node the node (may be null) in question
    759     * @param dataElement  either {@link DataElement#KEY} key}
    760     *                     or the {@link DataElement#VALUE value}.
    761     */
    762    private static boolean isRed(final Node<?, ?> node, final DataElement dataElement) {
    763        return node != null && node.isRed(dataElement);
    764    }
    765
    766    /**
    767     * is the specified black red? if the node does not exist, sure,
    768     * it's black, thank you
    769     *
    770     * @param node the node (may be null) in question
    771     * @param dataElement  either {@link DataElement#KEY} key}
    772     *                     or the {@link DataElement#VALUE value}.
    773     */
    774    private static boolean isBlack(final Node<?, ?> node, final DataElement dataElement) {
    775        return node == null || node.isBlack(dataElement);
    776    }
    777
    778    /**
    779     * force a node (if it exists) red
    780     *
    781     * @param node the node (may be null) in question
    782     * @param dataElement  either {@link DataElement#KEY} key}
    783     *                     or the {@link DataElement#VALUE value}.
    784     */
    785    private static void makeRed(final Node<?, ?> node, final DataElement dataElement) {
    786        if (node != null) {
    787            node.setRed(dataElement);
    788        }
    789    }
    790
    791    /**
    792     * force a node (if it exists) black
    793     *
    794     * @param node the node (may be null) in question
    795     * @param dataElement  either {@link DataElement#KEY} key}
    796     *                     or the {@link DataElement#VALUE value}.
    797     */
    798    private static void makeBlack(final Node<?, ?> node, final DataElement dataElement) {
    799        if (node != null) {
    800            node.setBlack(dataElement);
    801        }
    802    }
    803
    804    /**
    805     * get a node's grandparent. mind you, the node, its parent, or
    806     * its grandparent may not exist. no problem
    807     *
    808     * @param node the node (may be null) in question
    809     * @param dataElement  either {@link DataElement#KEY} key}
    810     *                     or the {@link DataElement#VALUE value}.
    811     */
    812    private Node<K, V> getGrandParent(final Node<K, V> node, final DataElement dataElement) {
    813        return getParent(getParent(node, dataElement), dataElement);
    814    }
    815
    816    /**
    817     * get a node's parent. mind you, the node, or its parent, may not
    818     * exist. no problem
    819     *
    820     * @param node the node (may be null) in question
    821     * @param dataElement  either {@link DataElement#KEY} key}
    822     *                     or the {@link DataElement#VALUE value}.
    823     */
    824    private Node<K, V> getParent(final Node<K, V> node, final DataElement dataElement) {
    825        return node == null ? null : node.getParent(dataElement);
    826    }
    827
    828    /**
    829     * get a node's right child. mind you, the node may not exist. no
    830     * problem
    831     *
    832     * @param node the node (may be null) in question
    833     * @param dataElement  either {@link DataElement#KEY} key}
    834     *                     or the {@link DataElement#VALUE value}.
    835     */
    836    private Node<K, V> getRightChild(final Node<K, V> node, final DataElement dataElement) {
    837        return node == null ? null : node.getRight(dataElement);
    838    }
    839
    840    /**
    841     * get a node's left child. mind you, the node may not exist. no
    842     * problem
    843     *
    844     * @param node the node (may be null) in question
    845     * @param dataElement  either {@link DataElement#KEY} key}
    846     *                     or the {@link DataElement#VALUE value}.
    847     */
    848    private Node<K, V> getLeftChild(final Node<K, V> node, final DataElement dataElement) {
    849        return node == null ? null : node.getLeft(dataElement);
    850    }
    851
    852    /**
    853     * do a rotate left. standard fare in the world of balanced trees
    854     *
    855     * @param node the node to be rotated
    856     * @param dataElement  either {@link DataElement#KEY} key}
    857     *                     or the {@link DataElement#VALUE value}.
    858     */
    859    private void rotateLeft(final Node<K, V> node, final DataElement dataElement) {
    860        final Node<K, V> rightChild = node.getRight(dataElement);
    861        node.setRight(rightChild.getLeft(dataElement), dataElement);
    862
    863        if (rightChild.getLeft(dataElement) != null) {
    864            rightChild.getLeft(dataElement).setParent(node, dataElement);
    865        }
    866        rightChild.setParent(node.getParent(dataElement), dataElement);
    867
    868        if (node.getParent(dataElement) == null) {
    869            // node was the root ... now its right child is the root
    870            rootNode[dataElement.ordinal()] = rightChild;
    871        } else if (node.getParent(dataElement).getLeft(dataElement) == node) {
    872            node.getParent(dataElement).setLeft(rightChild, dataElement);
    873        } else {
    874            node.getParent(dataElement).setRight(rightChild, dataElement);
    875        }
    876
    877        rightChild.setLeft(node, dataElement);
    878        node.setParent(rightChild, dataElement);
    879    }
    880
    881    /**
    882     * do a rotate right. standard fare in the world of balanced trees
    883     *
    884     * @param node the node to be rotated
    885     * @param dataElement  either {@link DataElement#KEY} key}
    886     *                     or the {@link DataElement#VALUE value}.
    887     */
    888    private void rotateRight(final Node<K, V> node, final DataElement dataElement) {
    889        final Node<K, V> leftChild = node.getLeft(dataElement);
    890        node.setLeft(leftChild.getRight(dataElement), dataElement);
    891        if (leftChild.getRight(dataElement) != null) {
    892            leftChild.getRight(dataElement).setParent(node, dataElement);
    893        }
    894        leftChild.setParent(node.getParent(dataElement), dataElement);
    895
    896        if (node.getParent(dataElement) == null) {
    897            // node was the root ... now its left child is the root
    898            rootNode[dataElement.ordinal()] = leftChild;
    899        } else if (node.getParent(dataElement).getRight(dataElement) == node) {
    900            node.getParent(dataElement).setRight(leftChild, dataElement);
    901        } else {
    902            node.getParent(dataElement).setLeft(leftChild, dataElement);
    903        }
    904
    905        leftChild.setRight(node, dataElement);
    906        node.setParent(leftChild, dataElement);
    907    }
    908
    909    /**
    910     * complicated red-black insert stuff. Based on Sun's TreeMap
    911     * implementation, though it's barely recognizable any more
    912     *
    913     * @param insertedNode the node to be inserted
    914     * @param dataElement  the KEY or VALUE int
    915     */
    916    private void doRedBlackInsert(final Node<K, V> insertedNode, final DataElement dataElement) {
    917        Node<K, V> currentNode = insertedNode;
    918        makeRed(currentNode, dataElement);
    919
    920        while (currentNode != null
    921            && currentNode != rootNode[dataElement.ordinal()]
    922            && isRed(currentNode.getParent(dataElement), dataElement)) {
    923            if (currentNode.isLeftChild(dataElement)) {
    924                final Node<K, V> y = getRightChild(getGrandParent(currentNode, dataElement), dataElement);
    925
    926                if (isRed(y, dataElement)) {
    927                    makeBlack(getParent(currentNode, dataElement), dataElement);
    928                    makeBlack(y, dataElement);
    929                    makeRed(getGrandParent(currentNode, dataElement), dataElement);
    930
    931                    currentNode = getGrandParent(currentNode, dataElement);
    932                } else {
    933                    //dead code?
    934                    if (currentNode.isRightChild(dataElement)) {
    935                        currentNode = getParent(currentNode, dataElement);
    936
    937                        rotateLeft(currentNode, dataElement);
    938                    }
    939
    940                    makeBlack(getParent(currentNode, dataElement), dataElement);
    941                    makeRed(getGrandParent(currentNode, dataElement), dataElement);
    942
    943                    if (getGrandParent(currentNode, dataElement) != null) {
    944                        rotateRight(getGrandParent(currentNode, dataElement), dataElement);
    945                    }
    946                }
    947            } else {
    948
    949                // just like clause above, except swap left for right
    950                final Node<K, V> y = getLeftChild(getGrandParent(currentNode, dataElement), dataElement);
    951
    952                if (isRed(y, dataElement)) {
    953                    makeBlack(getParent(currentNode, dataElement), dataElement);
    954                    makeBlack(y, dataElement);
    955                    makeRed(getGrandParent(currentNode, dataElement), dataElement);
    956
    957                    currentNode = getGrandParent(currentNode, dataElement);
    958                } else {
    959                    //dead code?
    960                    if (currentNode.isLeftChild(dataElement)) {
    961                        currentNode = getParent(currentNode, dataElement);
    962
    963                        rotateRight(currentNode, dataElement);
    964                    }
    965
    966                    makeBlack(getParent(currentNode, dataElement), dataElement);
    967                    makeRed(getGrandParent(currentNode, dataElement), dataElement);
    968
    969                    if (getGrandParent(currentNode, dataElement) != null) {
    970                        rotateLeft(getGrandParent(currentNode, dataElement), dataElement);
    971                    }
    972                }
    973            }
    974        }
    975
    976        makeBlack(rootNode[dataElement.ordinal()], dataElement);
    977    }
    978
    979    /**
    980     * complicated red-black delete stuff. Based on Sun's TreeMap
    981     * implementation, though it's barely recognizable any more
    982     *
    983     * @param deletedNode the node to be deleted
    984     */
    985    private void doRedBlackDelete(final Node<K, V> deletedNode) {
    986        for (final DataElement dataElement : DataElement.values()) {
    987            // if deleted node has both left and children, swap with
    988            // the next greater node
    989            if (deletedNode.getLeft(dataElement) != null && deletedNode.getRight(dataElement) != null) {
    990                swapPosition(nextGreater(deletedNode, dataElement), deletedNode, dataElement);
    991            }
    992
    993            final Node<K, V> replacement = deletedNode.getLeft(dataElement) != null ?
    994                    deletedNode.getLeft(dataElement) : deletedNode.getRight(dataElement);
    995
    996            if (replacement != null) {
    997                replacement.setParent(deletedNode.getParent(dataElement), dataElement);
    998
    999                if (deletedNode.getParent(dataElement) == null) {
    1000                    rootNode[dataElement.ordinal()] = replacement;
    1001                } else if (deletedNode == deletedNode.getParent(dataElement).getLeft(dataElement)) {
    1002                    deletedNode.getParent(dataElement).setLeft(replacement, dataElement);
    1003                } else {
    1004                    deletedNode.getParent(dataElement).setRight(replacement, dataElement);
    1005                }
    1006
    1007                deletedNode.setLeft(null, dataElement);
    1008                deletedNode.setRight(null, dataElement);
    1009                deletedNode.setParent(null, dataElement);
    1010
    1011                if (isBlack(deletedNode, dataElement)) {
    1012                    doRedBlackDeleteFixup(replacement, dataElement);
    1013                }
    1014            } else {
    1015
    1016                // replacement is null
    1017                if (deletedNode.getParent(dataElement) == null) {
    1018
    1019                    // empty tree
    1020                    rootNode[dataElement.ordinal()] = null;
    1021                } else {
    1022
    1023                    // deleted node had no children
    1024                    if (isBlack(deletedNode, dataElement)) {
    1025                        doRedBlackDeleteFixup(deletedNode, dataElement);
    1026                    }
    1027
    1028                    if (deletedNode.getParent(dataElement) != null) {
    1029                        if (deletedNode == deletedNode.getParent(dataElement).getLeft(dataElement)) {
    1030                            deletedNode.getParent(dataElement).setLeft(null, dataElement);
    1031                        } else {
    1032                            deletedNode.getParent(dataElement).setRight(null, dataElement);
    1033                        }
    1034
    1035                        deletedNode.setParent(null, dataElement);
    1036                    }
    1037                }
    1038            }
    1039        }
    1040        shrink();
    1041    }
    1042
    1043    /**
    1044     * complicated red-black delete stuff. Based on Sun's TreeMap
    1045     * implementation, though it's barely recognizable any more. This
    1046     * rebalances the tree (somewhat, as red-black trees are not
    1047     * perfectly balanced -- perfect balancing takes longer)
    1048     *
    1049     * @param replacementNode the node being replaced
    1050     * @param dataElement  the KEY or VALUE int
    1051     */
    1052    private void doRedBlackDeleteFixup(final Node<K, V> replacementNode, final DataElement dataElement) {
    1053        Node<K, V> currentNode = replacementNode;
    1054
    1055        while (currentNode != rootNode[dataElement.ordinal()] && isBlack(currentNode, dataElement)) {
    1056            if (currentNode.isLeftChild(dataElement)) {
    1057                Node<K, V> siblingNode = getRightChild(getParent(currentNode, dataElement), dataElement);
    1058
    1059                if (isRed(siblingNode, dataElement)) {
    1060                    makeBlack(siblingNode, dataElement);
    1061                    makeRed(getParent(currentNode, dataElement), dataElement);
    1062                    rotateLeft(getParent(currentNode, dataElement), dataElement);
    1063
    1064                    siblingNode = getRightChild(getParent(currentNode, dataElement), dataElement);
    1065                }
    1066
    1067                if (isBlack(getLeftChild(siblingNode, dataElement), dataElement)
    1068                    && isBlack(getRightChild(siblingNode, dataElement), dataElement)) {
    1069                    makeRed(siblingNode, dataElement);
    1070
    1071                    currentNode = getParent(currentNode, dataElement);
    1072                } else {
    1073                    if (isBlack(getRightChild(siblingNode, dataElement), dataElement)) {
    1074                        makeBlack(getLeftChild(siblingNode, dataElement), dataElement);
    1075                        makeRed(siblingNode, dataElement);
    1076                        rotateRight(siblingNode, dataElement);
    1077
    1078                        siblingNode = getRightChild(getParent(currentNode, dataElement), dataElement);
    1079                    }
    1080
    1081                    copyColor(getParent(currentNode, dataElement), siblingNode, dataElement);
    1082                    makeBlack(getParent(currentNode, dataElement), dataElement);
    1083                    makeBlack(getRightChild(siblingNode, dataElement), dataElement);
    1084                    rotateLeft(getParent(currentNode, dataElement), dataElement);
    1085
    1086                    currentNode = rootNode[dataElement.ordinal()];
    1087                }
    1088            } else {
    1089                Node<K, V> siblingNode = getLeftChild(getParent(currentNode, dataElement), dataElement);
    1090
    1091                if (isRed(siblingNode, dataElement)) {
    1092                    makeBlack(siblingNode, dataElement);
    1093                    makeRed(getParent(currentNode, dataElement), dataElement);
    1094                    rotateRight(getParent(currentNode, dataElement), dataElement);
    1095
    1096                    siblingNode = getLeftChild(getParent(currentNode, dataElement), dataElement);
    1097                }
    1098
    1099                if (isBlack(getRightChild(siblingNode, dataElement), dataElement)
    1100                    && isBlack(getLeftChild(siblingNode, dataElement), dataElement)) {
    1101                    makeRed(siblingNode, dataElement);
    1102
    1103                    currentNode = getParent(currentNode, dataElement);
    1104                } else {
    1105                    if (isBlack(getLeftChild(siblingNode, dataElement), dataElement)) {
    1106                        makeBlack(getRightChild(siblingNode, dataElement), dataElement);
    1107                        makeRed(siblingNode, dataElement);
    1108                        rotateLeft(siblingNode, dataElement);
    1109
    1110                        siblingNode = getLeftChild(getParent(currentNode, dataElement), dataElement);
    1111                    }
    1112
    1113                    copyColor(getParent(currentNode, dataElement), siblingNode, dataElement);
    1114                    makeBlack(getParent(currentNode, dataElement), dataElement);
    1115                    makeBlack(getLeftChild(siblingNode, dataElement), dataElement);
    1116                    rotateRight(getParent(currentNode, dataElement), dataElement);
    1117
    1118                    currentNode = rootNode[dataElement.ordinal()];
    1119                }
    1120            }
    1121        }
    1122
    1123        makeBlack(currentNode, dataElement);
    1124    }
    1125
    1126    /**
    1127     * swap two nodes (except for their content), taking care of
    1128     * special cases where one is the other's parent ... hey, it
    1129     * happens.
    1130     *
    1131     * @param x one node
    1132     * @param y another node
    1133     * @param dataElement  the KEY or VALUE int
    1134     */
    1135    private void swapPosition(final Node<K, V> x, final Node<K, V> y, final DataElement dataElement) {
    1136        // Save initial values.
    1137        final Node<K, V> xFormerParent = x.getParent(dataElement);
    1138        final Node<K, V> xFormerLeftChild = x.getLeft(dataElement);
    1139        final Node<K, V> xFormerRightChild = x.getRight(dataElement);
    1140        final Node<K, V> yFormerParent = y.getParent(dataElement);
    1141        final Node<K, V> yFormerLeftChild = y.getLeft(dataElement);
    1142        final Node<K, V> yFormerRightChild = y.getRight(dataElement);
    1143        final boolean xWasLeftChild =
    1144                x.getParent(dataElement) != null && x == x.getParent(dataElement).getLeft(dataElement);
    1145        final boolean yWasLeftChild =
    1146                y.getParent(dataElement) != null && y == y.getParent(dataElement).getLeft(dataElement);
    1147
    1148        // Swap, handling special cases of one being the other's parent.
    1149        if (x == yFormerParent) { // x was y's parent
    1150            x.setParent(y, dataElement);
    1151
    1152            if (yWasLeftChild) {
    1153                y.setLeft(x, dataElement);
    1154                y.setRight(xFormerRightChild, dataElement);
    1155            } else {
    1156                y.setRight(x, dataElement);
    1157                y.setLeft(xFormerLeftChild, dataElement);
    1158            }
    1159        } else {
    1160            x.setParent(yFormerParent, dataElement);
    1161
    1162            if (yFormerParent != null) {
    1163                if (yWasLeftChild) {
    1164                    yFormerParent.setLeft(x, dataElement);
    1165                } else {
    1166                    yFormerParent.setRight(x, dataElement);
    1167                }
    1168            }
    1169
    1170            y.setLeft(xFormerLeftChild, dataElement);
    1171            y.setRight(xFormerRightChild, dataElement);
    1172        }
    1173
    1174        if (y == xFormerParent) { // y was x's parent
    1175            y.setParent(x, dataElement);
    1176
    1177            if (xWasLeftChild) {
    1178                x.setLeft(y, dataElement);
    1179                x.setRight(yFormerRightChild, dataElement);
    1180            } else {
    1181                x.setRight(y, dataElement);
    1182                x.setLeft(yFormerLeftChild, dataElement);
    1183            }
    1184        } else {
    1185            y.setParent(xFormerParent, dataElement);
    1186
    1187            if (xFormerParent != null) {
    1188                if (xWasLeftChild) {
    1189                    xFormerParent.setLeft(y, dataElement);
    1190                } else {
    1191                    xFormerParent.setRight(y, dataElement);
    1192                }
    1193            }
    1194
    1195            x.setLeft(yFormerLeftChild, dataElement);
    1196            x.setRight(yFormerRightChild, dataElement);
    1197        }
    1198
    1199        // Fix children's parent pointers
    1200        if (x.getLeft(dataElement) != null) {
    1201            x.getLeft(dataElement).setParent(x, dataElement);
    1202        }
    1203
    1204        if (x.getRight(dataElement) != null) {
    1205            x.getRight(dataElement).setParent(x, dataElement);
    1206        }
    1207
    1208        if (y.getLeft(dataElement) != null) {
    1209            y.getLeft(dataElement).setParent(y, dataElement);
    1210        }
    1211
    1212        if (y.getRight(dataElement) != null) {
    1213            y.getRight(dataElement).setParent(y, dataElement);
    1214        }
    1215
    1216        x.swapColors(y, dataElement);
    1217
    1218        // Check if root changed
    1219        if (rootNode[dataElement.ordinal()] == x) {
    1220            rootNode[dataElement.ordinal()] = y;
    1221        } else if (rootNode[dataElement.ordinal()] == y) {
    1222            rootNode[dataElement.ordinal()] = x;
    1223        }
    1224    }
    1225
    1226    /**
    1227     * check if an object is fit to be proper input ... has to be
    1228     * Comparable and non-null
    1229     *
    1230     * @param o the object being checked
    1231     * @param dataElement  either {@link DataElement#KEY} key}
    1232     *                     or the {@link DataElement#VALUE value}.
    1233     *
    1234     * @throws NullPointerException if o is null
    1235     * @throws ClassCastException if o is not Comparable
    1236     */
    1237    private static void checkNonNullComparable(final Object o, final DataElement dataElement) {
    1238        if (o == null) {
    1239            throw new NullPointerException(dataElement + " cannot be null");
    1240        }
    1241        if (!(o instanceof Comparable)) {
    1242            throw new ClassCastException(dataElement + " must be Comparable");
    1243        }
    1244    }
    1245
    1246    /**
    1247     * check a key for validity (non-null and implements Comparable)
    1248     *
    1249     * @param key the key to be checked
    1250     *
    1251     * @throws NullPointerException if key is null
    1252     * @throws ClassCastException if key is not Comparable
    1253     */
    1254    private static void checkKey(final Object key) {
    1255        checkNonNullComparable(key, KEY);
    1256    }
    1257
    1258    /**
    1259     * check a value for validity (non-null and implements Comparable)
    1260     *
    1261     * @param value the value to be checked
    1262     *
    1263     * @throws NullPointerException if value is null
    1264     * @throws ClassCastException if value is not Comparable
    1265     */
    1266    private static void checkValue(final Object value) {
    1267        checkNonNullComparable(value, VALUE);
    1268    }
    1269
    1270    /**
    1271     * check a key and a value for validity (non-null and implements
    1272     * Comparable)
    1273     *
    1274     * @param key the key to be checked
    1275     * @param value the value to be checked
    1276     *
    1277     * @throws NullPointerException if key or value is null
    1278     * @throws ClassCastException if key or value is not Comparable
    1279     */
    1280    private static void checkKeyAndValue(final Object key, final Object value) {
    1281        checkKey(key);
    1282        checkValue(value);
    1283    }
    1284
    1285    /**
    1286     * increment the modification count -- used to check for
    1287     * concurrent modification of the map through the map and through
    1288     * an Iterator from one of its Set or Collection views
    1289     */
    1290    private void modify() {
    1291        modifications++;
    1292    }
    1293
    1294    /**
    1295     * bump up the size and note that the map has changed
    1296     */
    1297    private void grow() {
    1298        modify();
    1299        nodeCount++;
    1300    }
    1301
    1302    /**
    1303     * decrement the size and note that the map has changed
    1304     */
    1305    private void shrink() {
    1306        modify();
    1307        nodeCount--;
    1308    }
    1309
    1310    /**
    1311     * insert a node by its value
    1312     *
    1313     * @param newNode the node to be inserted
    1314     *
    1315     * @throws IllegalArgumentException if the node already exists
    1316     *                                     in the value mapping
    1317     */
    1318    private void insertValue(final Node<K, V> newNode) throws IllegalArgumentException {
    1319        Node<K, V> node = rootNode[VALUE.ordinal()];
    1320
    1321        while (true) {
    1322            final int cmp = compare(newNode.getValue(), node.getValue());
    1323
    1324            if (cmp == 0) {
    1325                throw new IllegalArgumentException(
    1326                    "Cannot store a duplicate value (\"" + newNode.getData(VALUE) + "\") in this Map");
    1327            } else if (cmp < 0) {
    1328                if (node.getLeft(VALUE) != null) {
    1329                    node = node.getLeft(VALUE);
    1330                } else {
    1331                    node.setLeft(newNode, VALUE);
    1332                    newNode.setParent(node, VALUE);
    1333                    doRedBlackInsert(newNode, VALUE);
    1334
    1335                    break;
    1336                }
    1337            } else { // cmp > 0
    1338                if (node.getRight(VALUE) != null) {
    1339                    node = node.getRight(VALUE);
    1340                } else {
    1341                    node.setRight(newNode, VALUE);
    1342                    newNode.setParent(node, VALUE);
    1343                    doRedBlackInsert(newNode, VALUE);
    1344
    1345                    break;
    1346                }
    1347            }
    1348        }
    1349    }
    1350
    1351    //-----------------------------------------------------------------------
    1352    /**
    1353     * Compares for equals as per the API.
    1354     *
    1355     * @param obj  the object to compare to
    1356     * @param dataElement  either {@link DataElement#KEY} key}
    1357     *                     or the {@link DataElement#VALUE value}.
    1358     * @return true if equal
    1359     */
    1360    private boolean doEquals(final Object obj, final DataElement dataElement) {
    1361        if (obj == this) {
    1362            return true;
    1363        }
    1364        if (obj instanceof Map == false) {
    1365            return false;
    1366        }
    1367        final Map<?, ?> other = (Map<?, ?>) obj;
    1368        if (other.size() != size()) {
    1369            return false;
    1370        }
    1371
    1372        if (nodeCount > 0) {
    1373            try {
    1374                for (final MapIterator<?, ?> it = getMapIterator(dataElement); it.hasNext(); ) {
    1375                    final Object key = it.next();
    1376                    final Object value = it.getValue();
    1377                    if (value.equals(other.get(key)) == false) {
    1378                        return false;
    1379                    }
    1380                }
    1381            } catch (final ClassCastException ex) {
    1382                return false;
    1383            } catch (final NullPointerException ex) {
    1384                return false;
    1385            }
    1386        }
    1387        return true;
    1388    }
    1389
    1390    /**
    1391     * Gets the hash code value for this map as per the API.
    1392     *
    1393     * @param dataElement  either {@link DataElement#KEY} key}
    1394     *                     or the {@link DataElement#VALUE value}.
    1395     * @return the hash code value for this map
    1396     */
    1397    private int doHashCode(final DataElement dataElement) {
    1398        int total = 0;
    1399        if (nodeCount > 0) {
    1400            for (final MapIterator<?, ?> it = getMapIterator(dataElement); it.hasNext(); ) {
    1401                final Object key = it.next();
    1402                final Object value = it.getValue();
    1403                total += key.hashCode() ^ value.hashCode();
    1404            }
    1405        }
    1406        return total;
    1407    }
    1408
    1409    /**
    1410     * Gets the string form of this map as per AbstractMap.
    1411     *
    1412     * @param dataElement  either {@link DataElement#KEY} key}
    1413     *                     or the {@link DataElement#VALUE value}.
    1414     * @return the string form of this map
    1415     */
    1416    private String doToString(final DataElement dataElement) {
    1417        if (nodeCount == 0) {
    1418            return "{}";
    1419        }
    1420        final StringBuilder buf = new StringBuilder(nodeCount * 32);
    1421        buf.append('{');
    1422        final MapIterator<?, ?> it = getMapIterator(dataElement);
    1423        boolean hasNext = it.hasNext();
    1424        while (hasNext) {
    1425            final Object key = it.next();
    1426            final Object value = it.getValue();
    1427            buf.append(key == this ? "(this Map)" : key)
    1428               .append('=')
    1429               .append(value == this ? "(this Map)" : value);
    1430
    1431            hasNext = it.hasNext();
    1432            if (hasNext) {
    1433                buf.append(", ");
    1434            }
    1435        }
    1436
    1437        buf.append('}');
    1438        return buf.toString();
    1439    }
    1440
    1441    private MapIterator<?, ?> getMapIterator(final DataElement dataElement) {
    1442        switch (dataElement) {
    1443        case KEY:
    1444            return new ViewMapIterator(KEY);
    1445        case VALUE:
    1446            return new InverseViewMapIterator(VALUE);
    1447        default:
    1448            throw new IllegalArgumentException();
    1449        }
    1450    }
    1451
    1452    /**
    1453     * Reads the content of the stream.
    1454     *
    1455     * @param stream the input stream
    1456     * @throws IOException if an error occurs while reading from the stream
    1457     * @throws ClassNotFoundException if an object read from the stream can not be loaded
    1458     */
    1459    @SuppressWarnings("unchecked") // This will fail at runtime if the stream is incorrect
    1460    private void readObject(final ObjectInputStream stream) throws IOException, ClassNotFoundException{
    1461        stream.defaultReadObject();
    1462        rootNode = new Node[2];
    1463        final int size = stream.readInt();
    1464        for(int i = 0; i < size; i++){
    1465            final K k =(K) stream.readObject();
    1466            final V v =(V) stream.readObject();
    1467            put(k, v);
    1468        }
    1469    }
    1470
    1471    /**
    1472     * Writes the content to the stream for serialization.
    1473     *
    1474     * @param stream  the output stream
    1475     * @throws IOException if an error occurs while writing to the stream
    1476     */
    1477    private void writeObject(final ObjectOutputStream stream) throws IOException{
    1478        stream.defaultWriteObject();
    1479        stream.writeInt(this.size());
    1480        for (final Entry<K, V> entry : entrySet()) {
    1481            stream.writeObject(entry.getKey());
    1482            stream.writeObject(entry.getValue());
    1483        }
    1484    }
    1485
    1486    //-----------------------------------------------------------------------
    1487    /**
    1488     * A view of this map.
    1489     */
    1490    abstract class View<E> extends AbstractSet<E> {
    1491
    1492        /** Whether to return KEY or VALUE order. */
    1493        final DataElement orderType;
    1494
    1495        /**
    1496         * Constructor.
    1497         * @param orderType  the KEY or VALUE int for the order
    1498         */
    1499        View(final DataElement orderType) {
    1500            super();
    1501            this.orderType = orderType;
    1502        }
    1503
    1504        @Override
    1505        public int size() {
    1506            return TreeBidiMap.this.size();
    1507        }
    1508
    1509        @Override
    1510        public void clear() {
    1511            TreeBidiMap.this.clear();
    1512        }
    1513    }
    1514
    1515    class KeyView extends View<K> {
    1516
    1517        /**
    1518         * Create a new TreeBidiMap.KeyView.
    1519         */
    1520        public KeyView(final DataElement orderType) {
    1521            super(orderType);
    1522        }
    1523
    1524        @Override
    1525        public Iterator<K> iterator() {
    1526            return new ViewMapIterator(orderType);
    1527        }
    1528
    1529        @Override
    1530        public boolean contains(final Object obj) {
    1531            checkNonNullComparable(obj, KEY);
    1532            return lookupKey(obj) != null;
    1533        }
    1534
    1535        @Override
    1536        public boolean remove(final Object o) {
    1537            return doRemoveKey(o) != null;
    1538        }
    1539
    1540    }
    1541
    1542    class ValueView extends View<V> {
    1543
    1544        /**
    1545         * Create a new TreeBidiMap.ValueView.
    1546         */
    1547        public ValueView(final DataElement orderType) {
    1548            super(orderType);
    1549        }
    1550
    1551        @Override
    1552        public Iterator<V> iterator() {
    1553            return new InverseViewMapIterator(orderType);
    1554        }
    1555
    1556        @Override
    1557        public boolean contains(final Object obj) {
    1558            checkNonNullComparable(obj, VALUE);
    1559            return lookupValue(obj) != null;
    1560        }
    1561
    1562        @Override
    1563        public boolean remove(final Object o) {
    1564            return doRemoveValue(o) != null;
    1565        }
    1566
    1567    }
    1568
    1569    /**
    1570     * A view of this map.
    1571     */
    1572    class EntryView extends View<Map.Entry<K, V>> {
    1573
    1574        EntryView() {
    1575            super(KEY);
    1576        }
    1577
    1578        @Override
    1579        public boolean contains(final Object obj) {
    1580            if (obj instanceof Map.Entry == false) {
    1581                return false;
    1582            }
    1583            final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
    1584            final Object value = entry.getValue();
    1585            final Node<K, V> node = lookupKey(entry.getKey());
    1586            return node != null && node.getValue().equals(value);
    1587        }
    1588
    1589        @Override
    1590        public boolean remove(final Object obj) {
    1591            if (obj instanceof Map.Entry == false) {
    1592                return false;
    1593            }
    1594            final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
    1595            final Object value = entry.getValue();
    1596            final Node<K, V> node = lookupKey(entry.getKey());
    1597            if (node != null && node.getValue().equals(value)) {
    1598                doRedBlackDelete(node);
    1599                return true;
    1600            }
    1601            return false;
    1602        }
    1603
    1604        @Override
    1605        public Iterator<Map.Entry<K, V>> iterator() {
    1606            return new ViewMapEntryIterator();
    1607        }
    1608    }
    1609
    1610    /**
    1611     * A view of this map.
    1612     */
    1613    class InverseEntryView extends View<Map.Entry<V, K>> {
    1614
    1615        InverseEntryView() {
    1616            super(VALUE);
    1617        }
    1618
    1619        @Override
    1620        public boolean contains(final Object obj) {
    1621            if (obj instanceof Map.Entry == false) {
    1622                return false;
    1623            }
    1624            final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
    1625            final Object value = entry.getValue();
    1626            final Node<K, V> node = lookupValue(entry.getKey());
    1627            return node != null && node.getKey().equals(value);
    1628        }
    1629
    1630        @Override
    1631        public boolean remove(final Object obj) {
    1632            if (obj instanceof Map.Entry == false) {
    1633                return false;
    1634            }
    1635            final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
    1636            final Object value = entry.getValue();
    1637            final Node<K, V> node = lookupValue(entry.getKey());
    1638            if (node != null && node.getKey().equals(value)) {
    1639                doRedBlackDelete(node);
    1640                return true;
    1641            }
    1642            return false;
    1643        }
    1644
    1645        @Override
    1646        public Iterator<Map.Entry<V, K>> iterator() {
    1647            return new InverseViewMapEntryIterator();
    1648        }
    1649    }
    1650
    1651    //-----------------------------------------------------------------------
    1652    /**
    1653     * An iterator over the map.
    1654     */
    1655    abstract class ViewIterator {
    1656
    1657        /** Whether to return KEY or VALUE order. */
    1658        private final DataElement orderType;
    1659        /** The last node returned by the iterator. */
    1660        Node<K, V> lastReturnedNode;
    1661        /** The next node to be returned by the iterator. */
    1662        private Node<K, V> nextNode;
    1663        /** The previous node in the sequence returned by the iterator. */
    1664        private Node<K, V> previousNode;
    1665        /** The modification count. */
    1666        private int expectedModifications;
    1667
    1668        /**
    1669         * Constructor.
    1670         * @param orderType  the KEY or VALUE int for the order
    1671         */
    1672        ViewIterator(final DataElement orderType) {
    1673            super();
    1674            this.orderType = orderType;
    1675            expectedModifications = modifications;
    1676            nextNode = leastNode(rootNode[orderType.ordinal()], orderType);
    1677            lastReturnedNode = null;
    1678            previousNode = null;
    1679        }
    1680
    1681        public final boolean hasNext() {
    1682            return nextNode != null;
    1683        }
    1684
    1685        protected Node<K, V> navigateNext() {
    1686            if (nextNode == null) {
    1687                throw new NoSuchElementException();
    1688            }
    1689            if (modifications != expectedModifications) {
    1690                throw new ConcurrentModificationException();
    1691            }
    1692            lastReturnedNode = nextNode;
    1693            previousNode = nextNode;
    1694            nextNode = nextGreater(nextNode, orderType);
    1695            return lastReturnedNode;
    1696        }
    1697
    1698        public boolean hasPrevious() {
    1699            return previousNode != null;
    1700        }
    1701
    1702        protected Node<K, V> navigatePrevious() {
    1703            if (previousNode == null) {
    1704                throw new NoSuchElementException();
    1705            }
    1706            if (modifications != expectedModifications) {
    1707                throw new ConcurrentModificationException();
    1708            }
    1709            nextNode = lastReturnedNode;
    1710            if (nextNode == null) {
    1711                nextNode = nextGreater(previousNode, orderType);
    1712            }
    1713            lastReturnedNode = previousNode;
    1714            previousNode = nextSmaller(previousNode, orderType);
    1715            return lastReturnedNode;
    1716        }
    1717
    1718        public final void remove() {
    1719            if (lastReturnedNode == null) {
    1720                throw new IllegalStateException();
    1721            }
    1722            if (modifications != expectedModifications) {
    1723                throw new ConcurrentModificationException();
    1724            }
    1725            doRedBlackDelete(lastReturnedNode);
    1726            expectedModifications++;
    1727            lastReturnedNode = null;
    1728            if (nextNode == null) {
    1729                previousNode = greatestNode(rootNode[orderType.ordinal()], orderType);
    1730            } else {
    1731                previousNode = nextSmaller(nextNode, orderType);
    1732            }
    1733        }
    1734    }
    1735
    1736    //-----------------------------------------------------------------------
    1737    /**
    1738     * An iterator over the map.
    1739     */
    1740    class ViewMapIterator extends ViewIterator implements OrderedMapIterator<K, V> {
    1741
    1742        /**
    1743         * Constructor.
    1744         */
    1745        ViewMapIterator(final DataElement orderType) {
    1746            super(orderType);
    1747        }
    1748
    1749        @Override
    1750        public K getKey() {
    1751            if (lastReturnedNode == null) {
    1752                throw new IllegalStateException(
    1753                        "Iterator getKey() can only be called after next() and before remove()");
    1754            }
    1755            return lastReturnedNode.getKey();
    1756        }
    1757
    1758        @Override
    1759        public V getValue() {
    1760            if (lastReturnedNode == null) {
    1761                throw new IllegalStateException(
    1762                        "Iterator getValue() can only be called after next() and before remove()");
    1763            }
    1764            return lastReturnedNode.getValue();
    1765        }
    1766
    1767        @Override
    1768        public V setValue(final V obj) {
    1769            throw new UnsupportedOperationException();
    1770        }
    1771
    1772        @Override
    1773        public K next() {
    1774            return navigateNext().getKey();
    1775        }
    1776
    1777        @Override
    1778        public K previous() {
    1779            return navigatePrevious().getKey();
    1780        }
    1781    }
    1782
    1783    /**
    1784     * An iterator over the map.
    1785     */
    1786    class InverseViewMapIterator extends ViewIterator implements OrderedMapIterator<V, K> {
    1787
    1788        /**
    1789         * Create a new TreeBidiMap.InverseViewMapIterator.
    1790         */
    1791        public InverseViewMapIterator(final DataElement orderType) {
    1792            super(orderType);
    1793        }
    1794
    1795        @Override
    1796        public V getKey() {
    1797            if (lastReturnedNode == null) {
    1798                throw new IllegalStateException(
    1799                        "Iterator getKey() can only be called after next() and before remove()");
    1800            }
    1801            return lastReturnedNode.getValue();
    1802        }
    1803
    1804        @Override
    1805        public K getValue() {
    1806            if (lastReturnedNode == null) {
    1807                throw new IllegalStateException(
    1808                        "Iterator getValue() can only be called after next() and before remove()");
    1809            }
    1810            return lastReturnedNode.getKey();
    1811        }
    1812
    1813        @Override
    1814        public K setValue(final K obj) {
    1815            throw new UnsupportedOperationException();
    1816        }
    1817
    1818        @Override
    1819        public V next() {
    1820            return navigateNext().getValue();
    1821        }
    1822
    1823        @Override
    1824        public V previous() {
    1825            return navigatePrevious().getValue();
    1826        }
    1827    }
    1828
    1829    /**
    1830     * An iterator over the map entries.
    1831     */
    1832    class ViewMapEntryIterator extends ViewIterator implements OrderedIterator<Map.Entry<K, V>> {
    1833
    1834        /**
    1835         * Constructor.
    1836         */
    1837        ViewMapEntryIterator() {
    1838            super(KEY);
    1839        }
    1840
    1841        @Override
    1842        public Map.Entry<K, V> next() {
    1843            return navigateNext();
    1844        }
    1845
    1846        @Override
    1847        public Map.Entry<K, V> previous() {
    1848            return navigatePrevious();
    1849        }
    1850    }
    1851
    1852    /**
    1853     * An iterator over the inverse map entries.
    1854     */
    1855    class InverseViewMapEntryIterator extends ViewIterator implements OrderedIterator<Map.Entry<V, K>> {
    1856
    1857        /**
    1858         * Constructor.
    1859         */
    1860        InverseViewMapEntryIterator() {
    1861            super(VALUE);
    1862        }
    1863
    1864        @Override
    1865        public Map.Entry<V, K> next() {
    1866            return createEntry(navigateNext());
    1867        }
    1868
    1869        @Override
    1870        public Map.Entry<V, K> previous() {
    1871            return createEntry(navigatePrevious());
    1872        }
    1873
    1874        private Map.Entry<V, K> createEntry(final Node<K, V> node) {
    1875            return new UnmodifiableMapEntry<>(node.getValue(), node.getKey());
    1876        }
    1877    }
    1878
    1879    //-----------------------------------------------------------------------
    1880    //-----------------------------------------------------------------------
    1881    /**
    1882     * A node used to store the data.
    1883     */
    1884    static class Node<K extends Comparable<K>, V extends Comparable<V>> implements Map.Entry<K, V>, KeyValue<K, V> {
    1885
    1886        private final K key;
    1887        private final V value;
    1888        private final Node<K, V>[] leftNode;
    1889        private final Node<K, V>[] rightNode;
    1890        private final Node<K, V>[] parentNode;
    1891        private final boolean[] blackColor;
    1892        private int hashcodeValue;
    1893        private boolean calculatedHashCode;
    1894
    1895        /**
    1896         * Make a new cell with given key and value, and with null
    1897         * links, and black (true) colors.
    1898         *
    1899         * @param key the key of this node
    1900         * @param value the value of this node
    1901         */
    1902        @SuppressWarnings("unchecked")
    1903        Node(final K key, final V value) {
    1904            super();
    1905            this.key = key;
    1906            this.value = value;
    1907            leftNode = new Node[2];
    1908            rightNode = new Node[2];
    1909            parentNode = new Node[2];
    1910            blackColor = new boolean[] { true, true };
    1911            calculatedHashCode = false;
    1912        }
    1913
    1914        private Object getData(final DataElement dataElement) {
    1915            switch (dataElement) {
    1916            case KEY:
    1917                return getKey();
    1918            case VALUE:
    1919                return getValue();
    1920            default:
    1921                throw new IllegalArgumentException();
    1922            }
    1923        }
    1924
    1925        private void setLeft(final Node<K, V> node, final DataElement dataElement) {
    1926            leftNode[dataElement.ordinal()] = node;
    1927        }
    1928
    1929        private Node<K, V> getLeft(final DataElement dataElement) {
    1930            return leftNode[dataElement.ordinal()];
    1931        }
    1932
    1933        private void setRight(final Node<K, V> node, final DataElement dataElement) {
    1934            rightNode[dataElement.ordinal()] = node;
    1935        }
    1936
    1937        private Node<K, V> getRight(final DataElement dataElement) {
    1938            return rightNode[dataElement.ordinal()];
    1939        }
    1940
    1941        /**
    1942         * Set this node's parent node.
    1943         *
    1944         * @param node  the new parent node
    1945         * @param dataElement  either {@link DataElement#KEY} key}
    1946         *                     or the {@link DataElement#VALUE value}.
    1947         */
    1948        private void setParent(final Node<K, V> node, final DataElement dataElement) {
    1949            parentNode[dataElement.ordinal()] = node;
    1950        }
    1951
    1952        /**
    1953         * Get the parent node.
    1954         *
    1955         * @param dataElement  either {@link DataElement#KEY} key}
    1956         *                     or the {@link DataElement#VALUE value}.
    1957         * @return the parent node, may be null
    1958         */
    1959        private Node<K, V> getParent(final DataElement dataElement) {
    1960            return parentNode[dataElement.ordinal()];
    1961        }
    1962
    1963        /**
    1964         * Exchange colors with another node.
    1965         *
    1966         * @param node  the node to swap with
    1967         * @param dataElement  either {@link DataElement#KEY} key}
    1968         *                     or the {@link DataElement#VALUE value}.
    1969         */
    1970        private void swapColors(final Node<K, V> node, final DataElement dataElement) {
    1971            // Swap colors -- old hacker's trick
    1972            blackColor[dataElement.ordinal()]      ^= node.blackColor[dataElement.ordinal()];
    1973            node.blackColor[dataElement.ordinal()] ^= blackColor[dataElement.ordinal()];
    1974            blackColor[dataElement.ordinal()]      ^= node.blackColor[dataElement.ordinal()];
    1975        }
    1976
    1977        /**
    1978         * Is this node black?
    1979         *
    1980         * @param dataElement  either {@link DataElement#KEY} key}
    1981         *                     or the {@link DataElement#VALUE value}.
    1982         * @return true if black (which is represented as a true boolean)
    1983         */
    1984        private boolean isBlack(final DataElement dataElement) {
    1985            return blackColor[dataElement.ordinal()];
    1986        }
    1987
    1988        /**
    1989         * Is this node red?
    1990         *
    1991         * @param dataElement  either {@link DataElement#KEY} key}
    1992         *                     or the {@link DataElement#VALUE value}.
    1993         * @return true if non-black
    1994         */
    1995        private boolean isRed(final DataElement dataElement) {
    1996            return !blackColor[dataElement.ordinal()];
    1997        }
    1998
    1999        /**
    2000         * Make this node black.
    2001         *
    2002         * @param dataElement  either {@link DataElement#KEY} key}
    2003         *                     or the {@link DataElement#VALUE value}.
    2004         */
    2005        private void setBlack(final DataElement dataElement) {
    2006            blackColor[dataElement.ordinal()] = true;
    2007        }
    2008
    2009        /**
    2010         * Make this node red.
    2011         *
    2012         * @param dataElement  either {@link DataElement#KEY} key}
    2013         *                     or the {@link DataElement#VALUE value}.
    2014         */
    2015        private void setRed(final DataElement dataElement) {
    2016            blackColor[dataElement.ordinal()] = false;
    2017        }
    2018
    2019        /**
    2020         * Make this node the same color as another
    2021         *
    2022         * @param node  the node whose color we're adopting
    2023         * @param dataElement  either {@link DataElement#KEY} key}
    2024         *                     or the {@link DataElement#VALUE value}.
    2025         */
    2026        private void copyColor(final Node<K, V> node, final DataElement dataElement) {
    2027            blackColor[dataElement.ordinal()] = node.blackColor[dataElement.ordinal()];
    2028        }
    2029
    2030        private boolean isLeftChild(final DataElement dataElement) {
    2031            return parentNode[dataElement.ordinal()] != null
    2032                    && parentNode[dataElement.ordinal()].leftNode[dataElement.ordinal()] == this;
    2033        }
    2034
    2035        private boolean isRightChild(final DataElement dataElement) {
    2036            return parentNode[dataElement.ordinal()] != null
    2037                    && parentNode[dataElement.ordinal()].rightNode[dataElement.ordinal()] == this;
    2038        }
    2039
    2040        //-------------------------------------------------------------------
    2041        /**
    2042         * Gets the key.
    2043         *
    2044         * @return the key corresponding to this entry.
    2045         */
    2046        @Override
    2047        public K getKey() {
    2048            return key;
    2049        }
    2050
    2051        /**
    2052         * Gets the value.
    2053         *
    2054         * @return the value corresponding to this entry.
    2055         */
    2056        @Override
    2057        public V getValue() {
    2058            return value;
    2059        }
    2060
    2061        /**
    2062         * Optional operation that is not permitted in this implementation
    2063         *
    2064         * @param ignored this parameter is ignored.
    2065         * @return does not return
    2066         * @throws UnsupportedOperationException always
    2067         */
    2068        @Override
    2069        public V setValue(final V ignored) throws UnsupportedOperationException {
    2070            throw new UnsupportedOperationException("Map.Entry.setValue is not supported");
    2071        }
    2072
    2073        /**
    2074         * Compares the specified object with this entry for equality.
    2075         * Returns true if the given object is also a map entry and
    2076         * the two entries represent the same mapping.
    2077         *
    2078         * @param obj  the object to be compared for equality with this entry.
    2079         * @return true if the specified object is equal to this entry.
    2080         */
    2081        @Override
    2082        public boolean equals(final Object obj) {
    2083            if (obj == this) {
    2084                return true;
    2085            }
    2086            if (!(obj instanceof Map.Entry)) {
    2087                return false;
    2088            }
    2089            final Map.Entry<?, ?> e = (Map.Entry<?, ?>) obj;
    2090            return getKey().equals(e.getKey()) && getValue().equals(e.getValue());
    2091        }
    2092
    2093        /**
    2094         * @return the hash code value for this map entry.
    2095         */
    2096        @Override
    2097        public int hashCode() {
    2098            if (!calculatedHashCode) {
    2099                hashcodeValue = getKey().hashCode() ^ getValue().hashCode();
    2100                calculatedHashCode = true;
    2101            }
    2102            return hashcodeValue;
    2103        }
    2104    }
    2105
    2106    //-----------------------------------------------------------------------
    2107    /**
    2108     * The inverse map implementation.
    2109     */
    2110    class Inverse implements OrderedBidiMap<V, K> {
    2111
    2112        /** Store the keySet once created. */
    2113        private Set<V> inverseKeySet;
    2114        /** Store the valuesSet once created. */
    2115        private Set<K> inverseValuesSet;
    2116        /** Store the entrySet once created. */
    2117        private Set<Map.Entry<V, K>> inverseEntrySet;
    2118
    2119        @Override
    2120        public int size() {
    2121            return TreeBidiMap.this.size();
    2122        }
    2123
    2124        @Override
    2125        public boolean isEmpty() {
    2126            return TreeBidiMap.this.isEmpty();
    2127        }
    2128
    2129        @Override
    2130        public K get(final Object key) {
    2131            return TreeBidiMap.this.getKey(key);
    2132        }
    2133
    2134        @Override
    2135        public V getKey(final Object value) {
    2136            return TreeBidiMap.this.get(value);
    2137        }
    2138
    2139        @Override
    2140        public boolean containsKey(final Object key) {
    2141            return TreeBidiMap.this.containsValue(key);
    2142        }
    2143
    2144        @Override
    2145        public boolean containsValue(final Object value) {
    2146            return TreeBidiMap.this.containsKey(value);
    2147        }
    2148
    2149        @Override
    2150        public V firstKey() {
    2151            if (TreeBidiMap.this.nodeCount == 0) {
    2152                throw new NoSuchElementException("Map is empty");
    2153            }
    2154            return leastNode(TreeBidiMap.this.rootNode[VALUE.ordinal()], VALUE).getValue();
    2155        }
    2156
    2157        @Override
    2158        public V lastKey() {
    2159            if (TreeBidiMap.this.nodeCount == 0) {
    2160                throw new NoSuchElementException("Map is empty");
    2161            }
    2162            return greatestNode(TreeBidiMap.this.rootNode[VALUE.ordinal()], VALUE).getValue();
    2163        }
    2164
    2165        @Override
    2166        public V nextKey(final V key) {
    2167            checkKey(key);
    2168            final Node<K, V> node = nextGreater(TreeBidiMap.this.<V>lookup(key, VALUE), VALUE);
    2169            return node == null ? null : node.getValue();
    2170        }
    2171
    2172        @Override
    2173        public V previousKey(final V key) {
    2174            checkKey(key);
    2175            final Node<K, V> node = TreeBidiMap.this.nextSmaller(TreeBidiMap.this.<V>lookup(key, VALUE), VALUE);
    2176            return node == null ? null : node.getValue();
    2177        }
    2178
    2179        @Override
    2180        public K put(final V key, final K value) {
    2181            final K result = get(key);
    2182            TreeBidiMap.this.doPut(value, key);
    2183            return result;
    2184        }
    2185
    2186        @Override
    2187        public void putAll(final Map<? extends V, ? extends K> map) {
    2188            for (final Map.Entry<? extends V, ? extends K> e : map.entrySet()) {
    2189                put(e.getKey(), e.getValue());
    2190            }
    2191        }
    2192
    2193        @Override
    2194        public K remove(final Object key) {
    2195            return TreeBidiMap.this.removeValue(key);
    2196        }
    2197
    2198        @Override
    2199        public V removeValue(final Object value) {
    2200            return TreeBidiMap.this.remove(value);
    2201        }
    2202
    2203        @Override
    2204        public void clear() {
    2205            TreeBidiMap.this.clear();
    2206        }
    2207
    2208        @Override
    2209        public Set<V> keySet() {
    2210            if (inverseKeySet == null) {
    2211                inverseKeySet = new ValueView(VALUE);
    2212            }
    2213            return inverseKeySet;
    2214        }
    2215
    2216        @Override
    2217        public Set<K> values() {
    2218            if (inverseValuesSet == null) {
    2219                inverseValuesSet = new KeyView(VALUE);
    2220            }
    2221            return inverseValuesSet;
    2222        }
    2223
    2224        @Override
    2225        public Set<Map.Entry<V, K>> entrySet() {
    2226            if (inverseEntrySet == null) {
    2227                inverseEntrySet = new InverseEntryView();
    2228            }
    2229            return inverseEntrySet;
    2230        }
    2231
    2232        @Override
    2233        public OrderedMapIterator<V, K> mapIterator() {
    2234            if (isEmpty()) {
    2235                return EmptyOrderedMapIterator.<V, K>emptyOrderedMapIterator();
    2236            }
    2237            return new InverseViewMapIterator(VALUE);
    2238        }
    2239
    2240        @Override
    2241        public OrderedBidiMap<K, V> inverseBidiMap() {
    2242            return TreeBidiMap.this;
    2243        }
    2244
    2245        @Override
    2246        public boolean equals(final Object obj) {
    2247            return TreeBidiMap.this.doEquals(obj, DataElement.VALUE);
    2248        }
    2249
    2250        @Override
    2251        public int hashCode() {
    2252            return TreeBidiMap.this.doHashCode(DataElement.VALUE);
    2253        }
    2254
    2255        @Override
    2256        public String toString() {
    2257            return TreeBidiMap.this.doToString(DataElement.VALUE);
    2258        }
    2259    }
    2260
    2261}