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