harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From lvj...@apache.org
Subject svn commit: r727339 [2/5] - in /harmony/enhanced/classlib/branches/java6/modules/luni/src: main/java/java/util/ test/api/common/org/apache/harmony/luni/tests/java/util/
Date Wed, 17 Dec 2008 10:40:46 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?rev=727339&r1=727338&r2=727339&view=diff
==============================================================================
--- 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 Wed Dec 17 02:40:45 2008
@@ -41,7 +41,7 @@
 
     transient int size;
 
-    transient Entry<K, V> root;
+    transient Node<K, V> root;
 
     Comparator<? super K> comparator;
 
@@ -52,13 +52,73 @@
     transient NavigableMap<K, V> descendingMap;
 
     transient NavigableSet<K> navigableKeySet;
+    
+    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;
+
+        @SuppressWarnings("unchecked")
+        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) {
+                clone.right = right.clone(clone);
+            }
+            clone.prev = null;
+            clone.next = null;
+            return clone;
+        }
+    }
+    
     /**
      * Entry is an internal class which is used to hold the entries of a
      * TreeMap.
+     * 
+     * also used to record key, value, and position
      */
     static class Entry<K, V> extends MapEntry<K, V> {
         Entry<K, V> parent, left, right;
+        
+        Node<K, V> node;
+
+        int index;
+
+        public void setLocation(Node<K, V> node, int index, V value, K key) {
+            this.node = node;
+            this.index = index;
+            this.value = value;
+            this.key = key;
+        }
 
         boolean color;
 
@@ -82,30 +142,13 @@
             }
             return clone;
         }
