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