harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From le...@apache.org
Subject svn commit: r549743 [2/3] - in /harmony/enhanced/classlib/branches/java6/modules/luni/src: main/java/java/util/ test/api/common/tests/api/java/util/
Date Fri, 22 Jun 2007 07:32:13 GMT

Modified: harmony/enhanced/classlib/branches/java6/modules/luni/src/main/java/java/util/TreeMap.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/branches/java6/modules/luni/src/main/java/java/util/TreeMap.java?view=diff&rev=549743&r1=549742&r2=549743
==============================================================================
--- harmony/enhanced/classlib/branches/java6/modules/luni/src/main/java/java/util/TreeMap.java (original)
+++ harmony/enhanced/classlib/branches/java6/modules/luni/src/main/java/java/util/TreeMap.java Fri Jun 22 00:32:12 2007
@@ -23,82 +23,125 @@
 import java.io.Serializable;
 
 /**
- * TreeMap is an implementation of SortedMap. All optional operations are
+ * TreeMap is an implementation of NavigableMap. All optional operations are
  * supported, adding and removing. The values can be any objects. The keys can
  * be any objects which are comparable to each other either using their natural
  * order or a specified Comparator.
+ * 
+ * @param <K>
+ *            type of key
+ * @param <V>
+ *            type of value
+ * 
  * @since 1.2
  */
