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