1/*
2 *  Licensed to the Apache Software Foundation (ASF) under one or more
3 *  contributor license agreements.  See the NOTICE file distributed with
4 *  this work for additional information regarding copyright ownership.
5 *  The ASF licenses this file to You under the Apache License, Version 2.0
6 *  (the "License"); you may not use this file except in compliance with
7 *  the License.  You may obtain a copy of the License at
8 *
9 *     http://www.apache.org/licenses/LICENSE-2.0
10 *
11 *  Unless required by applicable law or agreed to in writing, software
12 *  distributed under the License is distributed on an "AS IS" BASIS,
13 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 *  See the License for the specific language governing permissions and
15 *  limitations under the License.
16 */
17
18package java.util;
19
20import java.io.IOException;
21import java.io.ObjectInputStream;
22import java.io.ObjectOutputStream;
23import java.io.Serializable;
24
25/**
26 * TreeMap is an implementation of SortedMap. All optional operations (adding
27 * and removing) are supported. The values can be any objects. The keys can be
28 * any objects which are comparable to each other either using their natural
29 * order or a specified Comparator.
30 *
31 * @since 1.2
32 */
33public class TreeMap <K, V> extends AbstractMap<K, V> implements SortedMap<K, V>,
34                                                        Cloneable, Serializable {
35    private static final long serialVersionUID = 919286545866124006L;
36
37    transient int size;
38
39    private Comparator<? super K> comparator;
40
41    transient int modCount;
42
43    transient Set<Map.Entry<K, V>> entrySet;
44
45    transient Node<K, V> root;
46
47class MapEntry implements Map.Entry<K, V>, Cloneable {
48
49		final int offset;
50		final Node<K, V> node;
51		final K key;
52
53	    MapEntry(Node<K, V> node, int offset) {
54	    	this.node = node;
55	    	this.offset = offset;
56	    	key = node.keys[offset];
57	    }
58
59	    @Override
60	    public Object clone() {
61	        try {
62	            return super.clone();
63	        } catch (CloneNotSupportedException e) {
64                throw new AssertionError(e); // android-changed
65	        }
66	    }
67
68	    @Override
69	    public boolean equals(Object object) {
70	        if (this == object) {
71	            return true;
72	        }
73	        if (object instanceof Map.Entry) {
74	            Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object;
75	            V value = getValue();
76	            return (key == null ? entry.getKey() == null : key.equals(entry
77	                    .getKey()))
78	                    && (value == null ? entry.getValue() == null : value
79	                            .equals(entry.getValue()));
80	        }
81	        return false;
82	    }
83
84	    public K getKey() {
85	        return key;
86	    }
87
88	    public V getValue() {
89	    	if (node.keys[offset] == key) {
90	    		return node.values[offset];
91	    	}
92	    	if (containsKey(key)) {
93	    		return get(key);
94	    	}
95	    	throw new IllegalStateException();
96	    }
97
98	    @Override
99	    public int hashCode() {
100	    	V value = getValue();
101	        return (key == null ? 0 : key.hashCode())
102	                ^ (value == null ? 0 : value.hashCode());
103	    }
104
105	    public V setValue(V object) {
106	    	if (node.keys[offset] == key) {
107	    		V res = node.values[offset];
108	    		node.values[offset] = object;
109	    		return res;
110	    	}
111	    	if (containsKey(key)) {
112	    		return put(key, object);
113	    	}
114	    	throw new IllegalStateException();
115	    }
116
117	    @Override
118	    public String toString() {
119	        return key + "=" + getValue();
120	    }
121	}
122
123    static class Node <K,V> implements Cloneable {
124        static final int NODE_SIZE = 64;
125        Node<K, V> prev, next;
126        Node<K, V> parent, left, right;
127        V[] values;
128        K[] keys;
129        int left_idx = 0;
130        int right_idx = -1;
131        int size = 0;
132        boolean color;
133
134        public Node() {
135            keys = (K[]) new Object[NODE_SIZE];
136            values = (V[]) new Object[NODE_SIZE];
137        }
138
139        @SuppressWarnings("unchecked")
140        Node<K, V> clone(Node<K, V> parent) throws CloneNotSupportedException {
141            Node<K, V> clone = (Node<K, V>) super.clone();
142            clone.keys   = (K[]) new Object[NODE_SIZE];
143            clone.values = (V[]) new Object[NODE_SIZE];
144            System.arraycopy(keys,   0, clone.keys,   0, keys.length);
145            System.arraycopy(values, 0, clone.values, 0, values.length);
146            clone.left_idx  = left_idx;
147            clone.right_idx = right_idx;
148            clone.parent = parent;
149            if (left != null) {
150                clone.left = left.clone(clone);
151            }
152            if (right != null) {
153                clone.right = right.clone(clone);
154            }
155            clone.prev = null;
156            clone.next = null;
157            return clone;
158        }
159    }
160
161    @SuppressWarnings("unchecked")
162     private static <T> Comparable<T> toComparable(T obj) {
163        if (obj == null) {
164            throw new NullPointerException();
165        }
166        return (Comparable) obj;
167    }
168
169    static class AbstractMapIterator <K,V> {
170        TreeMap<K, V> backingMap;
171        int expectedModCount;
172        Node<K, V> node;
173        Node<K, V> lastNode;
174        int offset;
175        int lastOffset;
176
177        AbstractMapIterator(TreeMap<K, V> map, Node<K, V> startNode, int startOffset) {
178            backingMap = map;
179            expectedModCount = map.modCount;
180            node = startNode;
181            offset = startOffset;
182        }
183
184        AbstractMapIterator(TreeMap<K, V> map, Node<K, V> startNode) {
185            this(map, startNode, startNode != null ?
186                                 startNode.right_idx - startNode.left_idx : 0);
187        }
188
189        AbstractMapIterator(TreeMap<K, V> map) {
190            this(map, minimum(map.root));
191        }
192
193        public boolean hasNext() {
194            return node != null;
195        }
196
197        final void makeNext() {
198            if (expectedModCount != backingMap.modCount) {
199                throw new ConcurrentModificationException();
200            } else if (node == null) {
201                throw new NoSuchElementException();
202            }
203            lastNode = node;
204            lastOffset = offset;
205            if (offset != 0) {
206                offset--;
207            } else {
208                node = node.next;
209                if (node != null) {
210                    offset = node.right_idx - node.left_idx;
211                }
212            }
213        }
214
215        final public void remove() {
216            if (expectedModCount == backingMap.modCount) {
217                if (lastNode != null) {
218                    int idx = lastNode.right_idx - lastOffset;
219                    backingMap.removeFromIterator(lastNode, idx);
220                    lastNode = null;
221                    expectedModCount++;
222                } else {
223                    throw new IllegalStateException();
224                }
225            } else {
226                throw new ConcurrentModificationException();
227            }
228        }
229    }
230
231    static class UnboundedEntryIterator <K, V> extends AbstractMapIterator<K, V>
232                                            implements Iterator<Map.Entry<K, V>> {
233
234        UnboundedEntryIterator(TreeMap<K, V> map, Node<K, V> startNode, int startOffset) {
235            super(map, startNode, startOffset);
236        }
237
238        UnboundedEntryIterator(TreeMap<K, V> map) {
239            super(map);
240        }
241
242        public Map.Entry<K, V> next() {
243            makeNext();
244            int idx = lastNode.right_idx - lastOffset;
245            return backingMap.new MapEntry(lastNode, idx);
246        }
247    }
248
249    static class UnboundedKeyIterator <K, V> extends AbstractMapIterator<K, V>
250                                                          implements Iterator<K> {
251
252        UnboundedKeyIterator(TreeMap<K, V> map, Node<K, V> startNode, int startOffset) {
253            super(map, startNode, startOffset);
254        }
255
256        UnboundedKeyIterator(TreeMap<K, V> map) {
257            super(map);
258        }
259
260        public K next() {
261            makeNext();
262            return lastNode.keys[lastNode.right_idx - lastOffset];
263        }
264    }
265
266    static class UnboundedValueIterator <K, V> extends AbstractMapIterator<K, V>
267                                                          implements Iterator<V> {
268
269        UnboundedValueIterator(TreeMap<K, V> map, Node<K, V> startNode, int startOffset) {
270            super(map, startNode, startOffset);
271        }
272
273        UnboundedValueIterator(TreeMap<K, V> map) {
274            super(map);
275        }
276
277        public V next() {
278            makeNext();
279            return lastNode.values[lastNode.right_idx - lastOffset];
280        }
281    }
282
283    static class BoundedMapIterator <K, V> extends AbstractMapIterator<K, V> {
284
285        Node<K, V> finalNode;
286        int finalOffset;
287
288        BoundedMapIterator(Node<K, V> startNode, int startOffset, TreeMap<K, V> map,
289                           Node<K, V> finalNode, int finalOffset) {
290            super(map, finalNode==null? null : startNode, startOffset);
291            this.finalNode = finalNode;
292            this.finalOffset = finalOffset;
293        }
294
295        BoundedMapIterator(Node<K, V> startNode, TreeMap<K, V> map,
296                           Node<K, V> finalNode, int finalOffset) {
297            this(startNode, startNode != null ?
298                            startNode.right_idx - startNode.left_idx : 0,
299                            map, finalNode, finalOffset);
300        }
301
302        BoundedMapIterator(Node<K, V> startNode, int startOffset,
303                           TreeMap<K, V> map, Node<K, V> finalNode) {
304            this(startNode, startOffset, map, finalNode,
305                         finalNode.right_idx - finalNode.left_idx);
306        }
307
308        void makeBoundedNext() {
309            makeNext();
310            if (lastNode == finalNode && lastOffset == finalOffset) {
311                node = null;
312            }
313        }
314    }
315
316    static class BoundedEntryIterator <K, V> extends BoundedMapIterator<K, V>
317                                          implements Iterator<Map.Entry<K, V>> {
318
319        public BoundedEntryIterator(Node<K, V> startNode, int startOffset, TreeMap<K, V> map,
320                                    Node<K, V> finalNode, int finalOffset) {
321            super(startNode, startOffset, map, finalNode, finalOffset);
322        }
323
324        public Map.Entry<K, V> next() {
325            makeBoundedNext();
326            int idx = lastNode.right_idx - lastOffset;
327            return backingMap.new MapEntry(lastNode, idx);
328        }
329    }
330
331    static class BoundedKeyIterator <K, V> extends BoundedMapIterator<K, V>
332                                                     implements Iterator<K> {
333
334        public BoundedKeyIterator(Node<K, V> startNode, int startOffset, TreeMap<K, V> map,
335                                  Node<K, V> finalNode, int finalOffset) {
336            super(startNode, startOffset, map, finalNode, finalOffset);
337        }
338
339        public K next() {
340            makeBoundedNext();
341            return lastNode.keys[lastNode.right_idx - lastOffset];
342        }
343    }
344
345    static class BoundedValueIterator <K, V> extends BoundedMapIterator<K, V>
346                                                       implements Iterator<V> {
347
348        public BoundedValueIterator(Node<K, V> startNode, int startOffset, TreeMap<K, V> map,
349                                    Node<K, V> finalNode, int finalOffset) {
350            super(startNode, startOffset, map, finalNode, finalOffset);
351        }
352
353        public V next() {
354            makeBoundedNext();
355            return lastNode.values[lastNode.right_idx - lastOffset];
356        }
357    }
358
359    static final class SubMap <K,V> extends AbstractMap<K, V>
360                                 implements SortedMap<K, V>, Serializable {
361        private static final long serialVersionUID = -6520786458950516097L;
362
363        private TreeMap<K, V> backingMap;
364
365        boolean hasStart, hasEnd;
366        K startKey, endKey;
367        transient Set<Map.Entry<K, V>> entrySet = null;
368        transient int firstKeyModCount = -1;
369        transient int lastKeyModCount = -1;
370        transient Node<K, V> firstKeyNode;
371        transient int firstKeyIndex;
372        transient Node<K, V> lastKeyNode;
373        transient int lastKeyIndex;
374
375        SubMap(K start, TreeMap<K, V> map) {
376            backingMap = map;
377            hasStart = true;
378            startKey = start;
379        }
380
381        SubMap(K start, TreeMap<K, V> map, K end) {
382            backingMap = map;
383            hasStart = hasEnd = true;
384            startKey = start;
385            endKey = end;
386        }
387
388        SubMap(TreeMap<K, V> map, K end) {
389            backingMap = map;
390            hasEnd = true;
391            endKey = end;
392        }
393
394        private void checkRange(K key) {
395            Comparator<? super K> cmp = backingMap.comparator;
396            if (cmp == null) {
397                Comparable<K> object = toComparable(key);
398                if (hasStart && object.compareTo(startKey) < 0) {
399                    throw new IllegalArgumentException();
400                }
401                if (hasEnd && object.compareTo(endKey) > 0) {
402                    throw new IllegalArgumentException();
403                }
404            } else {
405                if (hasStart
406                    && backingMap.comparator().compare(key, startKey) < 0) {
407                    throw new IllegalArgumentException();
408                }
409                if (hasEnd && backingMap.comparator().compare(key, endKey) > 0) {
410                    throw new IllegalArgumentException();
411                }
412            }
413        }
414
415        private boolean isInRange(K key) {
416            Comparator<? super K> cmp = backingMap.comparator;
417            if (cmp == null) {
418                Comparable<K> object = toComparable(key);
419                if (hasStart && object.compareTo(startKey) < 0) {
420                    return false;
421                }
422                if (hasEnd && object.compareTo(endKey) >= 0) {
423                    return false;
424                }
425            } else {
426                if (hasStart && cmp.compare(key, startKey) < 0) {
427                    return false;
428                }
429                if (hasEnd && cmp.compare(key, endKey) >= 0) {
430                    return false;
431                }
432            }
433            return true;
434        }
435
436        private boolean checkUpperBound(K key) {
437            if (hasEnd) {
438                Comparator<? super K> cmp = backingMap.comparator;
439                if (cmp == null) {
440                    return (toComparable(key).compareTo(endKey) < 0);
441                }
442                return (cmp.compare(key, endKey) < 0);
443            }
444            return true;
445        }
446
447        private boolean checkLowerBound(K key) {
448            if (hasStart) {
449                Comparator<? super K> cmp = backingMap.comparator;
450                if (cmp == null) {
451                    return (toComparable(key).compareTo(startKey) >= 0);
452                }
453                return (cmp.compare(key, startKey) >= 0);
454            }
455            return true;
456        }
457
458        public Comparator<? super K> comparator() {
459            return backingMap.comparator();
460        }
461
462        @SuppressWarnings("unchecked")
463        @Override
464        public boolean containsKey(Object key) {
465            if (isInRange((K) key)) {
466                return backingMap.containsKey(key);
467            }
468            return false;
469        }
470
471        @Override
472         public void clear() {
473            keySet().clear();
474        }
475
476        @Override
477         public boolean containsValue(Object value) {
478            Iterator<V> it = values().iterator();
479            if (value != null) {
480                while (it.hasNext()) {
481                    if (value.equals(it.next())) {
482                        return true;
483                    }
484                }
485            } else {
486                while (it.hasNext()) {
487                    if (it.next() == null) {
488                        return true;
489                    }
490                }
491            }
492            return false;
493        }
494
495        @Override
496        public Set<Map.Entry<K, V>> entrySet() {
497            if (entrySet == null) {
498                entrySet = new SubMapEntrySet<K, V>(this);
499            }
500            return entrySet;
501        }
502
503        private void setFirstKey() {
504            if (firstKeyModCount == backingMap.modCount) {
505                return;
506            }
507            Comparable<K> object = backingMap.comparator == null ?
508                                   toComparable((K) startKey) : null;
509            K key = (K) startKey;
510            Node<K, V> node = backingMap.root;
511            Node<K, V> foundNode = null;
512            int foundIndex = -1;
513            TOP_LOOP:
514            while (node != null) {
515                K[] keys = node.keys;
516                int left_idx = node.left_idx;
517                int result = backingMap.cmp(object, key, keys[left_idx]);
518                if (result < 0) {
519                    foundNode = node;
520                    foundIndex = left_idx;
521                    node = node.left;
522                } else if (result == 0) {
523                    foundNode = node;
524                    foundIndex = left_idx;
525                    break;
526                } else {
527                    int right_idx = node.right_idx;
528                    if (left_idx != right_idx) {
529                        result = backingMap.cmp(object, key, keys[right_idx]);
530                    }
531                    if (result > 0) {
532                        node = node.right;
533                    } else if (result == 0) {
534                        foundNode = node;
535                        foundIndex = right_idx;
536                        break;
537                    } else { /*search in node*/
538                        foundNode = node;
539                        foundIndex = right_idx;
540                        int low = left_idx + 1, mid = 0, high = right_idx - 1;
541                        while (low <= high) {
542                            mid = (low + high) >>> 1;
543                            result = backingMap.cmp(object, key, keys[mid]);
544                            if (result > 0) {
545                                low = mid + 1;
546                            } else if (result == 0) {
547                                foundNode = node;
548                                foundIndex = mid;
549                                break TOP_LOOP;
550                            } else {
551                                foundNode = node;
552                                foundIndex = mid;
553                                high = mid - 1;
554                            }
555                        }
556                        break TOP_LOOP;
557                    }
558                }
559            }
560            if (foundNode != null && !checkUpperBound(foundNode.keys[foundIndex])) {
561                foundNode = null;
562            }
563            firstKeyNode = foundNode;
564            firstKeyIndex = foundIndex;
565            firstKeyModCount = backingMap.modCount;
566        }
567
568        public K firstKey() {
569            if (backingMap.size > 0) {
570                if (!hasStart) {
571                    Node<K, V> node = minimum(backingMap.root);
572                    if (node != null && checkUpperBound(node.keys[node.left_idx])) {
573                        return node.keys[node.left_idx];
574                    }
575                } else {
576                    setFirstKey();
577                    if (firstKeyNode != null) {
578                        return firstKeyNode.keys[firstKeyIndex];
579                    }
580                }
581            }
582            throw new NoSuchElementException();
583        }
584
585
586        @SuppressWarnings("unchecked")
587        @Override
588        public V get(Object key) {
589            if (isInRange((K) key)) {
590                return backingMap.get(key);
591            }
592            return null;
593        }
594
595        public SortedMap<K, V> headMap(K endKey) {
596            checkRange(endKey);
597            if (hasStart) {
598                return new SubMap<K, V>(startKey, backingMap, endKey);
599            }
600            return new SubMap<K, V>(backingMap, endKey);
601        }
602
603        @Override
604        public boolean isEmpty() {
605            if (hasStart) {
606                setFirstKey();
607                return firstKeyNode == null;
608            } else {
609                setLastKey();
610                return lastKeyNode == null;
611            }
612        }
613
614        @Override
615        public Set<K> keySet() {
616            if (keySet == null) {
617                keySet = new SubMapKeySet<K, V>(this);
618            }
619            return keySet;
620        }
621
622        private void setLastKey() {
623            if (lastKeyModCount == backingMap.modCount) {
624                return;
625            }
626            Comparable<K> object = backingMap.comparator == null ?
627                                   toComparable((K) endKey) : null;
628            K key = (K) endKey;
629            Node<K, V> node = backingMap.root;
630            Node<K, V> foundNode = null;
631            int foundIndex = -1;
632            TOP_LOOP:
633            while (node != null) {
634                K[] keys = node.keys;
635                int left_idx = node.left_idx;
636                int result = backingMap.cmp(object, key, keys[left_idx]);
637                if (result <= 0) {
638                    node = node.left;
639                } else {
640                    int right_idx = node.right_idx;
641                    if (left_idx != right_idx) {
642                        result = backingMap.cmp(object, key, keys[right_idx]);
643                    }
644                    if (result > 0) {
645                        foundNode = node;
646                        foundIndex = right_idx;
647                        node = node.right;
648                    } else if (result == 0) {
649                        if (node.left_idx == node.right_idx) {
650                            foundNode = node.prev;
651                            if (foundNode != null) {
652                                foundIndex = foundNode.right_idx - 1;
653                            }
654                        } else {
655                            foundNode = node;
656                            foundIndex = right_idx - 1;
657                        }
658                        break;
659                    } else { /*search in node*/
660                        foundNode = node;
661                        foundIndex = left_idx;
662                        int low = left_idx + 1, mid = 0, high = right_idx - 1;
663                        while (low <= high) {
664                            mid = (low + high) >>> 1;
665                            result = backingMap.cmp(object, key, keys[mid]);
666                            if (result > 0) {
667                                foundNode = node;
668                                foundIndex = mid;
669                                low = mid + 1;
670                            } else if (result == 0) {
671                                foundNode = node;
672                                foundIndex = mid - 1;
673                                break TOP_LOOP;
674                            } else {
675                                high = mid - 1;
676                            }
677                        }
678                        break TOP_LOOP;
679                    }
680                }
681            }
682            if (foundNode != null && !checkLowerBound(foundNode.keys[foundIndex])) {
683                foundNode = null;
684            }
685            lastKeyNode = foundNode;
686            lastKeyIndex = foundIndex;
687            lastKeyModCount = backingMap.modCount;
688        }
689
690        public K lastKey() {
691            if (backingMap.size > 0) {
692                if (!hasEnd) {
693                    Node<K, V> node = maximum(backingMap.root);
694                    if (node != null && checkLowerBound(node.keys[node.right_idx])) {
695                        return node.keys[node.right_idx];
696                    }
697                } else {
698                    setLastKey();
699                    if (lastKeyNode != null) {
700                        return lastKeyNode.keys[lastKeyIndex];
701                    }
702                }
703            }
704            throw new NoSuchElementException();
705        }
706
707
708        @Override
709        public V put(K key, V value) {
710            if (isInRange(key)) {
711                return backingMap.put(key, value);
712            }
713            throw new IllegalArgumentException();
714        }
715
716        @SuppressWarnings("unchecked")
717        @Override
718        public V remove(Object key) {
719            if (isInRange((K) key)) {
720                return backingMap.remove(key);
721            }
722            return null;
723        }
724
725        public SortedMap<K, V> subMap(K startKey, K endKey) {
726            checkRange(startKey);
727            checkRange(endKey);
728            Comparator<? super K> c = backingMap.comparator();
729            if (c == null) {
730                if (toComparable(startKey).compareTo(endKey) <= 0) {
731                    return new SubMap<K, V>(startKey, backingMap, endKey);
732                }
733            } else {
734                if (c.compare(startKey, endKey) <= 0) {
735                    return new SubMap<K, V>(startKey, backingMap, endKey);
736                }
737            }
738            throw new IllegalArgumentException();
739        }
740
741        public SortedMap<K, V> tailMap(K startKey) {
742            checkRange(startKey);
743            if (hasEnd) {
744                return new SubMap<K, V>(startKey, backingMap, endKey);
745            }
746            return new SubMap<K, V>(startKey, backingMap);
747        }
748
749        @Override
750        public Collection<V> values() {
751            if (valuesCollection == null) {
752                valuesCollection = new SubMapValuesCollection<K, V>(this);
753            }
754            return valuesCollection;
755        }
756
757        public int size() {
758            Node<K, V> from, to;
759            int fromIndex, toIndex;
760            if (hasStart) {
761                setFirstKey();
762                from = firstKeyNode;
763                fromIndex = firstKeyIndex;
764            } else {
765                from = minimum(backingMap.root);
766                fromIndex = from == null ? 0 : from.left_idx;
767            }
768            if (from == null) {
769                return 0;
770            }
771            if (hasEnd) {
772                setLastKey();
773                to = lastKeyNode;
774                toIndex = lastKeyIndex;
775            } else {
776                to = maximum(backingMap.root);
777                toIndex = to == null ? 0 : to.right_idx;
778            }
779            if (to == null) {
780                return 0;
781            }
782            if (from == to) {
783                return toIndex - fromIndex + 1;
784            }
785            int sum = 0;
786            while (from != to) {
787                sum += (from.right_idx - fromIndex + 1);
788                from = from.next;
789                fromIndex = from.left_idx;
790            }
791            return sum + toIndex - fromIndex + 1;
792        }
793
794        private void readObject(ObjectInputStream stream) throws IOException,
795                                                                 ClassNotFoundException {
796            stream.defaultReadObject();
797            firstKeyModCount = -1;
798            lastKeyModCount = -1;
799        }
800    }
801
802    static class SubMapEntrySet <K,V> extends AbstractSet<Map.Entry<K, V>>
803                                                implements Set<Map.Entry<K, V>> {
804        SubMap<K, V> subMap;
805
806        SubMapEntrySet(SubMap<K, V> map) {
807            subMap = map;
808        }
809
810        @Override
811        public boolean isEmpty() {
812            return subMap.isEmpty();
813        }
814
815        public Iterator<Map.Entry<K, V>> iterator() {
816            Node<K, V> from;
817            int fromIndex;
818            if (subMap.hasStart) {
819                subMap.setFirstKey();
820                from = subMap.firstKeyNode;
821                fromIndex = subMap.firstKeyIndex;
822            } else {
823                from = minimum(subMap.backingMap.root);
824                fromIndex = from != null ? from.left_idx : 0;
825            }
826            if (!subMap.hasEnd) {
827                return new UnboundedEntryIterator<K, V>(subMap.backingMap, from, from == null ? 0 : from.right_idx - fromIndex);
828            }
829            subMap.setLastKey();
830            Node<K, V> to = subMap.lastKeyNode;
831            int toIndex = subMap.lastKeyIndex;
832            return new BoundedEntryIterator<K, V>(from, from == null ? 0 : from.right_idx - fromIndex, subMap.backingMap, to, to == null ? 0 : to.right_idx - toIndex);
833        }
834
835        @Override
836        public int size() {
837            return subMap.size();
838        }
839
840        @SuppressWarnings("unchecked")
841        @Override
842        public boolean contains(Object object) {
843            if (object instanceof Map.Entry) {
844                Map.Entry<K, V> entry = (Map.Entry<K, V>) object;
845                K key = entry.getKey();
846                if (subMap.isInRange(key)) {
847                    V v1 = subMap.get(key), v2 = entry.getValue();
848                    return v1 == null ? ( v2 == null && subMap.containsKey(key) ) : v1.equals(v2);
849                }
850            }
851            return false;
852        }
853
854        @Override
855        public boolean remove(Object object) {
856            if (contains(object)) {
857                Map.Entry<K, V> entry = (Map.Entry<K, V>) object;
858                K key = entry.getKey();
859                subMap.remove(key);
860                return true;
861            }
862            return false;
863        }
864    }
865
866    static class SubMapKeySet <K,V> extends AbstractSet<K> implements Set<K> {
867        SubMap<K, V> subMap;
868
869        SubMapKeySet(SubMap<K, V> map) {
870            subMap = map;
871        }
872
873        @Override
874        public boolean contains(Object object) {
875            return subMap.containsKey(object);
876        }
877
878        @Override
879        public boolean isEmpty() {
880            return subMap.isEmpty();
881        }
882
883        @Override
884        public int size() {
885            return subMap.size();
886        }
887
888        @Override
889        public boolean remove(Object object) {
890            if (subMap.containsKey(object)) {
891                subMap.remove(object);
892                return true;
893            }
894            return false;
895        }
896
897        public Iterator<K> iterator() {
898            Node<K, V> from;
899            int fromIndex;
900            if (subMap.hasStart) {
901                subMap.setFirstKey();
902                from = subMap.firstKeyNode;
903                fromIndex = subMap.firstKeyIndex;
904            } else {
905                from = minimum(subMap.backingMap.root);
906                fromIndex = from != null ? from.left_idx : 0;
907            }
908            if (!subMap.hasEnd) {
909                return new UnboundedKeyIterator<K, V>(subMap.backingMap, from,
910                                   from == null ? 0 : from.right_idx - fromIndex);
911            }
912            subMap.setLastKey();
913            Node<K, V> to = subMap.lastKeyNode;
914            int toIndex = subMap.lastKeyIndex;
915            return new BoundedKeyIterator<K, V>(from,
916               from == null ? 0 : from.right_idx - fromIndex, subMap.backingMap, to,
917                 to == null ? 0 : to.right_idx   - toIndex);
918        }
919    }
920
921    static class SubMapValuesCollection <K,V> extends AbstractCollection<V> {
922        SubMap<K, V> subMap;
923
924        public SubMapValuesCollection(SubMap<K, V> subMap) {
925            this.subMap = subMap;
926        }
927
928        @Override
929        public boolean isEmpty() {
930            return subMap.isEmpty();
931        }
932
933        @Override
934        public Iterator<V> iterator() {
935            Node<K, V> from;
936            int fromIndex;
937            if (subMap.hasStart) {
938                subMap.setFirstKey();
939                from = subMap.firstKeyNode;
940                fromIndex = subMap.firstKeyIndex;
941            } else {
942                from = minimum(subMap.backingMap.root);
943                fromIndex = from != null ? from.left_idx : 0;
944            }
945            if (!subMap.hasEnd) {
946                return new UnboundedValueIterator<K, V>(subMap.backingMap, from,
947                                   from == null ? 0 : from.right_idx - fromIndex);
948            }
949            subMap.setLastKey();
950            Node<K, V> to = subMap.lastKeyNode;
951            int toIndex = subMap.lastKeyIndex;
952            return new BoundedValueIterator<K, V>(from,
953               from == null ? 0 : from.right_idx - fromIndex, subMap.backingMap, to,
954                 to == null ? 0 : to.right_idx - toIndex);
955        }
956
957        @Override
958        public int size() {
959            return subMap.size();
960        }
961    }
962
963    /**
964     * Constructs a new empty {@code TreeMap} instance.
965     */
966    public TreeMap() {
967    }
968
969    /**
970     * Constructs a new empty {@code TreeMap} instance with the specified
971     * comparator.
972     *
973     * @param comparator
974     *            the comparator to compare keys with.
975     */
976    public TreeMap(Comparator<? super K> comparator) {
977        this.comparator = comparator;
978    }
979
980    /**
981     * Constructs a new {@code TreeMap} instance containing the mappings from
982     * the specified map and using natural ordering.
983     *
984     * @param map
985     *            the mappings to add.
986     * @throws ClassCastException
987     *             if a key in the specified map does not implement the
988     *             Comparable interface, or if the keys in the map cannot be
989     *             compared.
990     */
991    public TreeMap(Map<? extends K, ? extends V> map) {
992        putAll(map);
993    }
994
995    /**
996     * Constructs a new {@code TreeMap} instance containing the mappings from
997     * the specified SortedMap and using the same comparator.
998     *
999     * @param map
1000     *            the mappings to add.
1001     */
1002    public TreeMap(SortedMap<K, ? extends V> map) {
1003        this(map.comparator());
1004        Node<K, V> lastNode = null;
1005        Iterator<? extends Map.Entry<K, ? extends V>> it = map.entrySet().iterator();
1006        while (it.hasNext()) {
1007            Map.Entry<K, ? extends V> entry = it.next();
1008            lastNode = addToLast(lastNode, entry.getKey(), entry.getValue());
1009        }
1010    }
1011
1012    Node<K, V> addToLast(Node<K, V> last, K key, V value) {
1013        if (last == null) {
1014            root = last = createNode(key, value);
1015            size = 1;
1016        } else if (last.size == Node.NODE_SIZE) {
1017            Node<K, V> newNode = createNode(key, value);
1018            attachToRight(last, newNode);
1019            balance(newNode);
1020            size++;
1021            last = newNode;
1022        } else {
1023            appendFromRight(last, key, value);
1024            size++;
1025        }
1026        return last;
1027    }
1028
1029    /**
1030     * Removes all mappings from this TreeMap, leaving it empty.
1031     *
1032     * @see Map#isEmpty()
1033     * @see #size()
1034     */
1035    @Override
1036    public void clear() {
1037        root = null;
1038        size = 0;
1039        modCount++;
1040    }
1041
1042    /**
1043     * Returns a new {@code TreeMap} with the same mappings, size and comparator
1044     * as this instance.
1045     *
1046     * @return a shallow copy of this instance.
1047     * @see java.lang.Cloneable
1048     */
1049    @SuppressWarnings("unchecked")
1050    @Override
1051    public Object clone() {
1052        try {
1053            TreeMap<K, V> clone = (TreeMap<K, V>) super.clone();
1054            clone.entrySet = null;
1055            if (root != null) {
1056                clone.root = root.clone(null);
1057                // restore prev/next chain
1058                Node<K, V> node = minimum(clone.root);
1059                while (true) {
1060                    Node<K, V> nxt = successor(node);
1061                    if (nxt == null) {
1062                        break;
1063                    }
1064                    nxt.prev = node;
1065                    node.next = nxt;
1066                    node = nxt;
1067                }
1068            }
1069            return clone;
1070        } catch (CloneNotSupportedException e) {
1071            throw new AssertionError(e); // android-changed
1072        }
1073    }
1074
1075    static private <K, V> Node<K, V> successor(Node<K, V> x) {
1076        if (x.right != null) {
1077            return minimum(x.right);
1078        }
1079        Node<K, V> y = x.parent;
1080        while (y != null && x == y.right) {
1081            x = y;
1082            y = y.parent;
1083        }
1084        return y;
1085    }
1086
1087    /**
1088     * Returns the comparator used to compare elements in this map.
1089     *
1090     * @return the comparator or {@code null} if the natural ordering is used.
1091     */
1092    public Comparator<? super K> comparator() {
1093        return comparator;
1094    }
1095
1096    /**
1097     * Returns whether this map contains the specified key.
1098     *
1099     * @param key
1100     *            the key to search for.
1101     * @return {@code true} if this map contains the specified key,
1102     *         {@code false} otherwise.
1103     * @throws ClassCastException
1104     *             if the specified key cannot be compared with the keys in this
1105     *             map.
1106     * @throws NullPointerException
1107     *             if the specified key is {@code null} and the comparator
1108     *             cannot handle {@code null} keys.
1109     */
1110    @Override
1111    public boolean containsKey(Object key) {
1112        Comparable<K> object = comparator == null ? toComparable((K) key) : null;
1113        K keyK = (K) key;
1114        Node<K, V> node = root;
1115        while (node != null) {
1116            K[] keys = node.keys;
1117            int left_idx = node.left_idx;
1118            int result = cmp(object, keyK, keys[left_idx]);
1119            if (result < 0) {
1120                node = node.left;
1121            } else if (result == 0) {
1122                return true;
1123            } else {
1124                int right_idx = node.right_idx;
1125                if (left_idx != right_idx) {
1126                    result = cmp(object, keyK, keys[right_idx]);
1127                }
1128                if (result > 0) {
1129                    node = node.right;
1130                } else if (result == 0) {
1131                    return true;
1132                } else { /*search in node*/
1133                    int low = left_idx + 1, mid = 0, high = right_idx - 1;
1134                    while (low <= high) {
1135                        mid = (low + high) >>> 1;
1136                        result = cmp(object, keyK, keys[mid]);
1137                        if (result > 0) {
1138                            low = mid + 1;
1139                        } else if (result == 0) {
1140                            return true;
1141                        } else {
1142                            high = mid - 1;
1143                        }
1144                    }
1145                    return false;
1146                }
1147            }
1148        }
1149        return false;
1150    }
1151
1152    /**
1153     * Returns whether this map contains the specified value.
1154     *
1155     * @param value
1156     *            the value to search for.
1157     * @return {@code true} if this map contains the specified value,
1158     *         {@code false} otherwise.
1159     */
1160    @Override
1161    public boolean containsValue(Object value) {
1162        if (root == null) {
1163            return false;
1164        }
1165        Node<K, V> node = minimum(root);
1166        if (value != null) {
1167            while (node != null) {
1168                int to = node.right_idx;
1169                V[] values = node.values;
1170                for (int i = node.left_idx; i <= to; i++) {
1171                    if (value.equals(values[i])) {
1172                        return true;
1173                    }
1174                }
1175                node = node.next;
1176            }
1177        } else {
1178            while (node != null) {
1179                int to = node.right_idx;
1180                V[] values = node.values;
1181                for (int i = node.left_idx; i <= to; i++) {
1182                    if (values[i] == null) {
1183                        return true;
1184                    }
1185                }
1186                node = node.next;
1187            }
1188        }
1189        return false;
1190    }
1191
1192    /**
1193     * Returns a set containing all of the mappings in this map. Each mapping is
1194     * an instance of {@link Map.Entry}. As the set is backed by this map,
1195     * changes in one will be reflected in the other. It does not support adding
1196     * operations.
1197     *
1198     * @return a set of the mappings.
1199     */
1200    @Override
1201    public Set<Map.Entry<K, V>> entrySet() {
1202        if (entrySet == null) {
1203            entrySet = new AbstractSet<Map.Entry<K, V>>() {
1204                @Override
1205                public int size() {
1206                    return size;
1207                }
1208
1209                @Override
1210                public void clear() {
1211                    TreeMap.this.clear();
1212                }
1213
1214                @SuppressWarnings("unchecked")
1215                @Override
1216                public boolean contains(Object object) {
1217                    if (object instanceof Map.Entry) {
1218                        Map.Entry<K, V> entry = (Map.Entry<K, V>) object;
1219                        K key = entry.getKey();
1220                        Object v1 = TreeMap.this.get(key), v2 = entry.getValue();
1221                        return v1 == null ? ( v2 == null && TreeMap.this.containsKey(key) ) : v1.equals(v2);
1222                    }
1223                    return false;
1224                }
1225
1226                @Override
1227                public boolean remove(Object object) {
1228                    if (contains(object)) {
1229                        Map.Entry<K, V> entry = (Map.Entry<K, V>) object;
1230                        K key = entry.getKey();
1231                        TreeMap.this.remove(key);
1232                        return true;
1233                    }
1234                    return false;
1235                }
1236
1237                @Override
1238                public Iterator<Map.Entry<K, V>> iterator() {
1239                    return new UnboundedEntryIterator<K, V>(TreeMap.this);
1240                }
1241            };
1242        }
1243        return entrySet;
1244    }
1245
1246    /**
1247     * Returns the first key in this map.
1248     *
1249     * @return the first key in this map.
1250     * @throws NoSuchElementException
1251     *                if this map is empty.
1252     */
1253    public K firstKey() {
1254        if (root != null) {
1255            Node<K, V> node = minimum(root);
1256            return node.keys[node.left_idx];
1257        }
1258        throw new NoSuchElementException();
1259    }
1260
1261
1262    /**
1263     * Returns the value of the mapping with the specified key.
1264     *
1265     * @param key
1266     *            the key.
1267     * @return the value of the mapping with the specified key.
1268     * @throws ClassCastException
1269     *             if the key cannot be compared with the keys in this map.
1270     * @throws NullPointerException
1271     *             if the key is {@code null} and the comparator cannot handle
1272     *             {@code null}.
1273     */
1274    @Override
1275    public V get(Object key) {
1276        Comparable<K> object = comparator == null ? toComparable((K) key) : null;
1277        K keyK = (K) key;
1278        Node<K, V> node = root;
1279        while (node != null) {
1280            K[] keys = node.keys;
1281            int left_idx = node.left_idx;
1282            int result = cmp(object, keyK, keys[left_idx]);
1283            if (result < 0) {
1284                node = node.left;
1285            } else if (result == 0) {
1286                return node.values[left_idx];
1287            } else {
1288                int right_idx = node.right_idx;
1289                if (left_idx != right_idx) {
1290                    result = cmp(object, keyK, keys[right_idx]);
1291                }
1292                if (result > 0) {
1293                    node = node.right;
1294                } else if (result == 0) {
1295                    return node.values[right_idx];
1296                } else { /*search in node*/
1297                    int low = left_idx + 1, mid = 0, high = right_idx - 1;
1298                    while (low <= high) {
1299                        mid = (low + high) >>> 1;
1300                        result = cmp(object, keyK, keys[mid]);
1301                        if (result > 0) {
1302                            low = mid + 1;
1303                        } else if (result == 0) {
1304                            return node.values[mid];
1305                        } else {
1306                            high = mid - 1;
1307                        }
1308                    }
1309                    return null;
1310                }
1311            }
1312        }
1313        return null;
1314    }
1315
1316    private int cmp(Comparable<K> object, K key1, K key2) {
1317        return object != null ?
1318               object.compareTo(key2) : comparator.compare(key1, key2);
1319    }
1320
1321    /**
1322     * Returns a sorted map over a range of this sorted map with all keys that
1323     * are less than the specified {@code endKey}. Changes to the returned
1324     * sorted map are reflected in this sorted map and vice versa.
1325     * <p>
1326     * Note: The returned map will not allow an insertion of a key outside the
1327     * specified range.
1328     *
1329     * @param endKey
1330     *            the high boundary of the range specified.
1331     * @return a sorted map where the keys are less than {@code endKey}.
1332     * @throws ClassCastException
1333     *             if the specified key cannot be compared with the keys in this
1334     *             map.
1335     * @throws NullPointerException
1336     *             if the specified key is {@code null} and the comparator
1337     *             cannot handle {@code null} keys.
1338     * @throws IllegalArgumentException
1339     *             if this map is itself a sorted map over a range of another
1340     *             map and the specified key is outside of its range.
1341     */
1342    public SortedMap<K, V> headMap(K endKey) {
1343        // Check for errors
1344        if (comparator == null) {
1345            toComparable(endKey).compareTo(endKey);
1346        } else {
1347            comparator.compare(endKey, endKey);
1348        }
1349        return new SubMap<K, V>(this, endKey);
1350    }
1351
1352    /**
1353     * Returns a set of the keys contained in this map. The set is backed by
1354     * this map so changes to one are reflected by the other. The set does not
1355     * support adding.
1356     *
1357     * @return a set of the keys.
1358     */
1359    @Override
1360    public Set<K> keySet() {
1361        if (keySet == null) {
1362            keySet = new AbstractSet<K>() {
1363                @Override
1364                public boolean contains(Object object) {
1365                    return TreeMap.this.containsKey(object);
1366                }
1367
1368                @Override
1369                public int size() {
1370                    return TreeMap.this.size;
1371                }
1372
1373                @Override
1374                public void clear() {
1375                    TreeMap.this.clear();
1376                }
1377
1378                @Override
1379                public boolean remove(Object object) {
1380                    if (contains(object)) {
1381                        TreeMap.this.remove(object);
1382                        return true;
1383                    }
1384                    return false;
1385                }
1386
1387                @Override
1388                public Iterator<K> iterator() {
1389                    return new UnboundedKeyIterator<K, V>(TreeMap.this);
1390                }
1391            };
1392        }
1393        return keySet;
1394    }
1395
1396    /**
1397     * Returns the last key in this map.
1398     *
1399     * @return the last key in this map.
1400     * @throws NoSuchElementException
1401     *             if this map is empty.
1402     */
1403    public K lastKey() {
1404        if (root != null) {
1405            Node<K, V> node = maximum(root);
1406            return node.keys[node.right_idx];
1407        }
1408        throw new NoSuchElementException();
1409    }
1410
1411    static <K,V> Node<K, V> minimum(Node<K, V> x) {
1412        if (x == null) {
1413            return null;
1414        }
1415        while (x.left != null) {
1416            x = x.left;
1417        }
1418        return x;
1419    }
1420
1421    static <K,V> Node<K, V> maximum(Node<K, V> x) {
1422        if (x == null) {
1423            return null;
1424        }
1425        while (x.right != null) {
1426            x = x.right;
1427        }
1428        return x;
1429    }
1430
1431    /**
1432     * Maps the specified key to the specified value.
1433     *
1434     * @param key
1435     *            the key.
1436     * @param value
1437     *            the value.
1438     * @return the value of any previous mapping with the specified key or
1439     *         {@code null} if there was no mapping.
1440     * @throws ClassCastException
1441     *             if the specified key cannot be compared with the keys in this
1442     *             map.
1443     * @throws NullPointerException
1444     *             if the specified key is {@code null} and the comparator
1445     *             cannot handle {@code null} keys.
1446     */
1447    @Override
1448    public V put(K key, V value) {
1449        if (root == null) {
1450            root = createNode(key, value);
1451            size = 1;
1452            modCount++;
1453            return null;
1454        }
1455        Comparable<K> object = comparator == null ? toComparable((K) key) : null;
1456        K keyK = (K) key;
1457        Node<K, V> node = root;
1458        Node<K, V> prevNode = null;
1459        int result = 0;
1460        while (node != null) {
1461            prevNode = node;
1462            K[] keys = node.keys;
1463            int left_idx = node.left_idx;
1464            result = cmp(object, keyK, keys[left_idx]);
1465            if (result < 0) {
1466                node = node.left;
1467            } else if (result == 0) {
1468                V res = node.values[left_idx];
1469                node.values[left_idx] = value;
1470                return res;
1471            } else {
1472                int right_idx = node.right_idx;
1473                if (left_idx != right_idx) {
1474                    result = cmp(object, keyK, keys[right_idx]);
1475                }
1476                if (result > 0) {
1477                    node = node.right;
1478                } else if (result == 0) {
1479                    V res = node.values[right_idx];
1480                    node.values[right_idx] = value;
1481                    return res;
1482                } else { /*search in node*/
1483                    int low = left_idx + 1, mid = 0, high = right_idx - 1;
1484                    while (low <= high) {
1485                        mid = (low + high) >>> 1;
1486                        result = cmp(object, keyK, keys[mid]);
1487                        if (result > 0) {
1488                            low = mid + 1;
1489                        } else if (result == 0) {
1490                            V res = node.values[mid];
1491                            node.values[mid] = value;
1492                            return res;
1493                        } else {
1494                            high = mid - 1;
1495                        }
1496                    }
1497                    result = low;
1498                    break;
1499                }
1500            }
1501        } /* while */
1502/*
1503          if(node == null) {
1504             if(prevNode==null) {
1505                - case of empty Tree
1506             } else {
1507                result < 0 - prevNode.left==null - attach here
1508                result > 0 - prevNode.right==null - attach here
1509             }
1510          } else {
1511             insert into node.
1512             result - index where it should be inserted.
1513          }
1514        */
1515        size++;
1516        modCount++;
1517        if (node == null) {
1518            if (prevNode == null) {
1519                // case of empty Tree
1520                root = createNode(key, value);
1521            } else if (prevNode.size < Node.NODE_SIZE) {
1522                // there is a place for insert
1523                if (result < 0) {
1524                    appendFromLeft(prevNode, key, value);
1525                } else {
1526                    appendFromRight(prevNode, key, value);
1527                }
1528            } else {
1529                // create and link
1530                Node<K, V> newNode = createNode(key, value);
1531                if (result < 0) {
1532                    attachToLeft(prevNode, newNode);
1533                } else {
1534                    attachToRight(prevNode, newNode);
1535                }
1536                balance(newNode);
1537            }
1538        } else {
1539            // insert into node.
1540            // result - index where it should be inserted.
1541            if (node.size < Node.NODE_SIZE) { // insert and ok
1542                int left_idx = node.left_idx;
1543                int right_idx = node.right_idx;
1544                if (left_idx == 0 || ((right_idx != Node.NODE_SIZE - 1) && (right_idx - result <= result - left_idx))) {
1545                    int right_idxPlus1 = right_idx + 1;
1546                    System.arraycopy(node.keys,   result, node.keys,   result + 1, right_idxPlus1 - result);
1547                    System.arraycopy(node.values, result, node.values, result + 1, right_idxPlus1 - result);
1548                    node.right_idx = right_idxPlus1;
1549                    node.keys[result] = key;
1550                    node.values[result] = value;
1551                } else {
1552                    int left_idxMinus1 = left_idx - 1;
1553                    System.arraycopy(node.keys,   left_idx, node.keys,   left_idxMinus1, result - left_idx);
1554                    System.arraycopy(node.values, left_idx, node.values, left_idxMinus1, result - left_idx);
1555                    node.left_idx = left_idxMinus1;
1556                    node.keys[result - 1] = key;
1557                    node.values[result - 1] = value;
1558                }
1559                node.size++;
1560            } else {
1561                // there are no place here
1562                // insert and push old pair
1563                Node<K, V> previous = node.prev;
1564                Node<K, V> nextNode = node.next;
1565                boolean removeFromStart;
1566                boolean attachFromLeft = false;
1567                Node<K, V> attachHere = null;
1568                if (previous == null) {
1569                    if (nextNode != null && nextNode.size < Node.NODE_SIZE) {
1570                        // move last pair to next
1571                        removeFromStart = false;
1572                    } else {
1573                        // next node doesn't exist or full
1574                        // left==null
1575                        // drop first pair to new node from left
1576                        removeFromStart = true;
1577                        attachFromLeft = true;
1578                        attachHere = node;
1579                    }
1580                } else if (nextNode == null) {
1581                    if (previous.size < Node.NODE_SIZE) {
1582                        // move first pair to prev
1583                        removeFromStart = true;
1584                    } else {
1585                        // right == null;
1586                        // drop last pair to new node from right
1587                        removeFromStart = false;
1588                        attachFromLeft = false;
1589                        attachHere = node;
1590                    }
1591                } else {
1592                    if (previous.size < Node.NODE_SIZE) {
1593                        if (nextNode.size < Node.NODE_SIZE) {
1594                            // choose prev or next for moving
1595                            removeFromStart = previous.size < nextNode.size;
1596                        } else {
1597                            // move first pair to prev
1598                            removeFromStart = true;
1599                        }
1600                    } else {
1601                        if (nextNode.size < Node.NODE_SIZE) {
1602                            // move last pair to next
1603                            removeFromStart = false;
1604                        } else {
1605                            // prev & next are full
1606                            // if node.right!=null then node.next.left==null
1607                            // if node.left!=null then node.prev.right==null
1608                            if (node.right == null) {
1609                                attachHere = node;
1610                                attachFromLeft = false;
1611                                removeFromStart = false;
1612                            } else {
1613                                attachHere = nextNode;
1614                                attachFromLeft = true;
1615                                removeFromStart = false;
1616                            }
1617                        }
1618                    }
1619                }
1620                K movedKey;
1621                V movedValue;
1622                if (removeFromStart) {
1623                    // node.left_idx == 0
1624                    movedKey = node.keys[0];
1625                    movedValue = node.values[0];
1626                    int resMunus1 = result - 1;
1627                    System.arraycopy(node.keys,   1, node.keys,   0, resMunus1);
1628                    System.arraycopy(node.values, 1, node.values, 0, resMunus1);
1629                    node.keys  [resMunus1] = key;
1630                    node.values[resMunus1] = value;
1631                } else {
1632                    // node.right_idx == Node.NODE_SIZE - 1
1633                    movedKey   = node.keys[Node.NODE_SIZE - 1];
1634                    movedValue = node.values[Node.NODE_SIZE - 1];
1635                    System.arraycopy(node.keys,   result, node.keys,   result + 1, Node.NODE_SIZE - 1 - result);
1636                    System.arraycopy(node.values, result, node.values, result + 1, Node.NODE_SIZE - 1 - result);
1637                    node.keys[result] = key;
1638                    node.values[result] = value;
1639                }
1640                if (attachHere == null) {
1641                    if (removeFromStart) {
1642                        appendFromRight(previous, movedKey, movedValue);
1643                    } else {
1644                        appendFromLeft(nextNode, movedKey, movedValue);
1645                    }
1646                } else {
1647                    Node<K, V> newNode = createNode(movedKey, movedValue);
1648                    if (attachFromLeft) {
1649                        attachToLeft(attachHere, newNode);
1650                    } else {
1651                        attachToRight(attachHere, newNode);
1652                    }
1653                    balance(newNode);
1654                }
1655            }
1656        }
1657        return null;
1658    }
1659
1660    private void appendFromLeft(Node<K, V> node, K keyObj, V value) {
1661        if (node.left_idx == 0) {
1662            int new_right = node.right_idx + 1;
1663            System.arraycopy(node.keys,   0, node.keys,   1, new_right);
1664            System.arraycopy(node.values, 0, node.values, 1, new_right);
1665            node.right_idx = new_right;
1666        } else {
1667            node.left_idx--;
1668        }
1669        node.size++;
1670        node.keys[node.left_idx] = keyObj;
1671        node.values[node.left_idx] = value;
1672    }
1673
1674    private void attachToLeft(Node<K, V> node, Node<K, V> newNode) {
1675        newNode.parent = node;
1676        // node.left==null - attach here
1677        node.left = newNode;
1678        Node<K, V> predecessor = node.prev;
1679        newNode.prev = predecessor;
1680        newNode.next = node;
1681        if (predecessor != null) {
1682            predecessor.next = newNode;
1683        }
1684        node.prev = newNode;
1685    }
1686
1687    /* add pair into node; existence free room in the node should be checked
1688     * before call
1689     */
1690    private void appendFromRight(Node<K, V> node, K keyObj, V value) {
1691        if (node.right_idx == Node.NODE_SIZE - 1) {
1692            int left_idx = node.left_idx;
1693            int left_idxMinus1 = left_idx - 1;
1694            System.arraycopy(node.keys,   left_idx, node.keys,   left_idxMinus1, Node.NODE_SIZE - left_idx);
1695            System.arraycopy(node.values, left_idx, node.values, left_idxMinus1, Node.NODE_SIZE - left_idx);
1696            node.left_idx = left_idxMinus1;
1697        } else {
1698            node.right_idx++;
1699        }
1700        node.size++;
1701        node.keys[node.right_idx] = keyObj;
1702        node.values[node.right_idx] = value;
1703    }
1704
1705    private void attachToRight(Node<K, V> node, Node<K, V> newNode) {
1706        newNode.parent = node;
1707        // - node.right==null - attach here
1708        node.right = newNode;
1709        newNode.prev = node;
1710        Node<K, V> successor = node.next;
1711        newNode.next = successor;
1712        if (successor != null) {
1713            successor.prev = newNode;
1714        }
1715        node.next = newNode;
1716    }
1717
1718    private Node<K, V> createNode(K keyObj, V value) {
1719        Node<K, V> node = new Node<K, V>();
1720        node.keys[0] = keyObj;
1721        node.values[0] = value;
1722        node.left_idx = 0;
1723        node.right_idx = 0;
1724        node.size = 1;
1725        return node;
1726    }
1727
1728    void balance(Node<K, V> x) {
1729        Node<K, V> y;
1730        x.color = true;
1731        while (x != root && x.parent.color) {
1732            if (x.parent == x.parent.parent.left) {
1733                y = x.parent.parent.right;
1734                if (y != null && y.color) {
1735                    x.parent.color = false;
1736                    y.color = false;
1737                    x.parent.parent.color = true;
1738                    x = x.parent.parent;
1739                } else {
1740                    if (x == x.parent.right) {
1741                        x = x.parent;
1742                        leftRotate(x);
1743                    }
1744                    x.parent.color = false;
1745                    x.parent.parent.color = true;
1746                    rightRotate(x.parent.parent);
1747                }
1748            } else {
1749                y = x.parent.parent.left;
1750                if (y != null && y.color) {
1751                    x.parent.color = false;
1752                    y.color = false;
1753                    x.parent.parent.color = true;
1754                    x = x.parent.parent;
1755                } else {
1756                    if (x == x.parent.left) {
1757                        x = x.parent;
1758                        rightRotate(x);
1759                    }
1760                    x.parent.color = false;
1761                    x.parent.parent.color = true;
1762                    leftRotate(x.parent.parent);
1763                }
1764            }
1765        }
1766        root.color = false;
1767    }
1768
1769    private void rightRotate(Node<K, V> x) {
1770        Node<K, V> y = x.left;
1771        x.left = y.right;
1772        if (y.right != null) {
1773            y.right.parent = x;
1774        }
1775        y.parent = x.parent;
1776        if (x.parent == null) {
1777            root = y;
1778        } else {
1779            if (x == x.parent.right) {
1780                x.parent.right = y;
1781            } else {
1782                x.parent.left = y;
1783            }
1784        }
1785        y.right = x;
1786        x.parent = y;
1787    }
1788
1789
1790    private void leftRotate(Node<K, V> x) {
1791        Node<K, V> y = x.right;
1792        x.right = y.left;
1793        if (y.left != null) {
1794            y.left.parent = x;
1795        }
1796        y.parent = x.parent;
1797        if (x.parent == null) {
1798            root = y;
1799        } else {
1800            if (x == x.parent.left) {
1801                x.parent.left = y;
1802            } else {
1803                x.parent.right = y;
1804            }
1805        }
1806        y.left = x;
1807        x.parent = y;
1808    }
1809
1810
1811    /**
1812     * Copies all the mappings in the given map to this map. These mappings will
1813     * replace all mappings that this map had for any of the keys currently in
1814     * the given map.
1815     *
1816     * @param map
1817     *            the map to copy mappings from.
1818     * @throws ClassCastException
1819     *             if a key in the specified map cannot be compared with the
1820     *             keys in this map.
1821     * @throws NullPointerException
1822     *             if a key in the specified map is {@code null} and the
1823     *             comparator cannot handle {@code null} keys.
1824     */
1825    @Override
1826    public void putAll(Map<? extends K, ? extends V> map) {
1827        super.putAll(map);
1828    }
1829
1830    /**
1831     * Removes the mapping with the specified key from this map.
1832     *
1833     * @param key
1834     *            the key of the mapping to remove.
1835     * @return the value of the removed mapping or {@code null} if no mapping
1836     *         for the specified key was found.
1837     * @throws ClassCastException
1838     *             if the specified key cannot be compared with the keys in this
1839     *             map.
1840     * @throws NullPointerException
1841     *             if the specified key is {@code null} and the comparator
1842     *             cannot handle {@code null} keys.
1843     */
1844    @Override
1845    public V remove(Object key) {
1846        if (size == 0) {
1847            return null;
1848        }
1849        Comparable<K> object = comparator == null ? toComparable((K) key) : null;
1850        K keyK = (K) key;
1851        Node<K, V> node = root;
1852        while (node != null) {
1853            K[] keys = node.keys;
1854            int left_idx = node.left_idx;
1855            int result = cmp(object, keyK, keys[left_idx]);
1856            if (result < 0) {
1857                node = node.left;
1858            } else if (result == 0) {
1859                V value = node.values[left_idx];
1860                removeLeftmost(node);
1861                return value;
1862            } else {
1863                int right_idx = node.right_idx;
1864                if (left_idx != right_idx) {
1865                    result = cmp(object, keyK, keys[right_idx]);
1866                }
1867                if (result > 0) {
1868                    node = node.right;
1869                } else if (result == 0) {
1870                    V value = node.values[right_idx];
1871                    removeRightmost(node);
1872                    return value;
1873                } else { /*search in node*/
1874                    int low = left_idx + 1, mid = 0, high = right_idx - 1;
1875                    while (low <= high) {
1876                        mid = (low + high) >>> 1;
1877                        result = cmp(object, keyK, keys[mid]);
1878                        if (result > 0) {
1879                            low = mid + 1;
1880                        } else if (result == 0) {
1881                            V value = node.values[mid];
1882                            removeMiddleElement(node, mid);
1883                            return value;
1884                        } else {
1885                            high = mid - 1;
1886                        }
1887                    }
1888                    return null;
1889                }
1890            }
1891        }
1892        return null;
1893    }
1894
1895    void removeLeftmost(Node<K, V> node) {
1896        int index = node.left_idx;
1897        if (node.size == 1) {
1898            deleteNode(node);
1899        } else if (node.prev != null && (Node.NODE_SIZE - 1 - node.prev.right_idx) > node.size) {
1900            // move all to prev node and kill it
1901            Node<K, V> prev = node.prev;
1902            int size = node.right_idx - index;
1903            System.arraycopy(node.keys,   index + 1, prev.keys,   prev.right_idx + 1, size);
1904            System.arraycopy(node.values, index + 1, prev.values, prev.right_idx + 1, size);
1905            prev.right_idx += size;
1906            prev.size += size;
1907            deleteNode(node);
1908        } else if (node.next != null && (node.next.left_idx) > node.size) {
1909            // move all to next node and kill it
1910            Node<K, V> next = node.next;
1911            int size = node.right_idx - index;
1912            int next_new_left = next.left_idx - size;
1913            next.left_idx = next_new_left;
1914            System.arraycopy(node.keys,   index + 1, next.keys,   next_new_left, size);
1915            System.arraycopy(node.values, index + 1, next.values, next_new_left, size);
1916            next.size += size;
1917            deleteNode(node);
1918        } else {
1919            node.keys[index] = null;
1920            node.values[index] = null;
1921            node.left_idx++;
1922            node.size--;
1923            Node<K, V> prev = node.prev;
1924            if (prev != null && prev.size == 1) {
1925                node.size++;
1926                node.left_idx--;
1927                node.keys  [node.left_idx] = prev.keys  [prev.left_idx];
1928                node.values[node.left_idx] = prev.values[prev.left_idx];
1929                deleteNode(prev);
1930            }
1931        }
1932        modCount++;
1933        size--;
1934    }
1935
1936    void removeRightmost(Node<K, V> node) {
1937        int index = node.right_idx;
1938        if (node.size == 1) {
1939            deleteNode(node);
1940        } else if (node.prev != null && (Node.NODE_SIZE - 1 - node.prev.right_idx) > node.size) {
1941            // move all to prev node and kill it
1942            Node<K, V> prev = node.prev;
1943            int left_idx = node.left_idx;
1944            int size = index - left_idx;
1945            System.arraycopy(node.keys,   left_idx, prev.keys,   prev.right_idx + 1, size);
1946            System.arraycopy(node.values, left_idx, prev.values, prev.right_idx + 1, size);
1947            prev.right_idx += size;
1948            prev.size += size;
1949            deleteNode(node);
1950        } else if (node.next != null && (node.next.left_idx) > node.size) {
1951            // move all to next node and kill it
1952            Node<K, V> next = node.next;
1953            int left_idx = node.left_idx;
1954            int size = index - left_idx;
1955            int next_new_left = next.left_idx - size;
1956            next.left_idx = next_new_left;
1957            System.arraycopy(node.keys,   left_idx, next.keys,   next_new_left, size);
1958            System.arraycopy(node.values, left_idx, next.values, next_new_left, size);
1959            next.size += size;
1960            deleteNode(node);
1961        } else {
1962            node.keys[index] = null;
1963            node.values[index] = null;
1964            node.right_idx--;
1965            node.size--;
1966            Node<K, V> next = node.next;
1967            if (next != null && next.size == 1) {
1968                node.size++;
1969                node.right_idx++;
1970                node.keys[node.right_idx]   = next.keys[next.left_idx];
1971                node.values[node.right_idx] = next.values[next.left_idx];
1972                deleteNode(next);
1973            }
1974        }
1975        modCount++;
1976        size--;
1977    }
1978
1979    void removeMiddleElement(Node<K, V> node, int index) {
1980        // this function is called iff index if some middle element;
1981        // so node.left_idx < index < node.right_idx
1982        // condition above assume that node.size > 1
1983        if (node.prev != null && (Node.NODE_SIZE - 1 - node.prev.right_idx) > node.size) {
1984            // move all to prev node and kill it
1985            Node<K, V> prev = node.prev;
1986            int left_idx = node.left_idx;
1987            int size = index - left_idx;
1988            System.arraycopy(node.keys,   left_idx, prev.keys,   prev.right_idx + 1, size);
1989            System.arraycopy(node.values, left_idx, prev.values, prev.right_idx + 1, size);
1990            prev.right_idx += size;
1991            size = node.right_idx - index;
1992            System.arraycopy(node.keys,   index + 1, prev.keys,   prev.right_idx + 1, size);
1993            System.arraycopy(node.values, index + 1, prev.values, prev.right_idx + 1, size);
1994            prev.right_idx += size;
1995            prev.size += (node.size - 1);
1996            deleteNode(node);
1997        } else if (node.next != null && (node.next.left_idx) > node.size) {
1998            // move all to next node and kill it
1999            Node<K, V> next = node.next;
2000            int left_idx = node.left_idx;
2001            int next_new_left = next.left_idx - node.size + 1;
2002            next.left_idx = next_new_left;
2003            int size = index - left_idx;
2004            System.arraycopy(node.keys,   left_idx, next.keys,   next_new_left, size);
2005            System.arraycopy(node.values, left_idx, next.values, next_new_left, size);
2006            next_new_left += size;
2007            size = node.right_idx - index;
2008            System.arraycopy(node.keys,   index + 1, next.keys,   next_new_left, size);
2009            System.arraycopy(node.values, index + 1, next.values, next_new_left, size);
2010            next.size += (node.size - 1);
2011            deleteNode(node);
2012        } else {
2013            int moveFromRight = node.right_idx - index;
2014            int left_idx = node.left_idx;
2015            int moveFromLeft = index - left_idx ;
2016            if (moveFromRight <= moveFromLeft) {
2017                System.arraycopy(node.keys,   index + 1, node.keys,   index, moveFromRight);
2018                System.arraycopy(node.values, index + 1, node.values, index, moveFromRight);
2019                Node<K, V> next = node.next;
2020                if (next != null && next.size == 1) {
2021                    node.keys  [node.right_idx] = next.keys  [next.left_idx];
2022                    node.values[node.right_idx] = next.values[next.left_idx];
2023                    deleteNode(next);
2024                } else {
2025                    node.keys  [node.right_idx] = null;
2026                    node.values[node.right_idx] = null;
2027                    node.right_idx--;
2028                    node.size--;
2029                }
2030            } else {
2031                System.arraycopy(node.keys,   left_idx , node.keys,   left_idx  + 1, moveFromLeft);
2032                System.arraycopy(node.values, left_idx , node.values, left_idx + 1, moveFromLeft);
2033                Node<K, V> prev = node.prev;
2034                if (prev != null && prev.size == 1) {
2035                    node.keys  [left_idx ] = prev.keys  [prev.left_idx];
2036                    node.values[left_idx ] = prev.values[prev.left_idx];
2037                    deleteNode(prev);
2038                } else {
2039                    node.keys  [left_idx ] = null;
2040                    node.values[left_idx ] = null;
2041                    node.left_idx++;
2042                    node.size--;
2043                }
2044            }
2045        }
2046        modCount++;
2047        size--;
2048    }
2049
2050    void removeFromIterator(Node<K, V> node, int index) {
2051        if (node.size == 1) {
2052            // it is safe to delete the whole node here.
2053            // iterator already moved to the next node;
2054            deleteNode(node);
2055        } else {
2056            int left_idx = node.left_idx;
2057            if (index == left_idx) {
2058                Node<K, V> prev = node.prev;
2059                if (prev != null && prev.size == 1) {
2060                    node.keys  [left_idx] = prev.keys  [prev.left_idx];
2061                    node.values[left_idx] = prev.values[prev.left_idx];
2062                    deleteNode(prev);
2063                } else {
2064                    node.keys  [left_idx] = null;
2065                    node.values[left_idx] = null;
2066                    node.left_idx++;
2067                    node.size--;
2068                }
2069            } else if (index == node.right_idx) {
2070                node.keys  [index] = null;
2071                node.values[index] = null;
2072                node.right_idx--;
2073                node.size--;
2074            } else {
2075                int moveFromRight = node.right_idx - index;
2076                int moveFromLeft = index - left_idx;
2077                if (moveFromRight <= moveFromLeft) {
2078                    System.arraycopy(node.keys,   index + 1, node.keys,   index, moveFromRight );
2079                    System.arraycopy(node.values, index + 1, node.values, index, moveFromRight );
2080                    node.keys  [node.right_idx] = null;
2081                    node.values[node.right_idx] = null;
2082                    node.right_idx--;
2083                    node.size--;
2084                } else {
2085                    System.arraycopy(node.keys,   left_idx, node.keys,   left_idx+ 1, moveFromLeft);
2086                    System.arraycopy(node.values, left_idx, node.values, left_idx+ 1, moveFromLeft);
2087                    node.keys  [left_idx] = null;
2088                    node.values[left_idx] = null;
2089                    node.left_idx++;
2090                    node.size--;
2091               }
2092            }
2093        }
2094        modCount++;
2095        size--;
2096    }
2097
2098    private void deleteNode(Node<K, V> node) {
2099        if (node.right == null) {
2100            if (node.left != null) {
2101                attachToParent(node, node.left);
2102           } else {
2103                attachNullToParent(node);
2104            }
2105            fixNextChain(node);
2106        } else if(node.left == null) { // node.right != null
2107            attachToParent(node, node.right);
2108            fixNextChain(node);
2109        } else {
2110            // Here node.left!=nul && node.right!=null
2111            // node.next should replace node in tree
2112            // node.next!=null by tree logic.
2113            // node.next.left==null by tree logic.
2114            // node.next.right may be null or non-null
2115            Node<K, V> toMoveUp = node.next;
2116            fixNextChain(node);
2117            if(toMoveUp.right==null){
2118                attachNullToParent(toMoveUp);
2119            } else {
2120                attachToParent(toMoveUp, toMoveUp.right);
2121            }
2122            // Here toMoveUp is ready to replace node
2123            toMoveUp.left = node.left;
2124            if (node.left != null) {
2125            	node.left.parent = toMoveUp;
2126            }
2127            toMoveUp.right = node.right;
2128            if (node.right != null) {
2129            	node.right.parent = toMoveUp;
2130            }
2131            attachToParentNoFixup(node,toMoveUp);
2132            toMoveUp.color = node.color;
2133        }
2134    }
2135
2136    private void attachToParentNoFixup(Node<K, V> toDelete, Node<K, V> toConnect) {
2137        // assert toConnect!=null
2138        Node<K,V> parent = toDelete.parent;
2139        toConnect.parent = parent;
2140        if (parent == null) {
2141            root = toConnect;
2142        } else if (toDelete == parent.left) {
2143            parent.left = toConnect;
2144        } else {
2145            parent.right = toConnect;
2146        }
2147    }
2148
2149    private void attachToParent(Node<K, V> toDelete, Node<K, V> toConnect) {
2150        // assert toConnect!=null
2151        attachToParentNoFixup(toDelete,toConnect);
2152        if (!toDelete.color) {
2153            fixup(toConnect);
2154        }
2155    }
2156
2157    private void attachNullToParent(Node<K, V> toDelete) {
2158        Node<K, V> parent = toDelete.parent;
2159        if (parent == null) {
2160            root = null;
2161        } else {
2162            if (toDelete == parent.left) {
2163                parent.left = null;
2164            } else {
2165                parent.right = null;
2166            }
2167            if (!toDelete.color) {
2168                fixup(parent);
2169            }
2170        }
2171    }
2172
2173    private void fixNextChain(Node<K, V> node) {
2174        if (node.prev != null) {
2175            node.prev.next = node.next;
2176        }
2177        if (node.next != null) {
2178            node.next.prev = node.prev;
2179        }
2180    }
2181
2182    private void fixup(Node<K, V> x) {
2183        Node<K, V> w;
2184        while (x != root && !x.color) {
2185            if (x == x.parent.left) {
2186                w = x.parent.right;
2187                if (w == null) {
2188                    x = x.parent;
2189                    continue;
2190                }
2191                if (w.color) {
2192                    w.color = false;
2193                    x.parent.color = true;
2194                    leftRotate(x.parent);
2195                    w = x.parent.right;
2196                    if (w == null) {
2197                        x = x.parent;
2198                        continue;
2199                    }
2200                }
2201                if ((w.left == null || !w.left.color)
2202                    && (w.right == null || !w.right.color)) {
2203                    w.color = true;
2204                    x = x.parent;
2205                } else {
2206                    if (w.right == null || !w.right.color) {
2207                        w.left.color = false;
2208                        w.color = true;
2209                        rightRotate(w);
2210                        w = x.parent.right;
2211                    }
2212                    w.color = x.parent.color;
2213                    x.parent.color = false;
2214                    w.right.color = false;
2215                    leftRotate(x.parent);
2216                    x = root;
2217                }
2218            } else {
2219                w = x.parent.left;
2220                if (w == null) {
2221                    x = x.parent;
2222                    continue;
2223                }
2224                if (w.color) {
2225                    w.color = false;
2226                    x.parent.color = true;
2227                    rightRotate(x.parent);
2228                    w = x.parent.left;
2229                    if (w == null) {
2230                        x = x.parent;
2231                        continue;
2232                    }
2233                }
2234                if ((w.left == null || !w.left.color)
2235                    && (w.right == null || !w.right.color)) {
2236                    w.color = true;
2237                    x = x.parent;
2238                } else {
2239                    if (w.left == null || !w.left.color) {
2240                        w.right.color = false;
2241                        w.color = true;
2242                        leftRotate(w);
2243                        w = x.parent.left;
2244                    }
2245                    w.color = x.parent.color;
2246                    x.parent.color = false;
2247                    w.left.color = false;
2248                    rightRotate(x.parent);
2249                    x = root;
2250                }
2251            }
2252        }
2253        x.color = false;
2254    }
2255
2256
2257    /**
2258     * Returns the number of mappings in this map.
2259     *
2260     * @return the number of mappings in this map.
2261     */
2262    @Override
2263    public int size() {
2264        return size;
2265    }
2266
2267    /**
2268     * Returns a sorted map over a range of this sorted map with all keys
2269     * greater than or equal to the specified {@code startKey} and less than the
2270     * specified {@code endKey}. Changes to the returned sorted map are
2271     * reflected in this sorted map and vice versa.
2272     * <p>
2273     * Note: The returned map will not allow an insertion of a key outside the
2274     * specified range.
2275     *
2276     * @param startKey
2277     *            the low boundary of the range (inclusive).
2278     * @param endKey
2279     *            the high boundary of the range (exclusive),
2280     * @return a sorted map with the key from the specified range.
2281     * @throws ClassCastException
2282     *             if the start or end key cannot be compared with the keys in
2283     *             this map.
2284     * @throws NullPointerException
2285     *             if the start or end key is {@code null} and the comparator
2286     *             cannot handle {@code null} keys.
2287     * @throws IllegalArgumentException
2288     *             if the start key is greater than the end key, or if this map
2289     *             is itself a sorted map over a range of another sorted map and
2290     *             the specified range is outside of its range.
2291     */
2292    public SortedMap<K, V> subMap(K startKey, K endKey) {
2293        if (comparator == null) {
2294            if (toComparable(startKey).compareTo(endKey) <= 0) {
2295                return new SubMap<K, V>(startKey, this, endKey);
2296            }
2297        } else {
2298            if (comparator.compare(startKey, endKey) <= 0) {
2299                return new SubMap<K, V>(startKey, this, endKey);
2300            }
2301        }
2302        throw new IllegalArgumentException();
2303    }
2304
2305    /**
2306     * Returns a sorted map over a range of this sorted map with all keys that
2307     * are greater than or equal to the specified {@code startKey}. Changes to
2308     * the returned sorted map are reflected in this sorted map and vice versa.
2309     * <p>
2310     * Note: The returned map will not allow an insertion of a key outside the
2311     * specified range.
2312     *
2313     * @param startKey
2314     *            the low boundary of the range specified.
2315     * @return a sorted map where the keys are greater or equal to
2316     *         {@code startKey}.
2317     * @throws ClassCastException
2318     *             if the specified key cannot be compared with the keys in this
2319     *             map.
2320     * @throws NullPointerException
2321     *             if the specified key is {@code null} and the comparator
2322     *             cannot handle {@code null} keys.
2323     * @throws IllegalArgumentException
2324     *             if this map itself a sorted map over a range of another map
2325     *             and the specified key is outside of its range.
2326     */
2327    public SortedMap<K, V> tailMap(K startKey) {
2328        // Check for errors
2329        if (comparator == null) {
2330            toComparable(startKey).compareTo(startKey);
2331        } else {
2332            comparator.compare(startKey, startKey);
2333        }
2334        return new SubMap<K, V>(startKey, this);
2335    }
2336
2337    /**
2338     * Returns a collection of the values contained in this map. The collection
2339     * is backed by this map so changes to one are reflected by the other. The
2340     * collection supports remove, removeAll, retainAll and clear operations,
2341     * and it does not support add or addAll operations.
2342     * <p>
2343     * This method returns a collection which is the subclass of
2344     * AbstractCollection. The iterator method of this subclass returns a
2345     * "wrapper object" over the iterator of map's entrySet(). The {@code size}
2346     * method wraps the map's size method and the {@code contains} method wraps
2347     * the map's containsValue method.
2348     * <p>
2349     * The collection is created when this method is called for the first time
2350     * and returned in response to all subsequent calls. This method may return
2351     * different collections when multiple concurrent calls occur, since no
2352     * synchronization is performed.
2353     *
2354     * @return a collection of the values contained in this map.
2355     */
2356    @Override
2357    public Collection<V> values() {
2358        if (valuesCollection == null) {
2359            valuesCollection = new AbstractCollection<V>() {
2360                @Override
2361                public boolean contains(Object object) {
2362                    return containsValue(object);
2363                }
2364
2365                @Override
2366                public int size() {
2367                    return size;
2368                }
2369
2370                @Override
2371                public void clear() {
2372                    TreeMap.this.clear();
2373                }
2374
2375                @Override
2376                public Iterator<V> iterator() {
2377                    return new UnboundedValueIterator<K, V>(TreeMap.this);
2378                }
2379            };
2380        }
2381        return valuesCollection;
2382    }
2383
2384    private void writeObject(ObjectOutputStream stream) throws IOException {
2385        stream.defaultWriteObject();
2386        stream.writeInt(size);
2387        if (size > 0) {
2388            Node<K, V> node = minimum(root);
2389            while (node != null) {
2390                int to = node.right_idx;
2391                for (int i = node.left_idx; i <= to; i++) {
2392                    stream.writeObject(node.keys[i]);
2393                    stream.writeObject(node.values[i]);
2394                }
2395                node = node.next;
2396            }
2397        }
2398    }
2399
2400    @SuppressWarnings("unchecked")
2401    private void readObject(ObjectInputStream stream) throws IOException,
2402                                                          ClassNotFoundException {
2403        stream.defaultReadObject();
2404        int size = stream.readInt();
2405        Node<K, V> lastNode = null;
2406        for (int i = 0; i < size; i++) {
2407            lastNode = addToLast(lastNode, (K) stream.readObject(), (V) stream.readObject());
2408        }
2409    }
2410}
2411