1561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes/* 2561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes * Licensed to the Apache Software Foundation (ASF) under one or more 3561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes * contributor license agreements. See the NOTICE file distributed with 4561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes * this work for additional information regarding copyright ownership. 5561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes * The ASF licenses this file to You under the Apache License, Version 2.0 6561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes * (the "License"); you may not use this file except in compliance with 7561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes * the License. You may obtain a copy of the License at 8561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes * 9561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes * http://www.apache.org/licenses/LICENSE-2.0 10561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes * 11561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes * Unless required by applicable law or agreed to in writing, software 12561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes * distributed under the License is distributed on an "AS IS" BASIS, 13561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes * See the License for the specific language governing permissions and 15561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes * limitations under the License. 16561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes */ 17561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 18561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughespackage org.apache.harmony.luni.tests.java.util; 19561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 20561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughesimport java.io.IOException; 21561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughesimport java.io.ObjectInputStream; 22561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughesimport java.io.ObjectOutputStream; 23561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughesimport java.io.Serializable; 24561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughesimport java.util.AbstractSet; 25561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughesimport java.util.ArrayList; 26561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughesimport java.util.Collection; 27561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughesimport java.util.Collections; 28561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughesimport java.util.Comparator; 29561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughesimport java.util.ConcurrentModificationException; 30561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughesimport java.util.Iterator; 31561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughesimport java.util.Map; 32561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughesimport java.util.NoSuchElementException; 33561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughesimport java.util.Set; 34561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughesimport java.util.SortedMap; 35561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 36561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughespublic class RefSortedMap<K, V> extends java.util.AbstractMap<K, V> 37561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes implements SortedMap<K, V>, Cloneable, Serializable { 38561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 39561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes private static final long serialVersionUID = 1L; 40561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 41561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes private static final class MapEntry<K, V> implements Map.Entry<K, V> { 42561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 43561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes final K key; 44561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes V value; 45561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 46561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes MapEntry(K key, V value) { 47561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes this.key = key; 48561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes this.value = value; 49561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 50561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 51561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public K getKey() { 52561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return key; 53561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 54561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 55561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public V getValue() { 56561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return value; 57561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 58561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 59561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public V setValue(V v) { 60561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes V res = value; 61561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes value = v; 62561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return res; 63561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 64561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 65561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public int hashCode() { 66561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return (getKey() == null ? 0 : getKey().hashCode()) 67561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes ^ (getValue() == null ? 0 : getValue().hashCode()); 68561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 69561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 70561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public boolean equals(Object object) { 71561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes if (this == object) { 72561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return true; 73561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 74561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes if (object instanceof Map.Entry) { 75561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object; 76561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return (getKey() == null ? entry.getKey() == null : getKey().equals(entry 77561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes .getKey())) 78561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes && (getValue() == null ? entry.getValue() == null : getValue() 79561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes .equals(entry.getValue())); 80561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 81561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return false; 82561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 83561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 84561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 85561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes transient ArrayList<MapEntry<K, V>> entries = new ArrayList<MapEntry<K, V>>(); 86561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes transient int modCnt; 87561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 88561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes private final Comparator<? super K> comparator; 89561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 90561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes class SubMap extends java.util.AbstractMap<K, V> 91561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes implements SortedMap<K, V>, Cloneable { 92561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 93561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes final boolean hasStart, hasEnd; 94561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes final K start, end; 95561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 96561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes SubMap(boolean hasFirst, K first, boolean hasLast, K last) { 97561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes this.hasStart = hasFirst; 98561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes this.start = first; 99561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes this.hasEnd = hasLast; 100561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes this.end = last; 101561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes if (hasStart && hasEnd && compare(start, end) >= 0) { 102561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes throw new IllegalArgumentException(); 103561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 104561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 105561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 106561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes @Override 107561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public Set<java.util.Map.Entry<K, V>> entrySet() { 108561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return new AbstractSet<Entry<K,V>> () { 109561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 110561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes @Override 111561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public Iterator<java.util.Map.Entry<K, V>> iterator() { 112561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return new Iterator<Entry<K,V>>() { 113561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes int modCnt = RefSortedMap.this.modCnt; 114561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes int offset = SubMap.this.size() > 0 ? 115561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes bsearch(SubMap.this.firstKey()) - 1 : 116561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes entries.size(); 117561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 118561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public boolean hasNext() { 119561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes if (modCnt != RefSortedMap.this.modCnt) { 120561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes throw new ConcurrentModificationException(); 121561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 122561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return offset + 1 < entries.size() 123561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes && isInRange(entries.get(offset + 1).getKey()); 124561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 125561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 126561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public Map.Entry<K, V> next() { 127561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes if (modCnt != RefSortedMap.this.modCnt) { 128561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes throw new ConcurrentModificationException(); 129561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 130561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes if (!hasNext()) { 131561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes throw new NoSuchElementException(); 132561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 133561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes offset++; 134561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return entries.get(offset); 135561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 136561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 137561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public void remove() { 138561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes if (modCnt != RefSortedMap.this.modCnt) { 139561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes throw new ConcurrentModificationException(); 140561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 141561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes modCnt++; 142561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes RefSortedMap.this.modCnt++; 143561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes RefSortedMap.this.entries.remove(offset); 144561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes offset--; 145561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 146561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 147561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes }; 148561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 149561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 150561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes @Override 151561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public int size() { 152561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes try { 153561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes int lastIdx = bsearch(SubMap.this.lastKey()); 154561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes int firstIdx = bsearch(SubMap.this.firstKey()); 155561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return lastIdx - firstIdx + 1; 156561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } catch (NoSuchElementException e) { 157561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return 0; 158561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } catch (ArrayIndexOutOfBoundsException e) { 159561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return 0; 160561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 161561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 162561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 163561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes }; 164561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 165561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 166561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public Comparator<? super K> comparator() { 167561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return RefSortedMap.this.comparator(); 168561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 169561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 170561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public K firstKey() { 171561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes if (!hasStart) { 172561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes K res = RefSortedMap.this.firstKey(); 173561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes if (!isInRange(res)) { 174561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes throw new NoSuchElementException(); 175561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 176561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return res; 177561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 178561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes int idx = bsearch(start); 179561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes if (idx >= 0) { 180561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return start; 181561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 182561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes if (-idx - 1 >= entries.size() || !isInRange(entries.get(-idx - 1).getKey())) { 183561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes throw new NoSuchElementException(); 184561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 185561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return entries.get(-idx - 1).getKey(); 186561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 187561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 188561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public SortedMap<K, V> headMap(K key) { 189561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes if (!isInRange(key)) { 190561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes throw new IllegalArgumentException(); 191561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 192561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return new SubMap(hasStart, start, true, key); 193561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 194561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 195561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public K lastKey() { 196561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes if (!hasEnd) { 197561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes K res = RefSortedMap.this.lastKey(); 198561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes if (!isInRange(res)) { 199561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes throw new NoSuchElementException(); 200561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 201561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return res; 202561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 203561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes int idx = bsearch(end); 204561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes idx = idx >= 0 ? idx - 1 : -idx -2; 205561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes if (idx < 0 || !isInRange(entries.get(idx).getKey())) { 206561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes throw new NoSuchElementException(); 207561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 208561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return entries.get(idx).getKey(); 209561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 210561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 211561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public SortedMap<K, V> subMap(K startKey, K endKey) { 212561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes if (!isInRange(startKey)) { 213561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes throw new IllegalArgumentException(); 214561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 215561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes if (!isInRange(endKey)) { 216561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes throw new IllegalArgumentException(); 217561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 218561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return new SubMap(true, startKey, true, endKey); 219561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 220561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 221561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public SortedMap<K, V> tailMap(K key) { 222561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes if (!isInRange(key)) { 223561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes throw new IllegalArgumentException(); 224561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 225561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return new SubMap(true, key, hasEnd, end); 226561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 227561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 228561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes private boolean isInRange(K key) { 229561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes if (hasStart && compare(key, start) < 0) { 230561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return false; 231561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 232561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes if (hasEnd && compare(key, end) >= 0) { 233561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return false; 234561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 235561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return true; 236561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 237561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 238561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 239561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 240561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public RefSortedMap() { 241561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes this((Comparator<? super K>) null); 242561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 243561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 244561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes @SuppressWarnings("unchecked") 245561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public int compare(K start, K end) { 246561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return comparator != null ? comparator.compare(start, end) 247561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes : ((Comparable<K>) start).compareTo(end); 248561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 249561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 250561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes @SuppressWarnings("unchecked") 251561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public RefSortedMap(Comparator<? super K> comparator) { 252561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes this.comparator = comparator; 253561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes cmp = createCmp(); 254561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 255561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 256561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public RefSortedMap(Map<? extends K, ? extends V> map) { 257561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes this(); 258561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes putAll(map); 259561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 260561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 261561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public RefSortedMap(SortedMap<K, ? extends V> map) { 262561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes this(map.comparator()); 263561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes putAll(map); 264561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 265561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 266561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public Comparator<? super K> comparator() { 267561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return comparator; 268561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 269561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 270561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public Set<Map.Entry<K, V>> entrySet() { 271561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return tailMap(firstKey()).entrySet(); 272561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 273561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 274561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public K firstKey() { 275561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return entries.get(0).getKey(); 276561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 277561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 278561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public SortedMap<K, V> headMap(K key) { 279561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return new SubMap(false, null, true, key); 280561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 281561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 282561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public Set<K> keySet() { 283561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return tailMap(firstKey()).keySet(); 284561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 285561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 286561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public K lastKey() { 287561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return entries.get(entries.size() - 1).getKey(); 288561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 289561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 290561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public SortedMap<K, V> subMap(K startKey, K endKey) { 291561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return new SubMap(true, startKey, true, endKey); 292561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 293561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 294561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public SortedMap<K, V> tailMap(K key) { 295561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return new SubMap(true, key, false, null); 296561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 297561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 298561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public Collection<V> values() { 299561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return tailMap(firstKey()).values(); 300561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 301561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 302561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public void clear() { 303561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes entries.clear(); 304561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 305561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 306561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public boolean containsKey(Object arg0) { 307561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return bsearch(arg0) >= 0; 308561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 309561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 310561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public boolean containsValue(Object arg0) { 311561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes for (V v : values()) { 312561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes if (arg0.equals(v)) { 313561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return true; 314561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 315561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 316561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return false; 317561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 318561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 319561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes @SuppressWarnings("unchecked") 320561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public V get(Object arg0) { 321561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes int idx = bsearch(arg0); 322561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return idx >= 0 ? entries.get(idx).getValue() : null; 323561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 324561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 325561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public boolean isEmpty() { 326561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return entries.isEmpty(); 327561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 328561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 329561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public V put(K arg0, V arg1) { 330561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes modCnt++; 331561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes int idx = bsearch(arg0); 332561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes if (idx >= 0) { 333561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return entries.get(idx).setValue(arg1); 334561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 335561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes entries.add(-idx -1, new MapEntry<K, V>(arg0, arg1)); 336561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return null; 337561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 338561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 339561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public void putAll(Map<? extends K, ? extends V> arg0) { 340561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes for (Map.Entry<? extends K, ? extends V> e : arg0.entrySet()) { 341561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes put(e.getKey(), e.getValue()); 342561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 343561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 344561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 345561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes @SuppressWarnings("unchecked") 346561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public V remove(Object arg0) { 347561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes modCnt++; 348561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes int idx = bsearch(arg0); 349561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes if (idx < 0) { 350561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return null; 351561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 352561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return entries.remove(idx).getValue(); 353561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 354561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 355561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes transient private Comparator<MapEntry<K, V>> cmp = createCmp(); 356561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 357561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes Comparator<MapEntry<K, V>> createCmp() { 358561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return new Comparator<MapEntry<K, V>>() { 359561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 360561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public int compare(MapEntry<K, V> arg0, MapEntry<K, V> arg1) { 361561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return RefSortedMap.this.compare(arg0.getKey(), arg1.getKey()); 362561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 363561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 364561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes }; 365561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 366561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 367561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes @SuppressWarnings("unchecked") 368561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes private int bsearch(Object arg0) { 369561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return Collections.binarySearch(entries, new MapEntry<K, V>((K) arg0, null), cmp); 370561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 371561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 372561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public int size() { 373561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return entries.size(); 374561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 375561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 376561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes public RefSortedMap<K, V> clone() { 377561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes return new RefSortedMap<K, V>(this); 378561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 379561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 380561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes private void writeObject(ObjectOutputStream stream) throws IOException { 381561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes stream.defaultWriteObject(); 382561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes stream.writeInt(size()); 383561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes for (Map.Entry<K, V> e : entrySet()) { 384561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes stream.writeObject(e.getKey()); 385561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes stream.writeObject(e.getValue()); 386561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 387561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 388561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 389561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes @SuppressWarnings("unchecked") 390561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes private void readObject(ObjectInputStream stream) throws IOException, 391561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes ClassNotFoundException { 392561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 393561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes cmp = createCmp(); 394561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes stream.defaultReadObject(); 395561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes int size = stream.readInt(); 396561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes entries = new ArrayList<MapEntry<K, V>>(size); 397561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes for (int i = 0; i < size; i++) { 398561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes put((K) stream.readObject(), (V) stream.readObject()); 399561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 400561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes } 401561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes 402561ee011997c6c2f1befbfaa9d5f0a99771c1d63Elliott Hughes} 403