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.fusesource.hawtdb.util;
018    
019    import java.io.Serializable;
020    import java.util.AbstractCollection;
021    import java.util.AbstractSet;
022    import java.util.Collection;
023    import java.util.Comparator;
024    import java.util.Iterator;
025    import java.util.Map;
026    import java.util.Set;
027    import java.util.Map.Entry;
028    
029    /**
030     * A TreeMap that is lighter weight than the Sun implementation with
031     * implementations for upper/lower/floor/ceiling accessors.
032     *
033     * @author <a href="http://hiramchirino.com">Hiram Chirino</a>
034     */
035    public class TreeMap<K, V> implements Serializable {
036    
037        private static final long serialVersionUID = 6107175734705142096L;
038        
039        private static final boolean RED = false;
040        private static final boolean BLACK = true;
041    
042        private int count;
043        private TreeEntry<K, V> root;
044        private final Comparator<? super K> comparator;
045    
046        public TreeMap() {
047            this.comparator = null;
048        }
049    
050        @SuppressWarnings("unchecked")
051        private int compare(K k1, K k2) {
052            if (comparator != null) {
053                return comparator.compare(k1, k2);
054            } else {
055                return ((Comparable<K>) k1).compareTo(k2);
056            }
057        }
058    
059        public TreeMap(Comparator<? super K> comparator) {
060            this.comparator = comparator;
061        }
062    
063        public Comparator<? super K> comparator() {
064            return comparator;
065        }
066    
067        /**
068         * 
069         * @return The first key in the map.
070         */
071        public K firstKey() {
072            TreeEntry<K, V> first = firstEntry();
073            if (first != null) {
074                return first.key;
075            }
076            return null;
077        }
078    
079        /**
080         * @return The last key in the map.
081         */
082        public K lastKey() {
083            TreeEntry<K, V> last = lastEntry();
084            if (last != null) {
085                return last.key;
086            }
087            return null;
088        }
089    
090        /**
091         * Clears all elements in this map.
092         */
093        public void clear() {
094            //TODO possible assist gc here by scanning and removing refs?
095            //Will almost certain want to do this if we switch this over
096            //to allowing additions to be the entries themselves.
097            root = null;
098            count = 0;
099        }
100    
101        /*
102         * (non-Javadoc)
103         * 
104         * @see java.util.Map#containsKey(java.lang.Object)
105         */
106        public boolean containsKey(K key) {
107            return getEntry(key, root) != null;
108        }
109    
110        /*
111         * (non-Javadoc)
112         * 
113         * @see java.util.Map#containsValue(java.lang.Object)
114         */
115        public boolean containsValue(Object value) {
116            for (Map.Entry<K, V> entry : entrySet()) {
117                if (entry.getValue() == value) {
118                    return true;
119                } else if (value != null && value.equals(entry)) {
120                    return true;
121                }
122            }
123            return false;
124        }
125    
126        /*
127         * (non-Javadoc)
128         * 
129         * @see java.util.Map#entrySet()
130         */
131        public Set<Map.Entry<K, V>> entrySet() {
132            return new AbstractSet<Map.Entry<K, V>>() {
133    
134                @Override
135                public Iterator<Entry<K, V>> iterator() {
136                    return new EntryIterator();
137                }
138    
139                @SuppressWarnings("unchecked")
140                @Override
141                public boolean contains(Object o) {
142                    try {
143                        Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
144                        TreeEntry<K, V> ours = getEntry(entry.getKey(), root);
145                        if (ours != null) {
146                            return ours.value == null ? entry.getValue() == null : ours.value.equals(entry.getValue());
147                        } else {
148                            return false;
149                        }
150                    } catch (ClassCastException cce) {
151                        return false;
152                    }
153                }
154    
155                @SuppressWarnings("unchecked")
156                @Override
157                public boolean remove(Object o) {
158                    return TreeMap.this.removeEntry((TreeEntry<K, V>) o) != null;
159                }
160    
161                @Override
162                public int size() {
163                    return count;
164                }
165    
166                @Override
167                public void clear() {
168                    TreeMap.this.clear();
169                }
170            };
171        }
172    
173        /*
174         * (non-Javadoc)
175         * 
176         * @see java.util.Map#get(java.lang.Object)
177         */
178        public V get(K key) {
179            TreeEntry<K, V> node = getEntry(key, root);
180            if (node != null) {
181                return node.value;
182            }
183            return null;
184        }
185    
186        public final TreeEntry<K, V> getEntry(K key) {
187            return getEntry(key, root);
188        }
189        
190        private final TreeEntry<K, V> getEntry(K key, TreeEntry<K, V> r) {
191            while (r != null) {
192                int c = compare(key, r.key);
193                if (c == 0) {
194                    return r;
195                } else if (c > 0) {
196                    r = r.right;
197                } else {
198                    r = r.left;
199                }
200            }
201            return null;
202        }
203    
204        /**
205         * Returns a key-value mapping associated with the least key in this map, or
206         * null if the map is empty.
207         * 
208         * @return The lowest key in the map
209         */
210        public TreeEntry<K, V> firstEntry() {
211            TreeEntry<K, V> r = root;
212            while (r != null) {
213                if (r.left == null) {
214                    break;
215                }
216                r = r.left;
217            }
218    
219            return r;
220        }
221    
222        /**
223         * Returns a key-value mapping associated with the greatest key in this map,
224         * or null if the map is empty.
225         * 
226         * @return The entry associated with the greates key in the map.
227         */
228        public TreeEntry<K, V> lastEntry() {
229            TreeEntry<K, V> r = root;
230            while (r != null) {
231                if (r.right == null) {
232                    break;
233                }
234                r = r.right;
235            }
236    
237            return r;
238        }
239    
240        /**
241         * Returns a key-value mapping associated with the greatest key strictly
242         * less than the given key, or null if there is no such key
243         * 
244         * @param key
245         *            the key.
246         * @return
247         */
248        public TreeEntry<K, V> lowerEntry(K key) {
249            TreeEntry<K, V> n = root;
250            TreeEntry<K, V> l = null;
251            while (n != null) {
252                int c = compare(key, n.key);
253                if (c <= 0) {
254                    n = n.left;
255                } else {
256                    //Update the low node:
257                    if (l == null || compare(n.key, l.key) > 0) {
258                        l = n;
259                    }
260                    //Now need to scan the right tree to see if there is
261                    //a higher low value to consider:
262                    if (n.right == null) {
263                        break;
264                    }
265                    n = n.right;
266                }
267            }
268            return l;
269        }
270    
271        /**
272         * Returns a key-value mapping associated with the greatest key less than or
273         * equal to the given key, or null if there is no such key.
274         * 
275         * @param key
276         *            The key for which to search.
277         * @return a key-value mapping associated with the greatest key less than or
278         *         equal to the given key, or null if there is no such key.
279         */
280        public TreeEntry<K, V> floorEntry(K key) {
281            TreeEntry<K, V> n = root;
282            TreeEntry<K, V> l = null;
283            while (n != null) {
284                int c = compare(key, n.key);
285                if (c == 0) {
286                    return n;
287                }
288    
289                if (c < 0) {
290                    n = n.left;
291                } else {
292                    //Update the low node:
293                    if (l == null || compare(n.key, l.key) > 0) {
294                        l = n;
295                    }
296                    //Now need to scan the right tree to see if there is
297                    //a higher low value to consider:
298                    if (n.right == null) {
299                        break;
300                    }
301                    n = n.right;
302                }
303            }
304            return l;
305        }
306    
307        /**
308         * Returns a key-value mapping associated with the lowest key strictly
309         * greater than the given key, or null if there is no such key
310         * 
311         * @param key
312         *            The key
313         * @return a key-value mapping associated with the lowest key strictly
314         *         greater than the given key
315         */
316        public TreeEntry<K, V> upperEntry(K key) {
317            TreeEntry<K, V> n = root;
318            TreeEntry<K, V> h = null;
319            while (n != null) {
320                int c = compare(key, n.key);
321                if (c >= 0) {
322                    n = n.right;
323                } else {
324                    //Update the high node:
325                    if (h == null || compare(n.key, h.key) < 0) {
326                        h = n;
327                    }
328                    //Now need to scan the left tree to see if there is
329                    //a lower high value to consider:
330                    if (n.left == null) {
331                        break;
332                    }
333                    n = n.left;
334                }
335            }
336            return h;
337        }
338    
339        /**
340         * Returns a key-value mapping associated with the least key greater than or
341         * equal to the given key, or null if there is no such key.
342         * 
343         * @param key
344         * @return
345         */
346        public TreeEntry<K, V> ceilingEntry(K key) {
347            TreeEntry<K, V> n = root;
348            TreeEntry<K, V> h = null;
349            while (n != null) {
350                int c = compare(key, n.key);
351                if (c == 0) {
352                    return n;
353                }
354    
355                if (c > 0) {
356                    n = n.right;
357                } else {
358                    //Update the high node:
359                    if (h == null || compare(n.key, h.key) < 0) {
360                        h = n;
361                    }
362                    //Now need to scan the left tree to see if there is
363                    //a lower high value to consider:
364                    if (n.left == null) {
365                        break;
366                    }
367                    n = n.left;
368                }
369            }
370            return h;
371        }
372    
373        static private final <K,V> TreeEntry<K, V> next(TreeEntry<K, V> n) {
374            if (n == null)
375                return null;
376            else if (n.right != null) {
377                TreeEntry<K, V> p = n.right;
378                while (p.left != null) {
379                    p = p.left;
380                }
381                return p;
382            } else {
383                TreeEntry<K, V> p = n.parent;
384                TreeEntry<K, V> ch = n;
385                while (p != null && ch == p.right) {
386                    ch = p;
387                    p = p.parent;
388                }
389                return p;
390            }
391        }
392        
393        static private final <K,V> TreeEntry<K, V> previous(TreeEntry<K, V> n) {
394            if (n == null)
395                return null;
396            else if (n.left != null) {
397                TreeEntry<K, V> p = n.left;
398                while (p.right != null) {
399                    p = p.right;
400                }
401                return p;
402            } else {
403                TreeEntry<K, V> p = n.parent;
404                TreeEntry<K, V> ch = n;
405                while (p != null && ch == p.left) {
406                    ch = p;
407                    p = p.parent;
408                }
409                return p;
410            }
411        }
412    
413        /*
414         * (non-Javadoc)
415         * 
416         * @see java.util.Map#isEmpty()
417         */
418        public boolean isEmpty() {
419            return count == 0;
420        }
421    
422        /*
423         * (non-Javadoc)
424         * 
425         * @see java.util.Map#keySet()
426         */
427        public Set<K> keySet() {
428            return new AbstractSet<K>() {
429    
430                @Override
431                public void clear() {
432                    TreeMap.this.clear();
433                }
434    
435                @SuppressWarnings("unchecked")
436                @Override
437                public boolean remove(Object o) {
438                    return TreeMap.this.remove((K) o) != null;
439                }
440    
441                @Override
442                public Iterator<K> iterator() {
443                    return new KeyIterator();
444                }
445    
446                @Override
447                public int size() {
448                    return count;
449                }
450            };
451    
452        }
453    
454        /*
455         * (non-Javadoc)
456         * 
457         * @see java.util.Map#putAll(java.util.Map)
458         */
459        public void putAll(Map<? extends K, ? extends V> t) {
460            for (Map.Entry<? extends K, ? extends V> entry : t.entrySet()) {
461                put(entry.getKey(), entry.getValue());
462            }
463        }
464    
465        /*
466         * (non-Javadoc)
467         * 
468         * @see java.util.Map#remove(java.lang.Object)
469         */
470        public V remove(K key) {
471            return removeEntry(getEntry(key, root));
472        }
473    
474        /*
475         * (non-Javadoc)
476         * 
477         * @see java.util.Map#put(java.lang.Object, java.lang.Object)
478         */
479        public V put(final K key, final V value) {
480    
481            if (root == null) {
482                // map is empty
483                root = new TreeEntry<K, V>(key, value, null, this);
484                count++;
485                return null;
486            }
487            TreeEntry<K, V> n = root;
488    
489            // add new mapping
490            while (true) {
491                int c = compare(key, n.key);
492    
493                if (c == 0) {
494                    V old = n.value;
495                    n.value = value;
496                    return old;
497                } else if (c < 0) {
498                    if (n.left != null) {
499                        n = n.left;
500                    } else {
501                        n.left = new TreeEntry<K, V>(key, value, n, this);
502                        count++;
503                        doRedBlackInsert(n.left);
504                        return null;
505                    }
506                } else { // c > 0
507                    if (n.right != null) {
508                        n = n.right;
509                    } else {
510                        n.right = new TreeEntry<K, V>(key, value, n, this);
511                        count++;
512                        doRedBlackInsert(n.right);
513                        return null;
514                    }
515                }
516            }
517        }
518    
519        /**
520         * complicated red-black insert stuff. Based on apache commons BidiMap
521         * method:
522         * 
523         * @param n
524         *            the newly inserted node
525         */
526        private void doRedBlackInsert(final TreeEntry<K, V> n) {
527            TreeEntry<K, V> currentNode = n;
528            color(currentNode, RED);
529    
530            while (currentNode != null && currentNode != root && isRed(currentNode.parent)) {
531                if (isLeftChild(parent(currentNode))) {
532                    TreeEntry<K, V> y = getRight(getGrandParent(currentNode));
533    
534                    if (isRed(y)) {
535                        color(parent(currentNode), BLACK);
536                        color(y, BLACK);
537                        color(getGrandParent(currentNode), RED);
538    
539                        currentNode = getGrandParent(currentNode);
540                    } else {
541                        if (isRightChild(currentNode)) {
542                            currentNode = parent(currentNode);
543    
544                            rotateLeft(currentNode);
545                        }
546    
547                        color(parent(currentNode), BLACK);
548                        color(getGrandParent(currentNode), RED);
549    
550                        if (getGrandParent(currentNode) != null) {
551                            rotateRight(getGrandParent(currentNode));
552                        }
553                    }
554                } else {
555    
556                    // just like clause above, except swap left for right
557                    TreeEntry<K, V> y = getLeft(getGrandParent(currentNode));
558    
559                    if (isRed(y)) {
560                        color(parent(currentNode), BLACK);
561                        color(y, BLACK);
562                        color(getGrandParent(currentNode), RED);
563    
564                        currentNode = getGrandParent(currentNode);
565                    } else {
566                        if (isLeftChild(currentNode)) {
567                            currentNode = parent(currentNode);
568    
569                            rotateRight(currentNode);
570                        }
571    
572                        color(parent(currentNode), BLACK);
573                        color(getGrandParent(currentNode), RED);
574    
575                        if (getGrandParent(currentNode) != null) {
576                            rotateLeft(getGrandParent(currentNode));
577                        }
578                    }
579                }
580            }
581    
582            color(root, BLACK);
583        }
584    
585        //Based on Apache common's TreeBidiMap
586        private void rotateLeft(TreeEntry<K, V> n) {
587            TreeEntry<K, V> r = n.right;
588            n.right = r.left;
589            if (r.left != null) {
590                r.left.parent = n;
591            }
592            r.parent = n.parent;
593            if (n.parent == null) {
594                root = r;
595            } else if (n.parent.left == n) {
596                n.parent.left = r;
597            } else {
598                n.parent.right = r;
599            }
600    
601            r.left = n;
602            n.parent = r;
603        }
604    
605        //Based on Apache common's TreeBidiMap    
606        private void rotateRight(TreeEntry<K, V> n) {
607            TreeEntry<K, V> l = n.left;
608            n.left = l.right;
609            if (l.right != null) {
610                l.right.parent = n;
611            }
612            l.parent = n.parent;
613            if (n.parent == null) {
614                root = l;
615            } else if (n.parent.right == n) {
616                n.parent.right = l;
617            } else {
618                n.parent.left = l;
619            }
620            l.right = n;
621            n.parent = l;
622        }
623    
624        /**
625         * complicated red-black delete stuff. Based on Apache Common's TreeBidiMap
626         * 
627         * @param n
628         *            the node to be deleted
629         */
630        public final V removeEntry(TreeEntry<K, V> n) {
631            if (n == null) {
632                return null;
633            }
634    
635            if (n.map != this) {
636                throw new IllegalStateException("Node not in list");
637            }
638    
639            V old = n.value;
640    
641            count--;
642    
643            //if deleted node has both left and children, swap with
644            // the next greater node
645            if (n.left != null && n.right != null) {
646                TreeEntry<K, V> next = next(n);
647                n.key = next.key;
648                n.value = next.value;
649                n = next;
650            }
651    
652            TreeEntry<K, V> replacement = n.left != null ? n.left : n.right;
653    
654            if (replacement != null) {
655                replacement.parent = n.parent;
656    
657                if (n.parent == null) {
658                    root = replacement;
659                } else if (n == n.parent.left) {
660                    n.parent.left = replacement;
661                } else {
662                    n.parent.right = replacement;
663                }
664    
665                n.left = null;
666                n.right = null;
667                n.parent = null;
668    
669                if (isBlack(n)) {
670                    doRedBlackDeleteFixup(replacement);
671                }
672            } else {
673    
674                // replacement is null
675                if (n.parent == null) {
676                    // empty tree
677                    root = null;
678                } else {
679    
680                    // deleted node had no children
681                    if (isBlack(n)) {
682                        doRedBlackDeleteFixup(n);
683                    }
684    
685                    if (n.parent != null) {
686                        if (n == n.parent.left) {
687                            n.parent.left = null;
688                        } else {
689                            n.parent.right = null;
690                        }
691    
692                        n.parent = null;
693                    }
694                }
695            }
696            return old;
697        }
698    
699        /**
700         * complicated red-black delete stuff. Based on Apache Commons TreeBidiMap.
701         * 
702         * @param replacementNode
703         *            the node being replaced
704         */
705        private void doRedBlackDeleteFixup(final TreeEntry<K, V> replacementNode) {
706            TreeEntry<K, V> currentNode = replacementNode;
707    
708            while (currentNode != root && isBlack(currentNode)) {
709                if (isLeftChild(currentNode)) {
710                    TreeEntry<K, V> siblingNode = getRight(parent(currentNode));
711    
712                    if (isRed(siblingNode)) {
713                        color(siblingNode, BLACK);
714                        color(parent(currentNode), RED);
715                        rotateLeft(parent(currentNode));
716    
717                        siblingNode = getRight(parent(currentNode));
718                    }
719    
720                    if (isBlack(getLeft(siblingNode)) && isBlack(getRight(siblingNode))) {
721                        color(siblingNode, RED);
722    
723                        currentNode = parent(currentNode);
724                    } else {
725                        if (isBlack(getRight(siblingNode))) {
726                            color(getLeft(siblingNode), BLACK);
727                            color(siblingNode, RED);
728                            rotateRight(siblingNode);
729    
730                            siblingNode = getRight(parent(currentNode));
731                        }
732    
733                        color(siblingNode, getColor(parent(currentNode)));
734                        color(parent(currentNode), BLACK);
735                        color(getRight(siblingNode), BLACK);
736                        rotateLeft(parent(currentNode));
737    
738                        currentNode = root;
739                    }
740                } else {
741                    TreeEntry<K, V> siblingNode = getLeft(parent(currentNode));
742    
743                    if (isRed(siblingNode)) {
744                        color(siblingNode, BLACK);
745                        color(parent(currentNode), RED);
746                        rotateRight(parent(currentNode));
747    
748                        siblingNode = getLeft(parent(currentNode));
749                    }
750    
751                    if (isBlack(getRight(siblingNode)) && isBlack(getLeft(siblingNode))) {
752                        color(siblingNode, RED);
753    
754                        currentNode = parent(currentNode);
755                    } else {
756                        if (isBlack(getLeft(siblingNode))) {
757                            color(getRight(siblingNode), BLACK);
758                            color(siblingNode, RED);
759                            rotateLeft(siblingNode);
760    
761                            siblingNode = getLeft(parent(currentNode));
762                        }
763    
764                        color(siblingNode, getColor(parent(currentNode)));
765                        color(parent(currentNode), BLACK);
766                        color(getLeft(siblingNode), BLACK);
767                        rotateRight(parent(currentNode));
768    
769                        currentNode = root;
770                    }
771                }
772            }
773    
774            color(currentNode, BLACK);
775        }
776    
777    
778        /*
779         * (non-Javadoc)
780         * 
781         * @see java.util.Map#size()
782         */
783        public int size() {
784            return count;
785        }
786    
787        /*
788         * (non-Javadoc)
789         * 
790         * @see java.util.Map#values()
791         */
792        public Collection<V> values() {
793            return new AbstractCollection<V>() {
794    
795                @Override
796                public Iterator<V> iterator() {
797                    return new ValueIterator();
798                }
799    
800                @Override
801                public int size() {
802                    return count;
803                }
804            };
805        }
806    
807        private static <K, V> TreeEntry<K, V> parent(TreeEntry<K, V> n) {
808            return (n == null ? null : n.parent);
809        }
810    
811        private static <K, V> void color(TreeEntry<K, V> n, boolean c) {
812            if (n != null)
813                n.color = c;
814        }
815    
816        private static <K, V> boolean getColor(TreeEntry<K, V> n) {
817            return (n == null ? BLACK : n.color);
818        }
819    
820        /**
821         * get a node's left child. mind you, the node may not exist. no problem
822         * 
823         * @param node
824         *            the node (may be null) in question
825         */
826        private static <K, V> TreeEntry<K, V> getLeft(TreeEntry<K, V> n) {
827            return (n == null) ? null : n.left;
828        }
829    
830        /**
831         * get a node's right child. mind you, the node may not exist. no problem
832         * 
833         * @param node
834         *            the node (may be null) in question
835         */
836        private static <K, V> TreeEntry<K, V> getRight(TreeEntry<K, V> n) {
837            return (n == null) ? null : n.right;
838        }
839    
840        /**
841         * is the specified node red? if the node does not exist, no, it's black,
842         * thank you
843         * 
844         * @param node
845         *            the node (may be null) in question
846         */
847        private static <K, V> boolean isRed(TreeEntry<K, V> n) {
848            return n == null ? false : n.color == RED;
849        }
850    
851        /**
852         * is the specified black red? if the node does not exist, sure, it's black,
853         * thank you
854         * 
855         * @param node
856         *            the node (may be null) in question
857         */
858        private static <K, V> boolean isBlack(final TreeEntry<K, V> n) {
859            return n == null ? true : n.color == BLACK;
860        }
861    
862        /**
863         * is this node its parent's left child? mind you, the node, or its parent,
864         * may not exist. no problem. if the node doesn't exist ... it's its
865         * non-existent parent's left child. If the node does exist but has no
866         * parent ... no, we're not the non-existent parent's left child. Otherwise
867         * (both the specified node AND its parent exist), check.
868         * 
869         * @param node
870         *            the node (may be null) in question
871         */
872        private static <K, V> boolean isLeftChild(final TreeEntry<K, V> node) {
873    
874            return node == null ? true : (node.parent == null ? false : (node == node.parent.left));
875        }
876    
877        /**
878         * is this node its parent's right child? mind you, the node, or its parent,
879         * may not exist. no problem. if the node doesn't exist ... it's its
880         * non-existent parent's right child. If the node does exist but has no
881         * parent ... no, we're not the non-existent parent's right child. Otherwise
882         * (both the specified node AND its parent exist), check.
883         * 
884         * @param node
885         *            the node (may be null) in question
886         * @param index
887         *            the KEY or VALUE int
888         */
889        private static <K, V> boolean isRightChild(final TreeEntry<K, V> node) {
890            return node == null ? true : (node.parent == null ? false : (node == node.parent.right));
891    
892        }
893    
894        /**
895         * get a node's grandparent. mind you, the node, its parent, or its
896         * grandparent may not exist. no problem
897         * 
898         * @param node
899         *            the node (may be null) in question
900         */
901        private static <K, V> TreeEntry<K, V> getGrandParent(final TreeEntry<K, V> node) {
902            return parent(parent(node));
903        }
904    
905        public static class TreeEntry<K, V> implements Map.Entry<K, V>, Serializable {
906    
907            private static final long serialVersionUID = 8490652911043012737L;
908            
909            TreeMap<K, V> map;
910            V value;
911            K key;
912            boolean color = BLACK;
913    
914            TreeEntry<K, V> parent;
915            TreeEntry<K, V> left;
916            TreeEntry<K, V> right;
917    
918            TreeEntry(K key, V val, TreeEntry<K, V> parent, TreeMap<K, V> map) {
919                this.key = key;
920                this.parent = parent;
921                this.value = val;
922                this.map = map;
923            }
924    
925            /*
926             * (non-Javadoc)
927             * 
928             * @see java.util.Map.Entry#getKey()
929             */
930            public K getKey() {
931                return key;
932            }
933    
934            /*
935             * (non-Javadoc)
936             * 
937             * @see java.util.Map.Entry#getValue()
938             */
939            public V getValue() {
940                return value;
941            }
942    
943            /*
944             * (non-Javadoc)
945             * 
946             * @see java.util.Map.Entry#setValue(java.lang.Object)
947             */
948            public V setValue(V val) {
949                V old = this.value;
950                this.value = val;
951                return old;
952            }
953    
954            @SuppressWarnings("unchecked")
955            public boolean equals(Object o) {
956                if (!(o instanceof Map.Entry))
957                    return false;
958                Map.Entry e = (Map.Entry) o;
959    
960                return (key == null ? e.getKey() == null : key.equals(e.getKey())) && (value == null ? e.getValue() == null : value.equals(e.getValue()));
961            }
962    
963            public int hashCode() {
964                int keyHash = (key == null ? 0 : key.hashCode());
965                int valueHash = (value == null ? 0 : value.hashCode());
966                return keyHash ^ valueHash;
967            }
968            
969            public TreeEntry<K, V> next() {
970                return TreeMap.next(this);
971            }
972            
973            public TreeEntry<K, V> previous() {
974                return TreeMap.previous(this);
975            }
976            
977            @Override
978            public String toString() {
979                return "{ key: " +key+", value: "+value+" }";
980            }
981        }
982    
983        private class ValueIterator extends AbstractEntryIterator<V> {
984    
985            /*
986             * (non-Javadoc)
987             * 
988             * @see java.util.Iterator#next()
989             */
990            public V next() {
991                getNext();
992                if (last == null) {
993                    return null;
994                } else {
995                    return last.value;
996                }
997            }
998        }
999    
1000        private class KeyIterator extends AbstractEntryIterator<K> {
1001    
1002            /*
1003             * (non-Javadoc)
1004             * 
1005             * @see java.util.Iterator#next()
1006             */
1007            public K next() {
1008                getNext();
1009                if (last == null) {
1010                    return null;
1011                } else {
1012                    return last.key;
1013                }
1014            }
1015        }
1016    
1017        private class EntryIterator extends AbstractEntryIterator<Map.Entry<K, V>> {
1018            /*
1019             * (non-Javadoc)
1020             * 
1021             * @see java.util.Iterator#next()
1022             */
1023            public Entry<K, V> next() {
1024                getNext();
1025                if (last == null) {
1026                    return null;
1027                } else {
1028                    return last;
1029                }
1030            }
1031    
1032        }
1033    
1034        private abstract class AbstractEntryIterator<T> implements Iterator<T> {
1035    
1036            TreeEntry<K, V> last = null;
1037            TreeEntry<K, V> next = firstEntry();
1038    
1039            /*
1040             * (non-Javadoc)
1041             * 
1042             * @see java.util.Iterator#hasNext()
1043             */
1044            public boolean hasNext() {
1045                return next != null;
1046            }
1047    
1048            /*
1049             * (non-Javadoc)
1050             * 
1051             * @see java.util.Iterator#next()
1052             */
1053            protected TreeEntry<K, V> getNext() {
1054                last = next;
1055                next = TreeMap.next(next);
1056                return last;
1057            }
1058    
1059            /*
1060             * (non-Javadoc)
1061             * 
1062             * @see java.util.Iterator#remove()
1063             */
1064            public void remove() {
1065                TreeMap.this.removeEntry(last);
1066                last = null;
1067            }
1068    
1069        }
1070    }