1090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2009 The Guava Authors 3090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 4090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * you may not use this file except in compliance with the License. 6090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * You may obtain a copy of the License at 7090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 8090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 10090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * See the License for the specific language governing permissions and 14090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * limitations under the License. 15090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 16090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 17090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpackage com.google.common.collect; 18090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 19090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport static com.google.common.base.Preconditions.checkArgument; 20090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport static com.google.common.base.Preconditions.checkNotNull; 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.collect.SortedLists.KeyAbsentBehavior.INVERTED_INSERTION_INDEX; 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.collect.SortedLists.KeyAbsentBehavior.NEXT_HIGHER; 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.collect.SortedLists.KeyAbsentBehavior.NEXT_LOWER; 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.collect.SortedLists.KeyPresentBehavior.ANY_PRESENT; 25090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 26090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.annotations.GwtCompatible; 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.collect.SortedLists.KeyAbsentBehavior; 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.collect.SortedLists.KeyPresentBehavior; 29090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 30090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.Serializable; 31090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Arrays; 32090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Collections; 33090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Comparator; 34090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.List; 35090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Map; 36090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.NoSuchElementException; 37090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.SortedMap; 38090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.TreeMap; 39090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 40090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport javax.annotation.Nullable; 41090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 42090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/** 43090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * An immutable {@link SortedMap}. Does not permit null keys or values. 44090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 45090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Unlike {@link Collections#unmodifiableSortedMap}, which is a <i>view</i> 46090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * of a separate map which can still change, an instance of {@code 47090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ImmutableSortedMap} contains its own data and will <i>never</i> change. 48090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code ImmutableSortedMap} is convenient for {@code public static final} maps 49090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ("constant maps") and also lets you easily make a "defensive copy" of a map 50090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * provided to your class by a caller. 51090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p><b>Note:</b> Although this class is not final, it cannot be subclassed as 53090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * it has no public or protected constructors. Thus, instances of this class are 54090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * guaranteed to be immutable. 55090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 56090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Jared Levy 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Louis Wasserman 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 (imported from Google Collections Library) 59090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible(serializable = true, emulated = true) 61090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpublic class ImmutableSortedMap<K, V> 62090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson extends ImmutableSortedMapFauxverideShim<K, V> implements SortedMap<K, V> { 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * TODO(kevinb): Confirm that ImmutableSortedMap is faster to construct and 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * uses less memory than TreeMap; then say so in the class Javadoc. 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * TODO(kevinb): Create separate subclasses for empty, single-entry, and 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * multiple-entry instances, if it's deemed beneficial. 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 70090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final Comparator<Comparable> NATURAL_ORDER = 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Ordering.natural(); 73090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final ImmutableSortedMap<Comparable, Object> 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert NATURAL_EMPTY_MAP = 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert new ImmutableSortedMap<Comparable, Object>( 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ImmutableList.<Entry<Comparable, Object>>of(), NATURAL_ORDER); 78090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 79090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 80090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns the empty sorted map. 81090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 82090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // unsafe, comparator() returns a comparator on the specified type 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(kevinb): evaluate whether or not of().comparator() should return null 85090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K, V> ImmutableSortedMap<K, V> of() { 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (ImmutableSortedMap<K, V>) NATURAL_EMPTY_MAP; 87090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 88090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 90090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static <K, V> ImmutableSortedMap<K, V> emptyMap( 91090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Comparator<? super K> comparator) { 92090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (NATURAL_ORDER.equals(comparator)) { 931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (ImmutableSortedMap<K, V>) NATURAL_EMPTY_MAP; 94090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new ImmutableSortedMap<K, V>( 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ImmutableList.<Entry<K, V>>of(), comparator); 97090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 98090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 99090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 100090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 101090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable map containing a single entry. 102090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <K extends Comparable<? super K>, V> 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ImmutableSortedMap<K, V> of(K k1, V v1) { 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new ImmutableSortedMap<K, V>( 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ImmutableList.of(entryOf(k1, v1)), Ordering.natural()); 107090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 108090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 109090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 110090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable sorted map containing the given entries, sorted by the 111090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * natural ordering of their keys. 112090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 113090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if the two keys are equal according to 114090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * their natural ordering 115090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 116090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> 117090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson of(K k1, V v1, K k2, V v2) { 118090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Builder<K, V>(Ordering.natural()) 119090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson .put(k1, v1).put(k2, v2).build(); 120090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 121090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 122090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 123090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable sorted map containing the given entries, sorted by the 124090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * natural ordering of their keys. 125090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 126090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if any two keys are equal according to 127090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * their natural ordering 128090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 129090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> 130090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson of(K k1, V v1, K k2, V v2, K k3, V v3) { 131090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Builder<K, V>(Ordering.natural()) 132090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson .put(k1, v1).put(k2, v2).put(k3, v3).build(); 133090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 134090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 135090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 136090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable sorted map containing the given entries, sorted by the 137090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * natural ordering of their keys. 138090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 139090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if any two keys are equal according to 140090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * their natural ordering 141090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 142090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> 143090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) { 144090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Builder<K, V>(Ordering.natural()) 145090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson .put(k1, v1).put(k2, v2).put(k3, v3).put(k4, v4).build(); 146090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 147090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 148090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 149090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable sorted map containing the given entries, sorted by the 150090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * natural ordering of their keys. 151090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 152090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if any two keys are equal according to 153090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * their natural ordering 154090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 155090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> 156090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) { 157090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Builder<K, V>(Ordering.natural()) 158090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson .put(k1, v1).put(k2, v2).put(k3, v3).put(k4, v4).put(k5, v5).build(); 159090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 160090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 161090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 162090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable map containing the same entries as {@code map}, sorted 163090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * by the natural ordering of the keys. 164090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Despite the method name, this method attempts to avoid actually copying 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the data when it is safe to do so. The exact circumstances under which a 1671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * copy will or will not be performed are undocumented and subject to change. 168090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 169090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>This method is not type-safe, as it may be called on a map with keys 170090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * that are not mutually comparable. 171090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 172090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws ClassCastException if the keys in {@code map} are not mutually 1731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * comparable 174090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if any key or value in {@code map} is null 175090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if any two keys are equal according to 1761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * their natural ordering 177090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 178090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K, V> ImmutableSortedMap<K, V> copyOf( 179090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Map<? extends K, ? extends V> map) { 180090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Hack around K not being a subtype of Comparable. 181090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Unsafe, see ImmutableSortedSetFauxverideShim. 182090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 1831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Ordering<K> naturalOrder = (Ordering<K>) Ordering.<Comparable>natural(); 184090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return copyOfInternal(map, naturalOrder); 185090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 186090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 187090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 188090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable map containing the same entries as {@code map}, with 189090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * keys sorted by the provided comparator. 190090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 1911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Despite the method name, this method attempts to avoid actually copying 1921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the data when it is safe to do so. The exact circumstances under which a 1931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * copy will or will not be performed are undocumented and subject to change. 194090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 195090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if any key or value in {@code map} is null 1961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if any two keys are equal according to the 1971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * comparator 198090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 199090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K, V> ImmutableSortedMap<K, V> copyOf( 200090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Map<? extends K, ? extends V> map, Comparator<? super K> comparator) { 201090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return copyOfInternal(map, checkNotNull(comparator)); 202090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 203090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 204090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 205090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable map containing the same entries as the provided sorted 206090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * map, with the same ordering. 207090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 2081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Despite the method name, this method attempts to avoid actually copying 2091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the data when it is safe to do so. The exact circumstances under which a 2101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * copy will or will not be performed are undocumented and subject to change. 211090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 212090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if any key or value in {@code map} is null 213090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 2141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 215090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K, V> ImmutableSortedMap<K, V> copyOfSorted( 216090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson SortedMap<K, ? extends V> map) { 2171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Comparator<? super K> comparator = map.comparator(); 2181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (comparator == null) { 2191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // If map has a null comparator, the keys should have a natural ordering, 2201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // even though K doesn't explicitly implement Comparable. 2211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert comparator = (Comparator<? super K>) NATURAL_ORDER; 2221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 223090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return copyOfInternal(map, comparator); 224090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 225090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 226090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static <K, V> ImmutableSortedMap<K, V> copyOfInternal( 227090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Map<? extends K, ? extends V> map, Comparator<? super K> comparator) { 228090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean sameComparator = false; 229090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (map instanceof SortedMap) { 230090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson SortedMap<?, ?> sortedMap = (SortedMap<?, ?>) map; 231090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Comparator<?> comparator2 = sortedMap.comparator(); 232090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson sameComparator = (comparator2 == null) 2331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ? comparator == NATURAL_ORDER 234090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson : comparator.equals(comparator2); 235090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 236090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 237090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (sameComparator && (map instanceof ImmutableSortedMap)) { 2381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(kevinb): Prove that this cast is safe, even though 239090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Collections.unmodifiableSortedMap requires the same key type. 240090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 241090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ImmutableSortedMap<K, V> kvMap = (ImmutableSortedMap<K, V>) map; 2421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (!kvMap.isPartialView()) { 2431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return kvMap; 2441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 245090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 246090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // "adding" type params to an array of a raw type should be safe as 2481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // long as no one can ever cast that same array instance back to a 2491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // raw type. 2501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 2511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Entry<K, V>[] entries = map.entrySet().toArray(new Entry[0]); 2521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < entries.length; i++) { 2541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Entry<K, V> entry = entries[i]; 2551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert entries[i] = entryOf(entry.getKey(), entry.getValue()); 256090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 2571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<Entry<K, V>> list = Arrays.asList(entries); 259090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 260090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (!sameComparator) { 2611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert sortEntries(list, comparator); 2621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert validateEntries(list, comparator); 263090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 264090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new ImmutableSortedMap<K, V>(ImmutableList.copyOf(list), comparator); 266090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 2671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static <K, V> void sortEntries( 2691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<Entry<K, V>> entries, final Comparator<? super K> comparator) { 2701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Comparator<Entry<K, V>> entryComparator = new Comparator<Entry<K, V>>() { 271090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public int compare(Entry<K, V> entry1, Entry<K, V> entry2) { 2731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return comparator.compare(entry1.getKey(), entry2.getKey()); 274090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 275090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 2761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Collections.sort(entries, entryComparator); 278090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 279090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static <K, V> void validateEntries(List<Entry<K, V>> entries, 2811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Comparator<? super K> comparator) { 2821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 1; i < entries.size(); i++) { 2831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (comparator.compare( 2841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert entries.get(i - 1).getKey(), entries.get(i).getKey()) == 0) { 285090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throw new IllegalArgumentException( 2861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert "Duplicate keys in mappings " + entries.get(i - 1) + " and " 2871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert + entries.get(i)); 288090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 289090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 290090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 291090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 292090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 293090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a builder that creates immutable sorted maps whose keys are 294090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ordered by their natural ordering. The sorted maps use {@link 295090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Ordering#natural()} as the comparator. 296090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 297090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Note: the type parameter {@code K} extends {@code Comparable<K>} rather 298090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * than {@code Comparable<? super K>} as a workaround for javac <a 299090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 300090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 6468354</a>. 301090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 302090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K extends Comparable<K>, V> Builder<K, V> naturalOrder() { 303090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Builder<K, V>(Ordering.natural()); 304090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 305090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 306090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 307090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a builder that creates immutable sorted maps with an explicit 308090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * comparator. If the comparator has a more general type than the map's keys, 309090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * such as creating a {@code SortedMap<Integer, String>} with a {@code 310090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Comparator<Number>}, use the {@link Builder} constructor instead. 311090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 312090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if {@code comparator} is null 313090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 314090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K, V> Builder<K, V> orderedBy(Comparator<K> comparator) { 315090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Builder<K, V>(comparator); 316090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 317090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 318090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 319090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a builder that creates immutable sorted maps whose keys are 320090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ordered by the reverse of their natural ordering. 321090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 322090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Note: the type parameter {@code K} extends {@code Comparable<K>} rather 323090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * than {@code Comparable<? super K>} as a workaround for javac <a 324090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 325090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 6468354</a>. 326090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 327090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K extends Comparable<K>, V> Builder<K, V> reverseOrder() { 328090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Builder<K, V>(Ordering.natural().reverse()); 329090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 330090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 331090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 332090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * A builder for creating immutable sorted map instances, especially {@code 333090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * public static final} maps ("constant maps"). Example: <pre> {@code 334090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 335090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * static final ImmutableSortedMap<Integer, String> INT_TO_WORD = 336090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * new ImmutableSortedMap.Builder<Integer, String>(Ordering.natural()) 337090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * .put(1, "one") 338090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * .put(2, "two") 339090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * .put(3, "three") 340090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * .build();}</pre> 341090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 342090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * For <i>small</i> immutable sorted maps, the {@code ImmutableSortedMap.of()} 343090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * methods are even more convenient. 344090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 345090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Builder instances can be reused - it is safe to call {@link #build} 346090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multiple times to build multiple maps in series. Each map is a superset of 347090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the maps created before it. 3481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 (imported from Google Collections Library) 350090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 3511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static class Builder<K, V> extends ImmutableMap.Builder<K, V> { 352090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private final Comparator<? super K> comparator; 353090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 354090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 355090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a new builder. The returned builder is equivalent to the builder 356090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * generated by {@link ImmutableSortedMap#orderedBy}. 357090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 358090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Builder(Comparator<? super K> comparator) { 359090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.comparator = checkNotNull(comparator); 360090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 361090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 362090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 363090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Associates {@code key} with {@code value} in the built map. Duplicate 364090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * keys, according to the comparator (which might be the keys' natural 365090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * order), are not allowed, and will cause {@link #build} to fail. 366090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 367090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Builder<K, V> put(K key, V value) { 368090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson entries.add(entryOf(key, value)); 369090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return this; 370090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 371090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 372090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 3731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Adds the given {@code entry} to the map, making it immutable if 3741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * necessary. Duplicate keys, according to the comparator (which might be 3751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the keys' natural order), are not allowed, and will cause {@link #build} 3761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * to fail. 3771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 11.0 3791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public Builder<K, V> put(Entry<? extends K, ? extends V> entry) { 3811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert super.put(entry); 3821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return this; 3831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 386090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Associates all of the given map's keys and values in the built map. 387090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Duplicate keys, according to the comparator (which might be the keys' 388090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * natural order), are not allowed, and will cause {@link #build} to fail. 389090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 390090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if any key or value in {@code map} is null 391090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 392090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Builder<K, V> putAll(Map<? extends K, ? extends V> map) { 393090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (Entry<? extends K, ? extends V> entry : map.entrySet()) { 394090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson put(entry.getKey(), entry.getValue()); 395090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 396090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return this; 397090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 398090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 399090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 400090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a newly-created immutable sorted map. 401090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 402090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if any two keys are equal according to 403090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the comparator (which might be the keys' natural order) 404090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 405090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public ImmutableSortedMap<K, V> build() { 4061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert sortEntries(entries, comparator); 4071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert validateEntries(entries, comparator); 4081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new ImmutableSortedMap<K, V>( 4091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ImmutableList.copyOf(entries), comparator); 410090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 411090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 412090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 4131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final transient ImmutableList<Entry<K, V>> entries; 414090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private final transient Comparator<? super K> comparator; 415090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 4161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ImmutableSortedMap( 4171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ImmutableList<Entry<K, V>> entries, Comparator<? super K> comparator) { 4181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.entries = entries; 419090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.comparator = comparator; 420090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 421090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 4221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 423090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int size() { 4241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return entries.size(); 425090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 4261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Pretend the comparator can compare anything. If it turns out it can't 4281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // compare two elements, it'll throw a CCE. Only methods that are specified to 4291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // throw CCE should call this. 4301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 4311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Comparator<Object> unsafeComparator() { 4321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (Comparator<Object>) comparator; 4331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 435090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public V get(@Nullable Object key) { 436090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (key == null) { 437090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return null; 438090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 439090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int i; 440090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson try { 4411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert i = index(key, ANY_PRESENT, INVERTED_INSERTION_INDEX); 442090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } catch (ClassCastException e) { 443090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return null; 444090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 4451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return i >= 0 ? entries.get(i).getValue() : null; 446090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 447090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 448090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean containsValue(@Nullable Object value) { 449090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (value == null) { 450090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 451090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 4521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Iterators.contains(valueIterator(), value); 4531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override boolean isPartialView() { 4561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return entries.isPartialView(); 457090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 458090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 459090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient ImmutableSet<Entry<K, V>> entrySet; 460090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 461090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 462090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable set of the mappings in this map, sorted by the key 463090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ordering. 464090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 465090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public ImmutableSet<Entry<K, V>> entrySet() { 466090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ImmutableSet<Entry<K, V>> es = entrySet; 467090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (es == null) ? (entrySet = createEntrySet()) : es; 468090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 469090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 470090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private ImmutableSet<Entry<K, V>> createEntrySet() { 471090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return isEmpty() ? ImmutableSet.<Entry<K, V>>of() 472090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson : new EntrySet<K, V>(this); 473090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 474090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 475090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("serial") // uses writeReplace(), not default serialization 476090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static class EntrySet<K, V> extends ImmutableSet<Entry<K, V>> { 477090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final transient ImmutableSortedMap<K, V> map; 478090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 479090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson EntrySet(ImmutableSortedMap<K, V> map) { 480090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.map = map; 481090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 482090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 4831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override boolean isPartialView() { 4841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return map.isPartialView(); 4851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 488090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int size() { 489090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return map.size(); 490090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 491090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 492090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public UnmodifiableIterator<Entry<K, V>> iterator() { 4931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return map.entries.iterator(); 494090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 495090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 496090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean contains(Object target) { 497090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (target instanceof Entry) { 498090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Entry<?, ?> entry = (Entry<?, ?>) target; 499090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson V mappedValue = map.get(entry.getKey()); 500090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return mappedValue != null && mappedValue.equals(entry.getValue()); 501090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 502090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 503090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 504090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 505090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override Object writeReplace() { 506090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new EntrySetSerializedForm<K, V>(map); 507090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 508090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 509090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 510090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static class EntrySetSerializedForm<K, V> implements Serializable { 511090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final ImmutableSortedMap<K, V> map; 512090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson EntrySetSerializedForm(ImmutableSortedMap<K, V> map) { 513090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.map = map; 514090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 515090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Object readResolve() { 516090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return map.entrySet(); 517090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 518090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static final long serialVersionUID = 0; 519090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 520090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 521090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient ImmutableSortedSet<K> keySet; 522090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 523090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 524090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable sorted set of the keys in this map. 525090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 526090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public ImmutableSortedSet<K> keySet() { 527090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ImmutableSortedSet<K> ks = keySet; 528090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (ks == null) ? (keySet = createKeySet()) : ks; 529090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 530090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 5311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("serial") // does not use default serialization 532090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private ImmutableSortedSet<K> createKeySet() { 533090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (isEmpty()) { 534090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return ImmutableSortedSet.emptySet(comparator); 535090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 536090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 5371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new RegularImmutableSortedSet<K>( 5381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert new TransformedImmutableList<Entry<K, V>, K>(entries) { 539090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 5401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override K transform(Entry<K, V> entry) { 5411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return entry.getKey(); 5421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }, comparator); 5441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 546090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient ImmutableCollection<V> values; 547090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 548090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 549090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable collection of the values in this map, sorted by the 550090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ordering of the corresponding keys. 551090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 552090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public ImmutableCollection<V> values() { 553090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ImmutableCollection<V> v = values; 554090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (v == null) ? (values = new Values<V>(this)) : v; 555090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 5561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert UnmodifiableIterator<V> valueIterator(){ 5581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final UnmodifiableIterator<Entry<K, V>> entryIterator = entries.iterator(); 5591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new UnmodifiableIterator<V>() { 5601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean hasNext() { 5621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return entryIterator.hasNext(); 5631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public V next() { 5661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return entryIterator.next().getValue(); 5671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 5691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 570090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 571090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("serial") // uses writeReplace(), not default serialization 572090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static class Values<V> extends ImmutableCollection<V> { 573090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private final ImmutableSortedMap<?, V> map; 574090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 575090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Values(ImmutableSortedMap<?, V> map) { 576090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.map = map; 577090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 578090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 5791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 580090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int size() { 581090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return map.size(); 582090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 583090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 584090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public UnmodifiableIterator<V> iterator() { 5851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return map.valueIterator(); 586090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 587090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 588090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean contains(Object target) { 589090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return map.containsValue(target); 590090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 591090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 5921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override boolean isPartialView() { 5931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return true; 5941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 596090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override Object writeReplace() { 597090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new ValuesSerializedForm<V>(map); 598090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 599090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 600090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 601090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static class ValuesSerializedForm<V> implements Serializable { 602090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final ImmutableSortedMap<?, V> map; 603090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ValuesSerializedForm(ImmutableSortedMap<?, V> map) { 604090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.map = map; 605090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 606090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Object readResolve() { 607090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return map.values(); 608090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 609090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static final long serialVersionUID = 0; 610090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 611090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 612090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 613090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns the comparator that orders the keys, which is 614090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link Ordering#natural()} when the natural ordering of the keys is used. 615090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Note that its behavior is not consistent with {@link TreeMap#comparator()}, 616090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * which returns {@code null} to indicate natural ordering. 617090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 6181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 619090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Comparator<? super K> comparator() { 620090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return comparator; 621090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 622090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 6231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 624090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public K firstKey() { 625090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (isEmpty()) { 626090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throw new NoSuchElementException(); 627090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 6281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return entries.get(0).getKey(); 629090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 630090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 6311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 632090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public K lastKey() { 633090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (isEmpty()) { 634090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throw new NoSuchElementException(); 635090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 6361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return entries.get(size() - 1).getKey(); 637090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 638090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 639090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 640090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * This method returns a {@code ImmutableSortedMap}, consisting of the entries 641090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * whose keys are less than {@code toKey}. 642090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 643090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The {@link SortedMap#headMap} documentation states that a submap of a 644090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * submap throws an {@link IllegalArgumentException} if passed a {@code toKey} 645090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * greater than an earlier {@code toKey}. However, this method doesn't throw 646090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * an exception in that situation, but instead keeps the original {@code 647090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * toKey}. 648090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 6491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 650090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public ImmutableSortedMap<K, V> headMap(K toKey) { 6511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return headMap(toKey, false); 6521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 6541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ImmutableSortedMap<K, V> headMap(K toKey, boolean inclusive){ 6551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int index; 6561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (inclusive) { 6571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert index = index(toKey, ANY_PRESENT, NEXT_LOWER) + 1; 6581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 6591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert index = index(toKey, ANY_PRESENT, NEXT_HIGHER); 6601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return createSubmap(0, index); 662090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 663090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 664090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 665090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * This method returns a {@code ImmutableSortedMap}, consisting of the entries 666090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * whose keys ranges from {@code fromKey}, inclusive, to {@code toKey}, 667090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * exclusive. 668090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 669090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The {@link SortedMap#subMap} documentation states that a submap of a 670090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * submap throws an {@link IllegalArgumentException} if passed a {@code 671090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * fromKey} less than an earlier {@code fromKey}. However, this method doesn't 672090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * throw an exception in that situation, but instead keeps the original {@code 673090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * fromKey}. Similarly, this method keeps the original {@code toKey}, instead 674090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * of throwing an exception, if passed a {@code toKey} greater than an earlier 675090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code toKey}. 676090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 6771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 678090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public ImmutableSortedMap<K, V> subMap(K fromKey, K toKey) { 6791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return subMap(fromKey, true, toKey, false); 6801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 6821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ImmutableSortedMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, 6831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert boolean toInclusive) { 684090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(fromKey); 685090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(toKey); 686090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkArgument(comparator.compare(fromKey, toKey) <= 0); 6871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return tailMap(fromKey, fromInclusive).headMap(toKey, toInclusive); 688090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 689090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 690090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 691090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * This method returns a {@code ImmutableSortedMap}, consisting of the entries 692090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * whose keys are greater than or equals to {@code fromKey}. 693090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 694090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The {@link SortedMap#tailMap} documentation states that a submap of a 695090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * submap throws an {@link IllegalArgumentException} if passed a {@code 696090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * fromKey} less than an earlier {@code fromKey}. However, this method doesn't 697090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * throw an exception in that situation, but instead keeps the original {@code 698090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * fromKey}. 699090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 7001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 701090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public ImmutableSortedMap<K, V> tailMap(K fromKey) { 7021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return tailMap(fromKey, true); 7031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 7051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ImmutableSortedMap<K, V> tailMap(K fromKey, boolean inclusive) { 7061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int index; 7071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (inclusive) { 7081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert index = index(fromKey, ANY_PRESENT, NEXT_HIGHER); 7091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 7101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert index = index(fromKey, ANY_PRESENT, NEXT_LOWER) + 1; 7111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return createSubmap(index, size()); 7131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 7151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private ImmutableList<K> keyList() { 7161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new TransformedImmutableList<Entry<K, V>, K>(entries) { 7171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 7181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert K transform(Entry<K, V> entry) { 7191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return entry.getKey(); 7201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 722090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 723090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 7241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private int index( 7251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object key, KeyPresentBehavior presentBehavior, KeyAbsentBehavior absentBehavior) { 7261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return SortedLists.binarySearch( 7271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert keyList(), checkNotNull(key), unsafeComparator(), presentBehavior, absentBehavior); 728090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 729090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 730090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private ImmutableSortedMap<K, V> createSubmap( 731090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int newFromIndex, int newToIndex) { 732090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (newFromIndex < newToIndex) { 7331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new ImmutableSortedMap<K, V>( 7341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert entries.subList(newFromIndex, newToIndex), comparator); 735090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 736090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return emptyMap(comparator); 737090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 738090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 739090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 740090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 741090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Serialized type for all ImmutableSortedMap instances. It captures the 742090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * logical contents and they are reconstructed using public factory methods. 743090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * This ensures that the implementation types remain as implementation 744090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * details. 745090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 746090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static class SerializedForm extends ImmutableMap.SerializedForm { 747090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private final Comparator<Object> comparator; 748090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 749090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson SerializedForm(ImmutableSortedMap<?, ?> sortedMap) { 750090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super(sortedMap); 751090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson comparator = (Comparator<Object>) sortedMap.comparator(); 752090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 753090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override Object readResolve() { 754090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Builder<Object, Object> builder = new Builder<Object, Object>(comparator); 755090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return createMap(builder); 756090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 757090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static final long serialVersionUID = 0; 758090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 759090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 760090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override Object writeReplace() { 761090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new SerializedForm(this); 762090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 763090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 764090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // This class is never actually serialized directly, but we have to make the 765090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // warning go away (and suppressing would suppress for all nested classes too) 766090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static final long serialVersionUID = 0; 767090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson} 768