harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From apetre...@apache.org
Subject svn commit: r601752 [2/3] - in /harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util: TreeMap.java TreeSet.java
Date Thu, 06 Dec 2007 15:00:16 GMT

Modified: harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/TreeMap.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/TreeMap.java?rev=601752&r1=601751&r2=601752&view=diff
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/TreeMap.java (original)
+++ harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/TreeMap.java Thu Dec  6 07:00:16 2007
@@ -27,15 +27,14 @@
  * 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.
+ *
  * @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 SortedMap<K, V>,
+                                                        Cloneable, Serializable {
+    private static final long serialVersionUID = 919286545866124006L;
 
-	transient int size;
-
-    transient Entry<K, V> root;
+    transient int size;
 
     private Comparator<? super K> comparator;
 
@@ -43,69 +42,102 @@
 
     transient Set<Map.Entry<K, V>> entrySet;
 
-    static final int SMALL_LIMIT=127;
-    transient K[] small_keys;
-    transient V[] small_values;
-    transient Entry<K, V>[] small_entries;
-    transient int small_left=0;
-    transient int small_right=-1;
-
-	/**
-	 * 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;
-
-		boolean color;
-
-		Entry(K key) {
-			super(key);
-		}
-
-		Entry(K key, V value) {
-			super(key, value);
-		}
-
-		@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) {
+    transient Node<K, V> root;
+
+    static class Node <K,V> implements Cloneable {
+        static final int NODE_SIZE = 64;
+        Node<K, V> prev, next;
+        Node<K, V> parent, left, right;
+        V[] values;
+        K[] keys;
+        int left_idx = 0;
+        int right_idx = -1;
+        int size = 0;
+        boolean color;
+
+        public Node() {
+            keys = (K[]) new Object[NODE_SIZE];
+            values = (V[]) new Object[NODE_SIZE];
+        }
+
+        @SuppressWarnings("unchecked")
+        Node<K, V> clone(Node<K, V> parent) throws CloneNotSupportedException {
+            Node<K, V> clone = (Node<K, V>) super.clone();
+            clone.keys   = (K[]) new Object[NODE_SIZE];
+            clone.values = (V[]) new Object[NODE_SIZE];
+            System.arraycopy(keys,   0, clone.keys,   0, keys.length);
+            System.arraycopy(values, 0, clone.values, 0, values.length);
+            clone.left_idx  = left_idx;
+            clone.right_idx = right_idx;
+            clone.parent = parent;
+            if (left != null) {
                 clone.left = left.clone(clone);
             }
-			if (right != null) {
+            if (right != null) {
                 clone.right = right.clone(clone);
             }
-			return clone;
-		}
-	}
+            clone.prev = null;
+            clone.next = null;
+            return clone;
+        }
+    }
 
     @SuppressWarnings("unchecked")
-    private static <T> Comparable<T> toComparable(T obj) {
-        return (Comparable<T>)obj;
+     private static <T> Comparable<T> toComparable(T obj) {
+        return (Comparable) obj;
     }
 
-    private static class AbstractMapIterator <K,V> {
+    static class AbstractMapIterator <K,V> {
         TreeMap<K, V> backingMap;
         int expectedModCount;
-        TreeMap.Entry<K, V> node;
-        TreeMap.Entry<K, V> lastNode;
+        Node<K, V> node;
+        Node<K, V> lastNode;
+        int offset;
+        int lastOffset;
 
-        AbstractMapIterator(TreeMap<K, V> map, Entry<K, V> startNode) {
+        AbstractMapIterator(TreeMap<K, V> map, Node<K, V> startNode, int startOffset) {
             backingMap = map;
             expectedModCount = map.modCount;
             node = startNode;
+            offset = startOffset;
+        }
+
+        AbstractMapIterator(TreeMap<K, V> map, Node<K, V> startNode) {
+            this(map, startNode, startNode != null ?
+                                 startNode.right_idx - startNode.left_idx : 0);
+        }
+
+        AbstractMapIterator(TreeMap<K, V> map) {
+            this(map, minimum(map.root));
         }
 
         public boolean hasNext() {
             return node != null;
         }
 
+        final void makeNext() {
+            if (expectedModCount != backingMap.modCount) {
+                throw new ConcurrentModificationException();
+            } else if (node == null) {
+                throw new NoSuchElementException();
+            }
+            lastNode = node;
+            lastOffset = offset;
+            if (offset != 0) {
+                offset--;
+            } else {
+                node = node.next;
+                if (node != null) {
+                    offset = node.right_idx - node.left_idx;
+                }
+            }
+        }
+
         final public void remove() {
             if (expectedModCount == backingMap.modCount) {
                 if (lastNode != null) {
-                    backingMap.rbDelete(lastNode);
+                    int idx = lastNode.right_idx - lastOffset;
+                    backingMap.remove(lastNode, idx);
                     lastNode = null;
                     expectedModCount++;
                 } else {
@@ -117,957 +149,970 @@
         }
     }
 
-        private static class UnboundedIterator<K, V> extends AbstractMapIterator<K, V> {
-
-            public UnboundedIterator(TreeMap<K, V> treeMap, Entry<K, V> entry) {
-                super(treeMap, entry);
-            }
-
-            final void makeNext() {
-                if (expectedModCount != backingMap.modCount) {
-                    throw new ConcurrentModificationException();
-                } else if (node == null) {
-                    throw new NoSuchElementException();
-                }
-                lastNode = node;
-                node = TreeMap.successor(node);
-            }
-
-       }
-
-        private static class UnboundedEntryIterator <K, V> extends UnboundedIterator<K, V> implements Iterator<Map.Entry<K, V>> {
-
-            UnboundedEntryIterator(TreeMap<K, V> map, Entry<K, V> startNode) {
-                super(map, startNode);
-            }
-
-            UnboundedEntryIterator(TreeMap<K, V> map) {
-                super(map, map.root == null ? null : TreeMap.minimum(map.root));
-            }
-
-            public Map.Entry<K, V> next() {
-                makeNext();
-                return lastNode;
-            }
-        }
-
-        static class UnboundedKeyIterator <K, V> extends UnboundedIterator<K, V> implements Iterator<K> {
-            public UnboundedKeyIterator(TreeMap<K, V> treeMap, Entry<K, V> entry) {
-                super(treeMap, entry);
-            }
-
-            public UnboundedKeyIterator(TreeMap<K, V> map) {
-                super(map, map.root == null ? null : TreeMap.minimum(map.root));
-            }
-
-            public K next() {
-                makeNext();
-                return lastNode.key;
-            }
-        }
-
-        static class UnboundedValueIterator <K, V> extends UnboundedIterator<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;
-            }
-        }
-
-        private static class BoundedIterator<K, V> extends AbstractMapIterator<K, V> {
-            private final TreeMap.Entry<K, V> finishNode;
-
-            BoundedIterator(TreeMap<K, V> map, Entry<K, V> startNode, Entry<K, V> finishNode) {
-                super(map, startNode);
-                this.finishNode = finishNode;
-            }
+    static class UnboundedEntryIterator <K, V> extends AbstractMapIterator<K, V>
+                                            implements Iterator<Map.Entry<K, V>> {
 
-            final void makeNext() {
-                if (expectedModCount != backingMap.modCount) {
-                    throw new ConcurrentModificationException();
-                } else if (node == null) {
-                    throw new NoSuchElementException();
-                }
-                lastNode = node;
-                if(node!=finishNode) {
-                    node = TreeMap.successor(node);
-                } else {
-                    node = null;
-                }
-            }
+        UnboundedEntryIterator(TreeMap<K, V> map, Node<K, V> startNode, int startOffset) {
+            super(map, startNode, startOffset);
         }
 
-
-    private static class BoundedEntryIterator<K, V> extends
-            BoundedIterator<K, V> implements Iterator<Map.Entry<K, V>> {
-
-        BoundedEntryIterator(TreeMap<K, V> map, Entry<K, V> startNode, Entry<K, V> finishNode) {
-            super(map, startNode, finishNode);
+        UnboundedEntryIterator(TreeMap<K, V> map) {
+            super(map);
         }
 
         public Map.Entry<K, V> next() {
             makeNext();
-            return lastNode;
+            int idx = lastNode.right_idx - lastOffset;
+            return new MapEntry<K, V>(lastNode.keys[idx], lastNode.values[idx]);
         }
     }
 
-    private static class BoundedKeyIterator<K, V> extends
-            BoundedIterator<K, V> implements Iterator<K> {
+    static class UnboundedKeyIterator <K, V> extends AbstractMapIterator<K, V>
+                                                          implements Iterator<K> {
+
+        UnboundedKeyIterator(TreeMap<K, V> map, Node<K, V> startNode, int startOffset) {
+            super(map, startNode, startOffset);
+        }
 
-        BoundedKeyIterator(TreeMap<K, V> map, Entry<K, V> startNode, Entry<K, V> finishNode) {
-            super(map, startNode, finishNode);
+        UnboundedKeyIterator(TreeMap<K, V> map) {
+            super(map);
         }
 
         public K next() {
             makeNext();
-            return lastNode.key;
+            return lastNode.keys[lastNode.right_idx - lastOffset];
         }
     }
 
-    private static class BoundedValueIterator<K, V> extends
-              BoundedIterator<K, V> implements Iterator<V> {
+    static class UnboundedValueIterator <K, V> extends AbstractMapIterator<K, V>
+                                                          implements Iterator<V> {
+
+        UnboundedValueIterator(TreeMap<K, V> map, Node<K, V> startNode, int startOffset) {
+            super(map, startNode, startOffset);
+        }
 
-        BoundedValueIterator(TreeMap<K, V> map, Entry<K, V> startNode, Entry<K, V> finishNode) {
-            super(map, startNode, finishNode);
+        UnboundedValueIterator(TreeMap<K, V> map) {
+            super(map);
         }
 
         public V next() {
             makeNext();
-            return lastNode.value;
+            return lastNode.values[lastNode.right_idx - lastOffset];
         }
     }
 
-    private static class SmallMapIterator <K,V> {
-        TreeMap<K, V> backingMap;
-        int expectedModCount;
-        int index;
-        int lastIndex;
-        int endIndex;
+    static class BoundedMapIterator <K, V> extends AbstractMapIterator<K, V> {
 
-        SmallMapIterator(TreeMap<K, V> map, int startIndex, int endIndex) {
-            backingMap = map;
-            expectedModCount = map.modCount;
-            index = startIndex;
-            this.endIndex = endIndex;
+        Node<K, V> finalNode;
+        int finalOffset;
+
+        BoundedMapIterator(Node<K, V> startNode, int startOffset, TreeMap<K, V> map,
+                           Node<K, V> finalNode, int finalOffset) {
+            super(map, startNode, startOffset);
+            this.finalNode = finalNode;
+            this.finalOffset = finalOffset;
         }
 
-        public boolean hasNext() {
-            return index<=endIndex;
+        BoundedMapIterator(Node<K, V> startNode, TreeMap<K, V> map,
+                           Node<K, V> finalNode, int finalOffset) {
+            this(startNode, startNode != null ?
+                            startNode.right_idx - startNode.left_idx : 0,
+                            map, finalNode, finalOffset);
         }
 
-        final void makeNext() {
-                if (expectedModCount != backingMap.modCount) {
-                    throw new ConcurrentModificationException();
-                } else if (index>endIndex) {
-                    throw new NoSuchElementException();
-                }
-                lastIndex = index++;
-            }
+        BoundedMapIterator(Node<K, V> startNode, int startOffset,
+                           TreeMap<K, V> map, Node<K, V> finalNode) {
+            this(startNode, startOffset, map, finalNode,
+                         finalNode.right_idx - finalNode.left_idx);
+        }
 
-        final public void remove() {
-            if (expectedModCount == backingMap.modCount) {
-                if (lastIndex != -1) {
-                    if(backingMap.smallDelete(lastIndex)) {
-                        endIndex--;
-                        index--;
-                    }
-                    lastIndex = -1;
-                    expectedModCount++;
-                } else {
-                    throw new IllegalStateException();
-                }
-            } else {
-                throw new ConcurrentModificationException();
+        void makeBoundedNext() {
+            boolean endOfIterator = node == finalNode && offset == finalOffset;
+            makeNext();
+            if (endOfIterator) {
+                node = null;
             }
         }
     }
 
-       private static class SmallEntryIterator<K, V> extends
-               SmallMapIterator<K, V> implements Iterator<Map.Entry<K, V>> {
+    static class BoundedEntryIterator <K, V> extends BoundedMapIterator<K, V>
+                                          implements Iterator<Map.Entry<K, V>> {
+
+        public BoundedEntryIterator(Node<K, V> startNode, int startOffset, TreeMap<K, V> map,
+                                    Node<K, V> finalNode, int finalOffset) {
+            super(startNode, startOffset, map, finalNode, finalOffset);
+        }
 
-           SmallEntryIterator(TreeMap<K, V> map, int startIndex, int endIndex) {
-               super(map, startIndex, endIndex);
-           }
-
-           public Map.Entry<K, V> next() {
-               makeNext();
-               if(backingMap.small_entries==null) {
-                   backingMap.small_entries = (Entry<K,V>[])new Entry[backingMap.small_keys.length];
-               }
-               if(backingMap.small_entries[lastIndex]==null) {
-                   backingMap.small_entries[lastIndex]=new Entry<K,V>(backingMap.small_keys[lastIndex],backingMap.small_values[lastIndex]);
-               }
-               return backingMap.small_entries[lastIndex];
-           }
-       }
+        public Map.Entry<K, V> next() {
+            makeBoundedNext();
+            int idx = lastNode.right_idx - lastOffset;
+            return new MapEntry<K, V>(lastNode.keys[idx], lastNode.values[idx]);
+        }
+    }
 
-    private static class SmallKeyIterator<K, V> extends
-            SmallMapIterator<K, V> implements Iterator<K> {
+    static class BoundedKeyIterator <K, V> extends BoundedMapIterator<K, V>
+                                                     implements Iterator<K> {
 
-        SmallKeyIterator(TreeMap<K, V> map, int startIndex, int endIndex) {
-            super(map, startIndex, endIndex);
+        public BoundedKeyIterator(Node<K, V> startNode, int startOffset, TreeMap<K, V> map,
+                                  Node<K, V> finalNode, int finalOffset) {
+            super(startNode, startOffset, map, finalNode, finalOffset);
         }
 
         public K next() {
-            makeNext();
-            return backingMap.small_keys[lastIndex];
+            makeBoundedNext();
+            return lastNode.keys[lastNode.right_idx - lastOffset];
         }
     }
 
-    private static class SmallValueIterator<K, V> extends
-            SmallMapIterator<K, V> implements Iterator<V> {
+    static class BoundedValueIterator <K, V> extends BoundedMapIterator<K, V>
+                                                       implements Iterator<V> {
 
-        SmallValueIterator(TreeMap<K, V> map, int startIndex, int endIndex) {
-            super(map, startIndex, endIndex);
+        public BoundedValueIterator(Node<K, V> startNode, int startOffset, TreeMap<K, V> map,
+                                    Node<K, V> finalNode, int finalOffset) {
+            super(startNode, startOffset, map, finalNode, finalOffset);
         }
 
         public V next() {
-            makeNext();
-            return backingMap.small_values[lastIndex];
+            makeBoundedNext();
+            return lastNode.values[lastNode.right_idx - lastOffset];
         }
     }
 
-        static final class SubMap<K,V> extends AbstractMap<K,V> implements SortedMap<K,V>, Serializable {
-            private static final long serialVersionUID = -6520786458950516097L;
-
-            private TreeMap<K,V> backingMap;
-
-            boolean hasStart, hasEnd;
+    static final class SubMap <K,V> extends AbstractMap<K, V>
+                                 implements SortedMap<K, V>, Serializable {
+        private static final long serialVersionUID = -6520786458950516097L;
+
+        private TreeMap<K, V> backingMap;
+
+        boolean hasStart, hasEnd;
+        K startKey, endKey;
+        transient Set<Map.Entry<K, V>> entrySet = null;
+        transient int firstKeyModCount = -1;
+        transient int lastKeyModCount = -1;
+        transient Node<K, V> firstKeyNode;
+        transient int firstKeyIndex;
+        transient Node<K, V> lastKeyNode;
+        transient int lastKeyIndex;
 
-            K startKey, endKey;
+        SubMap(K start, TreeMap<K, V> map) {
+            backingMap = map;
+            hasStart = true;
+            startKey = start;
+        }
 
-            transient Set<Map.Entry<K,V>> entrySet = null;
-            transient int firstEntryModCount = -1;
-            transient int lastEntryModCount = -1;
-            transient TreeMap.Entry<K,V> firstEntry;
-            transient TreeMap.Entry<K,V> lastEntry;
+        SubMap(K start, TreeMap<K, V> map, K end) {
+            backingMap = map;
+            hasStart = hasEnd = true;
+            startKey = start;
+            endKey = end;
+        }
 
-            SubMap(K start, TreeMap<K,V> map) {
-                backingMap = map;
-                hasStart = true;
-                startKey = start;
-            }
+        SubMap(TreeMap<K, V> map, K end) {
+            backingMap = map;
+            hasEnd = true;
+            endKey = end;
+        }
 
-            SubMap(K start, TreeMap<K,V> map, K end) {
-                backingMap = map;
-                hasStart = hasEnd = true;
-                startKey = start;
-                endKey = end;
+        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();
+                }
             }
+        }
 
-            SubMap(TreeMap<K,V> map, K end) {
-                backingMap = map;
-                hasEnd = true;
-                endKey = end;
+        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;
+        }
 
-            private void checkRange(K key) {
+        private boolean checkUpperBound(K key) {
+            if (hasEnd) {
                 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();
-                    }
+                    return (toComparable(key).compareTo(endKey) < 0);
                 }
+                return (cmp.compare(key, endKey) < 0);
             }
+            return true;
+        }
 
-            private boolean isInRange(K key) {
+        private boolean checkLowerBound(K key) {
+            if (hasStart) {
                 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 (toComparable(key).compareTo(startKey) >= 0);
                 }
-                return true;
+                return (cmp.compare(key, startKey) >= 0);
             }
+            return true;
+        }
 
-            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 Comparator<? super K> comparator() {
+            return backingMap.comparator();
+        }
 
-            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;
+        @SuppressWarnings("unchecked")
+        @Override
+        public boolean containsKey(Object key) {
+            if (isInRange((K) key)) {
+                return backingMap.containsKey(key);
             }
+            return false;
+        }
 
-            public Comparator<? super K> comparator() {
-                return backingMap.comparator();
-            }
+        @Override
+         public void clear() {
+            keySet().clear();
+        }
 
-            @SuppressWarnings("unchecked")
-            @Override
-            public boolean containsKey(Object key) {
-                if (isInRange((K)key)) {
-                    return backingMap.containsKey(key);
+        @Override
+         public boolean containsValue(Object value) {
+            Iterator<V> it = values().iterator();
+            if (value != null) {
+                while (it.hasNext()) {
+                    if (value.equals(it.next())) {
+                        return true;
+                    }
                 }
-                return false;
-            }
-
-            @Override
-            public Set<Map.Entry<K,V>> entrySet() {
-                if(entrySet==null) {
-                    entrySet = new SubMapEntrySet<K,V>(this);
+            } else {
+                while (it.hasNext()) {
+                    if (it.next() == null) {
+                        return true;
+                    }
                 }
-                return entrySet;
             }
+            return false;
+        }
 
-            public K firstKey() {
-                if(backingMap.size>0) {
-                    if(backingMap.isSmall()) {
-                        if(!hasStart) {
-                            K kres = backingMap.small_keys[backingMap.small_left];
-                            if(checkUpperBound(kres)) {
-                                 return kres;
-                            }
-
-                        } else {
-                            int idx = backingMap.smallFindAfter(startKey);
-                            if(idx>=backingMap.small_left && idx <=backingMap.small_right){
-                                K kres = backingMap.small_keys[idx];
-                                if(checkUpperBound(kres)) {
-	                             return kres;
-	                        }
+        @Override
+        public Set<Map.Entry<K, V>> entrySet() {
+            if (entrySet == null) {
+                entrySet = new SubMapEntrySet<K, V>(this);
+            }
+            return entrySet;
+        }
+
+        private void setFirstKey() {
+            if (firstKeyModCount == backingMap.modCount) {
+                return;
+            }
+            Comparable<K> object = backingMap.comparator == null ?
+                                   toComparable((K) startKey) : null;
+            K key = (K) startKey;
+            Node<K, V> node = backingMap.root;
+            Node<K, V> foundNode = null;
+            int foundIndex = -1;
+            TOP_LOOP:
+            while (node != null) {
+                K[] keys = node.keys;
+                int left_idx = node.left_idx;
+                int result = backingMap.cmp(object, key, keys[left_idx]);
+                if (result < 0) {
+                    foundNode = node;
+                    foundIndex = left_idx;
+                    node = node.left;
+                } else if (result == 0) {
+                    foundNode = node;
+                    foundIndex = left_idx;
+                    break;
+                } else {
+                    int right_idx = node.right_idx;
+                    if (left_idx != right_idx) {
+                        result = backingMap.cmp(object, key, keys[right_idx]);
+                    }
+                    if (result > 0) {
+                        node = node.right;
+                    } else if (result == 0) {
+                        foundNode = node;
+                        foundIndex = right_idx;
+                        break;
+                    } else { /*search in node*/
+                        foundNode = node;
+                        foundIndex = right_idx;
+                        int low = left_idx + 1, mid = 0, high = right_idx - 1;
+                        while (low <= high) {
+                            mid = (low + high) >> 1;
+                            result = backingMap.cmp(object, key, keys[mid]);
+                            if (result > 0) {
+                                low = mid + 1;
+                            } else if (result == 0) {
+                                foundNode = node;
+                                foundIndex = mid;
+                                break TOP_LOOP;
+                            } else {
+                                foundNode = node;
+                                foundIndex = mid;
+                                high = mid - 1;
                             }
                         }
-                    } else {
-                        TreeMap.Entry<K,V> node = firstEntry();
-                        if (node != null ) {
-                            return node.key;
-                        }
+                        break TOP_LOOP;
                     }
                 }
