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