1adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/* 2984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Copyright (C) 2010 The Android Open Source Project 3adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 4984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * you may not use this file except in compliance with the License. 6984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * You may obtain a copy of the License at 7adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 8984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * 10984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Unless required by applicable law or agreed to in writing, software 11984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * See the License for the specific language governing permissions and 14984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * limitations under the License. 15adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 16adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 17adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpackage java.util; 18adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 19adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.IOException; 20adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.ObjectInputStream; 21984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilsonimport java.io.ObjectInputStream.GetField; 22adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.ObjectOutputStream; 23984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilsonimport java.io.ObjectStreamException; 24adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.Serializable; 257365de1056414750d0a7d1fdd26025fd247f0d04Jesse Wilsonimport static java.util.TreeMap.Bound.*; 267365de1056414750d0a7d1fdd26025fd247f0d04Jesse Wilsonimport static java.util.TreeMap.Relation.*; 276186821cb13f4ac7ff50950c813394367e021eaeJesse Wilsonimport libcore.util.Objects; 28adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 29adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/** 30984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * A map whose entries are sorted by their keys. All optional operations such as 31984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * {@link #put} and {@link #remove} are supported. 32984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * 33984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * <p>This map sorts keys using either a user-supplied comparator or the key's 34984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * natural order: 35984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * <ul> 36984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * <li>User supplied comparators must be able to compare any pair of keys in 37984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * this map. If a user-supplied comparator is in use, it will be returned 38984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * by {@link #comparator}. 39984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * <li>If no user-supplied comparator is supplied, keys will be sorted by 40984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * their natural order. Keys must be <i>mutually comparable</i>: they must 41984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * implement {@link Comparable} and {@link Comparable#compareTo 42984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * compareTo()} must be able to compare each key with any other key in 43984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * this map. In this case {@link #comparator} will return null. 44984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * </ul> 45984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * With either a comparator or a natural ordering, comparisons should be 46984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * <i>consistent with equals</i>. An ordering is consistent with equals if for 47984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * every pair of keys {@code a} and {@code b}, {@code a.equals(b)} if and only 48984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * if {@code compare(a, b) == 0}. 49984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * 50984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * <p>When the ordering is not consistent with equals the behavior of this 51984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * class is well defined but does not honor the contract specified by {@link 52984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Map}. Consider a tree map of case-insensitive strings, an ordering that is 53984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * not consistent with equals: <pre> {@code 54984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * TreeMap<String, String> map = new TreeMap<String, String>(String.CASE_INSENSITIVE_ORDER); 55984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * map.put("a", "android"); 56984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * 57984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * // The Map API specifies that the next line should print "null" because 58984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * // "a".equals("A") is false and there is no mapping for upper case "A". 59984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * // But the case insensitive ordering says compare("a", "A") == 0. TreeMap 60984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * // uses only comparators/comparable on keys and so this prints "android". 61984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * System.out.println(map.get("A")); 62984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * }</pre> 63f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 64f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * @since 1.2 65adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 66984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilsonpublic class TreeMap<K, V> extends AbstractMap<K, V> 67984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson implements SortedMap<K, V>, NavigableMap<K, V>, Cloneable, Serializable { 68adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 69984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @SuppressWarnings("unchecked") // to avoid Comparable<Comparable<Comparable<...>>> 70984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson private static final Comparator<Comparable> NATURAL_ORDER = new Comparator<Comparable>() { 71984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public int compare(Comparable a, Comparable b) { 72984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return a.compareTo(b); 73adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 74984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson }; 75984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 76984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Comparator<? super K> comparator; 77984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> root; 78984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson int size = 0; 79984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson int modCount = 0; 80984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 81984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /** 82984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Create a natural order, empty tree map whose keys must be mutually 83984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * comparable and non-null. 84984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 85984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @SuppressWarnings("unchecked") // unsafe! this assumes K is comparable 86984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public TreeMap() { 87984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson this.comparator = (Comparator<? super K>) NATURAL_ORDER; 88adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 89f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 90984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /** 91984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Create a natural order tree map populated with the key/value pairs of 92984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * {@code copyFrom}. This map's keys must be mutually comparable and 93984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * non-null. 94984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * 95984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * <p>Even if {@code copyFrom} is a {@code SortedMap}, the constructed map 96984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * <strong>will not</strong> use {@code copyFrom}'s ordering. This 97984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * constructor always creates a naturally-ordered map. Because the {@code 98984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * TreeMap} constructor overloads are ambiguous, prefer to construct a map 99984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * and populate it in two steps: <pre> {@code 100984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * TreeMap<String, Integer> customOrderedMap 101984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * = new TreeMap<String, Integer>(copyFrom.comparator()); 102984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * customOrderedMap.putAll(copyFrom); 103984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * }</pre> 104984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 105984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public TreeMap(Map<? extends K, ? extends V> copyFrom) { 106984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson this(); 107984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson for (Map.Entry<? extends K, ? extends V> entry : copyFrom.entrySet()) { 108984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson putInternal(entry.getKey(), entry.getValue()); 10955392539fea537abfb6581b474918f9d611fba27Jesse Wilson } 110adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 111adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 112984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /** 113984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Create a tree map ordered by {@code comparator}. This map's keys may only 114984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * be null if {@code comparator} permits. 115984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * 116162a12c1442641a95fe95859fa4e561b22db049fElliott Hughes * @param comparator the comparator to order elements with, or {@code null} to use the natural 117162a12c1442641a95fe95859fa4e561b22db049fElliott Hughes * ordering. 118984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 119984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @SuppressWarnings("unchecked") // unsafe! if comparator is null, this assumes K is comparable 120984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public TreeMap(Comparator<? super K> comparator) { 121984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (comparator != null) { 122984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson this.comparator = comparator; 123984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } else { 124984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson this.comparator = (Comparator<? super K>) NATURAL_ORDER; 125984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 126984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 127adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 128984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /** 129984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Create a tree map with the ordering and key/value pairs of {@code 130984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * copyFrom}. This map's keys may only be null if the {@code copyFrom}'s 131984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * ordering permits. 132984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * 133984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * <p>The constructed map <strong>will always use</strong> {@code 134984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * copyFrom}'s ordering. Because the {@code TreeMap} constructor overloads 135db40744613d500958c8b053b95b032c46540edceJesse Wilson * are ambiguous, prefer to construct a map and populate it in two steps: 136984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * <pre> {@code 137984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * TreeMap<String, Integer> customOrderedMap 138984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * = new TreeMap<String, Integer>(copyFrom.comparator()); 139984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * customOrderedMap.putAll(copyFrom); 140984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * }</pre> 141984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 142984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @SuppressWarnings("unchecked") // if copyFrom's keys are comparable this map's keys must be also 143984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public TreeMap(SortedMap<K, ? extends V> copyFrom) { 144984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Comparator<? super K> sourceComparator = copyFrom.comparator(); 145984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (sourceComparator != null) { 146984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson this.comparator = sourceComparator; 147984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } else { 148984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson this.comparator = (Comparator<? super K>) NATURAL_ORDER; 149f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 150984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson for (Map.Entry<K, ? extends V> entry : copyFrom.entrySet()) { 151984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson putInternal(entry.getKey(), entry.getValue()); 152984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 153984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 154f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 155984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public Object clone() { 156984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson try { 157984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @SuppressWarnings("unchecked") // super.clone() must return the same type 158984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson TreeMap<K, V> map = (TreeMap<K, V>) super.clone(); 159d44d87eac62e1710d2cd420b00c05c98aebc8c98Jesse Wilson map.root = root != null ? root.copy(null) : null; 160984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson map.entrySet = null; 161984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson map.keySet = null; 162984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return map; 163984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } catch (CloneNotSupportedException e) { 164984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson throw new AssertionError(); 165f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 166984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 167984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 168984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public int size() { 169984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return size; 170984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 171984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 172984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public boolean isEmpty() { 173984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return size == 0; 174984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 175984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 176984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public V get(Object key) { 177984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Entry<K, V> entry = findByObject(key); 178984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return entry != null ? entry.getValue() : null; 179984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 180984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 181984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public boolean containsKey(Object key) { 182984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return findByObject(key) != null; 183984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 184984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 185984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public V put(K key, V value) { 186984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return putInternal(key, value); 187984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 188984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 189984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public void clear() { 190984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson root = null; 191984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson size = 0; 192984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson modCount++; 193984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 194984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 195984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public V remove(Object key) { 196984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> node = removeInternalByKey(key); 197984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return node != null ? node.value : null; 198984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 199984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 200984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /* 201984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * AVL methods 202984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 203f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 204984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson enum Relation { 205984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson LOWER, 206984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson FLOOR, 207984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson EQUAL, 208984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson CREATE, 209984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson CEILING, 210984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson HIGHER; 211984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 212984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /** 213984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Returns a possibly-flipped relation for use in descending views. 214984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * 215984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * @param ascending false to flip; true to return this. 216984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 217984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Relation forOrder(boolean ascending) { 218984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (ascending) { 219984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return this; 220984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 221984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 222984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson switch (this) { 223984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case LOWER: 224984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return HIGHER; 225984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case FLOOR: 226984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return CEILING; 227984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case EQUAL: 228984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return EQUAL; 229984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case CEILING: 230984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return FLOOR; 231984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case HIGHER: 232984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return LOWER; 233984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson default: 234984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson throw new IllegalStateException(); 235984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 236adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 237984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 238adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 239984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson V putInternal(K key, V value) { 240984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> created = find(key, Relation.CREATE); 241984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson V result = created.value; 242984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson created.value = value; 243984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return result; 244984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 245984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 246984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /** 247984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Returns the node at or adjacent to the given key, creating it if requested. 248984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * 249984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * @throws ClassCastException if {@code key} and the tree's keys aren't mutually comparable. 250984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 251984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> find(K key, Relation relation) { 252984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (root == null) { 2533642569f572913df26e48b04f32b719cb1c38261Jesse Wilson if (comparator == NATURAL_ORDER && !(key instanceof Comparable)) { 254415c7497ec02890a73eb293f98f69c1f6983389bElliott Hughes throw new ClassCastException(key.getClass().getName() + " is not Comparable"); // NullPointerException ok 2553642569f572913df26e48b04f32b719cb1c38261Jesse Wilson } 256984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (relation == Relation.CREATE) { 257984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson root = new Node<K, V>(null, key); 258984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson size = 1; 259984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson modCount++; 260984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return root; 261984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } else { 262984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return null; 263984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 264984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 265984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 266984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /* 267984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Micro-optimization: avoid polymorphic calls to Comparator.compare(). 268984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * This is 10% faster for naturally ordered trees. 269984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 270984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @SuppressWarnings("unchecked") // will throw a ClassCastException below if there's trouble 271984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Comparable<Object> comparableKey = (comparator == NATURAL_ORDER) 272984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson ? (Comparable<Object>) key 273984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson : null; 274984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 275984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> nearest = root; 276984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson while (true) { 277984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson int comparison = (comparableKey != null) 278984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson ? comparableKey.compareTo(nearest.key) 279984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson : comparator.compare(key, nearest.key); 280984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 281984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /* 282984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * We found the requested key. 283984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 284984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (comparison == 0) { 285984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson switch (relation) { 286984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case LOWER: 287984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return nearest.prev(); 288984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case FLOOR: 289984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case EQUAL: 290984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case CREATE: 291984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case CEILING: 292984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return nearest; 293984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case HIGHER: 294984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return nearest.next(); 295984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 296984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 297984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 298984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> child = (comparison < 0) ? nearest.left : nearest.right; 299984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (child != null) { 300984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson nearest = child; 301984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson continue; 302984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 303984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 304984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /* 305984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * We found a nearest node. Every key not in the tree has up to two 306984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * nearest nodes, one lower and one higher. 307984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 308984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 309984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (comparison < 0) { // nearest.key is higher 310984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson switch (relation) { 311984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case LOWER: 312984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case FLOOR: 313984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return nearest.prev(); 314984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case CEILING: 315984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case HIGHER: 316984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return nearest; 317984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case EQUAL: 318984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return null; 319984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case CREATE: 320984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> created = new Node<K, V>(nearest, key); 321984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson nearest.left = created; 322984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson size++; 323984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson modCount++; 324984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson rebalance(nearest, true); 325984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return created; 326984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 327984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } else { // comparison > 0, nearest.key is lower 328984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson switch (relation) { 329984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case LOWER: 330984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case FLOOR: 331984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return nearest; 332984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case CEILING: 333984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case HIGHER: 334984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return nearest.next(); 335984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case EQUAL: 336984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return null; 337984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case CREATE: 338984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> created = new Node<K, V>(nearest, key); 339984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson nearest.right = created; 340984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson size++; 341984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson modCount++; 342984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson rebalance(nearest, true); 343984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return created; 344984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 345984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 346adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 347984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 348adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 349984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @SuppressWarnings("unchecked") // this method throws ClassCastExceptions! 350984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> findByObject(Object key) { 351984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return find((K) key, EQUAL); 352984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 353984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 354984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /** 355984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Returns this map's entry that has the same key and value as {@code 356984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * entry}, or null if this map has no such entry. 357984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * 358984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * <p>This method uses the comparator for key equality rather than {@code 359984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * equals}. If this map's comparator isn't consistent with equals (such as 360984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * {@code String.CASE_INSENSITIVE_ORDER}), then {@code remove()} and {@code 361984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * contains()} will violate the collections API. 362984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 363984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> findByEntry(Entry<?, ?> entry) { 364984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> mine = findByObject(entry.getKey()); 365e32b21f14d52bac429a9c54fe031f9e92c911d64Jesse Wilson boolean valuesEqual = mine != null && Objects.equal(mine.value, entry.getValue()); 366984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return valuesEqual ? mine : null; 367984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 368984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 369984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /** 370984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Removes {@code node} from this tree, rearranging the tree's structure as 371984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * necessary. 372984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 373984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson void removeInternal(Node<K, V> node) { 374984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> left = node.left; 375984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> right = node.right; 376984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> originalParent = node.parent; 377984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (left != null && right != null) { 378984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 379984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /* 380984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * To remove a node with both left and right subtrees, move an 381984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * adjacent node from one of those subtrees into this node's place. 382984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * 383984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Removing the adjacent node may change this node's subtrees. This 384984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * node may no longer have two subtrees once the adjacent node is 385984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * gone! 386984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 387984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 388984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> adjacent = (left.height > right.height) ? left.last() : right.first(); 389984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson removeInternal(adjacent); // takes care of rebalance and size-- 390984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 391984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson int leftHeight = 0; 392984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson left = node.left; 393984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (left != null) { 394984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson leftHeight = left.height; 395984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson adjacent.left = left; 396984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson left.parent = adjacent; 397984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson node.left = null; 398f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 399984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson int rightHeight = 0; 400984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson right = node.right; 401984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (right != null) { 402984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson rightHeight = right.height; 403984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson adjacent.right = right; 404984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson right.parent = adjacent; 405984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson node.right = null; 406984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 407984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson adjacent.height = Math.max(leftHeight, rightHeight) + 1; 408984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson replaceInParent(node, adjacent); 409984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return; 410984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } else if (left != null) { 411984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson replaceInParent(node, left); 412984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson node.left = null; 413984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } else if (right != null) { 414984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson replaceInParent(node, right); 415984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson node.right = null; 416984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } else { 417984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson replaceInParent(node, null); 418984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 419984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 420984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson rebalance(originalParent, false); 421984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson size--; 422984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson modCount++; 423984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 424984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 425984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> removeInternalByKey(Object key) { 426984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> node = findByObject(key); 427984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (node != null) { 428984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson removeInternal(node); 429984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 430984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return node; 431984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 432984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 433984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson private void replaceInParent(Node<K, V> node, Node<K, V> replacement) { 434984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> parent = node.parent; 435984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson node.parent = null; 436984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (replacement != null) { 437984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson replacement.parent = parent; 438984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 439984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 440984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (parent != null) { 441984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (parent.left == node) { 442984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson parent.left = replacement; 443f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } else { 444984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson assert (parent.right == node); 445984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson parent.right = replacement; 446f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 447984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } else { 448984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson root = replacement; 449f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 450984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 451f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 452984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /** 453984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Rebalances the tree by making any AVL rotations necessary between the 454984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * newly-unbalanced node and the tree's root. 455984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * 456984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * @param insert true if the node was unbalanced by an insert; false if it 457984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * was by a removal. 458984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 459984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson private void rebalance(Node<K, V> unbalanced, boolean insert) { 460984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson for (Node<K, V> node = unbalanced; node != null; node = node.parent) { 461984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> left = node.left; 462984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> right = node.right; 463984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson int leftHeight = left != null ? left.height : 0; 464984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson int rightHeight = right != null ? right.height : 0; 465984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 466984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson int delta = leftHeight - rightHeight; 467984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (delta == -2) { 468984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> rightLeft = right.left; 469984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> rightRight = right.right; 470984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson int rightRightHeight = rightRight != null ? rightRight.height : 0; 471984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson int rightLeftHeight = rightLeft != null ? rightLeft.height : 0; 472984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 473984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson int rightDelta = rightLeftHeight - rightRightHeight; 474984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (rightDelta == -1 || (rightDelta == 0 && !insert)) { 475984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson rotateLeft(node); // AVL right right 476adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 477984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson assert (rightDelta == 1); 478984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson rotateRight(right); // AVL right left 479984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson rotateLeft(node); 480984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 481984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (insert) { 482984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson break; // no further rotations will be necessary 483984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 484984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 485984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } else if (delta == 2) { 486984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> leftLeft = left.left; 487984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> leftRight = left.right; 488984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson int leftRightHeight = leftRight != null ? leftRight.height : 0; 489984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson int leftLeftHeight = leftLeft != null ? leftLeft.height : 0; 490984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 491984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson int leftDelta = leftLeftHeight - leftRightHeight; 492984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (leftDelta == 1 || (leftDelta == 0 && !insert)) { 493984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson rotateRight(node); // AVL left left 494984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } else { 495984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson assert (leftDelta == -1); 496984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson rotateLeft(left); // AVL left right 497984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson rotateRight(node); 498984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 499984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (insert) { 500984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson break; // no further rotations will be necessary 501984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 502984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 503984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } else if (delta == 0) { 504984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson node.height = leftHeight + 1; // leftHeight == rightHeight 505984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (insert) { 506984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson break; // the insert caused balance, so rebalancing is done! 507adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 508984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 509adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 510984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson assert (delta == -1 || delta == 1); 511984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson node.height = Math.max(leftHeight, rightHeight) + 1; 512984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (!insert) { 513984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson break; // the height hasn't changed, so rebalancing is done! 514984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 515adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 516adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 517f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 518adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 519984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /** 520984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Rotates the subtree so that its root's right child is the new root. 521984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 522984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson private void rotateLeft(Node<K, V> root) { 523984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> left = root.left; 524984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> pivot = root.right; 525984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> pivotLeft = pivot.left; 526984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> pivotRight = pivot.right; 527adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 528984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson // move the pivot's left child to the root's right 529984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson root.right = pivotLeft; 530984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (pivotLeft != null) { 531984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson pivotLeft.parent = root; 532adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 533adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 534984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson replaceInParent(root, pivot); 535adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 536984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson // move the root to the pivot's left 537984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson pivot.left = root; 538984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson root.parent = pivot; 539984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 540984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson // fix heights 541984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson root.height = Math.max(left != null ? left.height : 0, 542984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson pivotLeft != null ? pivotLeft.height : 0) + 1; 543984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson pivot.height = Math.max(root.height, 544984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson pivotRight != null ? pivotRight.height : 0) + 1; 545f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 546adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 547984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /** 548984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Rotates the subtree so that its root's left child is the new root. 549984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 550984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson private void rotateRight(Node<K, V> root) { 551984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> pivot = root.left; 552984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> right = root.right; 553984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> pivotLeft = pivot.left; 554984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> pivotRight = pivot.right; 555adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 556984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson // move the pivot's right child to the root's left 557984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson root.left = pivotRight; 558984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (pivotRight != null) { 559984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson pivotRight.parent = root; 560adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 561adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 562984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson replaceInParent(root, pivot); 563984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 564984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson // move the root to the pivot's right 565984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson pivot.right = root; 566984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson root.parent = pivot; 567984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 568984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson // fixup heights 569984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson root.height = Math.max(right != null ? right.height : 0, 570984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson pivotRight != null ? pivotRight.height : 0) + 1; 571984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson pivot.height = Math.max(root.height, 572984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson pivotLeft != null ? pivotLeft.height : 0) + 1; 573984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 574984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 575984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /* 576984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Navigable methods. 577984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 578984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 57959cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe /** 58059cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe * Returns an immutable version of {@param entry}. Need this because we allow entry to be null, 58159cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe * in which case we return a null SimpleImmutableEntry. 58259cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe */ 58359cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe private SimpleImmutableEntry<K, V> immutableCopy(Entry<K, V> entry) { 58459cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe return entry == null ? null : new SimpleImmutableEntry<K, V>(entry); 58559cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe } 58659cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe 587984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Entry<K, V> firstEntry() { 58859cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe return immutableCopy(root == null ? null : root.first()); 589984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 590984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 5917cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe private Entry<K, V> internalPollFirstEntry() { 592984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (root == null) { 593984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return null; 594adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 595984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> result = root.first(); 596984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson removeInternal(result); 597984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return result; 598984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 599adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 6007cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe public Entry<K, V> pollFirstEntry() { 60159cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe return immutableCopy(internalPollFirstEntry()); 6027cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe } 6037cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe 604984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K firstKey() { 605984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (root == null) { 606984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson throw new NoSuchElementException(); 607adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 608984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return root.first().getKey(); 609adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 610adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 611984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Entry<K, V> lastEntry() { 61259cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe return immutableCopy(root == null ? null : root.last()); 613984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 614adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 6157cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe private Entry<K, V> internalPollLastEntry() { 616984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (root == null) { 617984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return null; 618adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 619984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> result = root.last(); 620984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson removeInternal(result); 621984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return result; 622984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 623adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 6247cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe public Entry<K, V> pollLastEntry() { 62559cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe return immutableCopy(internalPollLastEntry()); 6267cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe } 6277cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe 628984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K lastKey() { 629984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (root == null) { 630984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson throw new NoSuchElementException(); 631adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 632984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return root.last().getKey(); 633984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 634adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 635984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Entry<K, V> lowerEntry(K key) { 63659cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe return immutableCopy(find(key, LOWER)); 637adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 638adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 639984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K lowerKey(K key) { 640984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Entry<K, V> entry = find(key, LOWER); 641984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return entry != null ? entry.getKey() : null; 642984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 643adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 644984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Entry<K, V> floorEntry(K key) { 64559cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe return immutableCopy(find(key, FLOOR)); 646984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 647adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 648984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K floorKey(K key) { 649984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Entry<K, V> entry = find(key, FLOOR); 650984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return entry != null ? entry.getKey() : null; 651984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 652adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 653984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Entry<K, V> ceilingEntry(K key) { 65459cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe return immutableCopy(find(key, CEILING)); 655984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 656adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 657984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K ceilingKey(K key) { 658984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Entry<K, V> entry = find(key, CEILING); 659984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return entry != null ? entry.getKey() : null; 660984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 661adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 662984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Entry<K, V> higherEntry(K key) { 66359cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe return immutableCopy(find(key, HIGHER)); 664984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 665984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 666984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K higherKey(K key) { 667984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Entry<K, V> entry = find(key, HIGHER); 668984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return entry != null ? entry.getKey() : null; 669adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 670adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 671984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Comparator<? super K> comparator() { 672984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return comparator != NATURAL_ORDER ? comparator : null; 673984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 674adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 675984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /* 676984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * View factory methods. 677984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 678adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 679984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson private EntrySet entrySet; 680984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson private KeySet keySet; 681984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 682984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public Set<Entry<K, V>> entrySet() { 683984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson EntrySet result = entrySet; 684984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return result != null ? result : (entrySet = new EntrySet()); 685adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 686adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 687984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public Set<K> keySet() { 688984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson KeySet result = keySet; 689984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return result != null ? result : (keySet = new KeySet()); 690984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 691adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 692984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public NavigableSet<K> navigableKeySet() { 693984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson KeySet result = keySet; 694984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return result != null ? result : (keySet = new KeySet()); 695984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 696adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 697984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public NavigableMap<K, V> subMap(K from, boolean fromInclusive, K to, boolean toInclusive) { 698984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Bound fromBound = fromInclusive ? INCLUSIVE : EXCLUSIVE; 699984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Bound toBound = toInclusive ? INCLUSIVE : EXCLUSIVE; 700984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return new BoundedMap(true, from, fromBound, to, toBound); 701adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 702adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 703984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public SortedMap<K, V> subMap(K fromInclusive, K toExclusive) { 704984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return new BoundedMap(true, fromInclusive, INCLUSIVE, toExclusive, EXCLUSIVE); 705984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 706adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 707984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public NavigableMap<K, V> headMap(K to, boolean inclusive) { 708984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Bound toBound = inclusive ? INCLUSIVE : EXCLUSIVE; 709984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return new BoundedMap(true, null, NO_BOUND, to, toBound); 710984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 711adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 712984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public SortedMap<K, V> headMap(K toExclusive) { 713984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return new BoundedMap(true, null, NO_BOUND, toExclusive, EXCLUSIVE); 714adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 715adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 716984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public NavigableMap<K, V> tailMap(K from, boolean inclusive) { 717984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Bound fromBound = inclusive ? INCLUSIVE : EXCLUSIVE; 718984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return new BoundedMap(true, from, fromBound, null, NO_BOUND); 719984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 720adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 721984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public SortedMap<K, V> tailMap(K fromInclusive) { 722984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return new BoundedMap(true, fromInclusive, INCLUSIVE, null, NO_BOUND); 723984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 724adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 725984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public NavigableMap<K, V> descendingMap() { 726984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return new BoundedMap(false, null, NO_BOUND, null, NO_BOUND); 727984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 728adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 729984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public NavigableSet<K> descendingKeySet() { 730984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return new BoundedMap(false, null, NO_BOUND, null, NO_BOUND).navigableKeySet(); 731984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 732adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 733984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson static class Node<K, V> implements Map.Entry<K, V> { 734984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> parent; 735984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> left; 736984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> right; 737984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson final K key; 738984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson V value; 739984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson int height; 740adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 741984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node(Node<K, V> parent, K key) { 742984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson this.parent = parent; 743984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson this.key = key; 744984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson this.height = 1; 745f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 746adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 747984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> copy(Node<K, V> parent) { 748984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> result = new Node<K, V>(parent, key); 749984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (left != null) { 750984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson result.left = left.copy(result); 751adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 752984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (right != null) { 753984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson result.right = right.copy(result); 754adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 755984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson result.value = value; 756984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson result.height = height; 757984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return result; 758f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 759adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 760984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K getKey() { 761984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return key; 762f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 763adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 764984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public V getValue() { 765984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return value; 766f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 767adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 768984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public V setValue(V value) { 7697cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe V oldValue = this.value; 7707cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe this.value = value; 7717cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe return oldValue; 772f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 773f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 774984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public boolean equals(Object o) { 775984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (o instanceof Map.Entry) { 776984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Map.Entry other = (Map.Entry) o; 777984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return (key == null ? other.getKey() == null : key.equals(other.getKey())) 778984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson && (value == null ? other.getValue() == null : value.equals(other.getValue())); 779adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 780f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson return false; 781f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 782f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 783984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public int hashCode() { 784984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return (key == null ? 0 : key.hashCode()) 785984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson ^ (value == null ? 0 : value.hashCode()); 786f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 787adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 788984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public String toString() { 789984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return key + "=" + value; 790f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 791adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 792984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /** 793984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Returns the next node in an inorder traversal, or null if this is the 794984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * last node in the tree. 795984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 796984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> next() { 797984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (right != null) { 798984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return right.first(); 799adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 800adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 801984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> node = this; 802984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> parent = node.parent; 803984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson while (parent != null) { 804984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (parent.left == node) { 805984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return parent; 806adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 807984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson node = parent; 808984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson parent = node.parent; 809adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 810984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return null; 811f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 812adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 813984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /** 814984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Returns the previous node in an inorder traversal, or null if this is 815984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * the first node in the tree. 816984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 817984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Node<K, V> prev() { 818984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (left != null) { 819984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return left.last(); 820984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 821adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 822984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> node = this; 823984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> parent = node.parent; 824984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson while (parent != null) { 825984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (parent.right == node) { 826984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return parent; 827984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 828984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson node = parent; 829984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson parent = node.parent; 830adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 831f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson return null; 832f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 833adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 834984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /** 835984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Returns the first node in this subtree. 836984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 837984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Node<K, V> first() { 838984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> node = this; 839984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> child = node.left; 840984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson while (child != null) { 841984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson node = child; 842984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson child = node.left; 843adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 844984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return node; 845f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 846adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 847984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /** 848984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Returns the last node in this subtree. 849984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 850984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Node<K, V> last() { 851984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> node = this; 852984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> child = node.right; 853984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson while (child != null) { 854984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson node = child; 855984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson child = node.right; 856adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 857984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return node; 858f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 859984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 860adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 861984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /** 862984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Walk the nodes of the tree left-to-right or right-to-left. Note that in 863984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * descending iterations, {@code next} will return the previous node. 864984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 865984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson abstract class MapIterator<T> implements Iterator<T> { 866984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson protected Node<K, V> next; 867984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson protected Node<K, V> last; 868984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson protected int expectedModCount = modCount; 869984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 870984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson MapIterator(Node<K, V> next) { 871984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson this.next = next; 872f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 873adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 874984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public boolean hasNext() { 875984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return next != null; 876984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 877984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 878984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson protected Node<K, V> stepForward() { 879984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (next == null) { 880984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson throw new NoSuchElementException(); 881adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 882984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (modCount != expectedModCount) { 883984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson throw new ConcurrentModificationException(); 884f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 885984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson last = next; 886984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson next = next.next(); 887984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return last; 888f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 889adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 890984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson protected Node<K, V> stepBackward() { 891984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (next == null) { 892984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson throw new NoSuchElementException(); 893adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 894984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (modCount != expectedModCount) { 895984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson throw new ConcurrentModificationException(); 896984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 897984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson last = next; 898984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson next = next.prev(); 899984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return last; 900f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 901adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 902984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public void remove() { 903984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (last == null) { 904984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson throw new IllegalStateException(); 905adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 906984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson removeInternal(last); 907984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson expectedModCount = modCount; 908984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson last = null; 909adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 910984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 911adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 912984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /* 913984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * View implementations. 914984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 915984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 916984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson class EntrySet extends AbstractSet<Map.Entry<K, V>> { 917984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public int size() { 918984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return size; 919f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 920adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 921984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public Iterator<Entry<K, V>> iterator() { 9227cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe return new MapIterator<Entry<K, V>>(root == null ? null : root.first()) { 923984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Entry<K, V> next() { 924984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return stepForward(); 925f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 926984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson }; 927f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 928adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 929984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public boolean contains(Object o) { 930984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return o instanceof Entry && findByEntry((Entry<?, ?>) o) != null; 931f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 932adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 933984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public boolean remove(Object o) { 934984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (!(o instanceof Entry)) { 935984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return false; 936adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 937adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 938984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> node = findByEntry((Entry<?, ?>) o); 939984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (node == null) { 940984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return false; 941adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 942984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson removeInternal(node); 943984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return true; 944f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 945adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 946984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public void clear() { 947984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson TreeMap.this.clear(); 948adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 949f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 950adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 951984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson class KeySet extends AbstractSet<K> implements NavigableSet<K> { 952984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public int size() { 953984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return size; 954984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 955adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 956984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public Iterator<K> iterator() { 9577cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe return new MapIterator<K>(root == null ? null : root.first()) { 958984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K next() { 959984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return stepForward().key; 960984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 961984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson }; 962f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 963adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 964984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Iterator<K> descendingIterator() { 9657cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe return new MapIterator<K>(root == null ? null : root.last()) { 966984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K next() { 967984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return stepBackward().key; 968984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 969984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson }; 970f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 971adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 972984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public boolean contains(Object o) { 973984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return containsKey(o); 974f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 975adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 976984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public boolean remove(Object key) { 977984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return removeInternalByKey(key) != null; 978f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 979f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 980984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public void clear() { 981984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson TreeMap.this.clear(); 982f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 983adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 984984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Comparator<? super K> comparator() { 985984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return TreeMap.this.comparator(); 986adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 987adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 988984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /* 989984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Navigable methods. 990984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 991adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 992984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K first() { 993984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return firstKey(); 994f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 995adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 996984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K last() { 997984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return lastKey(); 998f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 999adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1000984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K lower(K key) { 1001984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return lowerKey(key); 1002f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1003adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1004984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K floor(K key) { 1005984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return floorKey(key); 1006adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1007adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1008984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K ceiling(K key) { 1009984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return ceilingKey(key); 1010f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1011f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1012984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K higher(K key) { 1013984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return higherKey(key); 1014f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1015f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1016984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K pollFirst() { 10177cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe Entry<K, V> entry = internalPollFirstEntry(); 1018984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return entry != null ? entry.getKey() : null; 1019f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1020f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1021984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K pollLast() { 10227cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe Entry<K, V> entry = internalPollLastEntry(); 1023984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return entry != null ? entry.getKey() : null; 1024f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1025f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1026984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /* 1027984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * View factory methods. 1028984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 1029984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1030984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public NavigableSet<K> subSet(K from, boolean fromInclusive, K to, boolean toInclusive) { 1031984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return TreeMap.this.subMap(from, fromInclusive, to, toInclusive).navigableKeySet(); 1032f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1033f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1034984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public SortedSet<K> subSet(K fromInclusive, K toExclusive) { 1035984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return TreeMap.this.subMap(fromInclusive, true, toExclusive, false).navigableKeySet(); 1036f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1037f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1038984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public NavigableSet<K> headSet(K to, boolean inclusive) { 1039984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return TreeMap.this.headMap(to, inclusive).navigableKeySet(); 1040984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1041adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1042984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public SortedSet<K> headSet(K toExclusive) { 1043984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return TreeMap.this.headMap(toExclusive, false).navigableKeySet(); 1044984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1045adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1046984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public NavigableSet<K> tailSet(K from, boolean inclusive) { 1047984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return TreeMap.this.tailMap(from, inclusive).navigableKeySet(); 1048984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1049adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1050984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public SortedSet<K> tailSet(K fromInclusive) { 1051984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return TreeMap.this.tailMap(fromInclusive, true).navigableKeySet(); 1052adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1053adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1054984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public NavigableSet<K> descendingSet() { 1055984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return new BoundedMap(false, null, NO_BOUND, null, NO_BOUND).navigableKeySet(); 1056adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1057adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1058adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1059984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /* 1060984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Bounded views implementations. 1061adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1062984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1063984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson enum Bound { 10642f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson INCLUSIVE { 10652f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson @Override public String leftCap(Object from) { 10662f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson return "[" + from; 10672f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson } 10682f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson @Override public String rightCap(Object to) { 10692f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson return to + "]"; 10702f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson } 10712f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson }, 10722f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson EXCLUSIVE { 10732f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson @Override public String leftCap(Object from) { 10742f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson return "(" + from; 10752f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson } 10762f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson @Override public String rightCap(Object to) { 10772f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson return to + ")"; 10782f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson } 10792f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson }, 10802f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson NO_BOUND { 10812f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson @Override public String leftCap(Object from) { 10822f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson return "."; 10832f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson } 10842f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson @Override public String rightCap(Object to) { 10852f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson return "."; 10862f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson } 10872f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson }; 10882f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson 10892f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson public abstract String leftCap(Object from); 10902f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson public abstract String rightCap(Object to); 1091adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1092adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1093adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1094984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * A map with optional limits on its range. 1095adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1096984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson final class BoundedMap extends AbstractMap<K, V> implements NavigableMap<K, V>, Serializable { 1097bad51d783a94c137c3775bbbb95e2eefa87bd0b3Jesse Wilson private final transient boolean ascending; 1098bad51d783a94c137c3775bbbb95e2eefa87bd0b3Jesse Wilson private final transient K from; 1099bad51d783a94c137c3775bbbb95e2eefa87bd0b3Jesse Wilson private final transient Bound fromBound; 1100bad51d783a94c137c3775bbbb95e2eefa87bd0b3Jesse Wilson private final transient K to; 1101bad51d783a94c137c3775bbbb95e2eefa87bd0b3Jesse Wilson private final transient Bound toBound; 1102984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1103984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson BoundedMap(boolean ascending, K from, Bound fromBound, K to, Bound toBound) { 1104984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /* 1105984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Validate the bounds. In addition to checking that from <= to, we 11062f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson * verify that the comparator supports our bound objects. 1107984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 1108984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (fromBound != NO_BOUND && toBound != NO_BOUND) { 1109984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (comparator.compare(from, to) > 0) { 1110984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson throw new IllegalArgumentException(from + " > " + to); 1111f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1112984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } else if (fromBound != NO_BOUND) { 1113984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson comparator.compare(from, from); 1114984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } else if (toBound != NO_BOUND) { 1115984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson comparator.compare(to, to); 1116adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1117984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1118984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson this.ascending = ascending; 1119984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson this.from = from; 1120984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson this.fromBound = fromBound; 1121984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson this.to = to; 1122984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson this.toBound = toBound; 1123984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1124984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1125984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public int size() { 1126984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return count(entrySet().iterator()); 1127adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1128adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1129984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public boolean isEmpty() { 11307cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe return endpoint(true) == null; 1131f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1132984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1133984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public V get(Object key) { 1134984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return isInBounds(key) ? TreeMap.this.get(key) : null; 1135f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1136f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1137984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public boolean containsKey(Object key) { 1138984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return isInBounds(key) && TreeMap.this.containsKey(key); 1139984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1140adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1141984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public V put(K key, V value) { 1142984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (!isInBounds(key)) { 11432f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson throw outOfBounds(key, fromBound, toBound); 1144f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1145984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return putInternal(key, value); 1146f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1147adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1148984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public V remove(Object key) { 1149984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return isInBounds(key) ? TreeMap.this.remove(key) : null; 1150adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1151984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1152984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /** 1153984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Returns true if the key is in bounds. 1154984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 1155984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @SuppressWarnings("unchecked") // this method throws ClassCastExceptions! 1156984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson private boolean isInBounds(Object key) { 1157984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return isInBounds((K) key, fromBound, toBound); 1158984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1159984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1160984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /** 1161984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Returns true if the key is in bounds. Use this overload with 1162984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * NO_BOUND to skip bounds checking on either end. 1163984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 1164984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson private boolean isInBounds(K key, Bound fromBound, Bound toBound) { 1165984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (fromBound == INCLUSIVE) { 1166984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (comparator.compare(key, from) < 0) { 1167984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return false; // less than from 1168f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1169984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } else if (fromBound == EXCLUSIVE) { 1170984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (comparator.compare(key, from) <= 0) { 1171984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return false; // less than or equal to from 1172f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1173adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1174adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1175984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (toBound == INCLUSIVE) { 1176984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (comparator.compare(key, to) > 0) { 1177984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return false; // greater than 'to' 1178adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1179984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } else if (toBound == EXCLUSIVE) { 1180984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (comparator.compare(key, to) >= 0) { 1181984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return false; // greater than or equal to 'to' 1182adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1183984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1184adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1185984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return true; 1186984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1187f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1188984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /** 1189984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Returns the entry if it is in bounds, or null if it is out of bounds. 1190984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 11917cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe private Node<K, V> bound(Node<K, V> node, Bound fromBound, Bound toBound) { 1192984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return node != null && isInBounds(node.getKey(), fromBound, toBound) ? node : null; 1193984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1194adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1195984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /* 1196984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Navigable methods. 1197984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 1198984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1199984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Entry<K, V> firstEntry() { 120059cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe return immutableCopy(endpoint(true)); 1201adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1202f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1203984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Entry<K, V> pollFirstEntry() { 12047cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe Node<K, V> result = endpoint(true); 1205984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (result != null) { 1206984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson removeInternal(result); 1207984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 120859cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe return immutableCopy(result); 1209984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1210f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1211984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K firstKey() { 12127cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe Entry<K, V> entry = endpoint(true); 1213984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (entry == null) { 1214984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson throw new NoSuchElementException(); 1215adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1216984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return entry.getKey(); 1217adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1218adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1219984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Entry<K, V> lastEntry() { 122059cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe return immutableCopy(endpoint(false)); 1221984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1222f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1223984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Entry<K, V> pollLastEntry() { 12247cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe Node<K, V> result = endpoint(false); 1225984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (result != null) { 1226984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson removeInternal(result); 1227984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 122859cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe return immutableCopy(result); 1229f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1230f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1231984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K lastKey() { 12327cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe Entry<K, V> entry = endpoint(false); 1233984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (entry == null) { 1234984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson throw new NoSuchElementException(); 1235984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1236984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return entry.getKey(); 1237984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1238f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1239984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /** 1240984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * @param first true for the first element, false for the last. 1241984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 12427cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe private Node<K, V> endpoint(boolean first) { 12437cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe Node<K, V> node; 1244984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (ascending == first) { 1245984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson switch (fromBound) { 1246984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case NO_BOUND: 12477cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe node = root == null ? null : root.first(); 1248984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson break; 1249984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case INCLUSIVE: 12507cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe node = find(from, CEILING); 1251984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson break; 1252984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case EXCLUSIVE: 12537cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe node = find(from, HIGHER); 1254984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson break; 1255984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson default: 1256984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson throw new AssertionError(); 1257f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 12587cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe return bound(node, NO_BOUND, toBound); 1259984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } else { 1260984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson switch (toBound) { 1261984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case NO_BOUND: 12627cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe node = root == null ? null : root.last(); 1263984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson break; 1264984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case INCLUSIVE: 12657cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe node = find(to, FLOOR); 1266984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson break; 1267984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson case EXCLUSIVE: 12687cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe node = find(to, LOWER); 1269984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson break; 1270984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson default: 1271984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson throw new AssertionError(); 1272f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 12737cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe return bound(node, fromBound, NO_BOUND); 1274984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1275984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1276f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 12772f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson /** 12782f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson * Performs a find on the underlying tree after constraining it to the 12792f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson * bounds of this view. Examples: 12802f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson * 12812f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson * bound is (A..C) 12822f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson * findBounded(B, FLOOR) stays source.find(B, FLOOR) 12832f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson * 12842f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson * bound is (A..C) 12852f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson * findBounded(C, FLOOR) becomes source.find(C, LOWER) 12862f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson * 12872f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson * bound is (A..C) 12882f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson * findBounded(D, LOWER) becomes source.find(C, LOWER) 12892f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson * 12902f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson * bound is (A..C] 12912f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson * findBounded(D, FLOOR) becomes source.find(C, FLOOR) 12922f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson * 12932f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson * bound is (A..C] 12942f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson * findBounded(D, LOWER) becomes source.find(C, FLOOR) 12952f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson */ 12962f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson private Entry<K, V> findBounded(K key, Relation relation) { 12972f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson relation = relation.forOrder(ascending); 12982f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson Bound fromBoundForCheck = fromBound; 12992f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson Bound toBoundForCheck = toBound; 13002f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson 13012f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson if (toBound != NO_BOUND && (relation == LOWER || relation == FLOOR)) { 13022f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson int comparison = comparator.compare(to, key); 13032f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson if (comparison <= 0) { 13042f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson key = to; 13052f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson if (toBound == EXCLUSIVE) { 13062f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson relation = LOWER; // 'to' is too high 13072f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson } else if (comparison < 0) { 13082f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson relation = FLOOR; // we already went lower 13092f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson } 13102f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson } 13112f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson toBoundForCheck = NO_BOUND; // we've already checked the upper bound 13122f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson } 13132f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson 13142f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson if (fromBound != NO_BOUND && (relation == CEILING || relation == HIGHER)) { 13152f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson int comparison = comparator.compare(from, key); 13162f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson if (comparison >= 0) { 13172f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson key = from; 13182f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson if (fromBound == EXCLUSIVE) { 13192f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson relation = HIGHER; // 'from' is too low 13202f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson } else if (comparison > 0) { 13212f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson relation = CEILING; // we already went higher 13222f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson } 13232f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson } 13242f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson fromBoundForCheck = NO_BOUND; // we've already checked the lower bound 13252f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson } 13262f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson 13272f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson return bound(find(key, relation), fromBoundForCheck, toBoundForCheck); 13282f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson } 13292f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson 1330984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Entry<K, V> lowerEntry(K key) { 133159cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe return immutableCopy(findBounded(key, LOWER)); 1332984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1333f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1334984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K lowerKey(K key) { 13352f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson Entry<K, V> entry = findBounded(key, LOWER); 1336984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return entry != null ? entry.getKey() : null; 1337f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1338f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1339984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Entry<K, V> floorEntry(K key) { 134059cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe return immutableCopy(findBounded(key, FLOOR)); 1341f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1342f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1343984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K floorKey(K key) { 13442f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson Entry<K, V> entry = findBounded(key, FLOOR); 1345984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return entry != null ? entry.getKey() : null; 1346f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1347984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1348984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Entry<K, V> ceilingEntry(K key) { 134959cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe return immutableCopy(findBounded(key, CEILING)); 1350f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1351f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1352984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K ceilingKey(K key) { 13532f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson Entry<K, V> entry = findBounded(key, CEILING); 1354984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return entry != null ? entry.getKey() : null; 1355f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1356984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1357984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Entry<K, V> higherEntry(K key) { 135859cb78e2355929587089ee436a0172af652d2aa5Jeremy Sharpe return immutableCopy(findBounded(key, HIGHER)); 1359f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1360f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1361984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K higherKey(K key) { 13622f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson Entry<K, V> entry = findBounded(key, HIGHER); 1363984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return entry != null ? entry.getKey() : null; 1364f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1365984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1366984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Comparator<? super K> comparator() { 136794fab96cd4c1bd4363ba1d70b59475132ddd441eJesse Wilson Comparator<? super K> forward = TreeMap.this.comparator(); 136894fab96cd4c1bd4363ba1d70b59475132ddd441eJesse Wilson if (ascending) { 136994fab96cd4c1bd4363ba1d70b59475132ddd441eJesse Wilson return forward; 137094fab96cd4c1bd4363ba1d70b59475132ddd441eJesse Wilson } else { 137194fab96cd4c1bd4363ba1d70b59475132ddd441eJesse Wilson return Collections.reverseOrder(forward); 137294fab96cd4c1bd4363ba1d70b59475132ddd441eJesse Wilson } 1373f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1374f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1375984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /* 1376984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * View factory methods. 1377984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 1378984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1379bad51d783a94c137c3775bbbb95e2eefa87bd0b3Jesse Wilson private transient BoundedEntrySet entrySet; 1380bad51d783a94c137c3775bbbb95e2eefa87bd0b3Jesse Wilson private transient BoundedKeySet keySet; 1381984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1382984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public Set<Entry<K, V>> entrySet() { 1383984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson BoundedEntrySet result = entrySet; 1384984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return result != null ? result : (entrySet = new BoundedEntrySet()); 1385f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1386f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1387984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public Set<K> keySet() { 1388984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return navigableKeySet(); 1389984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1390f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1391984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public NavigableSet<K> navigableKeySet() { 1392984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson BoundedKeySet result = keySet; 1393984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return result != null ? result : (keySet = new BoundedKeySet()); 1394adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1395f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1396984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public NavigableMap<K, V> descendingMap() { 1397984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return new BoundedMap(!ascending, from, fromBound, to, toBound); 1398984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1399f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1400984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public NavigableSet<K> descendingKeySet() { 1401984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return new BoundedMap(!ascending, from, fromBound, to, toBound).navigableKeySet(); 1402984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1403f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1404984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public NavigableMap<K, V> subMap(K from, boolean fromInclusive, K to, boolean toInclusive) { 1405984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Bound fromBound = fromInclusive ? INCLUSIVE : EXCLUSIVE; 1406984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Bound toBound = toInclusive ? INCLUSIVE : EXCLUSIVE; 1407984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return subMap(from, fromBound, to, toBound); 1408f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1409f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1410984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public NavigableMap<K, V> subMap(K fromInclusive, K toExclusive) { 1411984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return subMap(fromInclusive, INCLUSIVE, toExclusive, EXCLUSIVE); 1412f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1413984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1414984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public NavigableMap<K, V> headMap(K to, boolean inclusive) { 1415984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Bound toBound = inclusive ? INCLUSIVE : EXCLUSIVE; 1416984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return subMap(null, NO_BOUND, to, toBound); 1417f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1418f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1419984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public NavigableMap<K, V> headMap(K toExclusive) { 1420984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return subMap(null, NO_BOUND, toExclusive, EXCLUSIVE); 1421984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1422f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1423984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public NavigableMap<K, V> tailMap(K from, boolean inclusive) { 1424984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Bound fromBound = inclusive ? INCLUSIVE : EXCLUSIVE; 1425984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return subMap(from, fromBound, null, NO_BOUND); 1426f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1427984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1428984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public NavigableMap<K, V> tailMap(K fromInclusive) { 1429984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return subMap(fromInclusive, INCLUSIVE, null, NO_BOUND); 1430f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1431f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1432984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson private NavigableMap<K, V> subMap(K from, Bound fromBound, K to, Bound toBound) { 1433984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (!ascending) { 1434984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson K fromTmp = from; 1435984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Bound fromBoundTmp = fromBound; 1436984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson from = to; 1437984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson fromBound = toBound; 1438984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson to = fromTmp; 1439984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson toBound = fromBoundTmp; 1440984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1441f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 14422f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson /* 14432f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson * If both the current and requested bounds are exclusive, the isInBounds check must be 14442f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson * inclusive. For example, to create (C..F) from (A..F), the bound 'F' is in bounds. 14452f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson */ 14462f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson 1447984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (fromBound == NO_BOUND) { 1448984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson from = this.from; 1449984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson fromBound = this.fromBound; 14502f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson } else { 14512f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson Bound fromBoundToCheck = fromBound == this.fromBound ? INCLUSIVE : this.fromBound; 14522f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson if (!isInBounds(from, fromBoundToCheck, this.toBound)) { 14532f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson throw outOfBounds(to, fromBoundToCheck, this.toBound); 1454984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1455984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1456f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1457984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (toBound == NO_BOUND) { 1458984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson to = this.to; 1459984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson toBound = this.toBound; 14602f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson } else { 14612f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson Bound toBoundToCheck = toBound == this.toBound ? INCLUSIVE : this.toBound; 14622f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson if (!isInBounds(to, this.fromBound, toBoundToCheck)) { 14632f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson throw outOfBounds(to, this.fromBound, toBoundToCheck); 1464984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1465984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1466984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1467984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return new BoundedMap(ascending, from, fromBound, to, toBound); 1468f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1469984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 14702f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson private IllegalArgumentException outOfBounds(Object value, Bound fromBound, Bound toBound) { 14712f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson return new IllegalArgumentException(value + " not in range " 14722f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson + fromBound.leftCap(from) + ".." + toBound.rightCap(to)); 14732f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson } 14742f2e06eeabb1c4b2064918f4aa041ba3a7fe7c67Jesse Wilson 1475984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /* 1476984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Bounded view implementations. 1477984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 1478984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1479984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson abstract class BoundedIterator<T> extends MapIterator<T> { 1480984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson protected BoundedIterator(Node<K, V> next) { 1481984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson super(next); 1482984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1483984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1484984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override protected Node<K, V> stepForward() { 1485984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> result = super.stepForward(); 1486984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (next != null && !isInBounds(next.key, NO_BOUND, toBound)) { 1487984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson next = null; 1488f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1489984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return result; 1490984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1491984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1492984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override protected Node<K, V> stepBackward() { 1493984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Node<K, V> result = super.stepBackward(); 1494984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (next != null && !isInBounds(next.key, fromBound, NO_BOUND)) { 1495984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson next = null; 1496f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1497984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return result; 1498f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1499f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1500f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1501984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson final class BoundedEntrySet extends AbstractSet<Entry<K, V>> { 1502984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public int size() { 1503984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return BoundedMap.this.size(); 1504f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1505f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1506984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public boolean isEmpty() { 1507984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return BoundedMap.this.isEmpty(); 1508f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1509f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1510984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public Iterator<Entry<K, V>> iterator() { 15117cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe return new BoundedIterator<Entry<K, V>>(endpoint(true)) { 1512984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Entry<K, V> next() { 1513984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return ascending ? stepForward() : stepBackward(); 1514984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1515984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson }; 1516984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1517984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1518984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public boolean contains(Object o) { 1519984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (!(o instanceof Entry)) { 1520984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return false; 1521f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1522984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Entry<?, ?> entry = (Entry<?, ?>) o; 1523984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return isInBounds(entry.getKey()) && findByEntry(entry) != null; 1524f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1525f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1526984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public boolean remove(Object o) { 1527984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson if (!(o instanceof Entry)) { 1528984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return false; 1529f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1530984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Entry<?, ?> entry = (Entry<?, ?>) o; 1531984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return isInBounds(entry.getKey()) && TreeMap.this.entrySet().remove(entry); 1532f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1533f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1534f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1535984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson final class BoundedKeySet extends AbstractSet<K> implements NavigableSet<K> { 1536984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public int size() { 1537984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return BoundedMap.this.size(); 1538984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1539984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1540984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public boolean isEmpty() { 1541984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return BoundedMap.this.isEmpty(); 1542f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1543984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1544984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public Iterator<K> iterator() { 15457cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe return new BoundedIterator<K>(endpoint(true)) { 1546984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K next() { 1547984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return (ascending ? stepForward() : stepBackward()).key; 1548984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1549984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson }; 1550adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1551984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1552984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Iterator<K> descendingIterator() { 15537cf7ec13b4e7e8f044c310e63dd0f6f9f58577d7Jeremy Sharpe return new BoundedIterator<K>(endpoint(false)) { 1554984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K next() { 1555984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return (ascending ? stepBackward() : stepForward()).key; 1556984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1557984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson }; 1558f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1559f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1560984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public boolean contains(Object key) { 1561984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return isInBounds(key) && findByObject(key) != null; 1562984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1563f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 1564984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public boolean remove(Object key) { 1565984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return isInBounds(key) && removeInternalByKey(key) != null; 1566984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1567adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1568984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /* 1569984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Navigable methods. 1570984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 1571984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1572984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K first() { 1573984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return firstKey(); 1574f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 1575984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1576984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K pollFirst() { 1577984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Entry<K, ?> entry = pollFirstEntry(); 1578984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return entry != null ? entry.getKey() : null; 1579adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1580adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1581984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K last() { 1582984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return lastKey(); 1583984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1584adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1585984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K pollLast() { 1586984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Entry<K, ?> entry = pollLastEntry(); 1587984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return entry != null ? entry.getKey() : null; 1588984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1589984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1590984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K lower(K key) { 1591984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return lowerKey(key); 1592984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1593984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1594984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K floor(K key) { 1595984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return floorKey(key); 1596984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1597984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1598984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K ceiling(K key) { 1599984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return ceilingKey(key); 1600984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1601984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1602984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public K higher(K key) { 1603984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return higherKey(key); 1604984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1605984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1606984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public Comparator<? super K> comparator() { 1607984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return BoundedMap.this.comparator(); 1608984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1609984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1610984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /* 1611984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * View factory methods. 1612984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson */ 1613984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1614984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public NavigableSet<K> subSet(K from, boolean fromInclusive, K to, boolean toInclusive) { 1615984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return subMap(from, fromInclusive, to, toInclusive).navigableKeySet(); 1616984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1617984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1618984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public SortedSet<K> subSet(K fromInclusive, K toExclusive) { 1619984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return subMap(fromInclusive, toExclusive).navigableKeySet(); 1620984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1621984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1622984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public NavigableSet<K> headSet(K to, boolean inclusive) { 1623984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return headMap(to, inclusive).navigableKeySet(); 1624984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1625984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1626984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public SortedSet<K> headSet(K toExclusive) { 1627984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return headMap(toExclusive).navigableKeySet(); 1628984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1629984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1630984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public NavigableSet<K> tailSet(K from, boolean inclusive) { 1631984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return tailMap(from, inclusive).navigableKeySet(); 1632984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1633984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1634984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public SortedSet<K> tailSet(K fromInclusive) { 1635984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return tailMap(fromInclusive).navigableKeySet(); 1636984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1637984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1638984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson public NavigableSet<K> descendingSet() { 1639984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return new BoundedMap(!ascending, from, fromBound, to, toBound).navigableKeySet(); 1640adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1641adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1642adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1643984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Object writeReplace() throws ObjectStreamException { 1644984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return ascending 1645984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson ? new AscendingSubMap<K, V>(TreeMap.this, from, fromBound, to, toBound) 1646984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson : new DescendingSubMap<K, V>(TreeMap.this, from, fromBound, to, toBound); 1647984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1648984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1649adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1650adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1651984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Returns the number of elements in the iteration. 1652adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1653984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson static int count(Iterator<?> iterator) { 1654984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson int count = 0; 1655984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson while (iterator.hasNext()) { 1656984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson iterator.next(); 1657984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson count++; 1658984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1659984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return count; 1660adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1661adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1662984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson /* 1663984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson * Serialization 1664adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1665984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1666984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson private static final long serialVersionUID = 919286545866124006L; 1667984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1668984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson private void writeObject(ObjectOutputStream stream) throws IOException { 166994fab96cd4c1bd4363ba1d70b59475132ddd441eJesse Wilson stream.putFields().put("comparator", comparator()); 1670984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson stream.writeFields(); 1671984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson stream.writeInt(size); 1672984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson for (Map.Entry<K, V> entry : entrySet()) { 1673984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson stream.writeObject(entry.getKey()); 1674984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson stream.writeObject(entry.getValue()); 1675adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1676adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1677adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1678984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @SuppressWarnings("unchecked") // we have to trust that keys are Ks and values are Vs 1679984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { 1680984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson GetField fields = stream.readFields(); 1681984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson comparator = (Comparator<? super K>) fields.get("comparator", null); 1682adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (comparator == null) { 1683984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson comparator = (Comparator<? super K>) NATURAL_ORDER; 1684984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1685984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson int size = stream.readInt(); 1686984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson for (int i = 0; i < size; i++) { 1687984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson putInternal((K) stream.readObject(), (V) stream.readObject()); 1688adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1689adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1690adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1691984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson static abstract class NavigableSubMap<K, V> extends AbstractMap<K, V> implements Serializable { 16920790403433525b7ca94391592d72b13a4c94578cJesse Wilson private static final long serialVersionUID = -2102997345730753016L; 1693984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson TreeMap<K, V> m; 1694984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Object lo; 1695984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Object hi; 1696984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson boolean fromStart; 1697984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson boolean toEnd; 1698984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson boolean loInclusive; 1699984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson boolean hiInclusive; 1700adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1701984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson NavigableSubMap(TreeMap<K, V> delegate, K from, Bound fromBound, K to, Bound toBound) { 1702984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson this.m = delegate; 1703984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson this.lo = from; 1704984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson this.hi = to; 17050790403433525b7ca94391592d72b13a4c94578cJesse Wilson this.fromStart = fromBound == NO_BOUND; 17060790403433525b7ca94391592d72b13a4c94578cJesse Wilson this.toEnd = toBound == NO_BOUND; 1707984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson this.loInclusive = fromBound == INCLUSIVE; 1708984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson this.hiInclusive = toBound == INCLUSIVE; 1709984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1710adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1711984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public Set<Entry<K, V>> entrySet() { 1712984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson throw new UnsupportedOperationException(); 1713984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1714adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1715984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @SuppressWarnings("unchecked") // we have to trust that the bounds are Ks 17160790403433525b7ca94391592d72b13a4c94578cJesse Wilson protected Object readResolve() throws ObjectStreamException { 17170790403433525b7ca94391592d72b13a4c94578cJesse Wilson Bound fromBound = fromStart ? NO_BOUND : (loInclusive ? INCLUSIVE : EXCLUSIVE); 17180790403433525b7ca94391592d72b13a4c94578cJesse Wilson Bound toBound = toEnd ? NO_BOUND : (hiInclusive ? INCLUSIVE : EXCLUSIVE); 1719984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson boolean ascending = !(this instanceof DescendingSubMap); 1720984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson return m.new BoundedMap(ascending, (K) lo, fromBound, (K) hi, toBound); 1721adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1722adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1723adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1724984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson static class DescendingSubMap<K, V> extends NavigableSubMap<K, V> { 1725984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson private static final long serialVersionUID = 912986545866120460L; 1726984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson Comparator<K> reverseComparator; 1727984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson DescendingSubMap(TreeMap<K, V> delegate, K from, Bound fromBound, K to, Bound toBound) { 1728984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson super(delegate, from, fromBound, to, toBound); 1729adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1730adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1731adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1732984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson static class AscendingSubMap<K, V> extends NavigableSubMap<K, V> { 1733984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson private static final long serialVersionUID = 912986545866124060L; 1734984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson AscendingSubMap(TreeMap<K, V> delegate, K from, Bound fromBound, K to, Bound toBound) { 1735984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson super(delegate, from, fromBound, to, toBound); 1736984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1737984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1738984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 17390790403433525b7ca94391592d72b13a4c94578cJesse Wilson class SubMap extends AbstractMap<K, V> implements Serializable { 1740984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson private static final long serialVersionUID = -6520786458950516097L; 17410790403433525b7ca94391592d72b13a4c94578cJesse Wilson Object fromKey; 17420790403433525b7ca94391592d72b13a4c94578cJesse Wilson Object toKey; 1743984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson boolean fromStart; 1744984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson boolean toEnd; 1745984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1746984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @Override public Set<Entry<K, V>> entrySet() { 1747984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson throw new UnsupportedOperationException(); 1748984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson } 1749984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson 1750984dc62f58d1f9611ebccc2598f714c15242a6ebJesse Wilson @SuppressWarnings("unchecked") // we have to trust that the bounds are Ks 17510790403433525b7ca94391592d72b13a4c94578cJesse Wilson protected Object readResolve() throws ObjectStreamException { 17520790403433525b7ca94391592d72b13a4c94578cJesse Wilson Bound fromBound = fromStart ? NO_BOUND : INCLUSIVE; 17530790403433525b7ca94391592d72b13a4c94578cJesse Wilson Bound toBound = toEnd ? NO_BOUND : EXCLUSIVE; 17540790403433525b7ca94391592d72b13a4c94578cJesse Wilson return new BoundedMap(true, (K) fromKey, fromBound, (K) toKey, toBound); 1755adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1756adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1757adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project} 1758