-                throw new NoSuchElementException();
             }
+            if (foundNode != null && !checkUpperBound(foundNode.keys[foundIndex])) {
+                foundNode = null;
+            }
+            firstKeyNode = foundNode;
+            firstKeyIndex = foundIndex;
+            firstKeyModCount = backingMap.modCount;
+        }
 
-            TreeMap.Entry<K,V> firstEntry() {
-                if(firstEntryModCount == backingMap.modCount) {
-                    return firstEntry;
-                }
-                TreeMap.Entry<K,V> node;
+        public K firstKey() {
+            if (backingMap.size > 0) {
                 if (!hasStart) {
-                    TreeMap.Entry<K,V> root = backingMap.root;
-                    node = (root == null) ? null : minimum(root);
+                    Node<K, V> node = minimum(backingMap.root);
+                    if (node != null && checkUpperBound(node.keys[node.left_idx])) {
+                        return node.keys[node.left_idx];
+                    }
                 } else {
-                    node = backingMap.findAfter(startKey);
-                }
-                if (node != null && !checkUpperBound(node.key)) {
-                    node = null;
+                    setFirstKey();
+                    if (firstKeyNode != null) {
+                        return firstKeyNode.keys[firstKeyIndex];
+                    }
                 }
-                firstEntry = node;
-                firstEntryModCount = backingMap.modCount;
-                return node;
             }
+            throw new NoSuchElementException();
+        }
 
-            @SuppressWarnings("unchecked")
-            @Override
-            public V get(Object key) {
-                if (isInRange((K)key)) {
-                    return backingMap.get(key);
-                }
-                return null;
-            }
 
-            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);
+        @SuppressWarnings("unchecked")
+        @Override
+        public V get(Object key) {
+            if (isInRange((K) key)) {
+                return backingMap.get(key);
             }
+            return null;
+        }
 
