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