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