-            @Override
-            public boolean isEmpty() {
-                 if (!hasStart) {
-                     return firstEntry()==null;
-                 } else {
-                     return lastEntry()==null;
-                 }
+        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);
+        }
 
-            @Override
-            public Set<K> keySet() {
-                if (keySet == null) {
-                    keySet = new SubMapKeySet<K,V>(this);
-                }
-                return keySet;
+        @Override
+        public boolean isEmpty() {
+            if (hasStart) {
+                setFirstKey();
+                return firstKeyNode == null;
+            } else {
+                setLastKey();
+                return lastKeyNode == null;
             }
+        }
 
-            public K lastKey() {
-                if (backingMap.size > 0) {
-                    if (backingMap.isSmall()) {
-                        if (!hasEnd) {
-                            K kres = backingMap.small_keys[backingMap.small_right];
-                            if(checkLowerBound(kres)) {
-                                 return kres;
+        @Override
+        public Set<K> keySet() {
+            if (keySet == null) {
+                keySet = new SubMapKeySet<K, V>(this);
+            }
+            return keySet;
+        }
+
+        private void setLastKey() {
+            if (lastKeyModCount == backingMap.modCount) {
+                return;
+            }
+            Comparable<K> object = backingMap.comparator == null ?
+                                   toComparable((K) endKey) : null;
+            K key = (K) endKey;
+            Node<K, V> node = backingMap.root;
+            Node<K, V> foundNode = null;
+            int foundIndex = -1;
+            TOP_LOOP:
+            while (node != null) {
+                K[] keys = node.keys;
+                int left_idx = node.left_idx;
+                int result = backingMap.cmp(object, key, keys[left_idx]);
+                if (result <= 0) {
+                    node = node.left;
+                } else {
+                    int right_idx = node.right_idx;
+                    if (left_idx != right_idx) {
+                        result = backingMap.cmp(object, key, keys[right_idx]);
+                    }
+                    if (result > 0) {
+                        foundNode = node;
+                        foundIndex = right_idx;
+                        node = node.right;
+                    } else if (result == 0) {
+                        if (node.left_idx == node.right_idx) {
+                            foundNode = node.prev;
+                            if (foundNode != null) {
+                                foundIndex = foundNode.right_idx - 1;
                             }
                         } else {
-                            int idx = backingMap.smallFindBefore(endKey);
-                            if (idx>=backingMap.small_left && idx <= backingMap.small_right) {
-                                K kres = backingMap.small_keys[idx] ;
-                                if(checkLowerBound(kres)) {
-	                             return kres;
-	                        }
-                            }
+                            foundNode = node;
+                            foundIndex = right_idx - 1;
                         }
-                    } else {
-                        TreeMap.Entry<K, V> node = lastEntry();
-                        if (node != null) {
-                            return node.key;
+                        break;
+                    } else { /*search in node*/
+                        foundNode = node;
+                        foundIndex = left_idx;
+                        int low = left_idx + 1, mid = 0, high = right_idx - 1;
+                        while (low <= high) {
+                            mid = (low + high) >> 1;
+                            result = backingMap.cmp(object, key, keys[mid]);
+                            if (result > 0) {
+                                foundNode = node;
+                                foundIndex = mid;
+                                low = mid + 1;
+                            } else if (result == 0) {
+                                foundNode = node;
+                                foundIndex = mid - 1;
+                                break TOP_LOOP;
+                            } else {
+                                high = mid - 1;
+                            }
                         }
+                        break TOP_LOOP;
                     }
                 }
-                throw new NoSuchElementException();
             }
+            if (foundNode != null && !checkLowerBound(foundNode.keys[foundIndex])) {
+                foundNode = null;
+            }
+            lastKeyNode = foundNode;
+            lastKeyIndex = foundIndex;
+            lastKeyModCount = backingMap.modCount;
+        }
 
-            TreeMap.Entry<K,V> lastEntry() {
-                if(lastEntryModCount == backingMap.modCount) {
-                    return lastEntry;
-                }
-                TreeMap.Entry<K,V> node;
+        public K lastKey() {
+            if (backingMap.size > 0) {
                 if (!hasEnd) {
-                    TreeMap.Entry<K,V> root = backingMap.root;
-                    node = (root == null) ? null : maximum(root);
+                    Node<K, V> node = maximum(backingMap.root);
+                    if (node != null && checkLowerBound(node.keys[node.right_idx])) {
+                        return node.keys[node.right_idx];
+                    }
                 } else {
-                    node = backingMap.findBefore(endKey);
-                }
-                if (node != null && !checkLowerBound(node.key)) {
-                    node = null;
+                    setLastKey();
+                    if (lastKeyNode != null) {
+                        return lastKeyNode.keys[lastKeyIndex];
+                    }
                 }
-                lastEntry = node;
-                lastEntryModCount = backingMap.modCount;
-                return node;
             }
+            throw new NoSuchElementException();
+        }
 
-            @Override
-            public V put(K key, V value) {
-                if (isInRange(key)) {
-                    return backingMap.put(key, value);
-                }
-                throw new IllegalArgumentException();
+
+        @Override
+        public V put(K key, V value) {
+            if (isInRange(key)) {
+                return backingMap.put(key, value);
             }
+            throw new IllegalArgumentException();
+        }
 
-            @SuppressWarnings("unchecked")
-            @Override
-            public V remove(Object key) {
-                if (isInRange((K)key)) {
-                    return backingMap.remove(key);
-                }
-                return null;
+        @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);
-                    }
+        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();
             }
+            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);
+        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);
+        }
 
-            @Override
-            public Collection<V> values() {
-                if(valuesCollection==null) {
-                    valuesCollection = new SubMapValuesCollection<K,V>(this);
-                }
-                return valuesCollection;
+        @Override
+        public Collection<V> values() {
+            if (valuesCollection == null) {
+                valuesCollection = new SubMapValuesCollection<K, V>(this);
             }
+            return valuesCollection;
+        }
 
-            public int size() {
-                if(backingMap.isSmall()) {
-                    int start,end;
-                    if (!hasStart) {
-                        start = backingMap.small_left;
-                    } else {
-                        start = backingMap.smallFindAfter(startKey);
-                    }
-                    System.out.println(start);
-                    if (!hasEnd) {
-                        end = backingMap.small_right;
-                    } else {
-                        end = backingMap.smallFindBefore(endKey);
-                    }
-                    System.out.println(end);
-                    if(backingMap.small_left<=start && end <=backingMap.small_right && end-start>=0) {
-                        return end-start+1;
-                    } else {
-                        return 0;
-                    }
-                }
-                TreeMap.Entry<K,V> entry = firstEntry();
-                if(entry!=null) {
-                    int cnt=1;
-                    if(hasEnd) {
-                        TreeMap.Entry<K,V> last = lastEntry();
-                        while(entry!=last){
-                            entry = successor(entry);
-                            cnt++;
-                        }
-                    } else {
-                        while((entry=successor(entry))!=null) cnt++;
-                    }
-                    return cnt;
-                }
+        public int size() {
+            Node<K, V> from, to;
+            int fromIndex, toIndex;
+            if (hasStart) {
+                setFirstKey();
+                from = firstKeyNode;
+                fromIndex = firstKeyIndex;
+            } else {
+                from = minimum(backingMap.root);
+                fromIndex = from == null ? 0 : from.left_idx;
+            }
+            if (from == null) {
                 return 0;
             }
-
+            if (hasEnd) {
+                setLastKey();
+                to = lastKeyNode;
+                toIndex = lastKeyIndex;
+            } else {
+                to = maximum(backingMap.root);
+                toIndex = to == null ? 0 : to.right_idx;
+            }
+            if (to == null) {
+                return 0;
+            }
+            if (from == to) {
+                return toIndex - fromIndex + 1;
+            }
+            int sum = 0;
+            while (from != to) {
+                sum += (from.right_idx - fromIndex + 1);
+                from = from.next;
+                fromIndex = from.left_idx;
+            }
+            return sum + toIndex - fromIndex + 1;
+        }
+
+        private void readObject(ObjectInputStream stream) throws IOException,
+                                                                 ClassNotFoundException {
+            stream.defaultReadObject();
+            firstKeyModCount = -1;
+            lastKeyModCount = -1;
         }
+    }
 
-        static class SubMapEntrySet<K,V> extends AbstractSet<Map.Entry<K,V>> implements Set<Map.Entry<K,V>> {
-            SubMap<K,V> subMap;
-
-            SubMapEntrySet(SubMap<K,V> map) {
-                subMap = map;
+    static class SubMapEntrySet <K,V> extends AbstractSet<Map.Entry<K, V>>
+                                                implements Set<Map.Entry<K, V>> {
+        SubMap<K, V> subMap;
+
+        SubMapEntrySet(SubMap<K, V> map) {
+            subMap = map;
+        }
+
+        @Override
+        public boolean isEmpty() {
+            return subMap.isEmpty();
+        }
+
+        public Iterator<Map.Entry<K, V>> iterator() {
+            Node<K, V> from;
+            int fromIndex;
+            if (subMap.hasStart) {
+                subMap.setFirstKey();
+                from = subMap.firstKeyNode;
+                fromIndex = subMap.firstKeyIndex;
+            } else {
+                from = minimum(subMap.backingMap.root);
+                fromIndex = from != null ? from.left_idx : 0;
             }
-
-            @Override
-            public boolean isEmpty() {
-                return subMap.isEmpty();
-            }
-
-            @Override
-            public Iterator<Map.Entry<K,V>> iterator() {
-                if(subMap.backingMap.isSmall()) {
-                   int start, end;
-                   if(subMap.hasStart) {
-                       start = subMap.backingMap.smallFindAfter(subMap.startKey);
-                   } else {
-                       start = subMap.backingMap.small_left;
-                   }
-                    if(subMap.hasEnd) {
-                        end = subMap.backingMap.smallFindBefore(subMap.endKey);
-                    } else {
-                        end = subMap.backingMap.small_right;
-                    }
-                   return new SmallEntryIterator<K,V>(subMap.backingMap,start,end);
-                }
-                TreeMap.Entry<K,V> startNode = subMap.firstEntry();
-                if (subMap.hasEnd) {
-                    TreeMap.Entry<K,V> lastNode = subMap.lastEntry();
-                    return new BoundedEntryIterator<K,V>(subMap.backingMap, startNode, lastNode);
+            if (!subMap.hasEnd) {
+                return new UnboundedEntryIterator<K, V>(subMap.backingMap, from, from == null ? 0 : from.right_idx - fromIndex);
+            }
+            subMap.setLastKey();
+            Node<K, V> to = subMap.lastKeyNode;
+            int toIndex = subMap.lastKeyIndex;
+            return new BoundedEntryIterator<K, V>(from, from == null ? 0 : from.right_idx - fromIndex, subMap.backingMap, to, to == null ? 0 : to.right_idx - toIndex);
+        }
+
+        @Override
+        public int size() {
+            return subMap.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 new UnboundedEntryIterator<K,V>(subMap.backingMap, startNode);
             }
+            return false;
+        }
 
-            @Override
-            public int size() {
-                return subMap.size();
+        @Override
+        public boolean remove(Object object) {
+            if (contains(object)) {
+                Map.Entry<K, V> entry = (Map.Entry<K, V>) object;
+                K key = entry.getKey();
+                subMap.remove(key);
+                return true;
             }
+            return false;
+        }
+    }
 
-            @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;
-            }
+    static class SubMapKeySet <K,V> extends AbstractSet<K> implements Set<K> {
+        SubMap<K, V> subMap;
 
+        SubMapKeySet(SubMap<K, V> map) {
+            subMap = map;
         }
 
-        static class SubMapKeySet<K,V> extends  AbstractSet<K> implements Set<K> {
-            SubMap<K,V> subMap;
-
-            SubMapKeySet(SubMap<K,V> map) {
-                subMap = map;
-            }
+        @Override
+        public boolean contains(Object object) {
+            return subMap.containsKey(object);
+        }
 
-            @Override
-            public boolean contains(Object object) {
-                return subMap.containsKey(object);
-            }
+        @Override
+        public boolean isEmpty() {
+            return subMap.isEmpty();
+        }
 
-            @Override
-            public boolean isEmpty() {
-                return subMap.isEmpty();
-            }
+        @Override
+        public int size() {
+            return subMap.size();
+        }
 
-            @Override
-            public int size() {
-                return subMap.size();
+        @Override
+        public boolean remove(Object object) {
+            if (subMap.containsKey(object)) {
+                subMap.remove(object);
+                return true;
             }
+            return false;
+        }
 
-            @Override
-            public Iterator<K> iterator() {
-                if(subMap.backingMap.isSmall()) {
-                   int start, end;
-                   if(subMap.hasStart) {
-                       start = subMap.backingMap.smallFindAfter(subMap.startKey);
-                   } else {
-                       start = subMap.backingMap.small_left;
-                   }
-                    if(subMap.hasEnd) {
-                        end = subMap.backingMap.smallFindBefore(subMap.endKey);
-                    } else {
-                        end = subMap.backingMap.small_right;
-                    }
-                   return new SmallKeyIterator<K,V>(subMap.backingMap,start,end);
-                }
-                TreeMap.Entry<K,V> startNode = subMap.firstEntry();
-                if (subMap.hasEnd) {
-                    TreeMap.Entry<K,V> lastNode = subMap.lastEntry();
-                    return new BoundedKeyIterator<K,V>(subMap.backingMap, startNode, lastNode);
-                }
-                return new UnboundedKeyIterator<K,V>(subMap.backingMap, startNode);
+        public Iterator<K> iterator() {
+            Node<K, V> from;
+            int fromIndex;
+            if (subMap.hasStart) {
+                subMap.setFirstKey();
+                from = subMap.firstKeyNode;
+                fromIndex = subMap.firstKeyIndex;
+            } else {
+                from = minimum(subMap.backingMap.root);
+                fromIndex = from != null ? from.left_idx : 0;
             }
+            if (!subMap.hasEnd) {
+                return new UnboundedKeyIterator<K, V>(subMap.backingMap, from,
+                                   from == null ? 0 : from.right_idx - fromIndex);
+            }
+            subMap.setLastKey();
+            Node<K, V> to = subMap.lastKeyNode;
+            int toIndex = subMap.lastKeyIndex;
+            return new BoundedKeyIterator<K, V>(from,
+               from == null ? 0 : from.right_idx - fromIndex, subMap.backingMap, to,
+                 to == null ? 0 : to.right_idx   - toIndex);
         }
+    }
 
-        static class SubMapValuesCollection<K,V> extends AbstractCollection<V> {
-            SubMap<K,V> subMap;
+    static class SubMapValuesCollection <K,V> extends AbstractCollection<V> {
+        SubMap<K, V> subMap;
 
-            public SubMapValuesCollection(SubMap<K,V> subMap) {
-                this.subMap = subMap;
-            }
+        public SubMapValuesCollection(SubMap<K, V> subMap) {
+            this.subMap = subMap;
+        }
 
-            @Override
-            public boolean isEmpty() {
-                return subMap.isEmpty();
+        @Override
+        public boolean isEmpty() {
+            return subMap.isEmpty();
+        }
+
+        @Override
+        public Iterator<V> iterator() {
+            Node<K, V> from;
+            int fromIndex;
+            if (subMap.hasStart) {
+                subMap.setFirstKey();
+                from = subMap.firstKeyNode;
+                fromIndex = subMap.firstKeyIndex;
+            } else {
+                from = minimum(subMap.backingMap.root);
+                fromIndex = from != null ? from.left_idx : 0;
             }
+            if (!subMap.hasEnd) {
+                return new UnboundedValueIterator<K, V>(subMap.backingMap, from,
+                                   from == null ? 0 : from.right_idx - fromIndex);
+            }
+            subMap.setLastKey();
+            Node<K, V> to = subMap.lastKeyNode;
+            int toIndex = subMap.lastKeyIndex;
+            return new BoundedValueIterator<K, V>(from,
+               from == null ? 0 : from.right_idx - fromIndex, subMap.backingMap, to,
+                 to == null ? 0 : to.right_idx - toIndex);
+        }
+
+        @Override
+        public int size() {
+            return subMap.size();
+        }
+    }
 
-            @Override
-            public Iterator<V> iterator() {
-                if(subMap.backingMap.isSmall()) {
-                   int start, end;
-                   if(subMap.hasStart) {
-                       start = subMap.backingMap.smallFindAfter(subMap.startKey);
-                   } else {
-                       start = subMap.backingMap.small_left;
-                   }
-                    if(subMap.hasEnd) {
-                        end = subMap.backingMap.smallFindBefore(subMap.endKey);
-                    } else {
-                        end = subMap.backingMap.small_right;
-                    }
-                   return new SmallValueIterator<K,V>(subMap.backingMap,start,end); 
-                }
-                TreeMap.Entry<K,V> startNode = subMap.firstEntry();
-                if (subMap.hasEnd) {
-                    TreeMap.Entry<K,V> lastNode = subMap.lastEntry();
-                    return new BoundedValueIterator<K,V>(subMap.backingMap, startNode, lastNode);
-                }
-                return new UnboundedValueIterator<K,V>(subMap.backingMap, startNode);
-            }
-
-            @Override
-            public int size() {
-                return subMap.size();
-            }
-        }
-
-    private void createSmall(){
-        small_keys = (K[])new Object[SMALL_LIMIT];
-        small_values = (V[])new Object[SMALL_LIMIT];
-    }
-
-    private void clearSmall(){
-        small_keys = null;
-        small_values = null;
-        small_entries = null;
-        small_right = -1;
-        small_left = 0;
-    }
-
-    private boolean isSmall(){
-        return small_keys!=null;
-    }
-
-	/**
-	 * Constructs a new empty instance of TreeMap.
-	 *
-	 */
-	public TreeMap() {
-        createSmall();
-	}
-
-	/**
-	 * 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;
-        createSmall();
-	}
-
-	/**
-	 * 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) {
-		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.comparator = 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 {
-				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
+    /**
+     * Constructs a new empty instance of spec.TreeMap.
+     */
+    public TreeMap() {
+    }
+
+    /**
+     * Constructs a new empty instance of spec.TreeMap which uses the specified
+     * Comparator.
+     *
+     * @param comparator the Comparator
+     */
+    public TreeMap(Comparator<? super K> comparator) {
+        this.comparator = comparator;
+    }
+
+    /**
+     * Constructs a new instance of spec.TreeMap containing the mappings from the
+     * specified Map and using the natural ordering.
+     *
+     * @param map the mappings to add
+     * @throws 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) {
+        putAll(map);
+    }
+
+    /**
+     * Constructs a new instance of spec.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());
+        Node<K, V> lastNode = null;
+        Iterator<? extends Map.Entry<K, ? extends V>> it = map.entrySet().iterator();
+        while (it.hasNext()) {
+            Map.Entry<K, ? extends V> entry = it.next();
+            lastNode = addToLast(lastNode, entry.getKey(), entry.getValue());
+        }
+    }
+
+    Node<K, V> addToLast(Node<K, V> last, K key, V value) {
+        if (last == null) {
+            root = last = createNode(key, value);
+            size = 1;
+        } else if (last.size == Node.NODE_SIZE) {
+            Node<K, V> newNode = createNode(key, value);
+            attachToRight(last, newNode);
+            balance(newNode);
+            size++;
+            last = newNode;
+        } else {
+            appendFromRight(last, key, value);
+            size++;
+        }
+        return last;
+    }
+
+    /**
+     * Removes all mappings from this spec.TreeMap, leaving it empty.
+     *
+     * @see Map#isEmpty
+     * @see #size
+     */
+    @Override
     public void clear() {
-		root = null;
-		size = 0;
-		modCount++;
-        clearSmall();
-        createSmall();
-	}
-
-	/**
-	 * 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")
+        root = null;
+        size = 0;
+        modCount++;
+    }
+
+    /**
+     * Answers a new spec.TreeMap with the same mappings, size and comparator as this
+     * spec.TreeMap.
+     *
+     * @return a shallow copy of this spec.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) {
+        try {
+            TreeMap<K, V> clone = (TreeMap<K, V>) super.clone();
+            clone.entrySet = null;
+            if (root != null) {
                 clone.root = root.clone(null);
-            } else if(isSmall()) {
-                clone.createSmall();
-                clone.small_entries = null;
-                System.arraycopy(small_keys,0,clone.small_keys,0,small_keys.length);
-                System.arraycopy(small_values,0,clone.small_values,0,small_values.length);
-                clone.small_left = small_left;
-                clone.small_right = small_right;
-            }
-			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
-	 */
+                // restore prev/next chain
+                Node<K, V> node = minimum(clone.root);
+                while (true) {
+                    Node<K, V> nxt = successor(node);
+                    if (nxt == null) {
+                        break;
+                    }
+                    nxt.prev = node;
+                    node.next = nxt;
+                    node = nxt;
+                }
+            }
+            return clone;
+        } catch (CloneNotSupportedException e) {
+            return null;
+        }
+    }
+
+    static private <K, V> Node<K, V> successor(Node<K, V> x) {
+        if (x.right != null) {
+            return minimum(x.right);
+        }
+        Node<K, V> y = x.parent;
+        while (y != null && x == y.right) {
+            x = y;
+            y = y.parent;
+        }
+        return y;
+    }
+
+    /**
+     * Answers the Comparator used to compare elements in this spec.TreeMap.
+     *
+     * @return a Comparator or null if the natural ordering is used
+     */
+    public Comparator<? super K> comparator() {
+        return comparator;
+    }
+
+    /**
+     * Searches this spec.TreeMap for the specified key.
+     *
+     * @param key the object to search for
+     * @return true if <code>key</code> is a key of this spec.TreeMap, false
+     *         otherwise
+     * @throws ClassCastException   when the key cannot be compared with the keys in this
+     *                              spec.TreeMap
+     * @throws NullPointerException when the key is null and the comparator cannot handle null
+     */
     @Override
     public boolean containsKey(Object key) {
-		return isSmall() ? smallFind(key)>=0 : find(key) != null;
-	}
+        Comparable<K> object = comparator == null ? toComparable((K) key) : null;
+        K keyK = (K) key;
+        Node<K, V> node = root;
+        while (node != null) {
+            K[] keys = node.keys;
+            int left_idx = node.left_idx;
+            int result = cmp(object, keyK, keys[left_idx]);
+            if (result < 0) {
+                node = node.left;
+            } else if (result == 0) {
+                return true;
+            } else {
+                int right_idx = node.right_idx;
+                if (left_idx != right_idx) {
+                    result = cmp(object, keyK, keys[right_idx]);
+                }
+                if (result > 0) {
+                    node = node.right;
+                } else if (result == 0) {
+                    return true;
+                } else { /*search in node*/
+                    int low = left_idx + 1, mid = 0, high = right_idx - 1;
+                    while (low <= high) {
+                        mid = (low + high) >> 1;
+                        result = cmp(object, keyK, keys[mid]);
+                        if (result > 0) {
+                            low = mid + 1;
+                        } else if (result == 0) {
+                            return true;
+                        } else {
+                            high = mid - 1;
+                        }
+                    }
+                    return false;
+                }
+            }
+        }
+        return false;
+    }
 
-	/**
-	 * 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
-	 */
+    /**
+     * Searches this spec.TreeMap for the specified value.
+     *
+     * @param value the object to search for
+     * @return true if <code>value</code> is a value of this spec.TreeMap, false
+     *         otherwise
+     */
     @Override
     public boolean containsValue(Object value) {
-        if (root != null) {
-            return containsValue(root, value);
-        } else if (size > 0 & isSmall()) {
-            if (value == null) {
-                for (int i = small_left; i <= small_right; i++) {
-                    if (small_values[i] == null) {
+        if (root == null) {
+            return false;
+        }
+        Node<K, V> node = minimum(root);
+        if (value != null) {
+            while (node != null) {
+                int to = node.right_idx;
+                V[] values = node.values;
+                for (int i = node.left_idx; i <= to; i++) {
+                    if (value.equals(values[i])) {
                         return true;
                     }
                 }
-            } else {
-                for (int i = small_left; i <= small_right; i++) {
-                    if (value.equals(small_values[i])) {
+                node = node.next;
+            }
+        } else {
+            while (node != null) {
+                int to = node.right_idx;
+                V[] values = node.values;
+                for (int i = node.left_idx; i <= to; i++) {
+                    if (values[i] == null) {
                         return true;
                     }
                 }
+                node = node.next;
             }
         }
         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;
-	}
-
-	/**
-	 * 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
+    /**
+     * Answers a Set of the mappings contained in this spec.TreeMap. Each element in
+     * the set is a Map.Entry. The set is backed by this spec.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
+                @Override
                 public int size() {
                     return size;
                 }
@@ -1082,17 +1127,25 @@
                 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();
+                        Object v1 = TreeMap.this.get(entry.getKey()), v2 = entry.getValue();
                         return v1 == null ? v2 == null : v1.equals(v2);
                     }
                     return false;
                 }
 
                 @Override
-                public Iterator<Map.Entry<K, V>> iterator() {
-                    if(isSmall()) {
-                       return new SmallEntryIterator<K,V>(TreeMap.this,TreeMap.this.small_left,TreeMap.this.small_right);
+                public boolean remove(Object object) {
+                    if (contains(object)) {
+                        Map.Entry<K, V> entry = (Map.Entry<K, V>) object;
+                        K key = entry.getKey();
+                        TreeMap.this.remove(key);
+                        return true;
                     }
+                    return false;
+                }
+
+                @Override
+                public Iterator<Map.Entry<K, V>> iterator() {
                     return new UnboundedEntryIterator<K, V>(TreeMap.this);
                 }
             };
@@ -1100,845 +1153,952 @@
         return entrySet;
     }
 
-    /** @return the non-negative index of the element, or a negative index which
-      *         is the -index - 1 where the element would be inserted
-      */
-    private int smallFind(Object keyObj) {
-        if (small_left > small_right) {
-            return -1;
+    /**
+     * Answers the first sorted key in this spec.TreeMap.
+     *
+     * @return the first sorted key
+     * @throws NoSuchElementException when this spec.TreeMap is empty
+     */
+    public K firstKey() {
+        if (root != null) {
+            Node<K, V> node = minimum(root);
+            return node.keys[node.left_idx];
         }
-        K key = (K) keyObj;
-        if (comparator == null) {
-            Comparable<K> object = toComparable(key);
-            int low = small_left, mid = 0, high = small_right, result = 0;
-            while (low <= high) {
-                mid = (low + high) >> 1;
-                if ((result = object.compareTo(small_keys[mid])) > 0) {
-                    low = mid + 1;
-                } else if (result == 0) {
-                    return mid;
-                } else {
-                    high = mid - 1;
+        throw new NoSuchElementException();
+    }
+
+
+    /**
+     * Answers the value of the mapping with the specified key.
+     *
+     * @param key the key
+     * @return the value of the mapping with the specified key
+     * @throws ClassCastException   when the key cannot be compared with the keys in this
+     *                              spec.TreeMap
+     * @throws NullPointerException when the key is null and the comparator cannot handle null
+     */
+    @Override
+    public V get(Object key) {
+        Comparable<K> object = comparator == null ? toComparable((K) key) : null;
+        K keyK = (K) key;
+        Node<K, V> node = root;
+        while (node != null) {
+            K[] keys = node.keys;
+            int left_idx = node.left_idx;
+            int result = cmp(object, keyK, keys[left_idx]);
+            if (result < 0) {
+                node = node.left;
+            } else if (result == 0) {
+                return node.values[left_idx];
+            } else {
+                int right_idx = node.right_idx;
+                if (left_idx != right_idx) {
+                    result = cmp(object, keyK, keys[right_idx]);
                 }
-            }
-            return -mid - (result <= 0 ? 1 : 2);
-        } else {
-            int low = small_left, mid = 0, high = small_right, result = 0;
-            while (low <= high) {
-                mid = (low + high) >> 1;
-                if ((result = comparator.compare(key, small_keys[mid])) > 0) {
-                    low = mid + 1;
+                if (result > 0) {
+                    node = node.right;
                 } else if (result == 0) {
-                    return mid;
-                } else {
-                    high = mid - 1;
+                    return node.values[right_idx];
+                } else { /*search in node*/
+                    int low = left_idx + 1, mid = 0, high = right_idx - 1;
+                    while (low <= high) {
+                        mid = (low + high) >> 1;
+                        result = cmp(object, keyK, keys[mid]);
+                        if (result > 0) {
+                            low = mid + 1;
+                        } else if (result == 0) {
+                            return node.values[mid];
+                        } else {
+                            high = mid - 1;
+                        }
+                    }
+                    return null;
                 }
             }
-            return -mid - (result <= 0 ? 1 : 2);
         }
+        return null;
     }
 
-	@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;
-                }
-    			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;
-                }
-    			x = result < 0 ? x.left : x.right;
-    		}
-        }
-		return null;
-	}
-
-    int smallFindAfter(Object keyObj) {
-        int idx = smallFind(keyObj);
-        if(idx>=0) {
-            return idx;
-        } else {
-            idx = -idx - 1;
-            return (idx>small_right) ? -1 : idx;
-        }
-    }
-
-    int smallFindBefore(Object keyObj) {
-        int idx = smallFind(keyObj);
-        if(idx>=0) {
-            return (idx==small_left) ? -1 : idx-1;
-        } else {
-            idx = -idx - 1;
-            return (idx<=small_left) ? -1 : idx-1;
-        }
+    private int cmp(Comparable<K> object, K key1, K key2) {
+        return object != null ?
+               object.compareTo(key2) : comparator.compare(key1, key2);
     }
 
-	@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;
-            }
-		}
-		return last;
-	}
-
-	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;
-            } else {
-				last = x;
-				x = x.right;
-			}
-		}
-		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;
-        } else if(size>0 & isSmall()) {
-            return small_keys[small_left];
-        }
-		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) {
-        if(isSmall()) {
-            int idx = smallFind(key);
-            if(idx >= 0) {
-                return small_values[idx];
-            }
-        } else {
-		    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) {
+    /**
+     * Answers a SortedMap of the specified portion of this spec.TreeMap which
+     * contains keys less than the end key. The returned SortedMap is backed by
+     * this spec.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>
+     * @throws ClassCastException   when the end key cannot be compared with the keys in this
+     *                              spec.TreeMap
+     * @throws 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);
-	}
+        return new SubMap<K, V>(this, endKey);
+    }
 
-	/**
-	 * 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
+    /**
+     * Answers a Set of the keys contained in this spec.TreeMap. The set is backed by
+     * this spec.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
+        if (keySet == null) {
+            keySet = new AbstractSet<K>() {
+                @Override
                 public boolean contains(Object object) {
-					return containsKey(object);
-				}
+                    return TreeMap.this.containsKey(object);
+                }
 
-				@Override
+                @Override
                 public int size() {
-					return size;
-				}
+                    return TreeMap.this.size;
+                }
 
-				@Override
+                @Override
                 public void clear() {
-					TreeMap.this.clear();
-				}
+                    TreeMap.this.clear();
+                }
 
-				@Override
-                public Iterator<K> iterator() {
-                    if(isSmall()) {
-                       return new SmallKeyIterator<K,V>(TreeMap.this,TreeMap.this.small_left,TreeMap.this.small_right);
+                @Override
+                public boolean remove(Object object) {
+                    if (contains(object)) {
+                        TreeMap.this.remove(object);
+                        return true;
                     }
-                    return new UnboundedKeyIterator<K,V> (TreeMap.this);
-				}
-			};
-		}
-		return keySet;
-	}
-
-	/**
-	 * 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;
-        } else if(size>0 && isSmall()) {
-            return small_keys[small_right];
-        }
-		throw new NoSuchElementException();
-	}
-
-	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;
+                    return false;
+                }
+
+                @Override
+                public Iterator<K> iterator() {
+                    return new UnboundedKeyIterator<K, V>(TreeMap.this);
+                }
+            };
         }
-		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;
-	}
+        return keySet;
+    }
 
-	static <K, V> Entry<K, V> maximum(Entry<K, V> x) {
-		while (x.right != null) {
-            x = x.right;
+    /**
+     * Answer the last sorted key in this spec.TreeMap.
+     *
+     * @return the last sorted key
+     * @throws NoSuchElementException when this spec.TreeMap is empty
+     */
+    public K lastKey() {
+        if (root != null) {
+            Node<K, V> node = maximum(root);
+            return node.keys[node.right_idx];
         }
-		return x;
-	}
+        throw new NoSuchElementException();
+    }
 
-	static <K, V> Entry<K, V> minimum(Entry<K, V> x) {
-		while (x.left != null) {
+    static <K,V> Node<K, V> minimum(Node<K, V> x) {
+        if (x == null) {
+            return null;
+        }
+        while (x.left != null) {
             x = x.left;
         }
-		return x;
-	}
+        return x;
+    }
+
+    static <K,V> Node<K, V> maximum(Node<K, V> x) {
+        if (x == null) {
+            return null;
+        }
+        while (x.right != null) {
+            x = x.right;
+        }
+        return x;
+    }
 
-	static <K, V> Entry<K, V> predecessor(Entry<K, V> x) {
-		if (x.left != null) {
-            return maximum(x.left);
-        }
-		Entry<K, V> y = x.parent;
-		while (y != null && x == y.left) {
-			x = y;
-			y = y.parent;
-		}
-		return y;
-	}
-
-    private Entry<K, V> smallDeflate(int from, int to){
-        int elem = (from+to)>>1;
-        Entry<K, V> entry = small_entries==null? null:small_entries[elem];
-        if(entry == null) {
-            entry= new Entry<K, V>(small_keys[elem],small_values[elem]);
-        }
-        if(from<=elem-1) {
-            entry.left = smallDeflate(from,elem-1);
-            entry.left.parent = entry;
-        }
-        if(elem+1<=to) {
-            entry.right = smallDeflate(elem+1,to);
-            entry.right.parent = entry;
-        }
-        return entry;
-    }
-
-	/**
-	 * Maps the specified key to the specified value.
-	 *
-	 * @param key
-	 *            the key
-	 * @param value
-	 *            the value
-	 * @return the value of any previous mapping with the specified key or null
-	 *         if there was no mapping
-	 *
-	 * @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
+    /**
+     * Maps the specified key to the specified value.
+     *
+     * @param key   the key
+     * @param value the value
+     * @return the value of any previous mapping with the specified key or null
+     *         if there was no mapping
+     * @throws ClassCastException   when the key cannot be compared with the keys in this
+     *                              spec.TreeMap
+     * @throws NullPointerException when the key is null and the comparator cannot handle null
+     */
+    @Override
     public V put(K key, V value) {
-        if(isSmall()) {
-            if(small_left>small_right) {
-                small_left = small_right = 0;
-                small_keys[0] = key;
-                small_values[0] = value;
-                modCount++;
-                size++;
-                return null;
-            } else {
-                int idx = smallFind(key);
-                if(idx>=0) {
-                    V res = small_values[idx];
-                    small_values[idx] = value;
-                    if(small_entries!=null && small_entries[idx]!=null) {
-                        small_entries[idx].value = value;
-                    }
+        if (root == null) {
+            root = createNode(key, value);
+            size = 1;
+            modCount++;
+            return null;
+        }
+        Comparable<K> object = comparator == null ? toComparable((K) key) : null;
+        K keyK = (K) key;
+        Node<K, V> node = root;
+        Node<K, V> prevNode = null;
+        int result = 0;
+        while (node != null) {
+            prevNode = node;
+            K[] keys = node.keys;
+            int left_idx = node.left_idx;
+            result = cmp(object, keyK, keys[left_idx]);
+            if (result < 0) {
+                node = node.left;
+            } else if (result == 0) {
+                V res = node.values[left_idx];
+                node.values[left_idx] = value;
+                return res;
+            } else {
+                int right_idx = node.right_idx;
+                if (left_idx != right_idx) {
+                    result = cmp(object, keyK, keys[right_idx]);
+                }
+                if (result > 0) {
+                    node = node.right;
+                } else if (result == 0) {
+                    V res = node.values[right_idx];
+                    node.values[right_idx] = value;
                     return res;

[... 1091 lines stripped ...]


Mime
View raw message