-    }
-
-    /*
-     * 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;
-                }
-            }
+        
+        public V setValue(V object) {
+            V result = value;
+            value = object;
+            this.node.values[index] = value;
+            return result;
         }
-        return false;
     }
 
     private static abstract class AbstractSubMapIterator<K, V> {
@@ -113,64 +156,107 @@
 
         int expectedModCount;
 
-        TreeMap.Entry<K, V> node;
-
-        TreeMap.Entry<K, V> lastNode;
+        TreeMap.Node<K, V> node;
         
-        TreeMap.Entry<K, V> boundaryNode;
+        TreeMap.Node<K, V> lastNode;
         
-        boolean getToEnd = false;
+        TreeMap.Entry<K, V> boundaryPair;
+        
+        int offset;
 
+        int lastOffset;
+        
+        boolean getToEnd = false;
+        
         AbstractSubMapIterator(final NavigableSubMap<K, V> map) {
             subMap = map;
-            expectedModCount = subMap.backingMap.modCount;
-            node = getStartNode();
-            
-            boundaryNode = getBoundaryNode();
-			if (null == boundaryNode) {
-				node = null;
-			}
+            expectedModCount = subMap.m.modCount;
+
+            TreeMap.Entry<K, V> entry = map.findStartNode();
+            if (entry != null) {
+                if (map.toEnd && !map.checkUpperBound(entry.key)) {
+                } else {
+                    node = entry.node;
+                    offset = entry.index;
+                    boundaryPair = getBoundaryNode();
+                }
+            }
         }
 
-        public final void remove() {
-            if (expectedModCount == subMap.backingMap.modCount) {
-                if (lastNode != null) {
-                    if (lastNode.key == this.boundaryNode.key) {
-                        node = null;
+        public void remove() {
+            if (expectedModCount == subMap.m.modCount) {
+                if (expectedModCount == subMap.m.modCount) {
+                    K key = (node != null) ? node.keys[offset] : null;
+                    if (lastNode != null) {
+                        int idx = lastOffset;
+                        if (idx == lastNode.left_idx){
+                            subMap.m.removeLeftmost(lastNode);
+                        } else if (idx == lastNode.right_idx) {
+                            subMap.m.removeRightmost(lastNode);
+                        } else {
+                            int lastRight = lastNode.right_idx;
+                            key = subMap.m.removeMiddleElement(lastNode, idx);
+                            if (key == null && lastRight > lastNode.right_idx) {
+                                // removed from right
+                                offset--;
+                            }
+                        }
+                        if (null != key) {
+                            // the node has been cleared
+                            Entry<K, V> entry = subMap.m.find(key);
+                            if (this.subMap.isInRange(key)) {
+                                node = entry.node;
+                                offset = entry.index;
+                                boundaryPair = getBoundaryNode();
+                            } else {
+                                node = null;
+                            }
+                        }
+                        if (node != null && !this.subMap.isInRange(node.keys[offset])){
+                            node = null;
+                        }
+                        lastNode = null;
+                        expectedModCount++;
+                    } else {
+                        throw new IllegalStateException();
                     }
-                    subMap.backingMap.rbDelete(lastNode);
-                    if( null != node && node.key == lastNode.key) {
-                        node = lastNode;
-                    }
-                    lastNode = null;
-                    expectedModCount++;
-                } else {
-                    throw new IllegalStateException();
                 }
             } else {
                 throw new ConcurrentModificationException();
             }
         }
-
-        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;
-                }
+        
+        final void makeNext() {
+            if (expectedModCount != subMap.m.modCount) {
                 throw new ConcurrentModificationException();
+            } else if (node == null) {
+                throw new NoSuchElementException();
+            }
+            lastNode = node;
+            lastOffset = offset;
+            if (offset != lastNode.right_idx) {
+                offset++;
+            } else {
+                node = node.next;
+                if (node != null) {
+                    offset = node.left_idx;
+                }
+            }
+            if (boundaryPair.node == lastNode
+                    && boundaryPair.index == lastOffset) {
+                node = null;
             }
-            throw new NoSuchElementException();
         }
 
-        abstract TreeMap.Entry<K, V> getStartNode();
+        
+        Entry<K, V> createEntry(Node<K,V> node, int index) {
+            TreeMap.Entry<K, V> entry = new TreeMap.Entry<K, V>(node.keys[index], node.values[index]);
+            entry.node = node;
+            entry.index = index;
+            return entry; 
+        }
 
-        abstract TreeMap.Entry<K, V> getRealNext(TreeMap.Entry<K, V> entry);
+        abstract TreeMap.Entry<K, V> getStartNode();
 
         abstract boolean hasNext();
         
@@ -178,47 +264,67 @@
     }
 
     private abstract static class AscendingSubMapIterator<K, V> extends
-            AbstractSubMapIterator<K, V> {    	
-    	
-    	AscendingSubMapIterator(NavigableSubMap<K, V> map) {
+            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();
-		}
+            TreeMap.Entry<K, V> entry = null;
+            if (subMap.toEnd) {
+                entry = subMap.hiInclusive ? subMap
+                        .smallerOrEqualEntry(subMap.hi) : subMap
+                        .smallerEntry(subMap.hi);
+            } else {
+                entry = subMap.theBiggestEntry();
+            }
+            if (entry == null){
+                entry = subMap.findStartNode();
+            }
+            return entry;
+        }
 
         @Override
         final TreeMap.Entry<K, V> getStartNode() {
-            if (subMap.hasStart) {
-                return subMap.startInclusive ? subMap
-                        .biggerOrEqualEntry(subMap.startKey) : subMap
-                        .biggerEntry(subMap.startKey);
+            if (subMap.fromStart) {
+                return subMap.loInclusive ? subMap
+                        .biggerOrEqualEntry(subMap.lo) : subMap
+                        .biggerEntry(subMap.lo);
             }
             return subMap.theSmallestEntry();
         }
 
-        @Override
-        final Entry<K, V> getRealNext(Entry<K, V> entry) {
-            return TreeMap.successor(entry);            
+        TreeMap.Entry<K, V> getNext() {
+            if (expectedModCount != subMap.m.modCount) {
+                throw new ConcurrentModificationException();
+            } else if (node == null) {
+                throw new NoSuchElementException();
+            }
+            lastNode = node;
+            lastOffset = offset;
+            if (offset != node.right_idx) {
+                offset++;
+            } else {
+                node = node.next;
+                if (node != null) {
+                    offset = node.left_idx;
+                }
+            }
+            if (lastNode != null) {
+                boundaryPair = getBoundaryNode();
+                if (boundaryPair != null && boundaryPair.node == lastNode && boundaryPair.index == lastOffset) {
+                    node = null;
+                }
+                return createEntry(lastNode, lastOffset);
+            } 
+            return null;
         }
+        
 
         @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;
+            return null!=node;
         }
 
     }
@@ -250,45 +356,117 @@
     private abstract static class DescendingSubMapIterator<K, V> extends
             AbstractSubMapIterator<K, V> {
 
-    	DescendingSubMapIterator(NavigableSubMap<K, V> map) {
-            super(map);            
+        DescendingSubMapIterator(NavigableSubMap<K, V> map) {
+            super(map); 
+            TreeMap.Entry<K,V> entry;
+            if (map.fromStart){
+                entry = map.loInclusive ? map.m.findFloorEntry(map.lo) : map.m.findLowerEntry(map.lo);
+            } else {
+                entry = map.m.findBiggestEntry();
+            }
+            if (entry != null) {
+                if (!map.isInRange(entry.key)) {
+                    node = null;
+                    return;
+                }
+                node = entry.node;
+                offset = entry.index;
+            } else {
+                node = null;
+                return;
+            }
+            boundaryPair = getBoundaryNode();
+            if (boundaryPair != null){
+                if (map.m.keyCompare(boundaryPair.key,entry.key) > 0){
+                    node = null;
+                }
+            }
+            if (map.toEnd && !map.hiInclusive){
+                // the last element may be the same with first one but it is not included
+                if (map.m.keyCompare(map.hi,entry.key) == 0){
+                    node = null;
+                }
+            }
         }
 
         @Override
         final TreeMap.Entry<K, V> getStartNode() {
-            if (subMap.hasEnd) {
-                return subMap.endInclusive ? subMap
-                        .smallerOrEqualEntry(subMap.endKey) : subMap
-                        .smallerEntry(subMap.endKey);
+            if (subMap.toEnd) {
+                return subMap.hiInclusive ? subMap
+                        .smallerOrEqualEntry(subMap.hi) : subMap
+                        .smallerEntry(subMap.hi);
             }
             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();
-		}
-
-        @Override
-        final Entry<K, V> getRealNext(Entry<K, V> entry) {
-            return TreeMap.predecessor(entry);
+            if (subMap.toEnd) {
+                return subMap.hiInclusive ? subMap.m.findCeilingEntry(subMap.hi) : subMap.m.findHigherEntry(subMap.hi);
+            }
+            return subMap.m.findSmallestEntry();
+        }
+        
+        TreeMap.Entry<K, V> getNext() {
+            if (node == null) {
+                throw new NoSuchElementException();
+            }
+            if (expectedModCount != subMap.m.modCount) {
+                throw new ConcurrentModificationException();
+            }
+            
+            lastNode = node;
+            lastOffset = offset;
+            if (offset != node.left_idx) {
+                offset--;
+            } else {
+                node = node.prev;
+                if (node != null) {
+                    offset = node.right_idx;
+                }
+            }
+            boundaryPair = getBoundaryNode();
+            if (boundaryPair != null && boundaryPair.node == lastNode && boundaryPair.index == lastOffset) {
+                node = null;
+            }
+            return createEntry(lastNode, lastOffset);
         }
 
         @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;
+            return node != null;
+        }
+        
+        public final void remove() {
+            if (expectedModCount == subMap.m.modCount) {
+                if (expectedModCount == subMap.m.modCount) {
+                    K key = (node != null) ? node.keys[offset] : null;
+                    if (lastNode != null) {
+                        int idx = lastOffset;
+                        if (idx == lastNode.left_idx){
+                            subMap.m.removeLeftmost(lastNode);
+                        } else if (idx == lastNode.right_idx) {
+                            subMap.m.removeRightmost(lastNode);
+                        } else {
+                            subMap.m.removeMiddleElement(lastNode, idx);
+                        }
+                        if (null != key) {
+                            // the node has been cleared
+                            Entry<K,V> entry = subMap.m.find(key);
+                            node = entry.node;
+                            offset = entry.index;
+                            boundaryPair = getBoundaryNode();
+                        } else {
+                            node = null;
+                        }
+                        lastNode = null;
+                        expectedModCount++;
+                    } else {
+                        throw new IllegalStateException();
+                    }
+                }
+            } else {
+                throw new ConcurrentModificationException();
+            }
         }
     }
 
@@ -315,308 +493,1873 @@
             return getNext().key;
         }
     }
+    
+    static final class SubMap<K, V> extends AbstractMap<K, V> implements
+            SortedMap<K, V>, Serializable {
+        private static final long serialVersionUID = -6520786458950516097L;
 
-    /*
-     * 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;
+        private TreeMap<K, V> backingMap;
 
-        SubMapEntrySet(NavigableSubMap<K, V> map) {
-            subMap = map;
-        }
+        boolean hasStart, hasEnd;
 
-        @Override
-        public boolean isEmpty() {
-            return 0 == size();
-        }
+        K startKey, endKey;
 
-        @Override
-        public int size() {
-            int size = 0;
-            Iterator<Map.Entry<K, V>> it = iterator();
-            while (it.hasNext()) {
-                size++;
-                it.next();
-            }
-            return size;
-        }
+        transient Set<Map.Entry<K, V>> entrySet = null;
 
-        @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;
-        }
+        transient int firstKeyModCount = -1;
 
-        @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;
-        }
+        transient int lastKeyModCount = -1;
 
-        @Override
-        public abstract Iterator<Map.Entry<K, V>> iterator();
-    }
+        transient Node<K, V> firstKeyNode;
 
-    static class AscendingSubMapEntrySet<K, V> extends SubMapEntrySet<K, V> {
+        transient int firstKeyIndex;
 
-        AscendingSubMapEntrySet(NavigableSubMap<K, V> map) {
-            super(map);
-        }
+        transient Node<K, V> lastKeyNode;
 
-        @Override
-        public final Iterator<Map.Entry<K, V>> iterator() {
-            return new AscendingSubMapEntryIterator<K, V>(subMap);
+        transient int lastKeyIndex;
+
+        SubMap(K start, TreeMap<K, V> map) {
+            backingMap = map;
+            hasStart = true;
+            startKey = start;
         }
-    }
 
-    static class DescendingSubMapEntrySet<K, V> extends SubMapEntrySet<K, V> {
+        SubMap(K start, TreeMap<K, V> map, K end) {
+            backingMap = map;
+            hasStart = hasEnd = true;
+            startKey = start;
+            endKey = end;
+        }
+        
+        SubMap(K start, boolean hasStart, TreeMap<K, V> map, K end, boolean hasEnd) {
+            backingMap = map;
+            this.hasStart = hasStart;
+            this.hasEnd = hasEnd;
+            startKey = start;
+            endKey = end;
+        }
 
-        DescendingSubMapEntrySet(NavigableSubMap<K, V> map) {
-            super(map);
+        SubMap(TreeMap<K, V> map, K end) {
+            backingMap = map;
+            hasEnd = true;
+            endKey = end;
         }
 
-        @Override
-        public final Iterator<Map.Entry<K, V>> iterator() {
-            return new DescendingSubMapEntryIterator<K, V>(subMap);
+        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();
+                }
+            }
         }
-    }
 
-    static abstract class SubMapKeySet<K> extends AbstractSet<K> implements
-            NavigableSet<K> {
-        final NavigableSubMap<K, K> subMap;
+        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;
+        }
 
-        NavigableSet<K> descendingSet;
+        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;
+        }
 
-        SubMapKeySet(NavigableSubMap<K, K> map) {
-            subMap = map;
+        private boolean checkLowerBound(K key) {
+            if (hasStart && startKey != null) {
+                Comparator<? super K> cmp = backingMap.comparator;
+                if (cmp == null) {
+                    return (toComparable(key).compareTo(startKey) >= 0);
+                }
+                return (cmp.compare(key, startKey) >= 0);
+            }
+            return true;
         }
 
         public Comparator<? super K> comparator() {
-            return subMap.backingMap.comparator();
+            return backingMap.comparator();
         }
 
+        @SuppressWarnings("unchecked")
         @Override
-        public boolean contains(Object object) {
-            return subMap.backingMap.containsKey(object);
+        public boolean containsKey(Object key) {
+            if (isInRange((K) key)) {
+                return backingMap.containsKey(key);
+            }
+            return false;
         }
 
         @Override
-        public boolean isEmpty() {
-            return size() == 0;
+        public void clear() {
+            keySet().clear();
+        }
+
+        @Override
+        public boolean containsValue(Object value) {
+            Iterator<V> it = values().iterator();
+            if (value != null) {
+                while (it.hasNext()) {
+                    if (value.equals(it.next())) {
+                        return true;
+                    }
+                }
+            } else {
+                while (it.hasNext()) {
+                    if (it.next() == null) {
+                        return true;
+                    }
+                }
+            }
+            return false;
+        }
+
+        @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 = node.left_idx;
+                    node = node.left;
+                } else if (result == 0) {
+                    foundNode = node;
+                    foundIndex = node.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 = node.right_idx;
+                        break;
+                    } else { /* search in node */
+                        foundNode = node;
+                        foundIndex = node.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;
+                            }
+                        }
+                        break TOP_LOOP;
+                    }
+                }
+            }
+            if (foundNode != null
+                    && !checkUpperBound(foundNode.keys[foundIndex])) {
+                foundNode = null;
+            }
+            firstKeyNode = foundNode;
+            firstKeyIndex = foundIndex;
+            firstKeyModCount = backingMap.modCount;
+        }
+
+        public K firstKey() {
+            if (backingMap.size > 0 && !(startKey.equals(endKey))) {
+                if (!hasStart) {
+                    Node<K, V> node = minimum(backingMap.root);
+                    if (node != null
+                            && checkUpperBound(node.keys[node.left_idx])) {
+                        return node.keys[node.left_idx];
+                    }
+                } else {
+                    setFirstKey();
+                    if (firstKeyNode != null) {
+                        return firstKeyNode.keys[firstKeyIndex];
+                    }
+                }
+            }
+            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) {
+            Comparator<? super K> cmp = backingMap.comparator;
+            if (cmp == null) {
+                Comparable<K> object = toComparable(endKey);
+                if (hasStart && object.compareTo(startKey) < 0) {
+                    throw new IllegalArgumentException();
+                }
+                if (hasEnd && object.compareTo(this.endKey) > 0) {
+                    throw new IllegalArgumentException();
+                }
+            } else {
+                if (hasStart
+                        && backingMap.comparator().compare(endKey, startKey) < 0) {
+                    throw new IllegalArgumentException();
+                }
+                if (hasEnd && backingMap.comparator().compare(endKey, this.endKey) >= 0) {
+                    throw new IllegalArgumentException();
+                }
+            }
+            if (hasStart) {
+                return new SubMap<K, V>(startKey, backingMap, endKey);
+            }
+            return new SubMap<K, V>(backingMap, endKey);
+        }
+
+        @Override
+        public boolean isEmpty() {
+            return size() == 0;
+        }
+
+        @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;
+                // to be compatible with RI on null-key comparator
+                int result = object != null ? object.compareTo(keys[left_idx]) : -backingMap.comparator.compare(
+                        keys[left_idx] , key);
+                //int result =  - backingMap.cmp(object, keys[left_idx] , key);
+                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 {
+                            foundNode = node;
+                            foundIndex = right_idx;
+                        }
+                        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;
+                                break TOP_LOOP;
+                            } else {
+                                high = mid - 1;
+                            }
+                        }
+                        break TOP_LOOP;
+                    }
+                }
+            }
+            if (foundNode != null
+                    && !checkLowerBound(foundNode.keys[foundIndex])) {
+                foundNode = null;
+            }
+            lastKeyNode = foundNode;
+            lastKeyIndex = foundIndex;
+            lastKeyModCount = backingMap.modCount;
+        }
+
+        public K lastKey() {
+            if (backingMap.size > 0 && !(startKey.equals(endKey))) {
+                if (!hasEnd) {
+                    Node<K, V> node = maximum(backingMap.root);
+                    if (node != null
+                            && checkLowerBound(node.keys[node.right_idx])) {
+                        return node.keys[node.right_idx];
+                    }
+                } else {
+                    setLastKey();
+                    if (lastKeyNode != null) {
+                        Comparable<K> object = backingMap.comparator == null ? toComparable((K) endKey)
+                                : null;
+                        if (backingMap.cmp(object,  endKey, lastKeyNode.keys[lastKeyIndex]) != 0) {
+                            return lastKeyNode.keys[lastKeyIndex];
+                        } else {
+                            if (lastKeyIndex != lastKeyNode.left_idx) {
+                                object = backingMap.comparator == null ? toComparable((K) startKey)
+                                        : null;
+                                if (backingMap.cmp(object,  startKey, lastKeyNode.keys[lastKeyIndex-1]) < 0){
+                                    return lastKeyNode.keys[lastKeyIndex - 1];
+                                }
+                            } else {
+                                Node<K,V> last = lastKeyNode.prev;
+                                if (last != null) {
+                                    return last.keys[last.right_idx];
+                                }
+                            }
+                        }
+                    }
+                }
+            }
+            throw new NoSuchElementException();
+        }
+
+        @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;
+        }
+
+        public SortedMap<K, V> subMap(K startKey, K endKey) {
+            checkRange(startKey);
+            Comparator<? super K> cmp = backingMap.comparator;
+            if (cmp == null) {
+                Comparable<K> object = toComparable(endKey);
+                if (hasStart && object.compareTo(startKey) < 0) {
+                    throw new IllegalArgumentException();
+                }
+                if (hasEnd && object.compareTo(endKey) > 0) {
+                    throw new IllegalArgumentException();
+                }
+            } else {
+                if (hasStart
+                        && backingMap.comparator().compare(endKey, this.startKey) < 0) {
+                    throw new IllegalArgumentException();
+                }
+                if (hasEnd && backingMap.comparator().compare(endKey,this.endKey) > 0) {
+                    throw new IllegalArgumentException();
+                }
+            }
+            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();
+        }
+
+        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;
+        }
+
+        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;
+                Comparable<K> object = backingMap.comparator == null ? toComparable((K) endKey)
+                        : null;
+                if (backingMap.cmp(object, endKey, to.keys[toIndex]) != 0) {
+                    if (toIndex != to.keys.length) {
+                        toIndex++;
+                    } else {
+                        to = to.next;
+                        toIndex = to == null ? 0 : to.left_idx;
+                    }
+                }
+            } else {
+                to = maximum(backingMap.root);
+                toIndex = to == null ? 0 : to.right_idx;
+            }
+            if (to == null) {
+                return 0;
+            }
+            // the last element of submap if exist should be ignored
+            if (from == to) {
+                return toIndex - fromIndex + (hasEnd ? 0 : 1);
+            }
+            int sum = 0;
+            while (from != to) {
+                sum += (from.right_idx - fromIndex + 1);
+                from = from.next;
+                fromIndex = from.left_idx;
+            }
+            return sum + toIndex - fromIndex + (hasEnd ? 0 : 1);
+        }
+
+        private void readObject(ObjectInputStream stream) throws IOException,
+                ClassNotFoundException {
+            stream.defaultReadObject();
+            firstKeyModCount = -1;
+            lastKeyModCount = -1;
+        }
+    }
+    
+    static class SubMapValuesCollection<K, V> extends AbstractCollection<V> {
+        SubMap<K, V> subMap;
+
+        public SubMapValuesCollection(SubMap<K, V> subMap) {
+            this.subMap = subMap;
+        }
+
+        @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 : fromIndex);
+            }
+            subMap.setLastKey();
+            Node<K, V> to = subMap.lastKeyNode;
+            int toIndex = subMap.lastKeyIndex
+            + (subMap.lastKeyNode != null
+                    && (!subMap.lastKeyNode.keys[subMap.lastKeyIndex].equals(subMap.endKey)) ? 1
+                    : 0);
+            return new BoundedValueIterator<K, V>(from, from == null ? 0
+                    : fromIndex, subMap.backingMap, to,
+                    to == null ? 0 : toIndex);
+        }
+
+        @Override
+        public int size() {
+            return subMap.size();
+        }
+    }
+    
+    static class BoundedMapIterator<K, V> extends AbstractMapIterator<K, V> {
+
+        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);
+            if (startNode ==null &&  finalNode == null){
+                // no elements
+                node = null;
+                return;
+            }
+            if (finalNode != null) {
+                this.finalNode = finalNode;
+                this.finalOffset = finalOffset;
+            } else {
+                Entry<K, V> entry = map.findBiggestEntry();
+                if (entry != null) {
+                    this.finalNode = entry.node;
+                    this.finalOffset = entry.index;
+                } else {
+                    node = null;
+                    return;
+                }
+            }
+            if (startNode != null) {
+                if (node == this.finalNode && offset >= this.finalOffset) {
+                    node = null;
+                } else if (this.finalOffset < this.finalNode.right_idx) {
+                    Comparable<K> object = backingMap.comparator == null ? toComparable((K) startNode.keys[startOffset])
+                            : null;
+                    if (this.backingMap.cmp(object, node.keys[offset],
+                            this.finalNode.keys[this.finalOffset]) > 0) {
+                        node = null;
+                    }
+                }
+            }
+        }
+
+        BoundedMapIterator(Node<K, V> startNode, TreeMap<K, V> map,
+                Node<K, V> finalNode, int finalOffset) {
+            this(startNode, startNode.left_idx, map, finalNode, finalOffset);
+        }
+
+        BoundedMapIterator(Node<K, V> startNode, int startOffset,
+                TreeMap<K, V> map, Node<K, V> finalNode) {
+            this(startNode, startOffset, map, finalNode, finalNode.right_idx);
+        }
+
+        void makeBoundedNext() {
+            if (node != null){
+                boolean endOfIterator = lastNode == finalNode && lastOffset == finalOffset;
+                if (endOfIterator) {
+                    node = null;
+                } else {
+                    makeNext();
+                }
+            }
+        }
+        
+        public boolean hasNext(){
+            if (finalNode == node && finalOffset == offset) {
+                node = null;
+            }
+            return node != null;
+        }
+    }
+
+    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);
+        }
+
+        public Map.Entry<K, V> next() {
+            if (!hasNext()) {
+                throw new NoSuchElementException();
+            }
+            makeBoundedNext();
+            int idx = lastOffset;
+            return new MapEntry<K, V>(lastNode.keys[idx], lastNode.values[idx]);
+        }
+    }
+
+    static class BoundedKeyIterator<K, V> extends BoundedMapIterator<K, V>
+            implements Iterator<K> {
+
+        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() {
+            if (!hasNext()) {
+                throw new NoSuchElementException();
+            }
+            makeBoundedNext();
+            return lastNode.keys[lastOffset];
+        }
+    }
+
+    static class BoundedValueIterator<K, V> extends BoundedMapIterator<K, V>
+            implements Iterator<V> {
+
+        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() {
+            if (!hasNext()) {
+                throw new NoSuchElementException();
+            }
+            makeBoundedNext();
+            return lastNode.values[lastOffset];
+        }
+    }
+    
+    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 isEmpty() {
+            return subMap.isEmpty();
+        }
+
+        @Override
+        public int size() {
+            return subMap.size();
+        }
+
+        @Override
+        public boolean remove(Object object) {
+            return subMap.remove(object) != null;
+        }
+
+        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;
+            Comparable<K> object = subMap.backingMap.comparator == null ? toComparable((K) subMap.endKey)
+                    : null;
+            int toIndex = subMap.lastKeyIndex
+                    + (subMap.lastKeyNode != null
+                            && (!subMap.lastKeyNode.keys[subMap.lastKeyIndex].equals(subMap.endKey)) ? 1
+                            : 0);
+            if (subMap.lastKeyNode != null
+                    && toIndex > subMap.lastKeyNode.right_idx) {
+                to = to.next;
+                toIndex = to != null ? to.left_idx : 0;
+            }
+            return new BoundedKeyIterator<K, V>(from, from == null ? 0
+                    : fromIndex, subMap.backingMap, to,
+                    to == null ? 0 : toIndex);
+        }
+    }
+
+
+    /*
+     * Entry set of sub-maps, must override methods which check the range. add
+     * or addAll operations are disabled by default.
+     */
+    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;
+            }
+            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;
+            Comparable<K> object = subMap.backingMap.comparator == null ? toComparable((K) subMap.endKey)
+                    : null;
+            int toIndex = subMap.lastKeyIndex
+                    + (subMap.lastKeyNode != null
+                            && (!subMap.lastKeyNode.keys[subMap.lastKeyIndex].equals(subMap.endKey)) ? 1
+                            : 0);
+            if (subMap.lastKeyNode != null && toIndex > subMap.lastKeyNode.right_idx){
+                to = to.next;
+                toIndex = to != null ? to.left_idx : 0;
+            }
+            return new BoundedEntryIterator<K, V>(from, from == null ? 0
+                    : fromIndex, subMap.backingMap, to,
+                    to == null ? 0 : 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 && subMap.containsKey(key) ) : v1.equals(v2);
+                }
+            }
+            return false;
+        }
+
+        @SuppressWarnings("unchecked")
+        @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;
+        }
+    }
+    
+    static class AscendingSubMapEntrySet<K, V> extends
+            AbstractSet<Map.Entry<K, V>> implements NavigableSet<Map.Entry<K, V>> {
+        
+        boolean hasStart,hasEnd,startInclusive,endInclusive;
+        
+        java.util.Map.Entry<K,V> startEntry, lastentry; 
+        
+        NavigableSubMap<K, V> map;
+
+        AscendingSubMapEntrySet(NavigableSubMap<K, V> map) {
+            this.map = map;
+        }
+        
+        AscendingSubMapEntrySet(NavigableSubMap<K, V> map,
+                java.util.Map.Entry<K,V>  startEntry, boolean startInclusive,
+                java.util.Map.Entry<K,V>  endEntry, boolean endInclusive) {
+            if (startEntry != null) {
+                hasStart = true;
+                this.startEntry = startEntry;
+                this.startInclusive = startInclusive;
+            }
+            if (endEntry != null) {
+                hasEnd = true;
+                this.lastentry = endEntry;
+                this.endInclusive = endInclusive;
+            }
+            if (startEntry != null && endEntry != null) {
+                this.map = (NavigableSubMap<K, V>) map.subMap(startEntry
+                        .getKey(), startInclusive, endEntry.getKey(),
+                        endInclusive);
+                return;
+            }
+            if (startEntry != null) {
+                this.map = (NavigableSubMap<K, V>) map.tailMap(startEntry
+                        .getKey(), startInclusive);
+                return;
+            }
+            if (endEntry != null) {
+                this.map = (NavigableSubMap<K, V>) map.headMap(endEntry
+                        .getKey(), endInclusive);
+                return;
+            }
+            this.map = map;
+        }
+
+        @Override
+        public final Iterator<Map.Entry<K, V>> iterator() {
+            return new AscendingSubMapEntryIterator<K, V>(map);
+        }
+
+        @Override
+        public int size() {
+            int size = 0;
+            Iterator it = new AscendingSubMapEntryIterator<K, V>(map);
+            while (it.hasNext()){
+                it.next();
+                size ++;
+            }
+            return size;
+        }
+
+        public java.util.Map.Entry<K, V> ceiling(java.util.Map.Entry<K, V> e) {
+            Map.Entry<K, V> entry = map.ceilingEntry(e.getKey());
+            if (entry != null && map.isInRange(entry.getKey())){
+                return entry;
+            } else {
+                return null;
+            }
+        }
+
+        public Iterator<java.util.Map.Entry<K, V>> descendingIterator() {
+            return new DescendingSubMapEntrySet<K, V>(map.descendingSubMap()).iterator();
+        }
+
+        public NavigableSet<java.util.Map.Entry<K, V>> descendingSet() {
+            return new DescendingSubMapEntrySet<K, V>(map.descendingSubMap());
+        }
+
+        public java.util.Map.Entry<K, V> floor(java.util.Map.Entry<K, V> e) {
+            Map.Entry<K, V> entry = map.floorEntry(e.getKey());
+            if (entry!= null && map.isInRange(entry.getKey())){
+                return entry;
+            } else {
+                return null;
+            }
+        }
+
+        public NavigableSet<java.util.Map.Entry<K, V>> headSet(
+                java.util.Map.Entry<K, V> end, boolean endInclusive) {
+            boolean isInRange = true;
+            int result;
+            K endKey = end.getKey();
+            if (map.toEnd) {
+                result = (null != comparator()) ? comparator().compare(endKey,
+                        map.hi) : toComparable(endKey).compareTo(map.hi);
+                isInRange = (!map.hiInclusive && endInclusive) ? result < 0
+                        : result <= 0;
+            }
+            if (map.fromStart) {
+                result = (null != comparator()) ? comparator().compare(endKey,
+                        map.lo) : toComparable(endKey).compareTo(map.lo);
+                isInRange = isInRange
+                        && ((!map.loInclusive && endInclusive) ? result > 0
+                                : result >= 0);
+            }
+            if (isInRange) {
+                    return new AscendingSubMapEntrySet<K, V>(map, null, false,
+                            end, endInclusive);
+            }
+            throw new IllegalArgumentException();
+        }
+
+        public java.util.Map.Entry<K, V> higher(java.util.Map.Entry<K, V> e) {
+            Comparator<? super K> cmp = map.m.comparator;
+            if (cmp == null) {
+                Comparable<K> object = toComparable(e.getKey());
+                if (hasStart && object.compareTo(startEntry.getKey()) < 0) {
+                    return map.higherEntry(startEntry.getKey());
+                }
+                if (hasEnd && object.compareTo(lastentry.getKey()) >= 0) {
+                    return null;
+                }
+            } else {
+                if (hasStart && cmp.compare(e.getKey(), startEntry.getKey()) < 0) {
+                    return map.higherEntry(startEntry.getKey());
+                }
+                if (hasEnd && cmp.compare(e.getKey(), lastentry.getKey()) >= 0) {
+                    return null;
+                }
+            }
+            return map.higherEntry(e.getKey());
+        }
+
+        public java.util.Map.Entry<K, V> lower(java.util.Map.Entry<K, V> e) {
+            Comparator<? super K> cmp = map.m.comparator;
+            if (cmp == null) {
+                Comparable<K> object = toComparable(e.getKey());
+                if (hasStart && object.compareTo(startEntry.getKey()) < 0) {
+                    return null;
+                }
+                if (hasEnd && object.compareTo(lastentry.getKey()) >= 0) {
+                    return map.lowerEntry(lastentry.getKey());
+                }
+            } else {
+                if (hasStart && cmp.compare(e.getKey(), startEntry.getKey()) < 0) {
+                    return null;
+                }
+                if (hasEnd && cmp.compare(e.getKey(), lastentry.getKey()) >= 0) {
+                    return map.lowerEntry(lastentry.getKey());
+                }
+            }
+            return map.lowerEntry(e.getKey());
+        }
+
+        public java.util.Map.Entry<K, V> pollFirst() {
+            Map.Entry<K, V> ret = map.firstEntry(); 
+            if (ret == null){
+                return null;
+            }
+            map.m.remove(ret.getKey());
+            return ret;
+        }
+
+        public java.util.Map.Entry<K, V> pollLast() {
+            Map.Entry<K, V> ret = map.lastEntry(); 
+            if (ret == null){
+                return null;
+            }
+            map.m.remove(ret.getKey());
+            return ret;
+        }
+
+        public NavigableSet<java.util.Map.Entry<K, V>> subSet(java.util.Map.Entry<K, V> start, boolean startInclusive, java.util.Map.Entry<K, V> end, boolean endInclusive) {
+            if (map.m.keyCompare(start.getKey(), end.getKey()) > 0) {
+                throw new IllegalArgumentException();
+            }
+            if (map.fromStart
+                    && ((!map.loInclusive && endInclusive) ? map.m.keyCompare(end.getKey(), map.lo) <= 0
+                            : map.m.keyCompare(end.getKey(), map.lo) < 0)) {
+                throw new IllegalArgumentException();
+            }
+            if (map.toEnd
+                    && ((!map.hiInclusive && startInclusive) ? map.m.keyCompare(start.getKey(), map.hi) >= 0
+                            : map.m.keyCompare(start.getKey(), map.hi) > 0)) {
+                throw new IllegalArgumentException();
+            }
+            return new AscendingSubMapEntrySet<K, V>(map, start, startInclusive, end, endInclusive);
+        }
+
+        public NavigableSet<java.util.Map.Entry<K, V>> tailSet(java.util.Map.Entry<K, V> start, boolean startInclusive) {
+            boolean isInRange = true;
+            int result;
+            if (map.toEnd) {
+                result = (null != comparator()) ? comparator().compare(start.getKey(),
+                        map.hi) : toComparable(start.getKey()).compareTo(map.hi);
+                isInRange = (map.hiInclusive || !startInclusive) ? result <= 0
+                        : result < 0;
+            }
+            if (map.fromStart) {
+                result = (null != comparator()) ? comparator().compare(start.getKey(),
+                        map.lo) : toComparable(start.getKey()).compareTo(map.lo);
+                isInRange = isInRange
+                        && ((map.loInclusive || !startInclusive) ? result >= 0
+                                : result > 0);
+            }
+
+            if (isInRange) {
+                return new AscendingSubMapEntrySet<K, V>(map, start, startInclusive, null, false);
+            }
+            throw new IllegalArgumentException();
+            
+        }
+
+        public Comparator comparator() {
+            return map.m.comparator;
+        }
+
+        public java.util.Map.Entry<K, V> first() {
+            if (hasStart){
+                if (startInclusive){
+                    return startEntry;
+                } else {
+                    return map.floorEntry(startEntry.getKey());
+                }
+            }
+            java.util.Map.Entry<K, V> ret = map.firstEntry(); 
+            if (ret == null){
+                throw new NoSuchElementException();
+            }
+            return ret;
+        }
+
+        public SortedSet<java.util.Map.Entry<K, V>> headSet(java.util.Map.Entry<K, V> end) {
+            return headSet(end, false);
+        }
+
+        public java.util.Map.Entry<K, V> last() {
+            if (hasEnd){
+                if (endInclusive){
+                    return lastentry;
+                } else {
+                    return map.ceilingEntry(lastentry.getKey());
+                }
+            }
+            java.util.Map.Entry<K, V> ret = map.lastEntry();
+            if (ret == null){
+                throw new NoSuchElementException();
+            }
+            return ret;
+        }
+
+        public SortedSet<java.util.Map.Entry<K, V>> subSet(java.util.Map.Entry<K, V> start, java.util.Map.Entry<K, V> end) {
+            if ((null != comparator()) ? comparator().compare(start.getKey(), end.getKey()) > 0
+                    : toComparable(start.getKey()).compareTo(end.getKey()) > 0) {
+                throw new IllegalArgumentException();
+            }
+            if (!map.isInRange(start.getKey())) {
+                throw new IllegalArgumentException();
+            }
+            if (!map.isInRange(end.getKey())) {
+                throw new IllegalArgumentException();
+            }
+            return new AscendingSubMapEntrySet<K, V>(map, start, false, end, false);
+        }
+
+        public SortedSet<java.util.Map.Entry<K, V>> tailSet(java.util.Map.Entry<K, V> start) {
+            return tailSet(start, false);
+        }
+    }
+
+    static class DescendingSubMapEntrySet<K, V> extends
+            AbstractSet<Map.Entry<K, V>> implements NavigableSet<Map.Entry<K, V>> {
+        NavigableSubMap<K, V> map;
+        
+        DescendingSubMapEntrySet(NavigableSubMap<K, V> map) {
+            this.map = map;
+        }
+
+        @Override
+        public final Iterator<Map.Entry<K, V>> iterator() {
+            return new DescendingSubMapEntryIterator<K, V>(map);
         }
 
         @Override
         public int size() {
-            Iterator<K> it = iterator();
             int size = 0;
-            while (it.hasNext()) {
+            Iterator it = new DescendingSubMapEntryIterator<K, V>(map);
+            while (it.hasNext()){
                 it.next();
-                size++;
+                size ++;
             }
             return size;
         }
 
+        public java.util.Map.Entry<K, V> ceiling(java.util.Map.Entry<K, V> e) {
+            Entry<K,V> node =  map.m.findFloorEntry(e.getKey());
+            if (!map.checkUpperBound(node.key)){
+                node = map.findEndNode();
+            }
+            
+            if (!map.checkLowerBound(node.key)){
+                Comparable<K> object = map.comparator() == null ? toComparable((K) e.getKey())
+                        : null;
+                TreeMap.Entry<K, V> first = map.loInclusive ? map.m.findFloorEntry(map.lo) :map.m.findLowerEntry(map.lo);
+                if (first != null && map.cmp(object, e.getKey(), first.getKey()) <= 0){
+                    node = first;
+                } else {
+                    node = null;
+                }
+            }
+            return node;
+        }
+
+        public Iterator<java.util.Map.Entry<K, V>> descendingIterator() {
+            return descendingSet().iterator();
+        }
+
+        public NavigableSet<java.util.Map.Entry<K, V>> descendingSet() {
+            if (map.fromStart && map.toEnd) {
+                return new AscendingSubMapEntrySet<K, V>(
+                        new AscendingSubMap<K, V>(map.hi, map.hiInclusive,
+                                map.m, map.lo, map.loInclusive));
+            }
+            if (map.fromStart) {
+                return new AscendingSubMapEntrySet<K, V>(
+                        new AscendingSubMap<K, V>(map.m, map.lo,
+                                map.loInclusive));
+            }
+            if (map.toEnd) {
+                return new AscendingSubMapEntrySet<K, V>(
+                        new AscendingSubMap<K, V>(map.hi, map.hiInclusive,
+                                map.m));
+            }
+            return new AscendingSubMapEntrySet<K, V>(new AscendingSubMap<K, V>(
+                    map.m));
+        }
+
+        public java.util.Map.Entry<K, V> floor(java.util.Map.Entry<K, V> e) {
+            Entry<K,V> node =  map.m.findCeilingEntry(e.getKey());
+            if (!map.checkUpperBound(node.key)){
+                node = map.findEndNode();
+            }
+            
+            if (!map.checkLowerBound(node.key)){
+                Comparable<K> object = map.m.comparator == null ? toComparable((K) e.getKey())
+                        : null;
+                TreeMap.Entry<K, V> first = map.hiInclusive ? map.m.findCeilingEntry(map.hi) :map.m.findHigherEntry(map.hi);
+                if (first != null && map.cmp(object, e.getKey(), first.getKey()) < 0){
+                    node = first;
+                } else {
+                    node = null;
+                }
+            }
+            return node;
+        }
+        
+        void checkInRange(K key, boolean keyInclusive){
+            boolean isInRange = true;
+            int result = 0;
+            if (map.toEnd) {
+                result = (null != map.comparator()) ? comparator().compare(
+                        key, map.hi) : toComparable(key).compareTo(map.hi);
+                isInRange = ((!map.hiInclusive) && keyInclusive) ? result < 0
+                        : result <= 0;
+            }
+            if (map.fromStart) {
+                result = (null != comparator()) ? comparator().compare(key,
+                        map.lo) : toComparable(key).compareTo(map.lo);
+                isInRange = isInRange
+                        && (((!map.loInclusive) && keyInclusive) ? result > 0
+                                : result >= 0);
+            }
+            if (!isInRange){
+                throw new IllegalArgumentException();
+            }
+        }
+        
+        public NavigableSet<java.util.Map.Entry<K, V>> headSet(
+                java.util.Map.Entry<K, V> end, boolean endInclusive) {
+            boolean outRange = true;
+            int result = 0;
+            if (map.toEnd) {
+                result = (null != map.comparator()) ? comparator().compare(
+                        end.getKey(), map.hi) : toComparable(end.getKey()).compareTo(map.hi);
+                outRange = ((!map.hiInclusive) && endInclusive) ? result >= 0
+                        : result > 0;
+                 if (outRange){
+                            throw new IllegalArgumentException();
+                 }
+            }
+            if (map.fromStart) {
+                result = (null != comparator()) ? comparator().compare(end.getKey(),
+                        map.lo) : toComparable(end.getKey()).compareTo(map.lo);
+                outRange = (((!map.loInclusive) && endInclusive) ? result <= 0
+                                : result < 0);
+                if (outRange){
+                    throw new IllegalArgumentException();
+                }
+            }
+            
+            if (map.fromStart) {
+                return new DescendingSubMapEntrySet<K, V>(new DescendingSubMap<K, V>(
+                        map.lo, map.loInclusive, map.m, end.getKey(), endInclusive));
+            } else {
+                return new DescendingSubMapEntrySet<K, V>(new DescendingSubMap<K, V>(
+                        map.m, end.getKey(), endInclusive));
+            }
+        }
+
+        public java.util.Map.Entry<K, V> higher(java.util.Map.Entry<K, V> e) {
+            Entry<K,V> node =  map.m.findLowerEntry(e.getKey());
+            if (node != null && !map.checkUpperBound(node.key)){
+                node =  map.hiInclusive? map.findFloorEntryImpl(map.hi):map.findLowerEntryImpl(map.hi);
+                }
+            Comparable<K> object = map.comparator() == null ? toComparable((K) e.getKey())
+                    : null;
+            if (node != null && (map.cmp(object, e.getKey(), node.key)) > 0){
+                return null;
+            } 
+            if (node!=null && !map.checkLowerBound(node.key)){
+                TreeMap.Entry<K, V> first = map.loInclusive ? map.m.findFloorEntry(map.lo) :map.m.findLowerEntry(map.lo);
+                if (first != null && map.cmp(object, e.getKey(), first.getKey()) < 0){
+                    node = first;
+                } else {
+                    node = null;
+                }
+            }
+            return node;
+        }
+
+        public java.util.Map.Entry<K, V> lower(java.util.Map.Entry<K, V> e) {
+            Entry<K,V> node =  map.m.findHigherEntry(e.getKey());
+            if (node != null && !map.checkUpperBound(node.key)){
+                node =  map.loInclusive? map.findCeilingEntryImpl(map.hi):map.findHigherEntryImpl(map.hi);
+            }
+            Comparable<K> object = map.m.comparator == null ? toComparable((K) e.getKey())
+                    : null;
+            if (node != null && (map.cmp(object, e.getKey(), node.key)) >= 0){
+                return null;
+            } 
+            if (node!=null &&!map.checkLowerBound(node.key)){
+                Map.Entry<K, V> first = map.firstEntry();
+                if (first != null && map.cmp(object, e.getKey(),first.getKey()) < 0){
+                    node = map.findStartNode();
+                } else {
+                    node = null;
+                }
+            }
+            return node;
+        }
+
+        public java.util.Map.Entry<K, V> pollFirst() {
+            Map.Entry<K, V> ret = map.lastEntry();
+            if (ret == null){
+                return null;
+            }
+            map.m.remove(ret.getKey());
+            return ret;
+        }
+
+        public java.util.Map.Entry<K, V> pollLast() {
+            Map.Entry<K, V> ret = map.firstEntry();
+            if (ret == null){
+                return null;
+            }
+            map.m.remove(ret.getKey());
+            return ret;
+        }
+
+        public NavigableSet<java.util.Map.Entry<K, V>> subSet(
+                java.util.Map.Entry<K, V> start, boolean startInclusive,
+                java.util.Map.Entry<K, V> end, boolean endInclusive) {
+            Comparable<K> startobject = map.comparator() == null ? toComparable((K) start
+                    .getKey())
+                    : null;
+            Comparable<K> endobject = map.comparator() == null ? toComparable((K) end
+                    .getKey())
+                    : null;
+            if (map.fromStart
+                    && ((!map.loInclusive && startInclusive) ? map.cmp(
+                            startobject, start.getKey(), map.lo) <= 0 : map
+                            .cmp(startobject, start.getKey(), map.lo) < 0)
+                    || (map.toEnd && ((!map.hiInclusive && endInclusive) ? map
+                            .cmp(endobject, end.getKey(), map.hi) >= 0 : map
+                            .cmp(endobject, end.getKey(), map.hi) > 0))) {
+                throw new IllegalArgumentException();
+            }
+            if (map.cmp(startobject, start.getKey(), end.getKey()) > 0) {
+                throw new IllegalArgumentException();
+            }
+
+            return new DescendingSubMapEntrySet<K, V>(
+                    new DescendingSubMap<K, V>(start.getKey(), startInclusive,
+                            map.m, end.getKey(), endInclusive));
+        }
+
+        public NavigableSet<java.util.Map.Entry<K, V>> tailSet(
+                java.util.Map.Entry<K, V> start, boolean startInclusive) {
+            if (map.toEnd) {
+                return new DescendingSubMapEntrySet<K, V>(
+                        new DescendingSubMap<K, V>(start.getKey(),
+                                startInclusive, map.m, map.hi, map.hiInclusive));
+            } else {
+                return new DescendingSubMapEntrySet<K, V>(
+                        new DescendingSubMap<K, V>(start.getKey(),
+                                startInclusive, map.m));
+            }
+        }
+
+        public Comparator comparator() {
+            return map.comparator();
+        }
+
+        public java.util.Map.Entry<K, V> first() {
+            java.util.Map.Entry<K, V> ret = map.lastEntry();
+            if (ret == null){
+                throw new NoSuchElementException();
+            }
+            return ret;
+        }
+
+        public SortedSet<java.util.Map.Entry<K, V>> headSet(java.util.Map.Entry<K, V> end) {
+            return headSet(end,false);
+        }
+
+        public java.util.Map.Entry<K, V> last() {
+            java.util.Map.Entry<K, V> ret = map.firstEntry();
+            if (ret == null){
+                throw new NoSuchElementException();
+            }
+            return ret;
+        }
+
+        public SortedSet<java.util.Map.Entry<K, V>> subSet(
+                java.util.Map.Entry<K, V> start, java.util.Map.Entry<K, V> end) {
+                return subSet(start, true, end, false);
+        }
+        
+        int keyCompare(K left, K right) {
+            return (null != map.comparator()) ? map.comparator().compare(left,
+                    right) : toComparable(left).compareTo(right);
+        }
+
+        public SortedSet<java.util.Map.Entry<K, V>> tailSet(java.util.Map.Entry<K, V> start) {
+            return tailSet(start, true);
+        }
+    }
+
+    static class AscendingSubMapKeySet<K,V> extends AbstractSet<K> implements NavigableSet<K>  {
+        NavigableSubMap<K, V> map;
+        
+        AscendingSubMapKeySet(NavigableSubMap<K, V> map) {
+            this.map = map;
+        }
+
         @Override
-        public boolean remove(Object object) {
-            return null != subMap.remove(object);
+        public final Iterator<K> iterator() {
+            return new AscendingSubMapKeyIterator<K, V>(map);
+        }
+
+        public final Iterator<K> descendingIterator() {
+            return new DescendingSubMapKeyIterator<K, V>(map.descendingSubMap());
         }
 
         @Override
-        public abstract Iterator<K> iterator();
+        public int size() {
+            int size = 0;
+            Iterator it = new AscendingSubMapEntryIterator<K, V>(map);
+            while (it.hasNext()){
+                it.next();
+                size ++;
+            }
+            return size;
+        }
 
-        public abstract Iterator<K> descendingIterator();
+        public K ceiling(K e) {
+            Entry<K,V> ret = map.findFloorEntry(e);
+            if (ret != null && map.isInRange(ret.key)){
+                return ret.key;
+            } else {
+                return null;
+            }
+        }
 
-        public K first() {
-            return subMap.firstKey();
+        public NavigableSet<K> descendingSet() {
+            return new DescendingSubMapKeySet<K, V>(map.descendingSubMap());
         }
 
-        public K last() {
-            return subMap.lastKey();
+        public K floor(K e) {
+            Entry<K,V> ret = map.findFloorEntry(e);
+            if (ret != null && map.isInRange(ret.key)){
+                return ret.key;
+            } else {
+                return null;
+            }
         }
 
-        public K pollFirst() {
-            Map.Entry<K, K> entry = subMap.pollFirstEntry();
-            return (null == entry) ? null : entry.getKey();
+        public NavigableSet<K> headSet(K end, boolean endInclusive) {
+            boolean isInRange = true;
+                int result;
+            if (map.toEnd) {
+                result = (null != comparator()) ? comparator().compare(end,
+                        map.hi) : toComparable(end).compareTo(map.hi);
+                isInRange = (map.hiInclusive || !endInclusive) ? result <= 0
+                        : result < 0;
+            }
+            if (map.fromStart) {
+                result = (null != comparator()) ? comparator().compare(end,
+                        map.lo) : toComparable(end).compareTo(map.lo);
+                isInRange = isInRange
+                        && ((map.loInclusive || !endInclusive) ? result >= 0
+                                : result > 0);
+            }
+            if (isInRange) {
+                if (map.fromStart) {
+                    return new AscendingSubMapKeySet<K, V>(
+                            new AscendingSubMap<K, V>(map.lo, map.loInclusive,
+                                    map.m, end, endInclusive));
+                } else {
+                    return new AscendingSubMapKeySet<K, V>(
+                            new AscendingSubMap<K, V>(map.m, end, endInclusive));
+                }
+            }
+            throw new IllegalArgumentException();
         }
 
-        public K pollLast() {
-            Map.Entry<K, K> entry = subMap.pollLastEntry();
-            return (null == entry) ? null : entry.getKey();
+        public K higher(K e) {
+            K ret = map.m.higherKey(e);
+            if (ret != null && map.isInRange(ret)){
+                return ret;
+            } else {
+                return null;
+            }
         }
 
-        public K higher(K key) {
-            return subMap.higherKey(key);
+        public K lower(K e) {
+            K ret =map.m.lowerKey(e);
+            if (ret != null && map.isInRange(ret)){
+                return ret;
+            } else {
+                return null;
+            }
+        }
+        
+        public K pollFirst() {
+            Map.Entry<K, V> ret = map.firstEntry();
+            if (ret == null){
+                return null;
+            }
+            map.m.remove(ret.getKey());
+            return ret.getKey();
         }
 
-        public K lower(K key) {
-            return subMap.lowerKey(key);
+        public K pollLast() {
+            Map.Entry<K, V> ret = map.lastEntry();
+            if (ret == null){
+                return null;
+            }
+            map.m.remove(ret.getKey());
+            return ret.getKey();
         }
 
-        public K ceiling(K key) {
-            return subMap.ceilingKey(key);
+        public NavigableSet<K> subSet(K start, boolean startInclusive, K end, boolean endInclusive) {
+            if (map.fromStart
+                    && ((!map.loInclusive && startInclusive) ? map.m.keyCompare(start,
+                            map.lo) <= 0 : map.m.keyCompare(start, map.lo) < 0)
+                    || (map.toEnd && ((!map.hiInclusive && (endInclusive || (startInclusive && start.equals(end)))) ? map.m.keyCompare(
+                            end, map.hi) >= 0
+                            : map.m.keyCompare(end, map.hi) > 0))) {
+                throw new IllegalArgumentException();
+            }
+            if (map.m.keyCompare(start, end) > 0){
+                throw new IllegalArgumentException();
+            }
+            return new AscendingSubMapKeySet<K,V>(new AscendingSubMap<K, V>(start,
+                    startInclusive, map.m, end, endInclusive));
         }
 
-        public K floor(K key) {
-            return subMap.floorKey(key);
+        public NavigableSet<K> tailSet(K start, boolean startInclusive) {
+            boolean isInRange = true;
+            int result;
+            if (map.toEnd) {
+                result = (null != comparator()) ? comparator().compare(start,
+                        map.hi) : toComparable(start).compareTo(map.hi);
+                isInRange = (map.hiInclusive || !startInclusive) ? result <= 0
+                        : result < 0;
+            }
+            if (map.fromStart) {
+                result = (null != comparator()) ? comparator().compare(start,
+                        map.lo) : toComparable(start).compareTo(map.lo);
+                isInRange = isInRange
+                        && ((map.loInclusive || !startInclusive) ? result >= 0
+                                : result > 0);
+            }
+
+            if (isInRange) {
+                if (map.toEnd) {
+                    return new AscendingSubMapKeySet<K, V>(
+                            new AscendingSubMap<K, V>(start, startInclusive,
+                                    map.m, map.hi, map.hiInclusive));
+                } else {
+                    return new AscendingSubMapKeySet<K, V>(
+                            new AscendingSubMap<K, V>(start, startInclusive,
+                                    map.m));
+                }
+            }
+            throw new IllegalArgumentException();
         }
 
-        public NavigableSet<K> descendingSet() {
-            return (null != descendingSet) ? descendingSet
-                    : (descendingSet = new TreeSet<K>(subMap.descendingMap()));
+        public Comparator<? super K> comparator() {
+            return map.m.comparator;
         }
 
-        public SortedSet<K> subSet(K start, K end) {
-            return subSet(start, true, end, false);
+        public K first() {
+            return map.firstKey();
         }
 
         public SortedSet<K> headSet(K end) {
             return headSet(end, false);
         }
 
+        public K last() {
+            return map.lastKey();
+        }
+
+        public SortedSet<K> subSet(K start, K end) {
+            return subSet(start,true, end,false);
+        }
+
         public SortedSet<K> tailSet(K start) {
-            return tailSet(start, true);
+            return tailSet(start,true);
+        }
+        
+        @Override
+        public boolean contains(Object object) {
+            return map.containsKey(object);
+        }
+        
+        @Override
+        public boolean remove(Object object) {
+            return this.map.remove(object) != null;
         }
+    }
 
-        @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));
+    static class DescendingSubMapKeySet<K,V> extends AbstractSet<K> implements NavigableSet<K>  {
+        NavigableSubMap<K, V> map;
+        
+        DescendingSubMapKeySet(NavigableSubMap<K, V> map) {
+            this.map = map;
+        }
+
+        @Override
+        public final Iterator<K> iterator() {
+            return new DescendingSubMapKeyIterator<K, V>(map);
+        }
+
+        public final Iterator<K> descendingIterator() {
+            if (map.fromStart && map.toEnd) {
+                return new AscendingSubMapKeyIterator<K, V>(
+                        new AscendingSubMap<K, V>(map.hi, map.hiInclusive,
+                                map.m, map.lo, map.loInclusive));
+            }
+            if (map.toEnd) {
+                return new AscendingSubMapKeyIterator<K, V>(
+                        new AscendingSubMap<K, V>(map.hi, map.hiInclusive,
+                                map.m));
+            }
+            if (map.fromStart) {
+                return new AscendingSubMapKeyIterator<K, V>(
+                        new AscendingSubMap<K, V>(map.m, map.lo,
+                                map.loInclusive));
             }
-            throw new IllegalArgumentException();
+            return new AscendingSubMapKeyIterator<K, V>(
+                    new AscendingSubMap<K, V>(map.m));
+        }
+
+        @Override
+        public int size() {
+            int size = 0;
+            Iterator it = new DescendingSubMapEntryIterator<K, V>(map);
+            while (it.hasNext()){
+                it.next();
+                size ++;
+            }
+            return size;
+        }
+
+        public NavigableSet<K> descendingSet() {
+            if (map.fromStart && map.toEnd) {
+                return new AscendingSubMapKeySet<K, V>(
+                        new AscendingSubMap<K, V>(map.hi, map.hiInclusive,
+                                map.m, map.lo, map.loInclusive));
+            }
+            if (map.toEnd) {
+                return new AscendingSubMapKeySet<K, V>(
+                        new AscendingSubMap<K, V>(map.hi, map.hiInclusive,
+                                map.m));
+            }
+            if (map.fromStart) {
+                return new AscendingSubMapKeySet<K, V>(
+                        new AscendingSubMap<K, V>(map.m, map.lo,
+                                map.loInclusive));
+            }
+            return new AscendingSubMapKeySet<K, V>(
+                    new AscendingSubMap<K, V>(map.m));
+        }
+
+        public K ceiling(K e) {
+            Comparable<K> object = map.comparator() == null ? toComparable((K) e)
+                    : null;
+            Entry<K,V> node =  map.m.findFloorEntry(e);
+            if (node!= null && !map.checkUpperBound(node.key)){
+                return null;
+            }
+            
+            if (node!= null && !map.checkLowerBound(node.key)){
+                Entry<K,V> first = map.loInclusive?map.m.findFloorEntry(map.lo):map.m.findLowerEntry(map.lo);
+                if (first!= null  && map.cmp(object, e, first.key) <= 0 && map.checkUpperBound(first.key)){
+                    node = first;
+                } else {
+                    node = null;
+                }
+            }
+            return node ==null ? null : node.key;
+        }
+
+        public K floor(K e) {
+            Entry<K,V> node =  map.m.findCeilingEntry(e);
+            if (node!= null && !map.checkUpperBound(node.key)){
+                node = map.hiInclusive?map.m.findCeilingEntry(map.hi):map.m.findHigherEntry(map.hi);
+            }
+            
+            if (node!= null && !map.checkLowerBound(node.key)){
+                Comparable<K> object = map.comparator() == null ? toComparable((K) e)
+                        : null;
+                Entry<K,V> first = map.loInclusive?map.m.findFloorEntry(map.lo):map.m.findLowerEntry(map.lo);
+                if (first != null && map.cmp(object, e, first.key) > 0 && map.checkUpperBound(first.key)){
+                    node = first;
+                } else {
+                    node = null;
+                }
+            }
+            return node ==null ? null :  node.key;
         }
 
-        @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));
+            checkInRange(end,endInclusive);
+            if (map.fromStart) {
+                return new DescendingSubMapKeySet<K, V>(
+                        new DescendingSubMap<K, V>(map.lo, map.loInclusive,
+                                map.m, end, endInclusive));
+            } else {
+                return new DescendingSubMapKeySet<K, V>(
+                        new DescendingSubMap<K, V>(map.m, end, endInclusive));
+            }
+        }
+        
+        public K higher(K e) {
+            Comparable<K> object = map.comparator() == null ? toComparable((K) e)
+                    : null;
+            Entry<K,V> node =  map.m.findLowerEntry(e);
+            if (node != null && !map.checkUpperBound(node.key)){
+                    return null;
+            }
+            
+            if (node != null && !map.checkLowerBound(node.key)){
+                Entry<K,V> first = map.loInclusive?map.m.findFloorEntry(map.lo):map.m.findLowerEntry(map.lo);
+                if (first!= null && map.cmp(object, e, first.key) < 0 && map.checkUpperBound(first.key)){
+                    node = first;
+                } else {
+                    node = null;
+                }
+            }

[... 3759 lines stripped ...]


Mime
View raw message