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