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