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