1/*
2 * Copyright (C) 2010 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package java.util;
18
19import java.io.IOException;
20import java.io.ObjectInputStream;
21import java.io.ObjectInputStream.GetField;
22import java.io.ObjectOutputStream;
23import java.io.ObjectStreamException;
24import java.io.Serializable;
25import static java.util.TreeMap.Bound.*;
26import static java.util.TreeMap.Relation.*;
27import libcore.util.Objects;
28
29/**
30 * A map whose entries are sorted by their keys. All optional operations such as
31 * {@link #put} and {@link #remove} are supported.
32 *
33 * <p>This map sorts keys using either a user-supplied comparator or the key's
34 * natural order:
35 * <ul>
36 *   <li>User supplied comparators must be able to compare any pair of keys in
37 *       this map. If a user-supplied comparator is in use, it will be returned
38 *       by {@link #comparator}.
39 *   <li>If no user-supplied comparator is supplied, keys will be sorted by
40 *       their natural order. Keys must be <i>mutually comparable</i>: they must
41 *       implement {@link Comparable} and {@link Comparable#compareTo
42 *       compareTo()} must be able to compare each key with any other key in
43 *       this map. In this case {@link #comparator} will return null.
44 * </ul>
45 * With either a comparator or a natural ordering, comparisons should be
46 * <i>consistent with equals</i>. An ordering is consistent with equals if for
47 * every pair of keys {@code a} and {@code b}, {@code a.equals(b)} if and only
48 * if {@code compare(a, b) == 0}.
49 *
50 * <p>When the ordering is not consistent with equals the behavior of this
51 * class is well defined but does not honor the contract specified by {@link
52 * Map}. Consider a tree map of case-insensitive strings, an ordering that is
53 * not consistent with equals: <pre>   {@code
54 *   TreeMap<String, String> map = new TreeMap<String, String>(String.CASE_INSENSITIVE_ORDER);
55 *   map.put("a", "android");
56 *
57 *   // The Map API specifies that the next line should print "null" because
58 *   // "a".equals("A") is false and there is no mapping for upper case "A".
59 *   // But the case insensitive ordering says compare("a", "A") == 0. TreeMap
60 *   // uses only comparators/comparable on keys and so this prints "android".
61 *   System.out.println(map.get("A"));
62 * }</pre>
63 *
64 * @since 1.2
65 */
66public class TreeMap<K, V> extends AbstractMap<K, V>
67        implements SortedMap<K, V>, NavigableMap<K, V>, Cloneable, Serializable {
68
69    @SuppressWarnings("unchecked") // to avoid Comparable<Comparable<Comparable<...>>>
70    private static final Comparator<Comparable> NATURAL_ORDER = new Comparator<Comparable>() {
71        public int compare(Comparable a, Comparable b) {
72            return a.compareTo(b);
73        }
74    };
75
76    Comparator<? super K> comparator;
77    Node<K, V> root;
78    int size = 0;
79    int modCount = 0;
80
81    /**
82     * Create a natural order, empty tree map whose keys must be mutually
83     * comparable and non-null.
84     */
85    @SuppressWarnings("unchecked") // unsafe! this assumes K is comparable
86    public TreeMap() {
87        this.comparator = (Comparator<? super K>) NATURAL_ORDER;
88    }
89
90    /**
91     * Create a natural order tree map populated with the key/value pairs of
92     * {@code copyFrom}. This map's keys must be mutually comparable and
93     * non-null.
94     *
95     * <p>Even if {@code copyFrom} is a {@code SortedMap}, the constructed map
96     * <strong>will not</strong> use {@code copyFrom}'s ordering. This
97     * constructor always creates a naturally-ordered map. Because the {@code
98     * TreeMap} constructor overloads are ambiguous, prefer to construct a map
99     * and populate it in two steps: <pre>   {@code
100     *   TreeMap<String, Integer> customOrderedMap
101     *       = new TreeMap<String, Integer>(copyFrom.comparator());
102     *   customOrderedMap.putAll(copyFrom);
103     * }</pre>
104     */
105    public TreeMap(Map<? extends K, ? extends V> copyFrom) {
106        this();
107        for (Map.Entry<? extends K, ? extends V> entry : copyFrom.entrySet()) {
108            putInternal(entry.getKey(), entry.getValue());
109        }
110    }
111
112    /**
113     * Create a tree map ordered by {@code comparator}. This map's keys may only
114     * be null if {@code comparator} permits.
115     *
116     * @param comparator the comparator to order elements with, or {@code null} to use the natural
117     * ordering.
118     */
119    @SuppressWarnings("unchecked") // unsafe! if comparator is null, this assumes K is comparable
120    public TreeMap(Comparator<? super K> comparator) {
121        if (comparator != null) {
122            this.comparator = comparator;
123        } else {
124            this.comparator = (Comparator<? super K>) NATURAL_ORDER;
125        }
126    }
127
128    /**
129     * Create a tree map with the ordering and key/value pairs of {@code
130     * copyFrom}. This map's keys may only be null if the {@code copyFrom}'s
131     * ordering permits.
132     *
133     * <p>The constructed map <strong>will always use</strong> {@code
134     * copyFrom}'s ordering. Because the {@code TreeMap} constructor overloads
135     * are ambiguous, prefer to construct a map and populate it in two steps:
136     * <pre>   {@code
137     *   TreeMap<String, Integer> customOrderedMap
138     *       = new TreeMap<String, Integer>(copyFrom.comparator());
139     *   customOrderedMap.putAll(copyFrom);
140     * }</pre>
141     */
142    @SuppressWarnings("unchecked") // if copyFrom's keys are comparable this map's keys must be also
143    public TreeMap(SortedMap<K, ? extends V> copyFrom) {
144        Comparator<? super K> sourceComparator = copyFrom.comparator();
145        if (sourceComparator != null) {
146            this.comparator = sourceComparator;
147        } else {
148            this.comparator = (Comparator<? super K>) NATURAL_ORDER;
149        }
150        for (Map.Entry<K, ? extends V> entry : copyFrom.entrySet()) {
151            putInternal(entry.getKey(), entry.getValue());
152        }
153    }
154
155    @Override public Object clone() {
156        try {
157            @SuppressWarnings("unchecked") // super.clone() must return the same type
158            TreeMap<K, V> map = (TreeMap<K, V>) super.clone();
159            map.root = root != null ? root.copy(null) : null;
160            map.entrySet = null;
161            map.keySet = null;
162            return map;
163        } catch (CloneNotSupportedException e) {
164            throw new AssertionError();
165        }
166    }
167
168    @Override public int size() {
169        return size;
170    }
171
172    @Override public boolean isEmpty() {
173        return size == 0;
174    }
175
176    @Override public V get(Object key) {
177        Entry<K, V> entry = findByObject(key);
178        return entry != null ? entry.getValue() : null;
179    }
180
181    @Override public boolean containsKey(Object key) {
182        return findByObject(key) != null;
183    }
184
185    @Override public V put(K key, V value) {
186        return putInternal(key, value);
187    }
188
189    @Override public void clear() {
190        root = null;
191        size = 0;
192        modCount++;
193    }
194
195    @Override public V remove(Object key) {
196        Node<K, V> node = removeInternalByKey(key);
197        return node != null ? node.value : null;
198    }
199
200    /*
201     * AVL methods
202     */
203
204    enum Relation {
205        LOWER,
206        FLOOR,
207        EQUAL,
208        CREATE,
209        CEILING,
210        HIGHER;
211
212        /**
213         * Returns a possibly-flipped relation for use in descending views.
214         *
215         * @param ascending false to flip; true to return this.
216         */
217        Relation forOrder(boolean ascending) {
218            if (ascending) {
219                return this;
220            }
221
222            switch (this) {
223                case LOWER:
224                    return HIGHER;
225                case FLOOR:
226                    return CEILING;
227                case EQUAL:
228                    return EQUAL;
229                case CEILING:
230                    return FLOOR;
231                case HIGHER:
232                    return LOWER;
233                default:
234                    throw new IllegalStateException();
235            }
236        }
237    }
238
239    V putInternal(K key, V value) {
240        Node<K, V> created = find(key, Relation.CREATE);
241        V result = created.value;
242        created.value = value;
243        return result;
244    }
245
246    /**
247     * Returns the node at or adjacent to the given key, creating it if requested.
248     *
249     * @throws ClassCastException if {@code key} and the tree's keys aren't mutually comparable.
250     */
251    Node<K, V> find(K key, Relation relation) {
252        if (root == null) {
253            if (comparator == NATURAL_ORDER && !(key instanceof Comparable)) {
254                throw new ClassCastException(key.getClass().getName() + " is not Comparable"); // NullPointerException ok
255            }
256            if (relation == Relation.CREATE) {
257                root = new Node<K, V>(null, key);
258                size = 1;
259                modCount++;
260                return root;
261            } else {
262                return null;
263            }
264        }
265
266        /*
267         * Micro-optimization: avoid polymorphic calls to Comparator.compare().
268         * This is 10% faster for naturally ordered trees.
269         */
270        @SuppressWarnings("unchecked") // will throw a ClassCastException below if there's trouble
271        Comparable<Object> comparableKey = (comparator == NATURAL_ORDER)
272                ? (Comparable<Object>) key
273                : null;
274
275        Node<K, V> nearest = root;
276        while (true) {
277            int comparison = (comparableKey != null)
278                    ? comparableKey.compareTo(nearest.key)
279                    : comparator.compare(key, nearest.key);
280
281            /*
282             * We found the requested key.
283             */
284            if (comparison == 0) {
285                switch (relation) {
286                    case LOWER:
287                        return nearest.prev();
288                    case FLOOR:
289                    case EQUAL:
290                    case CREATE:
291                    case CEILING:
292                        return nearest;
293                    case HIGHER:
294                        return nearest.next();
295                }
296            }
297
298            Node<K, V> child = (comparison < 0) ? nearest.left : nearest.right;
299            if (child != null) {
300                nearest = child;
301                continue;
302            }
303
304            /*
305             * We found a nearest node. Every key not in the tree has up to two
306             * nearest nodes, one lower and one higher.
307             */
308
309            if (comparison < 0) { // nearest.key is higher
310                switch (relation) {
311                    case LOWER:
312                    case FLOOR:
313                        return nearest.prev();
314                    case CEILING:
315                    case HIGHER:
316                        return nearest;
317                    case EQUAL:
318                        return null;
319                    case CREATE:
320                        Node<K, V> created = new Node<K, V>(nearest, key);
321                        nearest.left = created;
322                        size++;
323                        modCount++;
324                        rebalance(nearest, true);
325                        return created;
326                }
327            } else { // comparison > 0, nearest.key is lower
328                switch (relation) {
329                    case LOWER:
330                    case FLOOR:
331                        return nearest;
332                    case CEILING:
333                    case HIGHER:
334                        return nearest.next();
335                    case EQUAL:
336                        return null;
337                    case CREATE:
338                        Node<K, V> created = new Node<K, V>(nearest, key);
339                        nearest.right = created;
340                        size++;
341                        modCount++;
342                        rebalance(nearest, true);
343                        return created;
344                }
345            }
346        }
347    }
348
349    @SuppressWarnings("unchecked") // this method throws ClassCastExceptions!
350    Node<K, V> findByObject(Object key) {
351        return find((K) key, EQUAL);
352    }
353
354    /**
355     * Returns this map's entry that has the same key and value as {@code
356     * entry}, or null if this map has no such entry.
357     *
358     * <p>This method uses the comparator for key equality rather than {@code
359     * equals}. If this map's comparator isn't consistent with equals (such as
360     * {@code String.CASE_INSENSITIVE_ORDER}), then {@code remove()} and {@code
361     * contains()} will violate the collections API.
362     */
363    Node<K, V> findByEntry(Entry<?, ?> entry) {
364        Node<K, V> mine = findByObject(entry.getKey());
365        boolean valuesEqual = mine != null && Objects.equal(mine.value, entry.getValue());
366        return valuesEqual ? mine : null;
367    }
368
369    /**
370     * Removes {@code node} from this tree, rearranging the tree's structure as
371     * necessary.
372     */
373    void removeInternal(Node<K, V> node) {
374        Node<K, V> left = node.left;
375        Node<K, V> right = node.right;
376        Node<K, V> originalParent = node.parent;
377        if (left != null && right != null) {
378
379            /*
380             * To remove a node with both left and right subtrees, move an
381             * adjacent node from one of those subtrees into this node's place.
382             *
383             * Removing the adjacent node may change this node's subtrees. This
384             * node may no longer have two subtrees once the adjacent node is
385             * gone!
386             */
387
388            Node<K, V> adjacent = (left.height > right.height) ? left.last() : right.first();
389            removeInternal(adjacent); // takes care of rebalance and size--
390
391            int leftHeight = 0;
392            left = node.left;
393            if (left != null) {
394                leftHeight = left.height;
395                adjacent.left = left;
396                left.parent = adjacent;
397                node.left = null;
398            }
399            int rightHeight = 0;
400            right = node.right;
401            if (right != null) {
402                rightHeight = right.height;
403                adjacent.right = right;
404                right.parent = adjacent;
405                node.right = null;
406            }
407            adjacent.height = Math.max(leftHeight, rightHeight) + 1;
408            replaceInParent(node, adjacent);
409            return;
410        } else if (left != null) {
411            replaceInParent(node, left);
412            node.left = null;
413        } else if (right != null) {
414            replaceInParent(node, right);
415            node.right = null;
416        } else {
417            replaceInParent(node, null);
418        }
419
420        rebalance(originalParent, false);
421        size--;
422        modCount++;
423    }
424
425    Node<K, V> removeInternalByKey(Object key) {
426        Node<K, V> node = findByObject(key);
427        if (node != null) {
428            removeInternal(node);
429        }
430        return node;
431    }
432
433    private void replaceInParent(Node<K, V> node, Node<K, V> replacement) {
434        Node<K, V> parent = node.parent;
435        node.parent = null;
436        if (replacement != null) {
437            replacement.parent = parent;
438        }
439
440        if (parent != null) {
441            if (parent.left == node) {
442                parent.left = replacement;
443            } else {
444                assert (parent.right == node);
445                parent.right = replacement;
446            }
447        } else {
448            root = replacement;
449        }
450    }
451
452    /**
453     * Rebalances the tree by making any AVL rotations necessary between the
454     * newly-unbalanced node and the tree's root.
455     *
456     * @param insert true if the node was unbalanced by an insert; false if it
457     *     was by a removal.
458     */
459    private void rebalance(Node<K, V> unbalanced, boolean insert) {
460        for (Node<K, V> node = unbalanced; node != null; node = node.parent) {
461            Node<K, V> left = node.left;
462            Node<K, V> right = node.right;
463            int leftHeight = left != null ? left.height : 0;
464            int rightHeight = right != null ? right.height : 0;
465
466            int delta = leftHeight - rightHeight;
467            if (delta == -2) {
468                Node<K, V> rightLeft = right.left;
469                Node<K, V> rightRight = right.right;
470                int rightRightHeight = rightRight != null ? rightRight.height : 0;
471                int rightLeftHeight = rightLeft != null ? rightLeft.height : 0;
472
473                int rightDelta = rightLeftHeight - rightRightHeight;
474                if (rightDelta == -1 || (rightDelta == 0 && !insert)) {
475                    rotateLeft(node); // AVL right right
476                } else {
477                    assert (rightDelta == 1);
478                    rotateRight(right); // AVL right left
479                    rotateLeft(node);
480                }
481                if (insert) {
482                    break; // no further rotations will be necessary
483                }
484
485            } else if (delta == 2) {
486                Node<K, V> leftLeft = left.left;
487                Node<K, V> leftRight = left.right;
488                int leftRightHeight = leftRight != null ? leftRight.height : 0;
489                int leftLeftHeight = leftLeft != null ? leftLeft.height : 0;
490
491                int leftDelta = leftLeftHeight - leftRightHeight;
492                if (leftDelta == 1 || (leftDelta == 0 && !insert)) {
493                    rotateRight(node); // AVL left left
494                } else {
495                    assert (leftDelta == -1);
496                    rotateLeft(left); // AVL left right
497                    rotateRight(node);
498                }
499                if (insert) {
500                    break; // no further rotations will be necessary
501                }
502
503            } else if (delta == 0) {
504                node.height = leftHeight + 1; // leftHeight == rightHeight
505                if (insert) {
506                    break; // the insert caused balance, so rebalancing is done!
507                }
508
509            } else {
510                assert (delta == -1 || delta == 1);
511                node.height = Math.max(leftHeight, rightHeight) + 1;
512                if (!insert) {
513                    break; // the height hasn't changed, so rebalancing is done!
514                }
515            }
516        }
517    }
518
519    /**
520     * Rotates the subtree so that its root's right child is the new root.
521     */
522    private void rotateLeft(Node<K, V> root) {
523        Node<K, V> left = root.left;
524        Node<K, V> pivot = root.right;
525        Node<K, V> pivotLeft = pivot.left;
526        Node<K, V> pivotRight = pivot.right;
527
528        // move the pivot's left child to the root's right
529        root.right = pivotLeft;
530        if (pivotLeft != null) {
531            pivotLeft.parent = root;
532        }
533
534        replaceInParent(root, pivot);
535
536        // move the root to the pivot's left
537        pivot.left = root;
538        root.parent = pivot;
539
540        // fix heights
541        root.height = Math.max(left != null ? left.height : 0,
542                pivotLeft != null ? pivotLeft.height : 0) + 1;
543        pivot.height = Math.max(root.height,
544                pivotRight != null ? pivotRight.height : 0) + 1;
545    }
546
547    /**
548     * Rotates the subtree so that its root's left child is the new root.
549     */
550    private void rotateRight(Node<K, V> root) {
551        Node<K, V> pivot = root.left;
552        Node<K, V> right = root.right;
553        Node<K, V> pivotLeft = pivot.left;
554        Node<K, V> pivotRight = pivot.right;
555
556        // move the pivot's right child to the root's left
557        root.left = pivotRight;
558        if (pivotRight != null) {
559            pivotRight.parent = root;
560        }
561
562        replaceInParent(root, pivot);
563
564        // move the root to the pivot's right
565        pivot.right = root;
566        root.parent = pivot;
567
568        // fixup heights
569        root.height = Math.max(right != null ? right.height : 0,
570                pivotRight != null ? pivotRight.height : 0) + 1;
571        pivot.height = Math.max(root.height,
572                pivotLeft != null ? pivotLeft.height : 0) + 1;
573    }
574
575    /*
576     * Navigable methods.
577     */
578
579    /**
580     * Returns an immutable version of {@param entry}. Need this because we allow entry to be null,
581     * in which case we return a null SimpleImmutableEntry.
582     */
583    private SimpleImmutableEntry<K, V> immutableCopy(Entry<K, V> entry) {
584        return entry == null ? null : new SimpleImmutableEntry<K, V>(entry);
585    }
586
587    public Entry<K, V> firstEntry() {
588        return immutableCopy(root == null ? null : root.first());
589    }
590
591    private Entry<K, V> internalPollFirstEntry() {
592        if (root == null) {
593            return null;
594        }
595        Node<K, V> result = root.first();
596        removeInternal(result);
597        return result;
598    }
599
600    public Entry<K, V> pollFirstEntry() {
601        return immutableCopy(internalPollFirstEntry());
602    }
603
604    public K firstKey() {
605        if (root == null) {
606            throw new NoSuchElementException();
607        }
608        return root.first().getKey();
609    }
610
611    public Entry<K, V> lastEntry() {
612        return immutableCopy(root == null ? null : root.last());
613    }
614
615    private Entry<K, V> internalPollLastEntry() {
616        if (root == null) {
617            return null;
618        }
619        Node<K, V> result = root.last();
620        removeInternal(result);
621        return result;
622    }
623
624    public Entry<K, V> pollLastEntry() {
625        return immutableCopy(internalPollLastEntry());
626    }
627
628    public K lastKey() {
629        if (root == null) {
630            throw new NoSuchElementException();
631        }
632        return root.last().getKey();
633    }
634
635    public Entry<K, V> lowerEntry(K key) {
636        return immutableCopy(find(key, LOWER));
637    }
638
639    public K lowerKey(K key) {
640        Entry<K, V> entry = find(key, LOWER);
641        return entry != null ? entry.getKey() : null;
642    }
643
644    public Entry<K, V> floorEntry(K key) {
645        return immutableCopy(find(key, FLOOR));
646    }
647
648    public K floorKey(K key) {
649        Entry<K, V> entry = find(key, FLOOR);
650        return entry != null ? entry.getKey() : null;
651    }
652
653    public Entry<K, V> ceilingEntry(K key) {
654        return immutableCopy(find(key, CEILING));
655    }
656
657    public K ceilingKey(K key) {
658        Entry<K, V> entry = find(key, CEILING);
659        return entry != null ? entry.getKey() : null;
660    }
661
662    public Entry<K, V> higherEntry(K key) {
663        return immutableCopy(find(key, HIGHER));
664    }
665
666    public K higherKey(K key) {
667        Entry<K, V> entry = find(key, HIGHER);
668        return entry != null ? entry.getKey() : null;
669    }
670
671    public Comparator<? super K> comparator() {
672        return comparator != NATURAL_ORDER ? comparator : null;
673    }
674
675    /*
676     * View factory methods.
677     */
678
679    private EntrySet entrySet;
680    private KeySet keySet;
681
682    @Override public Set<Entry<K, V>> entrySet() {
683        EntrySet result = entrySet;
684        return result != null ? result : (entrySet = new EntrySet());
685    }
686
687    @Override public Set<K> keySet() {
688        KeySet result = keySet;
689        return result != null ? result : (keySet = new KeySet());
690    }
691
692    public NavigableSet<K> navigableKeySet() {
693        KeySet result = keySet;
694        return result != null ? result : (keySet = new KeySet());
695    }
696
697    public NavigableMap<K, V> subMap(K from, boolean fromInclusive, K to, boolean toInclusive) {
698        Bound fromBound = fromInclusive ? INCLUSIVE : EXCLUSIVE;
699        Bound toBound = toInclusive ? INCLUSIVE : EXCLUSIVE;
700        return new BoundedMap(true, from, fromBound, to, toBound);
701    }
702
703    public SortedMap<K, V> subMap(K fromInclusive, K toExclusive) {
704        return new BoundedMap(true, fromInclusive, INCLUSIVE, toExclusive, EXCLUSIVE);
705    }
706
707    public NavigableMap<K, V> headMap(K to, boolean inclusive) {
708        Bound toBound = inclusive ? INCLUSIVE : EXCLUSIVE;
709        return new BoundedMap(true, null, NO_BOUND, to, toBound);
710    }
711
712    public SortedMap<K, V> headMap(K toExclusive) {
713        return new BoundedMap(true, null, NO_BOUND, toExclusive, EXCLUSIVE);
714    }
715
716    public NavigableMap<K, V> tailMap(K from, boolean inclusive) {
717        Bound fromBound = inclusive ? INCLUSIVE : EXCLUSIVE;
718        return new BoundedMap(true, from, fromBound, null, NO_BOUND);
719    }
720
721    public SortedMap<K, V> tailMap(K fromInclusive) {
722        return new BoundedMap(true, fromInclusive, INCLUSIVE, null, NO_BOUND);
723    }
724
725    public NavigableMap<K, V> descendingMap() {
726        return new BoundedMap(false, null, NO_BOUND, null, NO_BOUND);
727    }
728
729    public NavigableSet<K> descendingKeySet() {
730        return new BoundedMap(false, null, NO_BOUND, null, NO_BOUND).navigableKeySet();
731    }
732
733    static class Node<K, V> implements Map.Entry<K, V> {
734        Node<K, V> parent;
735        Node<K, V> left;
736        Node<K, V> right;
737        final K key;
738        V value;
739        int height;
740
741        Node(Node<K, V> parent, K key) {
742            this.parent = parent;
743            this.key = key;
744            this.height = 1;
745        }
746
747        Node<K, V> copy(Node<K, V> parent) {
748            Node<K, V> result = new Node<K, V>(parent, key);
749            if (left != null) {
750                result.left = left.copy(result);
751            }
752            if (right != null) {
753                result.right = right.copy(result);
754            }
755            result.value = value;
756            result.height = height;
757            return result;
758        }
759
760        public K getKey() {
761            return key;
762        }
763
764        public V getValue() {
765            return value;
766        }
767
768        public V setValue(V value) {
769            V oldValue = this.value;
770            this.value = value;
771            return oldValue;
772        }
773
774        @Override public boolean equals(Object o) {
775            if (o instanceof Map.Entry) {
776                Map.Entry other = (Map.Entry) o;
777                return (key == null ? other.getKey() == null : key.equals(other.getKey()))
778                        && (value == null ? other.getValue() == null : value.equals(other.getValue()));
779            }
780            return false;
781        }
782
783        @Override public int hashCode() {
784            return (key == null ? 0 : key.hashCode())
785                    ^ (value == null ? 0 : value.hashCode());
786        }
787
788        @Override public String toString() {
789            return key + "=" + value;
790        }
791
792        /**
793         * Returns the next node in an inorder traversal, or null if this is the
794         * last node in the tree.
795         */
796        Node<K, V> next() {
797            if (right != null) {
798                return right.first();
799            }
800
801            Node<K, V> node = this;
802            Node<K, V> parent = node.parent;
803            while (parent != null) {
804                if (parent.left == node) {
805                    return parent;
806                }
807                node = parent;
808                parent = node.parent;
809            }
810            return null;
811        }
812
813        /**
814         * Returns the previous node in an inorder traversal, or null if this is
815         * the first node in the tree.
816         */
817        public Node<K, V> prev() {
818            if (left != null) {
819                return left.last();
820            }
821
822            Node<K, V> node = this;
823            Node<K, V> parent = node.parent;
824            while (parent != null) {
825                if (parent.right == node) {
826                    return parent;
827                }
828                node = parent;
829                parent = node.parent;
830            }
831            return null;
832        }
833
834        /**
835         * Returns the first node in this subtree.
836         */
837        public Node<K, V> first() {
838            Node<K, V> node = this;
839            Node<K, V> child = node.left;
840            while (child != null) {
841                node = child;
842                child = node.left;
843            }
844            return node;
845        }
846
847        /**
848         * Returns the last node in this subtree.
849         */
850        public Node<K, V> last() {
851            Node<K, V> node = this;
852            Node<K, V> child = node.right;
853            while (child != null) {
854                node = child;
855                child = node.right;
856            }
857            return node;
858        }
859    }
860
861    /**
862     * Walk the nodes of the tree left-to-right or right-to-left. Note that in
863     * descending iterations, {@code next} will return the previous node.
864     */
865    abstract class MapIterator<T> implements Iterator<T> {
866        protected Node<K, V> next;
867        protected Node<K, V> last;
868        protected int expectedModCount = modCount;
869
870        MapIterator(Node<K, V> next) {
871            this.next = next;
872        }
873
874        public boolean hasNext() {
875            return next != null;
876        }
877
878        protected Node<K, V> stepForward() {
879            if (next == null) {
880                throw new NoSuchElementException();
881            }
882            if (modCount != expectedModCount) {
883                throw new ConcurrentModificationException();
884            }
885            last = next;
886            next = next.next();
887            return last;
888        }
889
890        protected Node<K, V> stepBackward() {
891            if (next == null) {
892                throw new NoSuchElementException();
893            }
894            if (modCount != expectedModCount) {
895                throw new ConcurrentModificationException();
896            }
897            last = next;
898            next = next.prev();
899            return last;
900        }
901
902        public void remove() {
903            if (last == null) {
904                throw new IllegalStateException();
905            }
906            removeInternal(last);
907            expectedModCount = modCount;
908            last = null;
909        }
910    }
911
912    /*
913     * View implementations.
914     */
915
916    class EntrySet extends AbstractSet<Map.Entry<K, V>> {
917        @Override public int size() {
918            return size;
919        }
920
921        @Override public Iterator<Entry<K, V>> iterator() {
922            return new MapIterator<Entry<K, V>>(root == null ? null : root.first()) {
923                public Entry<K, V> next() {
924                    return stepForward();
925                }
926            };
927        }
928
929        @Override public boolean contains(Object o) {
930            return o instanceof Entry && findByEntry((Entry<?, ?>) o) != null;
931        }
932
933        @Override public boolean remove(Object o) {
934            if (!(o instanceof Entry)) {
935                return false;
936            }
937
938            Node<K, V> node = findByEntry((Entry<?, ?>) o);
939            if (node == null) {
940                return false;
941            }
942            removeInternal(node);
943            return true;
944        }
945
946        @Override public void clear() {
947            TreeMap.this.clear();
948        }
949    }
950
951    class KeySet extends AbstractSet<K> implements NavigableSet<K> {
952        @Override public int size() {
953            return size;
954        }
955
956        @Override public Iterator<K> iterator() {
957            return new MapIterator<K>(root == null ? null : root.first()) {
958                public K next() {
959                    return stepForward().key;
960                }
961            };
962        }
963
964        public Iterator<K> descendingIterator() {
965            return new MapIterator<K>(root == null ? null : root.last()) {
966                public K next() {
967                    return stepBackward().key;
968                }
969            };
970        }
971
972        @Override public boolean contains(Object o) {
973            return containsKey(o);
974        }
975
976        @Override public boolean remove(Object key) {
977            return removeInternalByKey(key) != null;
978        }
979
980        @Override public void clear() {
981            TreeMap.this.clear();
982        }
983
984        public Comparator<? super K> comparator() {
985            return TreeMap.this.comparator();
986        }
987
988        /*
989         * Navigable methods.
990         */
991
992        public K first() {
993            return firstKey();
994        }
995
996        public K last() {
997            return lastKey();
998        }
999
1000        public K lower(K key) {
1001            return lowerKey(key);
1002        }
1003
1004        public K floor(K key) {
1005            return floorKey(key);
1006        }
1007
1008        public K ceiling(K key) {
1009            return ceilingKey(key);
1010        }
1011
1012        public K higher(K key) {
1013            return higherKey(key);
1014        }
1015
1016        public K pollFirst() {
1017            Entry<K, V> entry = internalPollFirstEntry();
1018            return entry != null ? entry.getKey() : null;
1019        }
1020
1021        public K pollLast() {
1022            Entry<K, V> entry = internalPollLastEntry();
1023            return entry != null ? entry.getKey() : null;
1024        }
1025
1026        /*
1027         * View factory methods.
1028         */
1029
1030        public NavigableSet<K> subSet(K from, boolean fromInclusive, K to, boolean toInclusive) {
1031            return TreeMap.this.subMap(from, fromInclusive, to, toInclusive).navigableKeySet();
1032        }
1033
1034        public SortedSet<K> subSet(K fromInclusive, K toExclusive) {
1035            return TreeMap.this.subMap(fromInclusive, true, toExclusive, false).navigableKeySet();
1036        }
1037
1038        public NavigableSet<K> headSet(K to, boolean inclusive) {
1039            return TreeMap.this.headMap(to, inclusive).navigableKeySet();
1040        }
1041
1042        public SortedSet<K> headSet(K toExclusive) {
1043            return TreeMap.this.headMap(toExclusive, false).navigableKeySet();
1044        }
1045
1046        public NavigableSet<K> tailSet(K from, boolean inclusive) {
1047            return TreeMap.this.tailMap(from, inclusive).navigableKeySet();
1048        }
1049
1050        public SortedSet<K> tailSet(K fromInclusive) {
1051            return TreeMap.this.tailMap(fromInclusive, true).navigableKeySet();
1052        }
1053
1054        public NavigableSet<K> descendingSet() {
1055            return new BoundedMap(false, null, NO_BOUND, null, NO_BOUND).navigableKeySet();
1056        }
1057    }
1058
1059    /*
1060     * Bounded views implementations.
1061     */
1062
1063    enum Bound {
1064        INCLUSIVE {
1065            @Override public String leftCap(Object from) {
1066                return "[" + from;
1067            }
1068            @Override public String rightCap(Object to) {
1069                return to + "]";
1070            }
1071        },
1072        EXCLUSIVE {
1073            @Override public String leftCap(Object from) {
1074                return "(" + from;
1075            }
1076            @Override public String rightCap(Object to) {
1077                return to + ")";
1078            }
1079        },
1080        NO_BOUND {
1081            @Override public String leftCap(Object from) {
1082                return ".";
1083            }
1084            @Override public String rightCap(Object to) {
1085                return ".";
1086            }
1087        };
1088
1089        public abstract String leftCap(Object from);
1090        public abstract String rightCap(Object to);
1091    }
1092
1093    /**
1094     * A map with optional limits on its range.
1095     */
1096    final class BoundedMap extends AbstractMap<K, V> implements NavigableMap<K, V>, Serializable {
1097        private final transient boolean ascending;
1098        private final transient K from;
1099        private final transient Bound fromBound;
1100        private final transient K to;
1101        private final transient Bound toBound;
1102
1103        BoundedMap(boolean ascending, K from, Bound fromBound, K to, Bound toBound) {
1104            /*
1105             * Validate the bounds. In addition to checking that from <= to, we
1106             * verify that the comparator supports our bound objects.
1107             */
1108            if (fromBound != NO_BOUND && toBound != NO_BOUND) {
1109                if (comparator.compare(from, to) > 0) {
1110                    throw new IllegalArgumentException(from + " > " + to);
1111                }
1112            } else if (fromBound != NO_BOUND) {
1113                comparator.compare(from, from);
1114            } else if (toBound != NO_BOUND) {
1115                comparator.compare(to, to);
1116            }
1117
1118            this.ascending = ascending;
1119            this.from = from;
1120            this.fromBound = fromBound;
1121            this.to = to;
1122            this.toBound = toBound;
1123        }
1124
1125        @Override public int size() {
1126            return count(entrySet().iterator());
1127        }
1128
1129        @Override public boolean isEmpty() {
1130            return endpoint(true) == null;
1131        }
1132
1133        @Override public V get(Object key) {
1134            return isInBounds(key) ? TreeMap.this.get(key) : null;
1135        }
1136
1137        @Override public boolean containsKey(Object key) {
1138            return isInBounds(key) && TreeMap.this.containsKey(key);
1139        }
1140
1141        @Override public V put(K key, V value) {
1142            if (!isInBounds(key)) {
1143                throw outOfBounds(key, fromBound, toBound);
1144            }
1145            return putInternal(key, value);
1146        }
1147
1148        @Override public V remove(Object key) {
1149            return isInBounds(key) ? TreeMap.this.remove(key) : null;
1150        }
1151
1152        /**
1153         * Returns true if the key is in bounds.
1154         */
1155        @SuppressWarnings("unchecked") // this method throws ClassCastExceptions!
1156        private boolean isInBounds(Object key) {
1157            return isInBounds((K) key, fromBound, toBound);
1158        }
1159
1160        /**
1161         * Returns true if the key is in bounds. Use this overload with
1162         * NO_BOUND to skip bounds checking on either end.
1163         */
1164        private boolean isInBounds(K key, Bound fromBound, Bound toBound) {
1165            if (fromBound == INCLUSIVE) {
1166                if (comparator.compare(key, from) < 0) {
1167                    return false; // less than from
1168                }
1169            } else if (fromBound == EXCLUSIVE) {
1170                if (comparator.compare(key, from) <= 0) {
1171                    return false; // less than or equal to from
1172                }
1173            }
1174
1175            if (toBound == INCLUSIVE) {
1176                if (comparator.compare(key, to) > 0) {
1177                    return false; // greater than 'to'
1178                }
1179            } else if (toBound == EXCLUSIVE) {
1180                if (comparator.compare(key, to) >= 0) {
1181                    return false; // greater than or equal to 'to'
1182                }
1183            }
1184
1185            return true;
1186        }
1187
1188        /**
1189         * Returns the entry if it is in bounds, or null if it is out of bounds.
1190         */
1191        private Node<K, V> bound(Node<K, V> node, Bound fromBound, Bound toBound) {
1192            return node != null && isInBounds(node.getKey(), fromBound, toBound) ? node : null;
1193        }
1194
1195        /*
1196         * Navigable methods.
1197         */
1198
1199        public Entry<K, V> firstEntry() {
1200            return immutableCopy(endpoint(true));
1201        }
1202
1203        public Entry<K, V> pollFirstEntry() {
1204            Node<K, V> result = endpoint(true);
1205            if (result != null) {
1206                removeInternal(result);
1207            }
1208            return immutableCopy(result);
1209        }
1210
1211        public K firstKey() {
1212            Entry<K, V> entry = endpoint(true);
1213            if (entry == null) {
1214                throw new NoSuchElementException();
1215            }
1216            return entry.getKey();
1217        }
1218
1219        public Entry<K, V> lastEntry() {
1220            return immutableCopy(endpoint(false));
1221        }
1222
1223        public Entry<K, V> pollLastEntry() {
1224            Node<K, V> result = endpoint(false);
1225            if (result != null) {
1226                removeInternal(result);
1227            }
1228            return immutableCopy(result);
1229        }
1230
1231        public K lastKey() {
1232            Entry<K, V> entry = endpoint(false);
1233            if (entry == null) {
1234                throw new NoSuchElementException();
1235            }
1236            return entry.getKey();
1237        }
1238
1239        /**
1240         * @param first true for the first element, false for the last.
1241         */
1242        private Node<K, V> endpoint(boolean first) {
1243            Node<K, V> node;
1244            if (ascending == first) {
1245                switch (fromBound) {
1246                    case NO_BOUND:
1247                        node = root == null ? null : root.first();
1248                        break;
1249                    case INCLUSIVE:
1250                        node = find(from, CEILING);
1251                        break;
1252                    case EXCLUSIVE:
1253                        node = find(from, HIGHER);
1254                        break;
1255                    default:
1256                        throw new AssertionError();
1257                }
1258                return bound(node, NO_BOUND, toBound);
1259            } else {
1260                switch (toBound) {
1261                    case NO_BOUND:
1262                        node = root == null ? null : root.last();
1263                        break;
1264                    case INCLUSIVE:
1265                        node = find(to, FLOOR);
1266                        break;
1267                    case EXCLUSIVE:
1268                        node = find(to, LOWER);
1269                        break;
1270                    default:
1271                        throw new AssertionError();
1272                }
1273                return bound(node, fromBound, NO_BOUND);
1274            }
1275        }
1276
1277        /**
1278         * Performs a find on the underlying tree after constraining it to the
1279         * bounds of this view. Examples:
1280         *
1281         *   bound is (A..C)
1282         *   findBounded(B, FLOOR) stays source.find(B, FLOOR)
1283         *
1284         *   bound is (A..C)
1285         *   findBounded(C, FLOOR) becomes source.find(C, LOWER)
1286         *
1287         *   bound is (A..C)
1288         *   findBounded(D, LOWER) becomes source.find(C, LOWER)
1289         *
1290         *   bound is (A..C]
1291         *   findBounded(D, FLOOR) becomes source.find(C, FLOOR)
1292         *
1293         *   bound is (A..C]
1294         *   findBounded(D, LOWER) becomes source.find(C, FLOOR)
1295         */
1296        private Entry<K, V> findBounded(K key, Relation relation) {
1297            relation = relation.forOrder(ascending);
1298            Bound fromBoundForCheck = fromBound;
1299            Bound toBoundForCheck = toBound;
1300
1301            if (toBound != NO_BOUND && (relation == LOWER || relation == FLOOR)) {
1302                int comparison = comparator.compare(to, key);
1303                if (comparison <= 0) {
1304                    key = to;
1305                    if (toBound == EXCLUSIVE) {
1306                        relation = LOWER; // 'to' is too high
1307                    } else if (comparison < 0) {
1308                        relation = FLOOR; // we already went lower
1309                    }
1310                }
1311                toBoundForCheck = NO_BOUND; // we've already checked the upper bound
1312            }
1313
1314            if (fromBound != NO_BOUND && (relation == CEILING || relation == HIGHER)) {
1315                int comparison = comparator.compare(from, key);
1316                if (comparison >= 0) {
1317                    key = from;
1318                    if (fromBound == EXCLUSIVE) {
1319                        relation = HIGHER; // 'from' is too low
1320                    } else if (comparison > 0) {
1321                        relation = CEILING; // we already went higher
1322                    }
1323                }
1324                fromBoundForCheck = NO_BOUND; // we've already checked the lower bound
1325            }
1326
1327            return bound(find(key, relation), fromBoundForCheck, toBoundForCheck);
1328        }
1329
1330        public Entry<K, V> lowerEntry(K key) {
1331            return immutableCopy(findBounded(key, LOWER));
1332        }
1333
1334        public K lowerKey(K key) {
1335            Entry<K, V> entry = findBounded(key, LOWER);
1336            return entry != null ? entry.getKey() : null;
1337        }
1338
1339        public Entry<K, V> floorEntry(K key) {
1340            return immutableCopy(findBounded(key, FLOOR));
1341        }
1342
1343        public K floorKey(K key) {
1344            Entry<K, V> entry = findBounded(key, FLOOR);
1345            return entry != null ? entry.getKey() : null;
1346        }
1347
1348        public Entry<K, V> ceilingEntry(K key) {
1349            return immutableCopy(findBounded(key, CEILING));
1350        }
1351
1352        public K ceilingKey(K key) {
1353            Entry<K, V> entry = findBounded(key, CEILING);
1354            return entry != null ? entry.getKey() : null;
1355        }
1356
1357        public Entry<K, V> higherEntry(K key) {
1358            return immutableCopy(findBounded(key, HIGHER));
1359        }
1360
1361        public K higherKey(K key) {
1362            Entry<K, V> entry = findBounded(key, HIGHER);
1363            return entry != null ? entry.getKey() : null;
1364        }
1365
1366        public Comparator<? super K> comparator() {
1367            Comparator<? super K> forward = TreeMap.this.comparator();
1368            if (ascending) {
1369                return forward;
1370            } else {
1371                return Collections.reverseOrder(forward);
1372            }
1373        }
1374
1375        /*
1376         * View factory methods.
1377         */
1378
1379        private transient BoundedEntrySet entrySet;
1380        private transient BoundedKeySet keySet;
1381
1382        @Override public Set<Entry<K, V>> entrySet() {
1383            BoundedEntrySet result = entrySet;
1384            return result != null ? result : (entrySet = new BoundedEntrySet());
1385        }
1386
1387        @Override public Set<K> keySet() {
1388            return navigableKeySet();
1389        }
1390
1391        public NavigableSet<K> navigableKeySet() {
1392            BoundedKeySet result = keySet;
1393            return result != null ? result : (keySet = new BoundedKeySet());
1394        }
1395
1396        public NavigableMap<K, V> descendingMap() {
1397            return new BoundedMap(!ascending, from, fromBound, to, toBound);
1398        }
1399
1400        public NavigableSet<K> descendingKeySet() {
1401            return new BoundedMap(!ascending, from, fromBound, to, toBound).navigableKeySet();
1402        }
1403
1404        public NavigableMap<K, V> subMap(K from, boolean fromInclusive, K to, boolean toInclusive) {
1405            Bound fromBound = fromInclusive ? INCLUSIVE : EXCLUSIVE;
1406            Bound toBound = toInclusive ? INCLUSIVE : EXCLUSIVE;
1407            return subMap(from, fromBound, to, toBound);
1408        }
1409
1410        public NavigableMap<K, V> subMap(K fromInclusive, K toExclusive) {
1411            return subMap(fromInclusive, INCLUSIVE, toExclusive, EXCLUSIVE);
1412        }
1413
1414        public NavigableMap<K, V> headMap(K to, boolean inclusive) {
1415            Bound toBound = inclusive ? INCLUSIVE : EXCLUSIVE;
1416            return subMap(null, NO_BOUND, to, toBound);
1417        }
1418
1419        public NavigableMap<K, V> headMap(K toExclusive) {
1420            return subMap(null, NO_BOUND, toExclusive, EXCLUSIVE);
1421        }
1422
1423        public NavigableMap<K, V> tailMap(K from, boolean inclusive) {
1424            Bound fromBound = inclusive ? INCLUSIVE : EXCLUSIVE;
1425            return subMap(from, fromBound, null, NO_BOUND);
1426        }
1427
1428        public NavigableMap<K, V> tailMap(K fromInclusive) {
1429            return subMap(fromInclusive, INCLUSIVE, null, NO_BOUND);
1430        }
1431
1432        private NavigableMap<K, V> subMap(K from, Bound fromBound, K to, Bound toBound) {
1433            if (!ascending) {
1434                K fromTmp = from;
1435                Bound fromBoundTmp = fromBound;
1436                from = to;
1437                fromBound = toBound;
1438                to = fromTmp;
1439                toBound = fromBoundTmp;
1440            }
1441
1442            /*
1443             * If both the current and requested bounds are exclusive, the isInBounds check must be
1444             * inclusive. For example, to create (C..F) from (A..F), the bound 'F' is in bounds.
1445             */
1446
1447            if (fromBound == NO_BOUND) {
1448                from = this.from;
1449                fromBound = this.fromBound;
1450            } else {
1451                Bound fromBoundToCheck = fromBound == this.fromBound ? INCLUSIVE : this.fromBound;
1452                if (!isInBounds(from, fromBoundToCheck, this.toBound)) {
1453                    throw outOfBounds(to, fromBoundToCheck, this.toBound);
1454                }
1455            }
1456
1457            if (toBound == NO_BOUND) {
1458                to = this.to;
1459                toBound = this.toBound;
1460            } else {
1461                Bound toBoundToCheck = toBound == this.toBound ? INCLUSIVE : this.toBound;
1462                if (!isInBounds(to, this.fromBound, toBoundToCheck)) {
1463                    throw outOfBounds(to, this.fromBound, toBoundToCheck);
1464                }
1465            }
1466
1467            return new BoundedMap(ascending, from, fromBound, to, toBound);
1468        }
1469
1470        private IllegalArgumentException outOfBounds(Object value, Bound fromBound, Bound toBound) {
1471            return new IllegalArgumentException(value + " not in range "
1472                    + fromBound.leftCap(from) + ".." + toBound.rightCap(to));
1473        }
1474
1475        /*
1476         * Bounded view implementations.
1477         */
1478
1479        abstract class BoundedIterator<T> extends MapIterator<T> {
1480            protected BoundedIterator(Node<K, V> next) {
1481                super(next);
1482            }
1483
1484            @Override protected Node<K, V> stepForward() {
1485                Node<K, V> result = super.stepForward();
1486                if (next != null && !isInBounds(next.key, NO_BOUND, toBound)) {
1487                    next = null;
1488                }
1489                return result;
1490            }
1491
1492            @Override protected Node<K, V> stepBackward() {
1493                Node<K, V> result = super.stepBackward();
1494                if (next != null && !isInBounds(next.key, fromBound, NO_BOUND)) {
1495                    next = null;
1496                }
1497                return result;
1498            }
1499        }
1500
1501        final class BoundedEntrySet extends AbstractSet<Entry<K, V>> {
1502            @Override public int size() {
1503                return BoundedMap.this.size();
1504            }
1505
1506            @Override public boolean isEmpty() {
1507                return BoundedMap.this.isEmpty();
1508            }
1509
1510            @Override public Iterator<Entry<K, V>> iterator() {
1511                return new BoundedIterator<Entry<K, V>>(endpoint(true)) {
1512                    public Entry<K, V> next() {
1513                        return ascending ? stepForward() : stepBackward();
1514                    }
1515                };
1516            }
1517
1518            @Override public boolean contains(Object o) {
1519                if (!(o instanceof Entry)) {
1520                    return false;
1521                }
1522                Entry<?, ?> entry = (Entry<?, ?>) o;
1523                return isInBounds(entry.getKey()) && findByEntry(entry) != null;
1524            }
1525
1526            @Override public boolean remove(Object o) {
1527                if (!(o instanceof Entry)) {
1528                    return false;
1529                }
1530                Entry<?, ?> entry = (Entry<?, ?>) o;
1531                return isInBounds(entry.getKey()) && TreeMap.this.entrySet().remove(entry);
1532            }
1533        }
1534
1535        final class BoundedKeySet extends AbstractSet<K> implements NavigableSet<K> {
1536            @Override public int size() {
1537                return BoundedMap.this.size();
1538            }
1539
1540            @Override public boolean isEmpty() {
1541                return BoundedMap.this.isEmpty();
1542            }
1543
1544            @Override public Iterator<K> iterator() {
1545                return new BoundedIterator<K>(endpoint(true)) {
1546                    public K next() {
1547                        return (ascending ? stepForward() : stepBackward()).key;
1548                    }
1549                };
1550            }
1551
1552            public Iterator<K> descendingIterator() {
1553                return new BoundedIterator<K>(endpoint(false)) {
1554                    public K next() {
1555                        return (ascending ? stepBackward() : stepForward()).key;
1556                    }
1557                };
1558            }
1559
1560            @Override public boolean contains(Object key) {
1561                return isInBounds(key) && findByObject(key) != null;
1562            }
1563
1564            @Override public boolean remove(Object key) {
1565                return isInBounds(key) && removeInternalByKey(key) != null;
1566            }
1567
1568            /*
1569             * Navigable methods.
1570             */
1571
1572            public K first() {
1573                return firstKey();
1574            }
1575
1576            public K pollFirst() {
1577                Entry<K, ?> entry = pollFirstEntry();
1578                return entry != null ? entry.getKey() : null;
1579            }
1580
1581            public K last() {
1582                return lastKey();
1583            }
1584
1585            public K pollLast() {
1586                Entry<K, ?> entry = pollLastEntry();
1587                return entry != null ? entry.getKey() : null;
1588            }
1589
1590            public K lower(K key) {
1591                return lowerKey(key);
1592            }
1593
1594            public K floor(K key) {
1595                return floorKey(key);
1596            }
1597
1598            public K ceiling(K key) {
1599                return ceilingKey(key);
1600            }
1601
1602            public K higher(K key) {
1603                return higherKey(key);
1604            }
1605
1606            public Comparator<? super K> comparator() {
1607                return BoundedMap.this.comparator();
1608            }
1609
1610            /*
1611             * View factory methods.
1612             */
1613
1614            public NavigableSet<K> subSet(K from, boolean fromInclusive, K to, boolean toInclusive) {
1615                return subMap(from, fromInclusive, to, toInclusive).navigableKeySet();
1616            }
1617
1618            public SortedSet<K> subSet(K fromInclusive, K toExclusive) {
1619                return subMap(fromInclusive, toExclusive).navigableKeySet();
1620            }
1621
1622            public NavigableSet<K> headSet(K to, boolean inclusive) {
1623                return headMap(to, inclusive).navigableKeySet();
1624            }
1625
1626            public SortedSet<K> headSet(K toExclusive) {
1627                return headMap(toExclusive).navigableKeySet();
1628            }
1629
1630            public NavigableSet<K> tailSet(K from, boolean inclusive) {
1631                return tailMap(from, inclusive).navigableKeySet();
1632            }
1633
1634            public SortedSet<K> tailSet(K fromInclusive) {
1635                return tailMap(fromInclusive).navigableKeySet();
1636            }
1637
1638            public NavigableSet<K> descendingSet() {
1639                return new BoundedMap(!ascending, from, fromBound, to, toBound).navigableKeySet();
1640            }
1641        }
1642
1643        Object writeReplace() throws ObjectStreamException {
1644            return ascending
1645                    ? new AscendingSubMap<K, V>(TreeMap.this, from, fromBound, to, toBound)
1646                    : new DescendingSubMap<K, V>(TreeMap.this, from, fromBound, to, toBound);
1647        }
1648    }
1649
1650    /**
1651     * Returns the number of elements in the iteration.
1652     */
1653    static int count(Iterator<?> iterator) {
1654        int count = 0;
1655        while (iterator.hasNext()) {
1656            iterator.next();
1657            count++;
1658        }
1659        return count;
1660    }
1661
1662    /*
1663     * Serialization
1664     */
1665
1666    private static final long serialVersionUID = 919286545866124006L;
1667
1668    private void writeObject(ObjectOutputStream stream) throws IOException {
1669        stream.putFields().put("comparator", comparator());
1670        stream.writeFields();
1671        stream.writeInt(size);
1672        for (Map.Entry<K, V> entry : entrySet()) {
1673            stream.writeObject(entry.getKey());
1674            stream.writeObject(entry.getValue());
1675        }
1676    }
1677
1678    @SuppressWarnings("unchecked") // we have to trust that keys are Ks and values are Vs
1679    private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
1680        GetField fields = stream.readFields();
1681        comparator = (Comparator<? super K>) fields.get("comparator", null);
1682        if (comparator == null) {
1683            comparator = (Comparator<? super K>) NATURAL_ORDER;
1684        }
1685        int size = stream.readInt();
1686        for (int i = 0; i < size; i++) {
1687            putInternal((K) stream.readObject(), (V) stream.readObject());
1688        }
1689    }
1690
1691    static abstract class NavigableSubMap<K, V> extends AbstractMap<K, V> implements Serializable {
1692        private static final long serialVersionUID = -2102997345730753016L;
1693        TreeMap<K, V> m;
1694        Object lo;
1695        Object hi;
1696        boolean fromStart;
1697        boolean toEnd;
1698        boolean loInclusive;
1699        boolean hiInclusive;
1700
1701        NavigableSubMap(TreeMap<K, V> delegate, K from, Bound fromBound, K to, Bound toBound) {
1702            this.m = delegate;
1703            this.lo = from;
1704            this.hi = to;
1705            this.fromStart = fromBound == NO_BOUND;
1706            this.toEnd = toBound == NO_BOUND;
1707            this.loInclusive = fromBound == INCLUSIVE;
1708            this.hiInclusive = toBound == INCLUSIVE;
1709        }
1710
1711        @Override public Set<Entry<K, V>> entrySet() {
1712            throw new UnsupportedOperationException();
1713        }
1714
1715        @SuppressWarnings("unchecked") // we have to trust that the bounds are Ks
1716        protected Object readResolve() throws ObjectStreamException {
1717            Bound fromBound = fromStart ? NO_BOUND : (loInclusive ? INCLUSIVE : EXCLUSIVE);
1718            Bound toBound = toEnd ? NO_BOUND : (hiInclusive ? INCLUSIVE : EXCLUSIVE);
1719            boolean ascending = !(this instanceof DescendingSubMap);
1720            return m.new BoundedMap(ascending, (K) lo, fromBound, (K) hi, toBound);
1721        }
1722    }
1723
1724    static class DescendingSubMap<K, V> extends NavigableSubMap<K, V> {
1725        private static final long serialVersionUID = 912986545866120460L;
1726        Comparator<K> reverseComparator;
1727        DescendingSubMap(TreeMap<K, V> delegate, K from, Bound fromBound, K to, Bound toBound) {
1728            super(delegate, from, fromBound, to, toBound);
1729        }
1730    }
1731
1732    static class AscendingSubMap<K, V> extends NavigableSubMap<K, V> {
1733        private static final long serialVersionUID = 912986545866124060L;
1734        AscendingSubMap(TreeMap<K, V> delegate, K from, Bound fromBound, K to, Bound toBound) {
1735            super(delegate, from, fromBound, to, toBound);
1736        }
1737    }
1738
1739    class SubMap extends AbstractMap<K, V> implements Serializable {
1740        private static final long serialVersionUID = -6520786458950516097L;
1741        Object fromKey;
1742        Object toKey;
1743        boolean fromStart;
1744        boolean toEnd;
1745
1746        @Override public Set<Entry<K, V>> entrySet() {
1747            throw new UnsupportedOperationException();
1748        }
1749
1750        @SuppressWarnings("unchecked") // we have to trust that the bounds are Ks
1751        protected Object readResolve() throws ObjectStreamException {
1752            Bound fromBound = fromStart ? NO_BOUND : INCLUSIVE;
1753            Bound toBound = toEnd ? NO_BOUND : EXCLUSIVE;
1754            return new BoundedMap(true, (K) fromKey, fromBound, (K) toKey, toBound);
1755        }
1756    }
1757}
1758