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