-public class TreeMap<K, V> extends AbstractMap<K, V> implements SortedMap<K, V>, Cloneable,
-		Serializable {
-	private static final long serialVersionUID = 919286545866124006L;
+public class TreeMap<K, V> extends AbstractMap<K, V> implements
+        NavigableMap<K, V>, Cloneable, Serializable {
+    private static final long serialVersionUID = 919286545866124006L;
 
-	transient int size;
+    transient int size;
 
     transient Entry<K, V> root;
 
-    private Comparator<? super K> comparator;
+    Comparator<? super K> comparator;
 
     transient int modCount;
 
     transient Set<Map.Entry<K, V>> entrySet;
 
-	/**
-	 * Entry is an internal class which is used to hold the entries of a
-	 * TreeMap.
-	 */
-	static class Entry<K, V> extends MapEntry<K, V> {
-		Entry<K, V> parent, left, right;
+    transient NavigableMap<K, V> descendingMap;
 
-		boolean color;
+    transient NavigableSet<K> navigableKeySet;
 
-		Entry(K key) {
-			super(key);
-		}
+    /**
+     * Entry is an internal class which is used to hold the entries of a
+     * TreeMap.
+     */
+    static class Entry<K, V> extends MapEntry<K, V> {
+        Entry<K, V> parent, left, right;
 
-		Entry(K key, V value) {
-			super(key, value);
-		}
+        boolean color;
+
+        Entry(K theKey) {
+            super(theKey);
+        }
+
+        Entry(K theKey, V theValue) {
+            super(theKey, theValue);
+        }
 
-		@SuppressWarnings("unchecked")
-        Entry<K, V> clone(Entry<K, V> parent) {
-			Entry<K, V> clone = (Entry<K, V>) super.clone();
-			clone.parent = parent;
-			if (left != null) {
+        @SuppressWarnings("unchecked")
+        Entry<K, V> clone(Entry<K, V> theParent) {
+            Entry<K, V> clone = (Entry<K, V>) super.clone();
+            clone.parent = theParent;
+            if (left != null) {
                 clone.left = left.clone(clone);
             }
-			if (right != null) {
+            if (right != null) {
                 clone.right = right.clone(clone);
             }
-			return clone;
-		}
-	}
-    
-    @SuppressWarnings("unchecked")
-    private static <T> Comparable<T> toComparable(T obj) {
-        return (Comparable<T>)obj;
+            return clone;
+        }
     }
 
-    private static class AbstractMapIterator <K,V> {
-        TreeMap<K, V> backingMap;
+    /*
+     * It is a "work-around" method because of a RI's bug. The RI's bug is that:
+     * if the TreeMap has no comparator or its comparator is not null-tolerable,
+     * it can not put a null-key entry into this TreeMap.But RI can do it when
+     * the TreeMap is empty, and can not do it when the TreeMap is not empty.It
+     * is best for Harmony to follow RI's behavior for legacy reason. This
+     * method is to check if this TreeMap is constructed by that bug.It can be
+     * easily removed when the bug is fixed in the future.
+     */
+    boolean isRootWithIllegalNullKey() {
+        if (null != root) {
+            if (null == root.key && null == comparator) {
+                return true;
+            } else if (null != comparator) {
+                try {
+                    comparator.compare(root.key, root.key);
+                } catch (NullPointerException e) {
+                    return true;
+                }
+            }
+        }
+        return false;
+    }
+
+    private static abstract class AbstractSubMapIterator<K, V> {
+        final NavigableSubMap<K, V> subMap;
+
         int expectedModCount;
-        TreeMap.Entry<K, V> node;
-        TreeMap.Entry<K, V> lastNode;
 
-        AbstractMapIterator(TreeMap<K, V> map, Entry<K, V> startNode) {
-            backingMap = map;
-            expectedModCount = map.modCount;
-            node = startNode;
-        }
+        TreeMap.Entry<K, V> node;
 
-        public boolean hasNext() {
-            return node != null;
+        TreeMap.Entry<K, V> lastNode;
+        
+        TreeMap.Entry<K, V> boundaryNode;
+        
+        boolean getToEnd = false;
+
+        AbstractSubMapIterator(final NavigableSubMap<K, V> map) {
+            subMap = map;
+            expectedModCount = subMap.backingMap.modCount;
+            node = getStartNode();
+            
+            boundaryNode = getBoundaryNode();
+			if (null == boundaryNode) {
+				node = null;
+			}
         }
 
-        final public void remove() {
-            if (expectedModCount == backingMap.modCount) {
+        public final void remove() {
+            if (expectedModCount == subMap.backingMap.modCount) {
                 if (lastNode != null) {
-                    backingMap.rbDelete(lastNode);
+                    if (lastNode.key == this.boundaryNode.key) {
+                        node = null;
+                    }
+                    subMap.backingMap.rbDelete(lastNode);
+                    if( null != node && node.key == lastNode.key) {
+                        node = lastNode;
+                    }
                     lastNode = null;
                     expectedModCount++;
                 } else {
@@ -109,1176 +152,1765 @@
             }
         }
 
-        final void makeNext() {
-            if (expectedModCount != backingMap.modCount) {
+        TreeMap.Entry<K, V> getNext() {
+            if (hasNext()) {
+                if (expectedModCount == subMap.backingMap.modCount) {
+                    lastNode = node;
+					if (node.key == this.boundaryNode.key) {
+						node = null;
+					} else {
+						node = getRealNext(node);
+					}
+					return lastNode;
+                }
                 throw new ConcurrentModificationException();
-            } else if (node == null) {
-                throw new NoSuchElementException();
-            }
-            lastNode = node;
-            node = TreeMap.successor(node);
             }
+            throw new NoSuchElementException();
         }
 
-        private static class UnboundedEntryIterator <K, V> extends AbstractMapIterator<K, V> implements Iterator<Map.Entry<K, V>> {
-
-            UnboundedEntryIterator(TreeMap<K, V> map, Entry<K, V> startNode) {
-                super(map, startNode);
-            }
+        abstract TreeMap.Entry<K, V> getStartNode();
 
-            UnboundedEntryIterator(TreeMap<K, V> map) {
-                super(map, map.root == null ? null : TreeMap.minimum(map.root));
-            }
+        abstract TreeMap.Entry<K, V> getRealNext(TreeMap.Entry<K, V> entry);
 
-            public Map.Entry<K, V> next() {
-                makeNext();
-                return lastNode;
-            }
-        }
+        abstract boolean hasNext();
+        
+        abstract TreeMap.Entry<K, V> getBoundaryNode();
+    }
 
-        static class UnboundedKeyIterator <K, V> extends AbstractMapIterator<K, V> implements Iterator<K> {
-            public UnboundedKeyIterator(TreeMap<K, V> treeMap, Entry<K, V> entry) {
-                super(treeMap, entry);
-            }
+    private abstract static class AscendingSubMapIterator<K, V> extends
+            AbstractSubMapIterator<K, V> {    	
+    	
+    	AscendingSubMapIterator(NavigableSubMap<K, V> map) {
+            super(map);            
+        }
+        
+        final TreeMap.Entry<K, V> getBoundaryNode() {
+			if (subMap.hasEnd) {
+				return subMap.endInclusive ? subMap
+						.smallerOrEqualEntry(subMap.endKey) : subMap
+						.smallerEntry(subMap.endKey);
+			}
+			return subMap.theBiggestEntry();
+		}
 
-            public UnboundedKeyIterator(TreeMap<K, V> map) {
-                super(map, map.root == null ? null : TreeMap.minimum(map.root));
+        @Override
+        final TreeMap.Entry<K, V> getStartNode() {
+            if (subMap.hasStart) {
+                return subMap.startInclusive ? subMap
+                        .biggerOrEqualEntry(subMap.startKey) : subMap
+                        .biggerEntry(subMap.startKey);
             }
+            return subMap.theSmallestEntry();
+        }
 
-            public K next() {
-                makeNext();
-                return lastNode.key;
-            }
+        @Override
+        final Entry<K, V> getRealNext(Entry<K, V> entry) {
+            return TreeMap.successor(entry);            
         }
 
-        static class UnboundedValueIterator <K, V> extends AbstractMapIterator<K, V> implements Iterator<V> {
-     
-            public UnboundedValueIterator(TreeMap<K, V> treeMap, Entry<K, V> startNode) {
-                super(treeMap, startNode);
-            }
-     
-            public UnboundedValueIterator(TreeMap<K, V> map) {
-                super(map, map.root == null ? null : TreeMap.minimum(map.root));
-            }
-     
-            public V next() {
-                makeNext();
-                return lastNode.value;
-            }
+        @Override
+        public final boolean hasNext() {
+//            if (null != node) {
+//                if (subMap.backingMap.root == node
+//                        && subMap.backingMap.isRootWithIllegalNullKey()) {
+//                    return true;
+//                }
+//                return subMap.checkUpperBound(node.key);
+//            }
+//            return false;
+        	return null!=node;
         }
 
-        private static class ComparatorBoundedIterator<K, V> extends AbstractMapIterator<K, V> {
-            private final  K endKey;
+    }
 
-            private final Comparator<? super K> cmp;
+    static class AscendingSubMapEntryIterator<K, V> extends
+            AscendingSubMapIterator<K, V> implements Iterator<Map.Entry<K, V>> {
 
-        ComparatorBoundedIterator(TreeMap<K, V> map, Entry<K, V> startNode, K end) {
-            super(map, startNode);
-            endKey = end;
-            cmp = map.comparator();
+        AscendingSubMapEntryIterator(NavigableSubMap<K, V> map) {
+            super(map);
         }
 
-        final void cleanNext() {
-            if (node != null && cmp.compare(endKey, node.key) <= 0) {
-                node = null;
-            }
+        public final Map.Entry<K, V> next() {
+            return getNext();
         }
+    }
 
-        @Override
-        public boolean hasNext() {
-            return (node != null && endKey != null) && (cmp.compare(node.key, endKey) < 0);
+    static class AscendingSubMapKeyIterator<K, V> extends
+            AscendingSubMapIterator<K, V> implements Iterator<K> {
+
+        AscendingSubMapKeyIterator(NavigableSubMap<K, V> map) {
+            super(map);
+        }
+
+        public final K next() {
+            return getNext().key;
         }
     }
 
-    private static class ComparatorBoundedEntryIterator<K, V> extends
-            ComparatorBoundedIterator<K, V> implements Iterator<Map.Entry<K, V>> {
+    private abstract static class DescendingSubMapIterator<K, V> extends
+            AbstractSubMapIterator<K, V> {
+
+    	DescendingSubMapIterator(NavigableSubMap<K, V> map) {
+            super(map);            
+        }
+
+        @Override
+        final TreeMap.Entry<K, V> getStartNode() {
+            if (subMap.hasEnd) {
+                return subMap.endInclusive ? subMap
+                        .smallerOrEqualEntry(subMap.endKey) : subMap
+                        .smallerEntry(subMap.endKey);
+            }
+            return subMap.theBiggestEntry();
+        }
+        
+        final TreeMap.Entry<K, V> getBoundaryNode() {
+			if (subMap.hasStart) {
+				return subMap.startInclusive ? subMap
+						.biggerOrEqualEntry(subMap.startKey) : subMap
+						.biggerEntry(subMap.startKey);
+			}
+			return subMap.theSmallestEntry();
+		}
 
-        ComparatorBoundedEntryIterator(TreeMap<K, V> map, Entry<K, V> startNode, K end) {
-            super(map, startNode, end);
+        @Override
+        final Entry<K, V> getRealNext(Entry<K, V> entry) {
+            return TreeMap.predecessor(entry);
         }
 
-        public Map.Entry<K, V> next() {
-            makeNext();
-            cleanNext();
-            return lastNode;
+        @Override
+        public final boolean hasNext() {
+//            if (null != node) {
+//                if (subMap.backingMap.root == node
+//                        && subMap.backingMap.isRootWithIllegalNullKey()) {
+//                    return true;
+//                }
+//                return subMap.checkLowerBound(node.key);
+//            }
+//            return false;
+        	return node != null;
         }
     }
 
-    private static class ComparatorBoundedKeyIterator<K, V> extends
-            ComparatorBoundedIterator<K, V> implements Iterator<K> {
+    static class DescendingSubMapEntryIterator<K, V> extends
+            DescendingSubMapIterator<K, V> implements Iterator<Map.Entry<K, V>> {
 
-        ComparatorBoundedKeyIterator(TreeMap<K, V> map, Entry<K, V> startNode, K end) {
-            super(map, startNode, end);
+        DescendingSubMapEntryIterator(NavigableSubMap<K, V> map) {
+            super(map);
         }
 
-        public K next() {
-            makeNext();
-            cleanNext();
-            return lastNode.key;
+        public final Map.Entry<K, V> next() {
+            return getNext();
         }
     }
 
-    private static class ComparatorBoundedValueIterator<K, V> extends
-            ComparatorBoundedIterator<K, V> implements Iterator<V> {
+    static class DescendingSubMapKeyIterator<K, V> extends
+            DescendingSubMapIterator<K, V> implements Iterator<K> {
 
-        ComparatorBoundedValueIterator(TreeMap<K, V> map, Entry<K, V> startNode, K end) {
-            super(map, startNode, end);
+        DescendingSubMapKeyIterator(NavigableSubMap<K, V> map) {
+            super(map);
         }
 
-        public V next() {
-            makeNext();
-            cleanNext();
-            return lastNode.value;
+        public final K next() {
+            return getNext().key;
         }
     }
 
-    private static class ComparableBoundedIterator<K, V> extends AbstractMapIterator<K, V> {
-        private final Comparable<K> endKey;
+    /*
+     * Entry set of sub-maps, must override methods which check the range. add
+     * or addAll operations are disabled by default.
+     */
+    static abstract class SubMapEntrySet<K, V> extends
+            AbstractSet<Map.Entry<K, V>> {
+        final NavigableSubMap<K, V> subMap;
 
-        public ComparableBoundedIterator(TreeMap<K, V> treeMap, Entry<K, V> entry,
-                Comparable<K> endKey) {
-            super(treeMap, entry);
-            this.endKey = endKey;
+        SubMapEntrySet(NavigableSubMap<K, V> map) {
+            subMap = map;
         }
 
-        final void cleanNext() {
-            if ((node != null) && (endKey.compareTo(node.key) <= 0)) {
-                node = null;
-            }
+        @Override
+        public boolean isEmpty() {
+            return 0 == size();
         }
 
         @Override
-        public boolean hasNext() {
-            return (node != null) && (endKey.compareTo(node.key) > 0);
+        public int size() {
+            int size = 0;
+            Iterator<Map.Entry<K, V>> it = iterator();
+            while (it.hasNext()) {
+                size++;
+                it.next();
+            }
+            return size;
         }
-    }
-
-    private static class ComparableBoundedEntryIterator<K, V> extends
-            ComparableBoundedIterator<K, V> implements Iterator<Map.Entry<K, V>> {
 
-        ComparableBoundedEntryIterator(TreeMap<K, V> map, Entry<K, V> startNode,
-                Comparable<K> end) {
-            super(map, startNode, end);
+        @SuppressWarnings("unchecked")
+        @Override
+        public boolean contains(Object object) {
+            if (object instanceof Map.Entry) {
+                Map.Entry<K, V> entry = (Map.Entry<K, V>) object;
+                K key = entry.getKey();
+                if (subMap.isInRange(key)) {
+                    V v1 = subMap.get(key), v2 = entry.getValue();
+                    return (v1 == null) ? v2 == null : v1.equals(v2);
+                }
+            }
+            return false;
         }
 
-        public Map.Entry<K, V> next() {
-            makeNext();
-            cleanNext();
-            return lastNode;
+        @SuppressWarnings("unchecked")
+        @Override
+        /*
+         * Must added, because it need check the range, and used in
+         * clear(),removeAll() methods.
+         */
+        public boolean remove(Object object) {
+            if (object instanceof Map.Entry) {
+                TreeMap.Entry<K, V> entry = (TreeMap.Entry<K, V>) object;
+                K key = entry.getKey();
+                if (subMap.isInRange(key)) {
+                    TreeMap.Entry<K, V> node = subMap.backingMap.find(key);
+                    if (node == null) {
+                        return false;
+                    }
+                    V v1 = node.value, v2 = entry.getValue();
+                    if ((v1 == null) ? (v2 == null) : v1.equals(v2)) {
+                        subMap.backingMap.rbDelete(node);
+                        return true;
+                    }
+                }
+            }
+            return false;
         }
 
+        @Override
+        public abstract Iterator<Map.Entry<K, V>> iterator();
     }
 
-    private static class ComparableBoundedKeyIterator<K, V> extends
-            ComparableBoundedIterator<K, V> implements Iterator<K> {
+    static class AscendingSubMapEntrySet<K, V> extends SubMapEntrySet<K, V> {
 
-        ComparableBoundedKeyIterator(TreeMap<K, V> map, Entry<K, V> startNode, Comparable<K> end) {
-            super(map, startNode, end);
+        AscendingSubMapEntrySet(NavigableSubMap<K, V> map) {
+            super(map);
         }
 
-        public K next() {
-            makeNext();
-            cleanNext();
-            return lastNode.key;
+        @Override
+        public final Iterator<Map.Entry<K, V>> iterator() {
+            return new AscendingSubMapEntryIterator<K, V>(subMap);
         }
     }
 
-    private static class ComparableBoundedValueIterator<K, V> extends
-            ComparableBoundedIterator<K, V> implements Iterator<V> {
+    static class DescendingSubMapEntrySet<K, V> extends SubMapEntrySet<K, V> {
 
-        ComparableBoundedValueIterator(TreeMap<K, V> map, Entry<K, V> startNode,
-                Comparable<K> end) {
-            super(map, startNode, end);
+        DescendingSubMapEntrySet(NavigableSubMap<K, V> map) {
+            super(map);
         }
 
-        public V next() {
-            makeNext();
-            cleanNext();
-            return lastNode.value;
+        @Override
+        public final Iterator<Map.Entry<K, V>> iterator() {
+            return new DescendingSubMapEntryIterator<K, V>(subMap);
         }
     }
 
-        static final class SubMap<K,V> extends AbstractMap<K,V> implements SortedMap<K,V>, Serializable {
-            private static final long serialVersionUID = -6520786458950516097L;
+    static abstract class SubMapKeySet<K> extends AbstractSet<K> implements
+            NavigableSet<K> {
+        final NavigableSubMap<K, K> subMap;
 
-            private TreeMap<K,V> backingMap;
+        NavigableSet<K> descendingSet;
 
-            boolean hasStart, hasEnd;
+        SubMapKeySet(NavigableSubMap<K, K> map) {
+            subMap = map;
+        }
 
-            K startKey, endKey;
+        public Comparator<? super K> comparator() {
+            return subMap.backingMap.comparator();
+        }
 
-            transient Set<Map.Entry<K,V>> entrySet = null;
+        @Override
+        public boolean contains(Object object) {
+            return subMap.backingMap.containsKey(object);
+        }
 
-            SubMap(K start, TreeMap<K,V> map) {
-                backingMap = map;
-                hasStart = true;
-                startKey = start;
-            }
+        @Override
+        public boolean isEmpty() {
+            return size() == 0;
+        }
 
-            SubMap(K start, TreeMap<K,V> map, K end) {
-                backingMap = map;
-                hasStart = hasEnd = true;
-                startKey = start;
-                endKey = end;
-            }
-            
-            SubMap(TreeMap<K,V> map, K end) {
-                backingMap = map;
-                hasEnd = true;
-                endKey = end;
+        @Override
+        public int size() {
+            Iterator<K> it = iterator();
+            int size = 0;
+            while (it.hasNext()) {
+                it.next();
+                size++;
             }
+            return size;
+        }
 
-            private void checkRange(K key) {
-                Comparator<? super K> cmp = backingMap.comparator;
-                if (cmp == null) {
-                    Comparable<K> object = toComparable(key);
-                    if (hasStart && object.compareTo(startKey) < 0) {
-                        throw new IllegalArgumentException();
-                    }
-                    if (hasEnd && object.compareTo(endKey) > 0) {
-                        throw new IllegalArgumentException();
-                    }
-                } else {
-                    if (hasStart
-                            && backingMap.comparator().compare(key, startKey) < 0) {
-                        throw new IllegalArgumentException();
-                    }
-                    if (hasEnd && backingMap.comparator().compare(key, endKey) > 0) {
-                        throw new IllegalArgumentException();
-                    }
-                }
-            }
+        @Override
+        public boolean remove(Object object) {
+            return null != subMap.remove(object);
+        }
 
-            private boolean isInRange(K key) {
-                Comparator<? super K> cmp = backingMap.comparator;
-                if (cmp == null) {
-                    Comparable<K> object = toComparable(key);
-                    if (hasStart && object.compareTo(startKey) < 0) {
-                        return false;
-                    }
-                    if (hasEnd && object.compareTo(endKey) >= 0) {
-                        return false;
-                    }
-                } else {
-                    if (hasStart && cmp.compare(key, startKey) < 0) {
-                        return false;
-                    }
-                    if (hasEnd && cmp.compare(key, endKey) >= 0) {
-                        return false;
-                    }
-                }
-                return true;
-            }
+        @Override
+        public abstract Iterator<K> iterator();
 
-            private boolean checkUpperBound(K key) {
-                if (hasEnd) {
-                    Comparator<? super K> cmp = backingMap.comparator;
-                    if (cmp == null) {
-                        return (toComparable(key).compareTo(endKey) < 0);
-                    }
-                    return (cmp.compare(key, endKey) < 0);
-                }
-                return true;
-            }
+        public abstract Iterator<K> descendingIterator();
 
-            private boolean checkLowerBound(K key) {
-                if (hasStart) {
-                    Comparator<? super K> cmp = backingMap.comparator;
-                    if (cmp == null) {
-                        return (toComparable(key).compareTo(startKey) >= 0);
-                    }
-                    return (cmp.compare(key, startKey) >= 0);
-                }
-                return true;
-            }
+        public K first() {
+            return subMap.firstKey();
+        }
 
-            public Comparator<? super K> comparator() {
-                return backingMap.comparator();
-            }
+        public K last() {
+            return subMap.lastKey();
+        }
 
-            @SuppressWarnings("unchecked")
-            @Override
-            public boolean containsKey(Object key) {
-                if (isInRange((K)key)) {
-                    return backingMap.containsKey(key);
-                }
-                return false;
-            }
+        public K pollFirst() {
+            Map.Entry<K, K> entry = subMap.pollFirstEntry();
+            return (null == entry) ? null : entry.getKey();
+        }
 
-            @Override
-            public Set<Map.Entry<K,V>> entrySet() {
-                if(entrySet==null) {
-                    entrySet = new SubMapEntrySet<K,V>(this);
-                }
-                return entrySet;
-            }
+        public K pollLast() {
+            Map.Entry<K, K> entry = subMap.pollLastEntry();
+            return (null == entry) ? null : entry.getKey();
+        }
 
-            public K firstKey() {
-                TreeMap.Entry<K,V> node = firstEntry();
-                if (node != null ) {
-                    return node.key;
-                }
-                throw new NoSuchElementException();
-            }
+        public K higher(K key) {
+            return subMap.higherKey(key);
+        }
 
-            TreeMap.Entry<K,V> firstEntry() {
-                if (!hasStart) {
-                    TreeMap.Entry<K,V> root = backingMap.root;
-                    return (root == null) ? null : minimum(backingMap.root);
-                }
-                TreeMap.Entry<K,V> node = backingMap.findAfter(startKey);
-                if (node != null && checkUpperBound(node.key)) {
-                    return node;
-                }
-                return null;
-            }
+        public K lower(K key) {
+            return subMap.lowerKey(key);
+        }
 
-            @SuppressWarnings("unchecked")
-            @Override
-            public V get(Object key) {
-                if (isInRange((K)key)) {
-                    return backingMap.get(key);
-                }
-                return null;
-            }
+        public K ceiling(K key) {
+            return subMap.ceilingKey(key);
+        }
 
-            public SortedMap<K,V> headMap(K endKey) {
-                checkRange(endKey);
-                if (hasStart) {
-                    return new SubMap<K,V>(startKey, backingMap, endKey);
-                }
-                return new SubMap<K,V>(backingMap, endKey);
-            }
+        public K floor(K key) {
+            return subMap.floorKey(key);
+        }
 
-            @Override
-            public boolean isEmpty() {
-                if (hasStart) {
-                    TreeMap.Entry<K,V> node = backingMap.findAfter(startKey);
-                    return node == null || !checkUpperBound(node.key);
-                }
-                return backingMap.findBefore(endKey) == null;
-            }
+        public NavigableSet<K> descendingSet() {
+            return (null != descendingSet) ? descendingSet
+                    : (descendingSet = new TreeSet<K>(subMap.descendingMap()));
+        }
 
-            @Override
-            public Set<K> keySet() {
-                if (keySet == null) {
-                    keySet = new SubMapKeySet<K,V>(this);
-                }
-                return keySet;
-            }
+        public SortedSet<K> subSet(K start, K end) {
+            return subSet(start, true, end, false);
+        }
 
-            public K lastKey() {
-                if (!hasEnd) {
-                    return backingMap.lastKey();
-                }
-                TreeMap.Entry<K,V> node = backingMap.findBefore(endKey);
-                if (node != null && checkLowerBound(node.key)) {
-                    return node.key;
-                }
-                throw new NoSuchElementException();
-            }
+        public SortedSet<K> headSet(K end) {
+            return headSet(end, false);
+        }
 
-            @Override
-            public V put(K key, V value) {
-                if (isInRange(key)) {
-                    return backingMap.put(key, value);
-                }
-                throw new IllegalArgumentException();
-            }
+        public SortedSet<K> tailSet(K start) {
+            return tailSet(start, true);
+        }
 
-            @SuppressWarnings("unchecked")
-            @Override
-            public V remove(Object key) {
-                if (isInRange((K)key)) {
-                    return backingMap.remove(key);
-                }
-                return null;
-            }
-
-            public SortedMap<K,V> subMap(K startKey, K endKey) {
-                checkRange(startKey);
-                checkRange(endKey);
-                Comparator<? super K> c = backingMap.comparator();
-                if (c == null) {
-                    if (toComparable(startKey).compareTo(endKey) <= 0) {
-                        return new SubMap<K,V>(startKey, backingMap, endKey);
-                    }
-                } else {
-                    if (c.compare(startKey, endKey) <= 0) {
-                        return new SubMap<K,V>(startKey, backingMap, endKey);
-                    }
-                }
-                throw new IllegalArgumentException();
+        @SuppressWarnings("unchecked")
+        public NavigableSet<K> subSet(K start, boolean startInclusive, K end,
+                boolean endInclusive) {
+            // copied from TreeSet
+            if (subMap.backingMap.keyCompare(start, end) <= 0) {
+                return new TreeSet<K>(subMap.subMap(start, startInclusive, end,
+                        endInclusive));
             }
+            throw new IllegalArgumentException();
+        }
 
-            public SortedMap<K,V> tailMap(K startKey) {
-                checkRange(startKey);
-                if (hasEnd) {
-                    return new SubMap<K,V>(startKey, backingMap, endKey);
-                }
-                return new SubMap<K,V>(startKey, backingMap);
-            }
+        @SuppressWarnings("unchecked")
+        public NavigableSet<K> headSet(K end, boolean endInclusive) {
+            // copied from TreeSet
+            // Check for errors
+            subMap.backingMap.keyCompare(end, end);
+            return new TreeSet<K>(subMap.headMap(end, endInclusive));
+        }
 
-            @Override
-            public Collection<V> values() {
-                if(valuesCollection==null) {
-                    valuesCollection = new SubMapValuesCollection<K,V>(this);
-                }
-                return valuesCollection;
-            }
+        @SuppressWarnings("unchecked")
+        public NavigableSet<K> tailSet(K start, boolean startInclusive) {
+            // copied from TreeSet
+            // Check for errors
+            subMap.backingMap.keyCompare(start, start);
+            return new TreeSet<K>(subMap.tailMap(start, startInclusive));
         }
+    }
 
-        static class SubMapEntrySet<K,V> extends AbstractSet<Map.Entry<K,V>> implements Set<Map.Entry<K,V>> {
-            SubMap<K,V> subMap;
+    static class AscendingSubMapKeySet<K> extends SubMapKeySet<K> {
+        AscendingSubMapKeySet(NavigableSubMap<K, K> map) {
+            super(map);
+        }
 
-            SubMapEntrySet(SubMap<K,V> map) {
-                subMap = map;
-            }
+        @Override
+        public final Iterator<K> iterator() {
+            return new AscendingSubMapKeyIterator<K, K>(subMap);
+        }
 
-            @Override
-            public boolean isEmpty() {
-                return subMap.isEmpty();
-            }
+        @Override
+        public final Iterator<K> descendingIterator() {
+            return new DescendingSubMapKeyIterator<K, K>(subMap);
+        }
+    }
 
-            @Override
-            public Iterator<Map.Entry<K,V>> iterator() {
-                TreeMap.Entry<K,V> startNode = subMap.firstEntry();
-                if (subMap.hasEnd) {
-                    Comparator<? super K> cmp = subMap.comparator();
-                    if (cmp == null) {
-                        return new ComparableBoundedEntryIterator<K,V>(subMap.backingMap, startNode, toComparable(subMap.endKey));
-                    }
-                    return new ComparatorBoundedEntryIterator<K,V>(subMap.backingMap, startNode, subMap.endKey);
-                }
-                return new UnboundedEntryIterator<K,V>(subMap.backingMap, startNode);
-            }
+    static class DescendingSubMapKeySet<K> extends SubMapKeySet<K> {
+        DescendingSubMapKeySet(NavigableSubMap<K, K> map) {
+            super(map);
+        }
 
-            @Override
-            public int size() {
-                int size = 0;
-                Iterator<Map.Entry<K,V>> it = iterator();
-                while (it.hasNext()) {
-                    size++;
-                    it.next();
-                }
-                return size;
-            }
-
-            @SuppressWarnings("unchecked")
-            @Override
-            public boolean contains(Object object) {
-                if (object instanceof Map.Entry) {
-                    Map.Entry<K,V> entry = (Map.Entry<K,V>) object;
-                    K key = entry.getKey();
-                    if (subMap.isInRange(key)) {
-                        V v1 = subMap.get(key), v2 = entry.getValue();
-                        return v1 == null ? v2 == null : v1.equals(v2);
-                    }
-                }
-                return false;
-            }
+        @Override
+        public final Iterator<K> iterator() {
+            return new DescendingSubMapKeyIterator<K, K>(subMap);
+        }
 
+        @Override
+        public final Iterator<K> descendingIterator() {
+            return new AscendingSubMapKeyIterator<K, K>(subMap);
         }
+    }
 
-        static class SubMapKeySet<K,V> extends  AbstractSet<K> implements Set<K> {
-            SubMap<K,V> subMap;
+    static abstract class NavigableSubMap<K, V> extends AbstractMap<K, V>
+            implements NavigableMap<K, V>, Serializable {
 
-            SubMapKeySet(SubMap<K,V> map) {
-                subMap = map;
-            }
+        final TreeMap<K, V> backingMap;
 
-            @Override
-            public boolean contains(Object object) {
-                return subMap.containsKey(object);
-            }
+        final K startKey, endKey;
 
-            @Override
-            public boolean isEmpty() {
-                return subMap.isEmpty();
-            }
+        final boolean hasStart, hasEnd;
 
-            @Override
-            public int size() {
-                int size = 0;
-                Iterator<K> it = iterator();
-                while (it.hasNext()) {
-                    size++;
-                    it.next();
-                }
-                return size;
-            }
+        final boolean startInclusive, endInclusive;
 
-            @Override
-            public Iterator<K> iterator() {
-                TreeMap.Entry<K,V> startNode = subMap.firstEntry();
-                if (subMap.hasEnd) {
-                    Comparator<? super K> cmp = subMap.comparator();
-                    if (cmp == null) {
-                        return new ComparableBoundedKeyIterator<K,V>(subMap.backingMap, startNode, toComparable(subMap.endKey));
-                    }
-                    return new ComparatorBoundedKeyIterator<K,V>(subMap.backingMap, startNode, subMap.endKey);
-                }
-                return new UnboundedKeyIterator<K,V>(subMap.backingMap, startNode);
-            }
+        NavigableSubMap(final K start, final boolean startKeyInclusive,
+                final TreeMap<K, V> map, final K end,
+                final boolean endKeyInclusive) {
+            backingMap = map;
+            hasStart = hasEnd = true;
+            startKey = start;
+            endKey = end;
+            startInclusive = startKeyInclusive;
+            endInclusive = endKeyInclusive;
+        }
+
+        NavigableSubMap(final K start, final boolean startKeyInclusive,
+                final TreeMap<K, V> map) {
+            backingMap = map;
+            hasStart = true;
+            hasEnd = false;
+            startKey = start;
+            endKey = null;
+            startInclusive = startKeyInclusive;
+            endInclusive = false;
+        }
+        
+        NavigableSubMap(final TreeMap<K, V> map, final K end,
+                final boolean endKeyInclusive) {
+            backingMap = map;
+            hasStart = false;
+            hasEnd = true;
+            startKey = null;
+            endKey = end;
+            startInclusive = false;
+            endInclusive = endKeyInclusive;
+        }
+
+        // the whole TreeMap
+        NavigableSubMap(final TreeMap<K, V> map) {
+            backingMap = map;
+            hasStart = hasEnd = false;
+            startKey = endKey = null;
+            startInclusive = endInclusive = false;
         }
 
-        static class SubMapValuesCollection<K,V> extends AbstractCollection<V> {
-            SubMap<K,V> subMap;
+        /*
+         * The basic public methods.
+         */
+
+        public Comparator<? super K> comparator() {
+            return backingMap.comparator();
+        }
 
-            public SubMapValuesCollection(SubMap<K,V> subMap) {
-                this.subMap = subMap;
+        @SuppressWarnings("unchecked")
+        @Override
+        public boolean containsKey(Object key) {
+            checkNull(key);
+            if (isInRange((K) key)) {
+                return backingMap.containsKey(key);
+            }
+            return false;
+        }
+        
+        private void checkNull (Object key) {
+            if (null == key && null ==comparator()){
+                throw new NullPointerException();
             }
+        }
+
+        @Override
+        public boolean isEmpty() {
+            return size() == 0;
+        }
+
+        @Override
+        public int size() {
+            return entrySet().size();
+        }
 
-            @Override
-            public boolean isEmpty() {
-                return subMap.isEmpty();
+        @Override
+        public V put(K key, V value) {
+            checkNull(key);
+            if (isInRange(key)) {
+                return backingMap.put(key, value);
             }
+            throw new IllegalArgumentException();
+        }
 
-            @Override
-            public Iterator<V> iterator() {
-                TreeMap.Entry<K,V> startNode = subMap.firstEntry();
-                if (subMap.hasEnd) {
-                    Comparator<? super K> cmp = subMap.comparator();
-                    if (cmp == null) {
-                        return new ComparableBoundedValueIterator<K,V>(subMap.backingMap, startNode, toComparable(subMap.endKey));
-                    }
-                    return new ComparatorBoundedValueIterator<K,V>(subMap.backingMap, startNode, subMap.endKey);
-                }
-                return new UnboundedValueIterator<K,V>(subMap.backingMap, startNode);
+        @SuppressWarnings("unchecked")
+        @Override
+        public V get(Object key) {
+            checkNull(key);
+            if (isInRange((K) key)) {
+                return backingMap.get(key);
             }
+            return null;
+        }
 
-            @Override
-            public int size() {
-                int cnt = 0;
-                for (Iterator<V> it = iterator(); it.hasNext();) {
-                    it.next();
-                    cnt++;
-                }
-                return cnt;
+        @SuppressWarnings("unchecked")
+        @Override
+        public V remove(Object key) {
+            checkNull(key);
+            if (isInRange((K) key)) {
+                return backingMap.remove(key);
             }
+            return null;
         }
 
-	/**
-	 * Constructs a new empty instance of TreeMap.
-	 * 
-	 */
-	public TreeMap() {
-		super();
-	}
+        /*
+         * The navigable methods.
+         */
 
-	/**
-	 * Constructs a new empty instance of TreeMap which uses the specified
-	 * Comparator.
-	 * 
-	 * @param comparator
-	 *            the Comparator
-	 */
-	public TreeMap(Comparator<? super K> comparator) {
-		this.comparator = comparator;
-	}
+        public abstract Map.Entry<K, V> firstEntry();
 
-	/**
-	 * Constructs a new instance of TreeMap containing the mappings from the
-	 * specified Map and using the natural ordering.
-	 * 
-	 * @param map
-	 *            the mappings to add
-	 * 
-	 * @exception ClassCastException
-	 *                when a key in the Map does not implement the Comparable
-	 *                interface, or they keys in the Map cannot be compared
-	 */
-	public TreeMap(Map<? extends K,? extends V> map) {
-		this();
-		putAll(map);
-	}
+        public abstract Map.Entry<K, V> lastEntry();
 
-	/**
-	 * Constructs a new instance of TreeMap containing the mappings from the
-	 * specified SortedMap and using the same Comparator.
-	 * 
-	 * @param map
-	 *            the mappings to add
-	 */
-	public TreeMap(SortedMap<K,? extends V> map) {
-		this(map.comparator());
-		Iterator<? extends Map.Entry<K, ? extends V>> it = map.entrySet().iterator();
-		if (it.hasNext()) {
-			Map.Entry<K, ? extends V> entry = it.next();
-			Entry<K, V> last = new Entry<K, V>(entry.getKey(), entry.getValue());
-			root = last;
-			size = 1;
-			while (it.hasNext()) {
-				entry = it.next();
-				Entry<K, V> x = new Entry<K, V>(entry.getKey(), entry.getValue());
-				x.parent = last;
-				last.right = x;
-				size++;
-				balance(x);
-				last = x;
-			}
-		}
-	}
+        public abstract Map.Entry<K, V> pollFirstEntry();
 
-	void balance(Entry<K, V> x) {
-		Entry<K, V> y;
-		x.color = true;
-		while (x != root && x.parent.color) {
-			if (x.parent == x.parent.parent.left) {
-				y = x.parent.parent.right;
-				if (y != null && y.color) {
-					x.parent.color = false;
-					y.color = false;
-					x.parent.parent.color = true;
-					x = x.parent.parent;
-				} else {
-					if (x == x.parent.right) {
-						x = x.parent;
-						leftRotate(x);
-					}
-					x.parent.color = false;
-					x.parent.parent.color = true;
-					rightRotate(x.parent.parent);
-				}
-			} else {
-				y = x.parent.parent.left;
-				if (y != null && y.color) {
-					x.parent.color = false;
-					y.color = false;
-					x.parent.parent.color = true;
-					x = x.parent.parent;
-				} else {
-					if (x == x.parent.left) {
-						x = x.parent;
-						rightRotate(x);
-					}
-					x.parent.color = false;
-					x.parent.parent.color = true;
-					leftRotate(x.parent.parent);
-				}
-			}
-		}
-		root.color = false;
-	}
+        public abstract Map.Entry<K, V> pollLastEntry();
 
-	/**
-	 * Removes all mappings from this TreeMap, leaving it empty.
-	 * 
-	 * @see Map#isEmpty
-	 * @see #size
-	 */
-	@Override
-    public void clear() {
-		root = null;
-		size = 0;
-		modCount++;
-	}
+        public abstract Map.Entry<K, V> higherEntry(K key);
 
-	/**
-	 * Answers a new TreeMap with the same mappings, size and comparator as this
-	 * TreeMap.
-	 * 
-	 * @return a shallow copy of this TreeMap
-	 * 
-	 * @see java.lang.Cloneable
-	 */
-	@SuppressWarnings("unchecked")
-    @Override
-    public Object clone() {
-		try {
-			TreeMap<K, V> clone = (TreeMap<K, V>) super.clone();
-			clone.entrySet = null;
-			if (root != null) {
-                clone.root = root.clone(null);
+        public abstract Map.Entry<K, V> lowerEntry(K key);
+
+        public abstract Map.Entry<K, V> ceilingEntry(K key);
+
+        public abstract Map.Entry<K, V> floorEntry(K key);
+
+        public K firstKey() {
+            Map.Entry<K, V> node = firstEntry();
+            if (node != null) {
+                return node.getKey();
             }
-			return clone;
-		} catch (CloneNotSupportedException e) {
-			return null;
-		}
-	}
+            throw new NoSuchElementException();
+        }
 
-	/**
-	 * Answers the Comparator used to compare elements in this TreeMap.
-	 * 
-	 * @return a Comparator or null if the natural ordering is used
-	 */
-	public Comparator<? super K> comparator() {
-		return comparator;
-	}
+        public K lastKey() {
+            Map.Entry<K, V> node = lastEntry();
+            if (node != null) {
+                return node.getKey();
+            }
+            throw new NoSuchElementException();
+        }
 
-	/**
-	 * Searches this TreeMap for the specified key.
-	 * 
-	 * @param key
-	 *            the object to search for
-	 * @return true if <code>key</code> is a key of this TreeMap, false
-	 *         otherwise
-	 * 
-	 * @exception ClassCastException
-	 *                when the key cannot be compared with the keys in this
-	 *                TreeMap
-	 * @exception NullPointerException
-	 *                when the key is null and the comparator cannot handle null
-	 */
-    @Override
-    public boolean containsKey(Object key) {
-		return find(key) != null;
-	}
+        public K higherKey(K key) {
+            Map.Entry<K, V> entry = higherEntry(key);
+            return (null == entry) ? null : entry.getKey();
+        }
 
-	/**
-	 * Searches this TreeMap for the specified value.
-	 * 
-	 * @param value
-	 *            the object to search for
-	 * @return true if <code>value</code> is a value of this TreeMap, false
-	 *         otherwise
-	 */
-	@Override
-    public boolean containsValue(Object value) {
-		if (root != null) {
-            return containsValue(root, value);
+        public K lowerKey(K key) {
+            Map.Entry<K, V> entry = lowerEntry(key);
+            return (null == entry) ? null : entry.getKey();
         }
-		return false;
-	}
 
-	private boolean containsValue(Entry<K, V> node, Object value) {
-		if (value == null ? node.value == null : value.equals(node.value)) {
+        public K ceilingKey(K key) {
+            Map.Entry<K, V> entry = ceilingEntry(key);
+            return (null == entry) ? null : entry.getKey();
+        }
+
+        public K floorKey(K key) {
+            Map.Entry<K, V> entry = floorEntry(key);
+            return (null == entry) ? null : entry.getKey();
+        }
+
+        /*
+         * The sub-collection methods.
+         */
+
+        public abstract NavigableSet<K> navigableKeySet();
+
+        @Override
+        public abstract Set<Map.Entry<K, V>> entrySet();
+
+        @Override
+        public Set<K> keySet() {
+            return navigableKeySet();
+        }
+
+        public NavigableSet<K> descendingKeySet() {
+            return descendingMap().navigableKeySet();
+        }
+
+        public SortedMap<K, V> subMap(K start, K end) {
+            return subMap(start, true, end, false);
+        }
+
+        public SortedMap<K, V> headMap(K end) {
+            return headMap(end, false);
+        }
+
+        public SortedMap<K, V> tailMap(K start) {
+            return tailMap(start, true);
+        }
+
+        public abstract NavigableMap<K, V> subMap(K start,
+                boolean startKeyInclusive, K end, boolean endKeyInclusive);
+
+        public abstract NavigableMap<K, V> headMap(K end, boolean inclusive);
+
+        public abstract NavigableMap<K, V> tailMap(K start, boolean inclusive);
+
+        /**
+         * 
+         * @param key
+         * @return false if the key bigger than the end key (if any)
+         */
+        final boolean checkUpperBound(K key) {
+            if (hasEnd) {
+                int result = backingMap.keyCompare(key, endKey);
+                return endInclusive ? result <= 0 : result < 0;
+            }
             return true;
         }
-		if (node.left != null) {
-            if (containsValue(node.left, value)) {
-                return true;
+
+        /**
+         * 
+         * @param key
+         * @return false if the key smaller than the start key (if any)
+         */
+        final boolean checkLowerBound(K key) {
+            if (hasStart) {
+                int result = -backingMap.keyCompare(startKey, key);
+                return startInclusive ? result >= 0 : result > 0;
             }
+            return true;
         }
-		if (node.right != null) {
-            if (containsValue(node.right, value)) {
-                return true;
+
+        final boolean isInRange(K key) {
+            return checkUpperBound(key) && checkLowerBound(key);
+        }
+
+        final TreeMap.Entry<K, V> theSmallestEntry() {
+            if (backingMap.isRootWithIllegalNullKey()) {
+                return backingMap.root;
             }
+            TreeMap.Entry<K, V> result = null;
+            if (!hasStart) {
+                result = backingMap.findSmallestEntry();
+            } else {
+                result = startInclusive ? backingMap.findCeilingEntry(startKey)
+                        : backingMap.findHigherEntry(startKey);
+            }
+            return (null != result && checkUpperBound(result.getKey())) ? result
+                    : null;
         }
-		return false;
-	}
 
-	/**
-	 * Answers a Set of the mappings contained in this TreeMap. Each element in
-	 * the set is a Map.Entry. The set is backed by this TreeMap so changes to
-	 * one are reflected by the other. The set does not support adding.
-	 * 
-	 * @return a Set of the mappings
-	 */
-	@Override
-    public Set<Map.Entry<K, V>> entrySet() {
-        if (entrySet == null) {
-            entrySet = new AbstractSet<Map.Entry<K, V>>() {
-                 @Override
-                public int size() {
-                    return size;
+        final TreeMap.Entry<K, V> theBiggestEntry() {
+            if (backingMap.isRootWithIllegalNullKey()) {
+                return backingMap.root;
+            }
+            TreeMap.Entry<K, V> result = null;
+            if (!hasEnd) {
+                result = backingMap.findBiggestEntry();
+            } else {
+                result = endInclusive ? backingMap.findFloorEntry(endKey)
+                        : backingMap.findLowerEntry(endKey);
+            }
+            return (null != result && checkLowerBound(result.getKey())) ? result
+                    : null;
+        }
+        
+        final TreeMap.Entry<K, V> smallerOrEqualEntry(K key) {
+            if (backingMap.isRootWithIllegalNullKey()) {
+                return backingMap.root;
+            }
+            TreeMap.Entry<K, V> result = findFloorEntry(key);
+            return (null != result && checkLowerBound(result.getKey())) ? result
+                    : null;
+        }
+        
+        TreeMap.Entry<K, V> findFloorEntry(K key) {
+            int result;
+            boolean belowUpper = false;
+            boolean aboveLower  = false;
+            TreeMap.Entry<K, V> node = backingMap.root, last = null;
+            while (node != null) {
+                belowUpper = checkUpperBound(node.key);
+                aboveLower  = checkLowerBound(node.key);
+                result = backingMap.keyCompare(key, node.key);
+                if (result == 0 && aboveLower && belowUpper) {
+                    return node;
+                } else if (0 < result && belowUpper || result == 0 && !aboveLower) {
+                    last = node;
+                    node = node.right;
+                } else if( 0 > result && aboveLower || result == 0 && !belowUpper){
+                    node = node.left;
+                } else {
+                    node = null;
                 }
+            }
+            return last;
+        }
 
-                @Override
-                public void clear() {
-                    TreeMap.this.clear();
+        final TreeMap.Entry<K, V> biggerOrEqualEntry(K key) {
+            if (backingMap.isRootWithIllegalNullKey()) {
+                return backingMap.root;
+            }
+            TreeMap.Entry<K, V> result = findCeilingEntry(key);
+            return (null != result && checkUpperBound(result.getKey())) ? result
+                    : null;
+        }
+        
+        TreeMap.Entry<K, V> findCeilingEntry(K key) {
+            int result;
+            boolean belowUpper = false;
+            boolean aboveLower  = false;
+            TreeMap.Entry<K, V> node = backingMap.root, last = null;
+            while (node != null) {
+                belowUpper = checkUpperBound(node.key);
+                aboveLower  = checkLowerBound(node.key);
+                result = backingMap.keyCompare(key, node.key);
+                if (result == 0 && aboveLower && belowUpper) {
+                    return node;
+                }
+                else if (0 > result && aboveLower || result == 0 && !belowUpper) {
+                    last = node;
+                    node = node.left;
                 }
+                else if (0 < result && belowUpper || result == 0 && !aboveLower){
+                    node = node.right;
+                } else {
+                    node = null;
+                }
+            }
+            return last;
+        }
 
-                @SuppressWarnings("unchecked")
-                @Override
-                public boolean contains(Object object) {
-                    if (object instanceof Map.Entry) {
-                        Map.Entry<K, V> entry = (Map.Entry<K, V>) object;
-                        Object v1 = get(entry.getKey()), v2 = entry.getValue();
-                        return v1 == null ? v2 == null : v1.equals(v2);
-                    }
-                    return false;
+        final TreeMap.Entry<K, V> smallerEntry(K key) {
+            if (backingMap.isRootWithIllegalNullKey()) {
+                return backingMap.root;
+            }
+            TreeMap.Entry<K, V> result = findLowerEntry(key);
+            return (null != result && checkLowerBound(result.getKey())) ? result
+                    : null;
+        }
+        
+        TreeMap.Entry<K, V> findLowerEntry(K key) {
+            int result = -1;
+            boolean belowUpper = true;
+            TreeMap.Entry<K, V> node = backingMap.root, last = null;
+            while (node != null) {
+                belowUpper = checkUpperBound(node.key);
+                result = backingMap.keyCompare(key, node.key);
+                if (result > 0 && belowUpper) {
+                    last = node;
+                    node = node.right;
+                } else {
+                    node = node.left;
                 }
+            }
+            return last;
+        }
 
-                @Override
-                public Iterator<Map.Entry<K, V>> iterator() {
-                    return new UnboundedEntryIterator<K, V>(TreeMap.this);
+        final TreeMap.Entry<K, V> biggerEntry(K key) {
+            if (backingMap.isRootWithIllegalNullKey()) {
+                return backingMap.root;
+            }
+            TreeMap.Entry<K, V> result = findHigherEntry(key);
+            return (null != result && checkUpperBound(result.getKey())) ? result
+                    : null;
+        }
+        
+        TreeMap.Entry<K, V> findHigherEntry(K key) {
+            int result = -1;
+            boolean aboveLower  = true;
+            TreeMap.Entry<K, V> node = backingMap.root, last = null;
+            while (node != null) {
+                aboveLower = checkLowerBound(node.key);
+                result = backingMap.keyCompare(key, node.key);
+                if (result < 0 && aboveLower) {
+                    last = node;
+                    node = node.left;
+                } else {
+                    node = node.right;
                 }
-            };
+            }
+            return last;
         }
-        return entrySet;
+
     }
 
-	@SuppressWarnings("unchecked")
-    private Entry<K, V> find(Object keyObj) {
-		int result;
-        K key = (K)keyObj;
-		Comparable<K> object = null;
-		if (comparator == null) {
-            object = toComparable(key);
-    		Entry<K, V> x = root;
-    		while (x != null) {
-    			result = object.compareTo(x.key);
-    			if (result == 0) {
-                    return x;
+    static class AscendingSubMap<K, V> extends NavigableSubMap<K, V> implements
+            Serializable {
+
+        private static final long serialVersionUID = 912986545866124060L;
+
+        AscendingSubMap(K start, boolean startKeyInclusive, TreeMap<K, V> map,
+                K end, boolean endKeyInclusive) {
+            super(start, startKeyInclusive, map, end, endKeyInclusive);
+        }
+
+        AscendingSubMap(TreeMap<K, V> map, K end, boolean endKeyInclusive) {
+            super(map, end, endKeyInclusive);
+        }
+
+        AscendingSubMap(K start, boolean startKeyInclusive, TreeMap<K, V> map) {
+            super(start, startKeyInclusive, map);
+        }
+
+        AscendingSubMap(TreeMap<K, V> map) {
+            super(map);
+        }
+
+        @Override
+        public Map.Entry<K, V> firstEntry() {
+            return backingMap.newImmutableEntry(theSmallestEntry());
+        }
+
+        @Override
+        public Map.Entry<K, V> lastEntry() {
+            return backingMap.newImmutableEntry(theBiggestEntry());
+        }
+
+        @Override
+        public Map.Entry<K, V> pollFirstEntry() {
+            TreeMap.Entry<K, V> node = theSmallestEntry();
+            SimpleImmutableEntry<K, V> result = backingMap
+                    .newImmutableEntry(node);
+            if (null != node) {
+                backingMap.rbDelete(node);
+            }
+            return result;
+        }
+
+        @Override
+        public Map.Entry<K, V> pollLastEntry() {
+            TreeMap.Entry<K, V> node = theBiggestEntry();
+            SimpleImmutableEntry<K, V> result = backingMap
+                    .newImmutableEntry(node);
+            if (null != node) {
+                backingMap.rbDelete(node);
+            }
+            return result;
+        }
+
+        @Override
+        public Map.Entry<K, V> higherEntry(K key) {
+            return backingMap.newImmutableEntry(biggerEntry(key));
+        }
+
+        @Override
+        public Map.Entry<K, V> lowerEntry(K key) {
+            return backingMap.newImmutableEntry(smallerEntry(key));
+        }
+
+        @Override
+        public Map.Entry<K, V> ceilingEntry(K key) {
+            return backingMap.newImmutableEntry(biggerOrEqualEntry(key));
+        }
+
+        @Override
+        public Map.Entry<K, V> floorEntry(K key) {
+            return backingMap.newImmutableEntry(smallerOrEqualEntry(key));
+        }
+
+        @Override
+        public Set<Map.Entry<K, V>> entrySet() {
+            return new AscendingSubMapEntrySet<K, V>(this);
+        }
+
+        @SuppressWarnings("unchecked")
+        @Override
+        public NavigableSet<K> navigableKeySet() {
+            return new AscendingSubMapKeySet(this);
+        }
+
+        public NavigableMap<K, V> descendingMap() {
+            if (hasStart && hasEnd) {
+                return new DescendingSubMap<K, V>(startKey, startInclusive,
+                        backingMap, endKey, endInclusive);
+            }
+            if (hasStart) {
+                return new DescendingSubMap<K, V>(startKey, startInclusive,
+                        backingMap);
+            }
+            if (hasEnd) {
+                return new AscendingSubMap<K, V>(backingMap, endKey, endInclusive);
+            }
+            return new DescendingSubMap<K, V>(backingMap);
+        }
+
+        @Override
+        public NavigableMap<K, V> subMap(K start, boolean startKeyInclusive,
+                K end, boolean endKeyInclusive) {
+            if (backingMap.keyCompare(start, end) <= 0) {
+                if ((hasStart && backingMap.keyCompare(start, startKey) < 0)
+                        || (hasEnd && backingMap.keyCompare(end, endKey) > 0)) {
+                    throw new IllegalArgumentException();
+                }
+                K inclusiveStart = startKeyInclusive ? start : higherKey(start);
+                K inclusiveEnd = endKeyInclusive ? end : lowerKey(end);
+                boolean legalStart = (null == inclusiveStart)
+                        || checkLowerBound(inclusiveStart);
+                boolean legalEnd = (null == inclusiveEnd)
+                        || checkUpperBound(inclusiveEnd);
+                if (legalStart && legalEnd) {
+                    return new AscendingSubMap<K, V>(start, startKeyInclusive,
+                            backingMap, end, endKeyInclusive);
                 }
-    			x = result < 0 ? x.left : x.right;
-    		}
-        } else {
-    		Entry<K, V> x = root;
-    		while (x != null) {
-    			result = comparator.compare(key, x.key);
-    			if (result == 0) {
-                    return x;
+            }
+            throw new IllegalArgumentException();
+        }
+
+        @Override
+        public NavigableMap<K, V> headMap(K end, boolean inclusive) {
+            if (hasEnd && backingMap.keyCompare(end, endKey) > 0) {
+                throw new IllegalArgumentException();
+            }
+            K inclusiveEnd = inclusive ? end : lowerKey(end);
+            if (null == inclusiveEnd || checkUpperBound(inclusiveEnd)) {
+                if (this.hasStart) {
+                    return new AscendingSubMap<K, V>(this.startKey,
+                            this.startInclusive, backingMap, end, inclusive);
                 }
-    			x = result < 0 ? x.left : x.right;
-    		}
+                return new AscendingSubMap<K, V>(backingMap, end, inclusive);
+            }
+            throw new IllegalArgumentException();
         }
-		return null;
-	}
 
-	@SuppressWarnings("unchecked")
-    Entry<K, V> findAfter(Object keyObj) {
-        K key = (K)keyObj;
-		int result;
-		Comparable<K> object = null;
-		if (comparator == null) {
-            object = toComparable(key);
-        }
-		Entry<K, V> x = root, last = null;
-		while (x != null) {
-			result = object != null ? object.compareTo(x.key) : comparator
-					.compare(key, x.key);
-			if (result == 0) {
-                return x;
-            }
-			if (result < 0) {
-				last = x;
-				x = x.left;
-			} else {
-                x = x.right;
+        @Override
+        public NavigableMap<K, V> tailMap(K start, boolean inclusive) {
+            if (hasStart && backingMap.keyCompare(start, startKey) < 0) {
+                throw new IllegalArgumentException();
             }
-		}
-		return last;
-	}
+            K inclusiveStart = inclusive ? start : higherKey(start);
+            if (null == inclusiveStart || checkLowerBound(inclusiveStart)) {
+                if (this.hasEnd) {
+                    return new AscendingSubMap<K, V>(start, inclusive,
+                            backingMap, this.endKey, this.endInclusive);
+                }
+                return new AscendingSubMap<K, V>(start, inclusive, backingMap);
 
-	Entry<K, V> findBefore(K key) {
-		int result;
-        Comparable<K> object = null;
-		if (comparator == null) {
-            object = toComparable(key);
-        }
-		Entry<K, V> x = root, last = null;
-		while (x != null) {
-			result = object != null ? object.compareTo(x.key) : comparator
-					.compare(key, x.key);
-			if (result <= 0) {
-                x = x.left;
+            }
+            throw new IllegalArgumentException();
+        }
+    }
+
+    static class DescendingSubMap<K, V> extends NavigableSubMap<K, V> implements
+            Serializable {
+        private static final long serialVersionUID = 912986545866120460L;
+
+        private final Comparator<? super K> reverseComparator = Collections
+                .reverseOrder(backingMap.comparator);
+
+        DescendingSubMap(K start, boolean startKeyInclusive, TreeMap<K, V> map,
+                K end, boolean endKeyInclusive) {
+            super(start, startKeyInclusive, map, end, endKeyInclusive);
+        }
+
+        DescendingSubMap(K start, boolean startKeyInclusive, TreeMap<K, V> map) {
+            super(start, startKeyInclusive, map);
+        }
+
+        DescendingSubMap(TreeMap<K, V> map, K end, boolean endKeyInclusive) {
+            super(map, end, endKeyInclusive);
+        }
+
+        DescendingSubMap(TreeMap<K, V> map) {
+            super(map);
+        }
+
+        @Override
+        public Comparator<? super K> comparator() {
+            return reverseComparator;
+        }
+
+        @Override
+        public Map.Entry<K, V> firstEntry() {
+            return backingMap.newImmutableEntry(theBiggestEntry());
+        }
+
+        @Override
+        public Map.Entry<K, V> lastEntry() {
+            return backingMap.newImmutableEntry(theSmallestEntry());
+        }
+
+        @Override
+        public Map.Entry<K, V> pollFirstEntry() {
+            TreeMap.Entry<K, V> node = theBiggestEntry();
+            SimpleImmutableEntry<K, V> result = backingMap
+                    .newImmutableEntry(node);
+            if (null != node) {
+                backingMap.rbDelete(node);
+            }
+            return result;
+        }
+
+        @Override
+        public Map.Entry<K, V> pollLastEntry() {
+            TreeMap.Entry<K, V> node = theSmallestEntry();
+            SimpleImmutableEntry<K, V> result = backingMap
+                    .newImmutableEntry(node);
+            if (null != node) {
+                backingMap.rbDelete(node);
+            }
+            return result;
+        }
+
+        @Override
+        public Map.Entry<K, V> higherEntry(K key) {
+            return backingMap.newImmutableEntry(smallerEntry(key));
+        }
+
+        @Override
+        public Map.Entry<K, V> lowerEntry(K key) {
+            return backingMap.newImmutableEntry(biggerEntry(key));
+        }
+
+        @Override
+        public Map.Entry<K, V> ceilingEntry(K key) {
+            return backingMap.newImmutableEntry(smallerOrEqualEntry(key));
+        }
+
+        @Override
+        public Map.Entry<K, V> floorEntry(K key) {
+            return backingMap.newImmutableEntry(biggerOrEqualEntry(key));
+        }
+
+        @Override
+        public Set<Map.Entry<K, V>> entrySet() {
+            return new DescendingSubMapEntrySet<K, V>(this);
+        }
+
+        @SuppressWarnings("unchecked")
+        @Override
+        public NavigableSet<K> navigableKeySet() {
+            return new DescendingSubMapKeySet(this);
+        }
+
+        public NavigableMap<K, V> descendingMap() {
+            if (hasStart && hasEnd) {
+                return new AscendingSubMap<K, V>(startKey, startInclusive,
+                        backingMap, endKey, endInclusive);
+            }
+            if (hasStart) {
+                return new AscendingSubMap<K, V>(startKey, startInclusive,
+                        backingMap);
+            }
+            if (hasEnd) {
+                return new AscendingSubMap<K, V>(backingMap, endKey, endInclusive);
+            }
+            return new AscendingSubMap<K, V>(backingMap);
+        }
+
+        int keyCompare(K left, K right) {
+            return (null != reverseComparator) ? reverseComparator.compare(
+                    left, right) : toComparable(left).compareTo(right);
+        }
+
+        @Override
+        public NavigableMap<K, V> subMap(K start, boolean startKeyInclusive,
+                K end, boolean endKeyInclusive) {
+            if (this.keyCompare(start, end) <= 0) {
+                K inclusiveStart = startKeyInclusive ? start : higherKey(start);
+                K inclusiveEnd = endKeyInclusive ? end : lowerKey(end);
+                boolean legalStart = (null == inclusiveStart)
+                        || checkLowerBound(inclusiveStart);
+                boolean legalEnd = (null == inclusiveEnd)
+                        || checkUpperBound(inclusiveEnd);
+                if (legalStart && legalEnd) {
+                    return new DescendingSubMap<K, V>(end, endKeyInclusive,
+                            backingMap, start, startKeyInclusive);
+                }
+            }
+            throw new IllegalArgumentException();
+        }
+
+        @Override
+        public NavigableMap<K, V> headMap(K end, boolean inclusive) {
+            // check for error
+            this.keyCompare(end, end);
+            K inclusiveEnd = inclusive ? end : lowerKey(end);
+            if (null == inclusiveEnd || checkLowerBound(inclusiveEnd)) {
+                if (this.hasEnd) {
+                    return new DescendingSubMap<K, V>(end, inclusive,
+                            backingMap, this.endKey, this.endInclusive);
+                }
+                return new DescendingSubMap<K, V>(end, inclusive, backingMap);
+            }
+            throw new IllegalArgumentException();
+        }
+
+        @Override
+        public NavigableMap<K, V> tailMap(K start, boolean inclusive) {
+            // check for error
+            this.keyCompare(start, start);
+            K inclusiveStart = inclusive ? start : higherKey(start);
+            if (null == inclusiveStart || checkUpperBound(inclusiveStart)) {
+                if (this.hasStart) {
+                    return new DescendingSubMap<K, V>(this.startKey,
+                            this.startInclusive, backingMap, start, inclusive);
+                }
+                return new DescendingSubMap<K, V>(backingMap, start, inclusive);
+
+            }
+            throw new IllegalArgumentException();
+        }
+    }
+
+    /**
+     * Constructs a new empty instance of TreeMap.
+     * 
+     */
+    public TreeMap() {
+        super();
+    }
+
+    /**
+     * Constructs a new empty instance of TreeMap which uses the specified
+     * Comparator.
+     * 
+     * @param theComparator
+     *            the Comparator
+     */
+    public TreeMap(Comparator<? super K> theComparator) {
+        this.comparator = theComparator;
+    }
+
+    /**
+     * Constructs a new instance of TreeMap containing the mappings from the
+     * specified Map and using the natural ordering.
+     * 
+     * @param map
+     *            the mappings to add
+     * 
+     * @exception ClassCastException
+     *                when a key in the Map does not implement the Comparable
+     *                interface, or they keys in the Map cannot be compared
+     */
+    public TreeMap(Map<? extends K, ? extends V> map) {
+        this();
+        putAll(map);
+    }
+
+    /**
+     * Constructs a new instance of TreeMap containing the mappings from the
+     * specified SortedMap and using the same Comparator.
+     * 
+     * @param map
+     *            the mappings to add
+     */
+    public TreeMap(SortedMap<K, ? extends V> map) {
+        this(map.comparator());
+        Iterator<? extends Map.Entry<K, ? extends V>> it = map.entrySet()
+                .iterator();
+        if (it.hasNext()) {
+            Map.Entry<K, ? extends V> entry = it.next();
+            Entry<K, V> last = new Entry<K, V>(entry.getKey(), entry.getValue());
+            root = last;
+            size = 1;
+            while (it.hasNext()) {
+                entry = it.next();
+                Entry<K, V> x = new Entry<K, V>(entry.getKey(), entry
+                        .getValue());
+                x.parent = last;
+                last.right = x;
+                size++;
+                balance(x);
+                last = x;
+            }
+        }
+    }
+
+    void balance(Entry<K, V> x) {
+        Entry<K, V> y;
+        x.color = true;
+        while (x != root && x.parent.color) {
+            if (x.parent == x.parent.parent.left) {
+                y = x.parent.parent.right;
+                if (y != null && y.color) {
+                    x.parent.color = false;
+                    y.color = false;
+                    x.parent.parent.color = true;
+                    x = x.parent.parent;
+                } else {
+                    if (x == x.parent.right) {
+                        x = x.parent;
+                        leftRotate(x);
+                    }
+                    x.parent.color = false;
+                    x.parent.parent.color = true;
+                    rightRotate(x.parent.parent);
+                }
             } else {
-				last = x;
-				x = x.right;
+                y = x.parent.parent.left;
+                if (y != null && y.color) {
+                    x.parent.color = false;
+                    y.color = false;
+                    x.parent.parent.color = true;
+                    x = x.parent.parent;
+                } else {
+                    if (x == x.parent.left) {
+                        x = x.parent;
+                        rightRotate(x);
+                    }
+                    x.parent.color = false;
+                    x.parent.parent.color = true;
+                    leftRotate(x.parent.parent);
+                }
+            }
+        }
+        root.color = false;
+    }
+
+    /**
+     * Removes all mappings from this TreeMap, leaving it empty.
+     * 
+     * @see Map#isEmpty
+     * @see #size
+     */
+    @Override
+    public void clear() {
+        root = null;
+        size = 0;
+        modCount++;
+    }
+
+    /**
+     * Answers a new TreeMap with the same mappings, size and comparator as this
+     * TreeMap.
+     * 
+     * @return a shallow copy of this TreeMap
+     * 
+     * @see java.lang.Cloneable
+     */
+    @SuppressWarnings("unchecked")
+    @Override
+    public Object clone() {
+        try {
+            TreeMap<K, V> clone = (TreeMap<K, V>) super.clone();
+            clone.entrySet = null;
+            clone.navigableKeySet = null;
+            clone.descendingMap = null;
+            clone.valuesCollection = null;
+            clone.keySet = null;
+            if (root != null) {
+                clone.root = root.clone(null);
+            }
+            return clone;
+        } catch (CloneNotSupportedException e) {
+            return null;
+        }
+    }
+
+    /**
+     * Answers the Comparator used to compare elements in this TreeMap.
+     * 
+     * @return a Comparator or null if the natural ordering is used
+     */
+    public Comparator<? super K> comparator() {
+        return comparator;
+    }
+
+    /**
+     * Searches this TreeMap for the specified key.
+     * 
+     * @param key
+     *            the object to search for
+     * @return true if <code>key</code> is a key of this TreeMap, false
+     *         otherwise
+     * 
+     * @exception ClassCastException
+     *                when the key cannot be compared with the keys in this
+     *                TreeMap
+     * @exception NullPointerException
+     *                when the key is null and the comparator cannot handle null
+     */
+    @Override
+    public boolean containsKey(Object key) {
+        return find(key) != null;
+    }
+
+    /**
+     * Searches this TreeMap for the specified value.
+     * 
+     * @param value
+     *            the object to search for
+     * @return true if <code>value</code> is a value of this TreeMap, false
+     *         otherwise
+     */
+    @Override
+    public boolean containsValue(Object value) {
+        if (root != null) {
+            return containsValue(root, value);
+        }
+        return false;
+    }
+
+    private boolean containsValue(Entry<K, V> node, Object value) {
+        if (value == null ? node.value == null : value.equals(node.value)) {
+            return true;
+        }
+        if (node.left != null) {
+            if (containsValue(node.left, value)) {
+                return true;
+            }
+        }
+        if (node.right != null) {
+            if (containsValue(node.right, value)) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    @SuppressWarnings("unchecked")
+    Entry<K, V> find(Object keyObj) {
+		int result;
+		K key = (K) keyObj;
+		Entry<K, V> x = root;
+		if (null != comparator) {
+			while (x != null) {
+				result = comparator.compare(key, x.key);
+				if (result == 0) {
+					return x;
+				}
+				x = result < 0 ? x.left : x.right;
 			}
+			return null;
+		} else {
+			Comparable<K> targetKey = (Comparable<K>) key;
+			while (x != null) {
+				result = targetKey.compareTo(x.key);
+				if (result == 0) {
+					return x;
+				}
+				x = result < 0 ? x.left : x.right;
+			}
+			return null;
 		}
-		return last;
 	}
 
-	/**
-	 * Answer the first sorted key in this TreeMap.
-	 * 
-	 * @return the first sorted key
-	 * 
-	 * @exception NoSuchElementException
-	 *                when this TreeMap is empty
-	 */
-	public K firstKey() {
-		if (root != null) {
-            return minimum(root).key;
-        }
-		throw new NoSuchElementException();
-	}
+    TreeMap.Entry<K, V> findSmallestEntry() {
+        return (null == root) ? null : minimum(root);
+    }
 
-	private void fixup(Entry<K, V> x) {
-		Entry<K, V> w;
-		while (x != root && !x.color) {
-			if (x == x.parent.left) {
-				w = x.parent.right;
-				if (w == null) {
-					x = x.parent;
-					continue;
-				}
-				if (w.color) {
-					w.color = false;
-					x.parent.color = true;
-					leftRotate(x.parent);
-					w = x.parent.right;
-					if (w == null) {
-						x = x.parent;
-						continue;
-					}
+    TreeMap.Entry<K, V> findBiggestEntry() {
+        return (null == root) ? null : maximum(root);
+    }
+
+    TreeMap.Entry<K, V> findCeilingEntry(K key) {
+		int result;
+		Entry<K, V> node = root, last = null;
+		if (null != comparator) {
+			while (node != null) {
+				result = comparator.compare(key, node.key);
+				if (result == 0) {
+					return node;
 				}
-				if ((w.left == null || !w.left.color)
-						&& (w.right == null || !w.right.color)) {
-					w.color = true;
-					x = x.parent;
+				if (result < 0) {
+					last = node;
+					node = node.left;
 				} else {
-					if (w.right == null || !w.right.color) {
-						w.left.color = false;
-						w.color = true;
-						rightRotate(w);
-						w = x.parent.right;
-					}
-					w.color = x.parent.color;
-					x.parent.color = false;
-					w.right.color = false;
-					leftRotate(x.parent);
-					x = root;
-				}
-			} else {
-				w = x.parent.left;
-				if (w == null) {
-					x = x.parent;
-					continue;
+					node = node.right;
 				}
-				if (w.color) {
-					w.color = false;
-					x.parent.color = true;
-					rightRotate(x.parent);
-					w = x.parent.left;
-					if (w == null) {
-						x = x.parent;
-						continue;
-					}
+			}
+			return last;
+		} else {
+			Comparable<K> targetKey = (Comparable<K>) key;
+			while (node != null) {
+				result = targetKey.compareTo(node.key);
+				if (result == 0) {
+					return node;
 				}
-				if ((w.left == null || !w.left.color)
-						&& (w.right == null || !w.right.color)) {
-					w.color = true;
-					x = x.parent;
+				if (result < 0) {
+					last = node;
+					node = node.left;
 				} else {
-					if (w.left == null || !w.left.color) {
-						w.right.color = false;
-						w.color = true;
-						leftRotate(w);
-						w = x.parent.left;
-					}
-					w.color = x.parent.color;
-					x.parent.color = false;
-					w.left.color = false;
-					rightRotate(x.parent);
-					x = root;
+					node = node.right;
 				}
 			}
+			return last;
 		}
-		x.color = false;
-	}
-
-	/**
-	 * Answers the value of the mapping with the specified key.
-	 * 
-	 * @param key
-	 *            the key
-	 * @return the value of the mapping with the specified key
-	 * 
-	 * @exception ClassCastException
-	 *                when the key cannot be compared with the keys in this
-	 *                TreeMap
-	 * @exception NullPointerException
-	 *                when the key is null and the comparator cannot handle null
-	 */
-	@Override
-    public V get(Object key) {
-		Entry<K, V> node = find(key);
-		if (node != null) {
-            return node.value;
-        }
-		return null;
 	}
 
-	/**
-	 * Answers a SortedMap of the specified portion of this TreeMap which
-	 * contains keys less than the end key. The returned SortedMap is backed by
-	 * this TreeMap so changes to one are reflected by the other.
-	 * 
-	 * @param endKey
-	 *            the end key
-	 * @return a sub-map where the keys are less than <code>endKey</code>
-	 * 
-	 * @exception ClassCastException
-	 *                when the end key cannot be compared with the keys in this
-	 *                TreeMap
-	 * @exception NullPointerException
-	 *                when the end key is null and the comparator cannot handle
-	 *                null
-	 */
-	public SortedMap<K, V> headMap(K endKey) {
-		// Check for errors
-		if (comparator == null) {
-            toComparable(endKey).compareTo(endKey);
-        } else {
-            comparator.compare(endKey, endKey);
-        }
-		return new SubMap<K, V>(this, endKey);
+    TreeMap.Entry<K, V> findFloorEntry(K key) {
+		int result;
+		Entry<K, V> node = root, last = null;
+		if (comparator != null) {
+			while (node != null) {
+				result = comparator.compare(key, node.key);
+				if (0 == result) {
+					return node;
+				} else if (0 < result) {
+					last = node;
+					node = node.right;
+				} else {
+					node = node.left;
+				}
+			}
+			return last;
+		} else {
+			Comparable<K> targetKey = (Comparable<K>) key;
+			while (node != null) {
+				result = targetKey.compareTo(node.key);
+				if (0 == result) {
+					return node;
+				} else if (0 < result) {
+					last = node;
+					node = node.right;
+				} else {
+					node = node.left;
+				}
+			}
+			return last;
+		}
 	}
 
-	/**
-	 * Answers a Set of the keys contained in this TreeMap. The set is backed by
-	 * this TreeMap so changes to one are reflected by the other. The set does
-	 * not support adding.
-	 * 
-	 * @return a Set of the keys
-	 */
-	@Override
-    public Set<K> keySet() {
-		if (keySet == null) {
-			keySet = new AbstractSet<K>() {
-				@Override
-                public boolean contains(Object object) {
-					return containsKey(object);
+    TreeMap.Entry<K, V> findLowerEntry(K key) {
+		int result;
+		Entry<K, V> node = root, last = null;
+		if (comparator != null) {
+			while (node != null) {
+				result = comparator.compare(key, node.key);
+				if (result <= 0) {
+					node = node.left;
+				} else {
+					last = node;
+					node = node.right;
 				}
-
-				@Override
-                public int size() {
-					return size;
+			}
+			return last;
+		} else {
+			Comparable<K> targetKey = (Comparable<K>) key;
+			while (node != null) {
+				result = targetKey.compareTo(node.key);
+				if (result <= 0) {
+					node = node.left;
+				} else {
+					last = node;
+					node = node.right;
 				}
+			}
+			return last;
 
-				@Override
-                public void clear() {
-					TreeMap.this.clear();
-				}
+		}
+	}
 
-				@Override
-                public Iterator<K> iterator() {
-                    return new UnboundedKeyIterator<K,V> (TreeMap.this);
+    TreeMap.Entry<K, V> findHigherEntry(K key) {
+		int result;
+		Entry<K, V> node = root, last = null;
+		if (comparator != null) {
+			while (node != null) {
+				result = comparator.compare(key, node.key);
+				if (result < 0) {
+					last = node;
+					node = node.left;
+				} else {
+					node = node.right;
 				}
-			};
+			}
+			return last;
+		} else {
+			Comparable<K> targetKey = (Comparable<K>) key;
+			while (node != null) {
+				result = targetKey.compareTo(node.key);
+				if (result < 0) {
+					last = node;
+					node = node.left;
+				} else {
+					node = node.right;
+				}
+			}
+			return last;
 		}
-		return keySet;
 	}
 
-	/**
-	 * Answer the last sorted key in this TreeMap.
+    /**
+	 * Answer the first sorted key in this TreeMap.
 	 * 
-	 * @return the last sorted key
+	 * @return the first sorted key
 	 * 
 	 * @exception NoSuchElementException
 	 *                when this TreeMap is empty
 	 */
-	public K lastKey() {
-		if (root != null) {
+    public K firstKey() {
+        if (root != null) {
+            return minimum(root).key;
+        }
+        throw new NoSuchElementException();
+    }
+
+    private void fixup(Entry<K, V> x) {
+        Entry<K, V> w;
+        while (x != root && !x.color) {
+            if (x == x.parent.left) {
+                w = x.parent.right;
+                if (w == null) {
+                    x = x.parent;
+                    continue;
+                }
+                if (w.color) {
+                    w.color = false;
+                    x.parent.color = true;
+                    leftRotate(x.parent);
+                    w = x.parent.right;
+                    if (w == null) {
+                        x = x.parent;
+                        continue;
+                    }
+                }
+                if ((w.left == null || !w.left.color)
+                        && (w.right == null || !w.right.color)) {
+                    w.color = true;
+                    x = x.parent;
+                } else {
+                    if (w.right == null || !w.right.color) {
+                        w.left.color = false;
+                        w.color = true;
+                        rightRotate(w);
+                        w = x.parent.right;
+                    }
+                    w.color = x.parent.color;
+                    x.parent.color = false;
+                    w.right.color = false;
+                    leftRotate(x.parent);
+                    x = root;
+                }
+            } else {
+                w = x.parent.left;
+                if (w == null) {
+                    x = x.parent;
+                    continue;
+                }
+                if (w.color) {
+                    w.color = false;
+                    x.parent.color = true;
+                    rightRotate(x.parent);
+                    w = x.parent.left;
+                    if (w == null) {
+                        x = x.parent;
+                        continue;
+                    }
+                }
+                if ((w.left == null || !w.left.color)
+                        && (w.right == null || !w.right.color)) {
+                    w.color = true;
+                    x = x.parent;
+                } else {
+                    if (w.left == null || !w.left.color) {
+                        w.right.color = false;
+                        w.color = true;
+                        leftRotate(w);
+                        w = x.parent.left;
+                    }
+                    w.color = x.parent.color;
+                    x.parent.color = false;
+                    w.left.color = false;
+                    rightRotate(x.parent);
+                    x = root;
+                }
+            }
+        }
+        x.color = false;
+    }
+
+    /**
+     * Answers the value of the mapping with the specified key.
+     * 
+     * @param key
+     *            the key
+     * @return the value of the mapping with the specified key
+     * 
+     * @exception ClassCastException
+     *                when the key cannot be compared with the keys in this
+     *                TreeMap
+     * @exception NullPointerException
+     *                when the key is null and the comparator cannot handle null
+     */
+    @Override
+    public V get(Object key) {
+        Entry<K, V> node = find(key);
+        if (node != null) {
+            return node.value;
+        }
+        return null;
+    }
+
+    /**
+     * Answers a Set of the keys contained in this TreeMap. The set is backed by
+     * this TreeMap so changes to one are reflected by the other. The set does
+     * not support adding.
+     * 
+     * @return a Set of the keys
+     */
+    @Override
+    public Set<K> keySet() {
+        return navigableKeySet();
+    }
+
+    /**
+     * Answer the last sorted key in this TreeMap.
+     * 
+     * @return the last sorted key
+     * 
+     * @exception NoSuchElementException
+     *                when this TreeMap is empty
+     */
+    public K lastKey() {
+        if (root != null) {
             return maximum(root).key;
         }
-		throw new NoSuchElementException();
-	}
+        throw new NoSuchElementException();
+    }
 
-	private void leftRotate(Entry<K, V> x) {
-		Entry<K, V> y = x.right;
-		x.right = y.left;
-		if (y.left != null) {
+    private void leftRotate(Entry<K, V> x) {
+        Entry<K, V> y = x.right;
+        x.right = y.left;
+        if (y.left != null) {
             y.left.parent = x;
         }
-		y.parent = x.parent;
-		if (x.parent == null) {
-			root = y;
-		} else {
-			if (x == x.parent.left) {
+        y.parent = x.parent;
+        if (x.parent == null) {
+            root = y;
+        } else {
+            if (x == x.parent.left) {
                 x.parent.left = y;
             } else {
                 x.parent.right = y;
             }
-		}
-		y.left = x;
-		x.parent = y;
-	}
+        }
+        y.left = x;
+        x.parent = y;
+    }
 
-	static <K, V> Entry<K, V> maximum(Entry<K, V> x) {
-		while (x.right != null) {
+    static <K, V> Entry<K, V> maximum(Entry<K, V> x) {
+        while (x.right != null) {
             x = x.right;
         }
-		return x;
-	}
+        return x;
+    }
 
-	static <K, V> Entry<K, V> minimum(Entry<K, V> x) {
-		while (x.left != null) {
+    static <K, V> Entry<K, V> minimum(Entry<K, V> x) {
+        while (x.left != null) {
             x = x.left;
         }
-		return x;
-	}
+        return x;
+    }
 
-	static <K, V> Entry<K, V> predecessor(Entry<K, V> x) {
-		if (x.left != null) {

[... 900 lines stripped ...]


Mime
View raw message