    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 (e.g.,
    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
    1214            final Node<K, V> replacement = deletedNode.getLeft(dataElement) != null ?
    1215                    deletedNode.getLeft(dataElement) : deletedNode.getRight(dataElement);
    1216
    1217            if (replacement != null) {
    1218                replacement.setParent(deletedNode.getParent(dataElement), dataElement);
    1219
    1220                if (deletedNode.getParent(dataElement) == null) {
    1221                    rootNode[dataElement.ordinal()] = replacement;
    1222                } else if (deletedNode == deletedNode.getParent(dataElement).getLeft(dataElement)) {
    1223                    deletedNode.getParent(dataElement).setLeft(replacement, dataElement);
    1224                } else {
    1225                    deletedNode.getParent(dataElement).setRight(replacement, dataElement);
    1226                }
    1227
    1228                deletedNode.setLeft(null, dataElement);
    1229                deletedNode.setRight(null, dataElement);
    1230                deletedNode.setParent(null, dataElement);
    1231
    1232                if (isBlack(deletedNode, dataElement)) {
    1233                    doRedBlackDeleteFixup(replacement, dataElement);
    1234                }
    1235            } else {
    1236
    1237                // replacement is null
    1238                if (deletedNode.getParent(dataElement) == null) {
    1239
    1240                    // empty tree
    1241                    rootNode[dataElement.ordinal()] = null;
    1242                } else {
    1243
    1244                    // deleted node had no children
    1245                    if (isBlack(deletedNode, dataElement)) {
    1246                        doRedBlackDeleteFixup(deletedNode, dataElement);
    1247                    }
    1248
    1249                    if (deletedNode.getParent(dataElement) != null) {
    1250                        if (deletedNode == deletedNode.getParent(dataElement).getLeft(dataElement)) {
    1251                            deletedNode.getParent(dataElement).setLeft(null, dataElement);
    1252                        } else {
    1253                            deletedNode.getParent(dataElement).setRight(null, dataElement);
    1254                        }
    1255
    1256                        deletedNode.setParent(null, dataElement);
    1257                    }
    1258                }
    1259            }
    1260        }
    1261        shrink();
    1262    }
    1263
    1264    /**
    1265     * Complicated red-black delete stuff. Based on Sun's TreeMap
    1266     * implementation, though it's barely recognizable anymore. This
    1267     * rebalances the tree (somewhat, as red-black trees are not
    1268     * perfectly balanced -- perfect balancing takes longer)
    1269     *
    1270     * @param replacementNode the node being replaced
    1271     * @param dataElement  the KEY or VALUE int
    1272     */
    1273    private void doRedBlackDeleteFixup(final Node<K, V> replacementNode, final DataElement dataElement) {
    1274        Node<K, V> currentNode = replacementNode;
    1275
    1276        while (currentNode != rootNode[dataElement.ordinal()] && isBlack(currentNode, dataElement)) {
    1277            if (currentNode.isLeftChild(dataElement)) {
    1278                Node<K, V> siblingNode = getRightChild(getParent(currentNode, dataElement), dataElement);
    1279
    1280                if (isRed(siblingNode, dataElement)) {
    1281                    makeBlack(siblingNode, dataElement);
    1282                    makeRed(getParent(currentNode, dataElement), dataElement);
    1283                    rotateLeft(getParent(currentNode, dataElement), dataElement);
    1284
    1285                    siblingNode = getRightChild(getParent(currentNode, dataElement), dataElement);
    1286                }
    1287
    1288                if (isBlack(getLeftChild(siblingNode, dataElement), dataElement)
    1289                    && isBlack(getRightChild(siblingNode, dataElement), dataElement)) {
    1290                    makeRed(siblingNode, dataElement);
    1291
    1292                    currentNode = getParent(currentNode, dataElement);
    1293                } else {
    1294                    if (isBlack(getRightChild(siblingNode, dataElement), dataElement)) {
    1295                        makeBlack(getLeftChild(siblingNode, dataElement), dataElement);
    1296                        makeRed(siblingNode, dataElement);
    1297                        rotateRight(siblingNode, dataElement);
    1298
    1299                        siblingNode = getRightChild(getParent(currentNode, dataElement), dataElement);
    1300                    }
    1301
    1302                    copyColor(getParent(currentNode, dataElement), siblingNode, dataElement);
    1303                    makeBlack(getParent(currentNode, dataElement), dataElement);
    1304                    makeBlack(getRightChild(siblingNode, dataElement), dataElement);
    1305                    rotateLeft(getParent(currentNode, dataElement), dataElement);
    1306
    1307                    currentNode = rootNode[dataElement.ordinal()];
    1308                }
    1309            } else {
    1310                Node<K, V> siblingNode = getLeftChild(getParent(currentNode, dataElement), dataElement);
    1311
    1312                if (isRed(siblingNode, dataElement)) {
    1313                    makeBlack(siblingNode, dataElement);
    1314                    makeRed(getParent(currentNode, dataElement), dataElement);
    1315                    rotateRight(getParent(currentNode, dataElement), dataElement);
    1316
    1317                    siblingNode = getLeftChild(getParent(currentNode, dataElement), dataElement);
    1318                }
    1319
    1320                if (isBlack(getRightChild(siblingNode, dataElement), dataElement)
    1321                    && isBlack(getLeftChild(siblingNode, dataElement), dataElement)) {
    1322                    makeRed(siblingNode, dataElement);
    1323
    1324                    currentNode = getParent(currentNode, dataElement);
    1325                } else {
    1326                    if (isBlack(getLeftChild(siblingNode, dataElement), dataElement)) {
    1327                        makeBlack(getRightChild(siblingNode, dataElement), dataElement);
    1328                        makeRed(siblingNode, dataElement);
    1329                        rotateLeft(siblingNode, dataElement);
    1330
    1331                        siblingNode = getLeftChild(getParent(currentNode, dataElement), dataElement);
    1332                    }
    1333
    1334                    copyColor(getParent(currentNode, dataElement), siblingNode, dataElement);
    1335                    makeBlack(getParent(currentNode, dataElement), dataElement);
    1336                    makeBlack(getLeftChild(siblingNode, dataElement), dataElement);
    1337                    rotateRight(getParent(currentNode, dataElement), dataElement);
    1338
    1339                    currentNode = rootNode[dataElement.ordinal()];
    1340                }
    1341            }
    1342        }
    1343
    1344        makeBlack(currentNode, dataElement);
    1345    }
    1346
    1347    /**
    1348     * Complicated red-black insert stuff. Based on Sun's TreeMap
    1349     * implementation, though it's barely recognizable anymore.
    1350     *
    1351     * @param insertedNode the node to be inserted
    1352     * @param dataElement  the KEY or VALUE int
    1353     */
    1354    private void doRedBlackInsert(final Node<K, V> insertedNode, final DataElement dataElement) {
    1355        Node<K, V> currentNode = insertedNode;
    1356        makeRed(currentNode, dataElement);
    1357
    1358        while (currentNode != null
    1359            && currentNode != rootNode[dataElement.ordinal()]
    1360            && isRed(currentNode.getParent(dataElement), dataElement)) {
    1361            if (currentNode.isLeftChild(dataElement)) {
    1362                final Node<K, V> y = getRightChild(getGrandParent(currentNode, dataElement), dataElement);
    1363
    1364                if (isRed(y, dataElement)) {
    1365                    makeBlack(getParent(currentNode, dataElement), dataElement);
    1366                    makeBlack(y, dataElement);
    1367                    makeRed(getGrandParent(currentNode, dataElement), dataElement);
    1368
    1369                    currentNode = getGrandParent(currentNode, dataElement);
    1370                } else {
    1371                    //dead code?
    1372                    if (currentNode.isRightChild(dataElement)) {
    1373                        currentNode = getParent(currentNode, dataElement);
    1374
    1375                        rotateLeft(currentNode, dataElement);
    1376                    }
    1377
    1378                    makeBlack(getParent(currentNode, dataElement), dataElement);
    1379                    makeRed(getGrandParent(currentNode, dataElement), dataElement);
    1380
    1381                    if (getGrandParent(currentNode, dataElement) != null) {
    1382                        rotateRight(getGrandParent(currentNode, dataElement), dataElement);
    1383                    }
    1384                }
    1385            } else {
    1386
    1387                // just like clause above, except swap left for right
    1388                final Node<K, V> y = getLeftChild(getGrandParent(currentNode, dataElement), dataElement);
    1389
    1390                if (isRed(y, dataElement)) {
    1391                    makeBlack(getParent(currentNode, dataElement), dataElement);
    1392                    makeBlack(y, dataElement);
    1393                    makeRed(getGrandParent(currentNode, dataElement), dataElement);
    1394
    1395                    currentNode = getGrandParent(currentNode, dataElement);
    1396                } else {
    1397                    //dead code?
    1398                    if (currentNode.isLeftChild(dataElement)) {
    1399                        currentNode = getParent(currentNode, dataElement);
    1400
    1401                        rotateRight(currentNode, dataElement);
    1402                    }
    1403
    1404                    makeBlack(getParent(currentNode, dataElement), dataElement);
    1405                    makeRed(getGrandParent(currentNode, dataElement), dataElement);
    1406
    1407                    if (getGrandParent(currentNode, dataElement) != null) {
    1408                        rotateLeft(getGrandParent(currentNode, dataElement), dataElement);
    1409                    }
    1410                }
    1411            }
    1412        }
    1413
    1414        makeBlack(rootNode[dataElement.ordinal()], dataElement);
    1415    }
    1416
    1417    private V doRemoveKey(final Object key) {
    1418        final Node<K, V> node = lookupKey(key);
    1419        if (node == null) {
    1420            return null;
    1421        }
    1422        doRedBlackDelete(node);
    1423        return node.getValue();
    1424    }
    1425
    1426    private K doRemoveValue(final Object value) {
    1427        final Node<K, V> node = lookupValue(value);
    1428        if (node == null) {
    1429            return null;
    1430        }
    1431        doRedBlackDelete(node);
    1432        return node.getKey();
    1433    }
    1434
    1435    /**
    1436     * Gets the string form of this map as per AbstractMap.
    1437     *
    1438     * @param dataElement  either the {@link DataElement#KEY key}
    1439     *                     or the {@link DataElement#VALUE value}.
    1440     * @return the string form of this map
    1441     */
    1442    private String doToString(final DataElement dataElement) {
    1443        if (nodeCount == 0) {
    1444            return "{}";
    1445        }
    1446        final StringBuilder buf = new StringBuilder(nodeCount * 32);
    1447        buf.append('{');
    1448        final MapIterator<?, ?> it = getMapIterator(dataElement);
    1449        boolean hasNext = it.hasNext();
    1450        while (hasNext) {
    1451            final Object key = it.next();
    1452            final Object value = it.getValue();
    1453            buf.append(key == this ? "(this Map)" : key)
    1454                .append('=')
    1455                .append(value == this ? "(this Map)" : value);
    1456
    1457            hasNext = it.hasNext();
    1458            if (hasNext) {
    1459                buf.append(", ");
    1460            }
    1461        }
    1462
    1463        buf.append('}');
    1464        return buf.toString();
    1465    }
    1466
    1467    /**
    1468     * Returns a set view of the entries contained in this map in key order.
    1469     * For simple iteration through the map, the MapIterator is quicker.
    1470     * <p>
    1471     * The set is backed by the map, so changes to the map are reflected in
    1472     * the set, and vice-versa. If the map is modified while an iteration over
    1473     * the set is in progress, the results of the iteration are undefined.
    1474     * <p>
    1475     * The set supports element removal, which removes the corresponding mapping
    1476     * from the map. It does not support the add or addAll operations.
    1477     * The returned MapEntry objects do not support setValue.
    1478     *
    1479     * @return a set view of the values contained in this map.
    1480     */
    1481    @Override
    1482    public Set<Map.Entry<K, V>> entrySet() {
    1483        if (entrySet == null) {
    1484            entrySet = new EntryView();
    1485        }
    1486        return entrySet;
    1487    }
    1488
    1489    /**
    1490     * Compares for equals as per the API.
    1491     *
    1492     * @param obj  the object to compare to
    1493     * @return true if equal
    1494     */
    1495    @Override
    1496    public boolean equals(final Object obj) {
    1497        return this.doEquals(obj, KEY);
    1498    }
    1499
    1500    /**
    1501     * Gets the first (lowest) key currently in this map.
    1502     *
    1503     * @return the first (lowest) key currently in this sorted map
    1504     * @throws NoSuchElementException if this map is empty
    1505     */
    1506    @Override
    1507    public K firstKey() {
    1508        if (nodeCount == 0) {
    1509            throw new NoSuchElementException("Map is empty");
    1510        }
    1511        return leastNode(rootNode[KEY.ordinal()], KEY).getKey();
    1512    }
    1513
    1514    /**
    1515     * Gets the value to which this map maps the specified key.
    1516     * Returns null if the map contains no mapping for this key.
    1517     * <p>
    1518     * The key must implement {@code Comparable}.
    1519     *
    1520     * @param key  key whose associated value is to be returned
    1521     * @return the value to which this map maps the specified key,
    1522     *  or null if the map contains no mapping for this key
    1523     * @throws ClassCastException if the key is of an inappropriate type
    1524     * @throws NullPointerException if the key is null
    1525     */
    1526    @Override
    1527    public V get(final Object key) {
    1528        checkKey(key);
    1529        final Node<K, V> node = lookupKey(key);
    1530        return node == null ? null : node.getValue();
    1531    }
    1532
    1533    /**
    1534     * Gets a node's grandparent. mind you, the node, its parent, or
    1535     * its grandparent may not exist. No problem.
    1536     *
    1537     * @param node the node (may be null) in question
    1538     * @param dataElement  either the {@link DataElement#KEY key}
    1539     *                     or the {@link DataElement#VALUE value}.
    1540     */
    1541    private Node<K, V> getGrandParent(final Node<K, V> node, final DataElement dataElement) {
    1542        return getParent(getParent(node, dataElement), dataElement);
    1543    }
    1544
    1545    /**
    1546     * Returns the key to which this map maps the specified value.
    1547     * Returns null if the map contains no mapping for this value.
    1548     * <p>
    1549     * The value must implement {@code Comparable}.
    1550     *
    1551     * @param value  value whose associated key is to be returned.
    1552     * @return the key to which this map maps the specified value,
    1553     *  or null if the map contains no mapping for this value.
    1554     * @throws ClassCastException if the value is of an inappropriate type
    1555     * @throws NullPointerException if the value is null
    1556     */
    1557    @Override
    1558    public K getKey(final Object value) {
    1559        checkValue(value);
    1560        final Node<K, V> node = lookupValue(value);
    1561        return node == null ? null : node.getKey();
    1562    }
    1563
    1564    /**
    1565     * Gets a node's left child. mind you, the node may not exist. no
    1566     * problem.
    1567     *
    1568     * @param node the node (may be null) in question
    1569     * @param dataElement  either the {@link DataElement#KEY key}
    1570     *                     or the {@link DataElement#VALUE value}.
    1571     */
    1572    private Node<K, V> getLeftChild(final Node<K, V> node, final DataElement dataElement) {
    1573        return node == null ? null : node.getLeft(dataElement);
    1574    }
    1575
    1576    private MapIterator<?, ?> getMapIterator(final DataElement dataElement) {
    1577        switch (dataElement) {
    1578        case KEY:
    1579            return new ViewMapIterator(KEY);
    1580        case VALUE:
    1581            return new InverseViewMapIterator(VALUE);
    1582        default:
    1583            throw new IllegalArgumentException();
    1584        }
    1585    }
    1586
    1587    /**
    1588     * Gets a node's parent. mind you, the node, or its parent, may not
    1589     * exist. no problem.
    1590     *
    1591     * @param node the node (may be null) in question
    1592     * @param dataElement  either the {@link DataElement#KEY key}
    1593     *                     or the {@link DataElement#VALUE value}.
    1594     */
    1595    private Node<K, V> getParent(final Node<K, V> node, final DataElement dataElement) {
    1596        return node == null ? null : node.getParent(dataElement);
    1597    }
    1598
    1599    /**
    1600     * Gets a node's right child. mind you, the node may not exist. no
    1601     * problem.
    1602     *
    1603     * @param node the node (may be null) in question
    1604     * @param dataElement  either the {@link DataElement#KEY key}
    1605     *                     or the {@link DataElement#VALUE value}.
    1606     */
    1607    private Node<K, V> getRightChild(final Node<K, V> node, final DataElement dataElement) {
    1608        return node == null ? null : node.getRight(dataElement);
    1609    }
    1610
    1611    /**
    1612     * Finds the greatest node from a given node.
    1613     *
    1614     * @param node  the node from which we will start searching
    1615     * @param dataElement  either the {@link DataElement#KEY key}
    1616     *                     or the {@link DataElement#VALUE value}.
    1617     * @return the greatest node, from the specified node
    1618     */
    1619    private Node<K, V> greatestNode(final Node<K, V> node, final DataElement dataElement) {
    1620        Node<K, V> rval = node;
    1621        if (rval != null) {
    1622            while (rval.getRight(dataElement) != null) {
    1623                rval = rval.getRight(dataElement);
    1624            }
    1625        }
    1626        return rval;
    1627    }
    1628
    1629    /**
    1630     * Bumps up the size and note that the map has changed.
    1631     */
    1632    private void grow() {
    1633        modify();
    1634        nodeCount++;
    1635    }
    1636
    1637    /**
    1638     * Gets the hash code value for this map as per the API.
    1639     *
    1640     * @return the hash code value for this map
    1641     */
    1642    @Override
    1643    public int hashCode() {
    1644        return this.doHashCode(KEY);
    1645    }
    1646
    1647    /**
    1648     * Inserts a node by its value.
    1649     *
    1650     * @param newNode the node to be inserted
    1651     * @throws IllegalArgumentException if the node already exists
    1652     *                                     in the value mapping
    1653     */
    1654    private void insertValue(final Node<K, V> newNode) throws IllegalArgumentException {
    1655        Node<K, V> node = rootNode[VALUE.ordinal()];
    1656
    1657        while (true) {
    1658            final int cmp = compare(newNode.getValue(), node.getValue());
    1659
    1660            if (cmp == 0) {
    1661                throw new IllegalArgumentException(
    1662                    "Cannot store a duplicate value (\"" + newNode.getData(VALUE) + "\") in this Map");
    1663            }
    1664            if (cmp < 0) {
    1665                if (node.getLeft(VALUE) == null) {
    1666                    node.setLeft(newNode, VALUE);
    1667                    newNode.setParent(node, VALUE);
    1668                    doRedBlackInsert(newNode, VALUE);
    1669
    1670                    break;
    1671                }
    1672                node = node.getLeft(VALUE);
    1673            } else { // cmp > 0
    1674                if (node.getRight(VALUE) == null) {
    1675                    node.setRight(newNode, VALUE);
    1676                    newNode.setParent(node, VALUE);
    1677                    doRedBlackInsert(newNode, VALUE);
    1678
    1679                    break;
    1680                }
    1681                node = node.getRight(VALUE);
    1682            }
    1683        }
    1684    }
    1685
    1686    /**
    1687     * Gets the inverse map for comparison.
    1688     *
    1689     * @return the inverse map
    1690     */
    1691    @Override
    1692    public OrderedBidiMap<V, K> inverseBidiMap() {
    1693        if (inverse == null) {
    1694            inverse = new Inverse();
    1695        }
    1696        return inverse;
    1697    }
    1698
    1699    /**
    1700     * Checks whether the map is empty or not.
    1701     *
    1702     * @return true if the map is empty
    1703     */
    1704    @Override
    1705    public boolean isEmpty() {
    1706        return nodeCount == 0;
    1707    }
    1708
    1709    /**
    1710     * Returns a set view of the keys contained in this map in key order.
    1711     * <p>
    1712     * The set is backed by the map, so changes to the map are reflected in
    1713     * the set, and vice-versa. If the map is modified while an iteration over
    1714     * the set is in progress, the results of the iteration are undefined.
    1715     * <p>
    1716     * The set supports element removal, which removes the corresponding mapping
    1717     * from the map. It does not support the add or addAll operations.
    1718     *
    1719     * @return a set view of the keys contained in this map.
    1720     */
    1721    @Override
    1722    public Set<K> keySet() {
    1723        if (keySet == null) {
    1724            keySet = new KeyView(KEY);
    1725        }
    1726        return keySet;
    1727    }
    1728
    1729    /**
    1730     * Gets the last (highest) key currently in this map.
    1731     *
    1732     * @return the last (highest) key currently in this sorted map
    1733     * @throws NoSuchElementException if this map is empty
    1734     */
    1735    @Override
    1736    public K lastKey() {
    1737        if (nodeCount == 0) {
    1738            throw new NoSuchElementException("Map is empty");
    1739        }
    1740        return greatestNode(rootNode[KEY.ordinal()], KEY).getKey();
    1741    }
    1742
    1743    /**
    1744     * Finds the least node from a given node.
    1745     *
    1746     * @param node  the node from which we will start searching
    1747     * @param dataElement  either the {@link DataElement#KEY key}
    1748     *                     or the {@link DataElement#VALUE value}.
    1749     * @return the smallest node, from the specified node, in the
    1750     *         specified mapping
    1751     */
    1752    private Node<K, V> leastNode(final Node<K, V> node, final DataElement dataElement) {
    1753        Node<K, V> rval = node;
    1754        if (rval != null) {
    1755            while (rval.getLeft(dataElement) != null) {
    1756                rval = rval.getLeft(dataElement);
    1757            }
    1758        }
    1759        return rval;
    1760    }
    1761
    1762    /**
    1763     * Does the actual lookup of a piece of data.
    1764     *
    1765     * @param data the key or value to be looked up
    1766     * @param dataElement  either the {@link DataElement#KEY key}
    1767     *                     or the {@link DataElement#VALUE value}.
    1768     * @return the desired Node, or null if there is no mapping of the
    1769     *         specified data
    1770     */
    1771    @SuppressWarnings("unchecked")
    1772    private <T extends Comparable<T>> Node<K, V> lookup(final Object data, final DataElement dataElement) {
    1773        Node<K, V> rval = null;
    1774        Node<K, V> node = rootNode[dataElement.ordinal()];
    1775
    1776        while (node != null) {
    1777            final int cmp = compare((T) data, (T) node.getData(dataElement));
    1778            if (cmp == 0) {
    1779                rval = node;
    1780                break;
    1781            }
    1782            node = cmp < 0 ? node.getLeft(dataElement) : node.getRight(dataElement);
    1783        }
    1784
    1785        return rval;
    1786    }
    1787
    1788    private Node<K, V> lookupKey(final Object key) {
    1789        return this.<K>lookup(key, KEY);
    1790    }
    1791
    1792    private Node<K, V> lookupValue(final Object value) {
    1793        return this.<V>lookup(value, VALUE);
    1794    }
    1795
    1796    @Override
    1797    public OrderedMapIterator<K, V> mapIterator() {
    1798        if (isEmpty()) {
    1799            return EmptyOrderedMapIterator.<K, V>emptyOrderedMapIterator();
    1800        }
    1801        return new ViewMapIterator(KEY);
    1802    }
    1803
    1804    /**
    1805     * Increments the modification count -- used to check for
    1806     * concurrent modification of the map through the map and through
    1807     * an Iterator from one of its Set or Collection views.
    1808     */
    1809    private void modify() {
    1810        modifications++;
    1811    }
    1812
    1813    /**
    1814     * Gets the next larger node from the specified node.
    1815     *
    1816     * @param node the node to be searched from
    1817     * @param dataElement  either the {@link DataElement#KEY key}
    1818     *                     or the {@link DataElement#VALUE value}.
    1819     * @return the specified node
    1820     */
    1821    private Node<K, V> nextGreater(final Node<K, V> node, final DataElement dataElement) {
    1822        final Node<K, V> rval;
    1823        if (node == null) {
    1824            rval = null;
    1825        } else if (node.getRight(dataElement) != null) {
    1826            // everything to the node's right is larger. The least of
    1827            // the right node's descendants is the next larger node
    1828            rval = leastNode(node.getRight(dataElement), dataElement);
    1829        } else {
    1830            // traverse up our ancestry until we find an ancestor that
    1831            // is null or one whose left child is our ancestor. If we
    1832            // find a null, then this node IS the largest node in the
    1833            // tree, and there is no greater node. Otherwise, we are
    1834            // the largest node in the subtree on that ancestor's left
    1835            // ... and that ancestor is the next greatest node
    1836            Node<K, V> parent = node.getParent(dataElement);
    1837            Node<K, V> child = node;
    1838
    1839            while (parent != null && child == parent.getRight(dataElement)) {
    1840                child = parent;
    1841                parent = parent.getParent(dataElement);
    1842            }
    1843            rval = parent;
    1844        }
    1845        return rval;
    1846    }
    1847
    1848    /**
    1849     * Gets the next key after the one specified.
    1850     * <p>
    1851     * The key must implement {@code Comparable}.
    1852     *
    1853     * @param key the key to search for next from
    1854     * @return the next key, null if no match or at end
    1855     */
    1856    @Override
    1857    public K nextKey(final K key) {
    1858        checkKey(key);
    1859        final Node<K, V> node = nextGreater(lookupKey(key), KEY);
    1860        return node == null ? null : node.getKey();
    1861    }
    1862
    1863    /**
    1864     * Gets the next smaller node from the specified node.
    1865     *
    1866     * @param node the node to be searched from
    1867     * @param dataElement  either the {@link DataElement#KEY key}
    1868     *                     or the {@link DataElement#VALUE value}.
    1869     * @return the specified node
    1870     */
    1871    private Node<K, V> nextSmaller(final Node<K, V> node, final DataElement dataElement) {
    1872        final Node<K, V> rval;
    1873        if (node == null) {
    1874            rval = null;
    1875        } else if (node.getLeft(dataElement) != null) {
    1876            // everything to the node's left is smaller. The greatest of
    1877            // the left node's descendants is the next smaller node
    1878            rval = greatestNode(node.getLeft(dataElement), dataElement);
    1879        } else {
    1880            // traverse up our ancestry until we find an ancestor that
    1881            // is null or one whose right child is our ancestor. If we
    1882            // find a null, then this node IS the largest node in the
    1883            // tree, and there is no greater node. Otherwise, we are
    1884            // the largest node in the subtree on that ancestor's right
    1885            // ... and that ancestor is the next greatest node
    1886            Node<K, V> parent = node.getParent(dataElement);
    1887            Node<K, V> child = node;
    1888
    1889            while (parent != null && child == parent.getLeft(dataElement)) {
    1890                child = parent;
    1891                parent = parent.getParent(dataElement);
    1892            }
    1893            rval = parent;
    1894        }
    1895        return rval;
    1896    }
    1897
    1898    /**
    1899     * Gets the previous key before the one specified.
    1900     * <p>
    1901     * The key must implement {@code Comparable}.
    1902     *
    1903     * @param key the key to search for previous from
    1904     * @return the previous key, null if no match or at start
    1905     */
    1906    @Override
    1907    public K previousKey(final K key) {
    1908        checkKey(key);
    1909        final Node<K, V> node = nextSmaller(lookupKey(key), KEY);
    1910        return node == null ? null : node.getKey();
    1911    }
    1912
    1913    /**
    1914     * Puts the key-value pair into the map, replacing any previous pair.
    1915     * <p>
    1916     * When adding a key-value pair, the value may already exist in the map
    1917     * against a different key. That mapping is removed, to ensure that the
    1918     * value only occurs once in the inverse map.
    1919     * <pre>
    1920     *  BidiMap map1 = new TreeBidiMap();
    1921     *  map.put("A","B");  // contains A mapped to B, as per Map
    1922     *  map.put("A","C");  // contains A mapped to C, as per Map
    1923     *
    1924     *  BidiMap map2 = new TreeBidiMap();
    1925     *  map.put("A","B");  // contains A mapped to B, as per Map
    1926     *  map.put("C","B");  // contains C mapped to B, key A is removed
    1927     * </pre>
    1928     * <p>
    1929     * Both key and value must implement {@code Comparable}.
    1930     *
    1931     * @param key  key with which the specified value is to be  associated
    1932     * @param value  value to be associated with the specified key
    1933     * @return the previous value for the key
    1934     * @throws ClassCastException if the key is of an inappropriate type
    1935     * @throws NullPointerException if the key is null
    1936     */
    1937    @Override
    1938    public V put(final K key, final V value) {
    1939        final V result = get(key);
    1940        doPut(key, value);
    1941        return result;
    1942    }
    1943
    1944    /**
    1945     * Puts all the mappings from the specified map into this map.
    1946     * <p>
    1947     * All keys and values must implement {@code Comparable}.
    1948     *
    1949     * @param map  the map to copy from
    1950     */
    1951    @Override
    1952    public void putAll(final Map<? extends K, ? extends V> map) {
    1953        for (final Map.Entry<? extends K, ? extends V> e : map.entrySet()) {
    1954            put(e.getKey(), e.getValue());
    1955        }
    1956    }
    1957
    1958    /**
    1959     * Deserializes the content of the stream.
    1960     *
    1961     * @param stream the input stream
    1962     * @throws IOException if an error occurs while reading from the stream
    1963     * @throws ClassNotFoundException if an object read from the stream cannot be loaded
    1964     */
    1965    @SuppressWarnings("unchecked") // This will fail at runtime if the stream is incorrect
    1966    private void readObject(final ObjectInputStream stream) throws IOException, ClassNotFoundException {
    1967        stream.defaultReadObject();
    1968        rootNode = new Node[2];
    1969        final int size = stream.readInt();
    1970        for (int i = 0; i < size; i++) {
    1971            final K k = (K) stream.readObject();
    1972            final V v = (V) stream.readObject();
    1973            put(k, v);
    1974        }
    1975    }
    1976
    1977    /**
    1978     * Removes the mapping for this key from this map if present.
    1979     * <p>
    1980     * The key must implement {@code Comparable}.
    1981     *
    1982     * @param key  key whose mapping is to be removed from the map.
    1983     * @return previous value associated with specified key,
    1984     *  or null if there was no mapping for key.
    1985     * @throws ClassCastException if the key is of an inappropriate type
    1986     * @throws NullPointerException if the key is null
    1987     */
    1988    @Override
    1989    public V remove(final Object key) {
    1990        return doRemoveKey(key);
    1991    }
    1992
    1993    /**
    1994     * Removes the mapping for this value from this map if present.
    1995     * <p>
    1996     * The value must implement {@code Comparable}.
    1997     *
    1998     * @param value  value whose mapping is to be removed from the map
    1999     * @return previous key associated with specified value,
    2000     *  or null if there was no mapping for value.
    2001     * @throws ClassCastException if the value is of an inappropriate type
    2002     * @throws NullPointerException if the value is null
    2003     */
    2004    @Override
    2005    public K removeValue(final Object value) {
    2006        return doRemoveValue(value);
    2007    }
    2008
    2009    /**
    2010     * Does a rotate left. standard fare in the world of balanced trees.
    2011     *
    2012     * @param node the node to be rotated
    2013     * @param dataElement  either the {@link DataElement#KEY key}
    2014     *                     or the {@link DataElement#VALUE value}.
    2015     */
    2016    private void rotateLeft(final Node<K, V> node, final DataElement dataElement) {
    2017        final Node<K, V> rightChild = node.getRight(dataElement);
    2018        node.setRight(rightChild.getLeft(dataElement), dataElement);
    2019
    2020        if (rightChild.getLeft(dataElement) != null) {
    2021            rightChild.getLeft(dataElement).setParent(node, dataElement);
    2022        }
    2023        rightChild.setParent(node.getParent(dataElement), dataElement);
    2024
    2025        if (node.getParent(dataElement) == null) {
    2026            // node was the root ... now its right child is the root
    2027            rootNode[dataElement.ordinal()] = rightChild;
    2028        } else if (node.getParent(dataElement).getLeft(dataElement) == node) {
    2029            node.getParent(dataElement).setLeft(rightChild, dataElement);
    2030        } else {
    2031            node.getParent(dataElement).setRight(rightChild, dataElement);
    2032        }
    2033
    2034        rightChild.setLeft(node, dataElement);
    2035        node.setParent(rightChild, dataElement);
    2036    }
    2037
    2038    /**
    2039     * Does a rotate right. standard fare in the world of balanced trees.
    2040     *
    2041     * @param node the node to be rotated
    2042     * @param dataElement  either the {@link DataElement#KEY key}
    2043     *                     or the {@link DataElement#VALUE value}.
    2044     */
    2045    private void rotateRight(final Node<K, V> node, final DataElement dataElement) {
    2046        final Node<K, V> leftChild = node.getLeft(dataElement);
    2047        node.setLeft(leftChild.getRight(dataElement), dataElement);
    2048        if (leftChild.getRight(dataElement) != null) {
    2049            leftChild.getRight(dataElement).setParent(node, dataElement);
    2050        }
    2051        leftChild.setParent(node.getParent(dataElement), dataElement);
    2052
    2053        if (node.getParent(dataElement) == null) {
    2054            // node was the root ... now its left child is the root
    2055            rootNode[dataElement.ordinal()] = leftChild;
    2056        } else if (node.getParent(dataElement).getRight(dataElement) == node) {
    2057            node.getParent(dataElement).setRight(leftChild, dataElement);
    2058        } else {
    2059            node.getParent(dataElement).setLeft(leftChild, dataElement);
    2060        }
    2061
    2062        leftChild.setRight(node, dataElement);
    2063        node.setParent(leftChild, dataElement);
    2064    }
    2065
    2066    /**
    2067     * Decrements the size and note that the map has changed.
    2068     */
    2069    private void shrink() {
    2070        modify();
    2071        nodeCount--;
    2072    }
    2073
    2074    /**
    2075     * Returns the number of key-value mappings in this map.
    2076     *
    2077     * @return the number of key-value mappings in this map
    2078     */
    2079    @Override
    2080    public int size() {
    2081        return nodeCount;
    2082    }
    2083
    2084    /**
    2085     * Swaps two nodes (except for their content), taking care of
    2086     * special cases where one is the other's parent ... hey, it
    2087     * happens.
    2088     *
    2089     * @param x one node
    2090     * @param y another node
    2091     * @param dataElement  the KEY or VALUE int
    2092     */
    2093    private void swapPosition(final Node<K, V> x, final Node<K, V> y, final DataElement dataElement) {
    2094        // Save initial values.
    2095        final Node<K, V> xFormerParent = x.getParent(dataElement);
    2096        final Node<K, V> xFormerLeftChild = x.getLeft(dataElement);
    2097        final Node<K, V> xFormerRightChild = x.getRight(dataElement);
    2098        final Node<K, V> yFormerParent = y.getParent(dataElement);
    2099        final Node<K, V> yFormerLeftChild = y.getLeft(dataElement);
    2100        final Node<K, V> yFormerRightChild = y.getRight(dataElement);
    2101        final boolean xWasLeftChild =
    2102                x.getParent(dataElement) != null && x == x.getParent(dataElement).getLeft(dataElement);
    2103        final boolean yWasLeftChild =
    2104                y.getParent(dataElement) != null && y == y.getParent(dataElement).getLeft(dataElement);
    2105
    2106        // Swap, handling special cases of one being the other's parent.
    2107        if (x == yFormerParent) { // x was y's parent
    2108            x.setParent(y, dataElement);
    2109
    2110            if (yWasLeftChild) {
    2111                y.setLeft(x, dataElement);
    2112                y.setRight(xFormerRightChild, dataElement);
    2113            } else {
    2114                y.setRight(x, dataElement);
    2115                y.setLeft(xFormerLeftChild, dataElement);
    2116            }
    2117        } else {
    2118            x.setParent(yFormerParent, dataElement);
    2119
    2120            if (yFormerParent != null) {
    2121                if (yWasLeftChild) {
    2122                    yFormerParent.setLeft(x, dataElement);
    2123                } else {
    2124                    yFormerParent.setRight(x, dataElement);
    2125                }
    2126            }
    2127
    2128            y.setLeft(xFormerLeftChild, dataElement);
    2129            y.setRight(xFormerRightChild, dataElement);
    2130        }
    2131
    2132        if (y == xFormerParent) { // y was x's parent
    2133            y.setParent(x, dataElement);
    2134
    2135            if (xWasLeftChild) {
    2136                x.setLeft(y, dataElement);
    2137                x.setRight(yFormerRightChild, dataElement);
    2138            } else {
    2139                x.setRight(y, dataElement);
    2140                x.setLeft(yFormerLeftChild, dataElement);
    2141            }
    2142        } else {
    2143            y.setParent(xFormerParent, dataElement);
    2144
    2145            if (xFormerParent != null) {
    2146                if (xWasLeftChild) {
    2147                    xFormerParent.setLeft(y, dataElement);
    2148                } else {
    2149                    xFormerParent.setRight(y, dataElement);
    2150                }
    2151            }
    2152
    2153            x.setLeft(yFormerLeftChild, dataElement);
    2154            x.setRight(yFormerRightChild, dataElement);
    2155        }
    2156
    2157        // Fix children's parent pointers
    2158        if (x.getLeft(dataElement) != null) {
    2159            x.getLeft(dataElement).setParent(x, dataElement);
    2160        }
    2161
    2162        if (x.getRight(dataElement) != null) {
    2163            x.getRight(dataElement).setParent(x, dataElement);
    2164        }
    2165
    2166        if (y.getLeft(dataElement) != null) {
    2167            y.getLeft(dataElement).setParent(y, dataElement);
    2168        }
    2169
    2170        if (y.getRight(dataElement) != null) {
    2171            y.getRight(dataElement).setParent(y, dataElement);
    2172        }
    2173
    2174        x.swapColors(y, dataElement);
    2175
    2176        // Check if root changed
    2177        if (rootNode[dataElement.ordinal()] == x) {
    2178            rootNode[dataElement.ordinal()] = y;
    2179        } else if (rootNode[dataElement.ordinal()] == y) {
    2180            rootNode[dataElement.ordinal()] = x;
    2181        }
    2182    }
    2183
    2184    /**
    2185     * Returns a string version of this Map in standard format.
    2186     *
    2187     * @return a standard format string version of the map
    2188     */
    2189    @Override
    2190    public String toString() {
    2191        return this.doToString(KEY);
    2192    }
    2193
    2194    /**
    2195     * Returns a set view of the values contained in this map in key order.
    2196     * The returned object can be cast to a Set.
    2197     * <p>
    2198     * The set is backed by the map, so changes to the map are reflected in
    2199     * the set, and vice-versa. If the map is modified while an iteration over
    2200     * the set is in progress, the results of the iteration are undefined.
    2201     * <p>
    2202     * The set supports element removal, which removes the corresponding mapping
    2203     * from the map. It does not support the add or addAll operations.
    2204     *
    2205     * @return a set view of the values contained in this map.
    2206     */
    2207    @Override
    2208    public Set<V> values() {
    2209        if (valuesSet == null) {
    2210            valuesSet = new ValueView(KEY);
    2211        }
    2212        return valuesSet;
    2213    }
    2214
    2215    /**
    2216     * Serializes this object to an ObjectOutputStream.
    2217     *
    2218     * @param out the target ObjectOutputStream.
    2219     * @throws IOException thrown when an I/O errors occur writing to the target stream.
    2220     */
    2221    private void writeObject(final ObjectOutputStream out) throws IOException {
    2222        out.defaultWriteObject();
    2223        out.writeInt(this.size());
    2224        for (final Entry<K, V> entry : entrySet()) {
    2225            out.writeObject(entry.getKey());
    2226            out.writeObject(entry.getValue());
    2227        }
    2228    }
    2229
    2230}