1cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath/* 2cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath * Licensed to the Apache Software Foundation (ASF) under one or more 3cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath * contributor license agreements. See the NOTICE file distributed with 4cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath * this work for additional information regarding copyright ownership. 5cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath * The ASF licenses this file to You under the Apache License, Version 2.0 6cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath * (the "License"); you may not use this file except in compliance with 7cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath * the License. You may obtain a copy of the License at 8cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath * 9cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath * http://www.apache.org/licenses/LICENSE-2.0 10cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath * 11cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath * Unless required by applicable law or agreed to in writing, software 12cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath * distributed under the License is distributed on an "AS IS" BASIS, 13cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath * See the License for the specific language governing permissions and 15cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath * limitations under the License. 16cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath */ 17cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 18ab762bb740405d0fefcccf4a0899a234f995be13Narayan Kamathpackage org.apache.harmony.tests.java.util; 19cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 20cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamathimport java.io.IOException; 21cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamathimport java.io.ObjectInputStream; 22cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamathimport java.io.ObjectOutputStream; 23cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamathimport java.io.Serializable; 24cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamathimport java.util.AbstractSet; 25cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamathimport java.util.ArrayList; 26cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamathimport java.util.Collection; 27cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamathimport java.util.Collections; 28cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamathimport java.util.Comparator; 29cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamathimport java.util.ConcurrentModificationException; 30cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamathimport java.util.Iterator; 31cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamathimport java.util.Map; 32cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamathimport java.util.NoSuchElementException; 33cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamathimport java.util.Set; 34cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamathimport java.util.SortedMap; 35cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 36cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamathpublic class RefSortedMap<K, V> extends java.util.AbstractMap<K, V> 37cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath implements SortedMap<K, V>, Cloneable, Serializable { 38cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 39cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath private static final long serialVersionUID = 1L; 40cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 41cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath private static final class MapEntry<K, V> implements Map.Entry<K, V> { 42cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 43cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath final K key; 44cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath V value; 45cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 46cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath MapEntry(K key, V value) { 47cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath this.key = key; 48cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath this.value = value; 49cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 50cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 51cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public K getKey() { 52cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return key; 53cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 54cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 55cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public V getValue() { 56cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return value; 57cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 58cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 59cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public V setValue(V v) { 60cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath V res = value; 61cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath value = v; 62cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return res; 63cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 64cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 65cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public int hashCode() { 66cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return (getKey() == null ? 0 : getKey().hashCode()) 67cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath ^ (getValue() == null ? 0 : getValue().hashCode()); 68cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 69cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 70cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public boolean equals(Object object) { 71cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath if (this == object) { 72cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return true; 73cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 74cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath if (object instanceof Map.Entry) { 75cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object; 76cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return (getKey() == null ? entry.getKey() == null : getKey().equals(entry 77cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath .getKey())) 78cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath && (getValue() == null ? entry.getValue() == null : getValue() 79cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath .equals(entry.getValue())); 80cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 81cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return false; 82cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 83cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 84cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 85cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath transient ArrayList<MapEntry<K, V>> entries = new ArrayList<MapEntry<K, V>>(); 86cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath transient int modCnt; 87cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 88cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath private final Comparator<? super K> comparator; 89cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 90cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath class SubMap extends java.util.AbstractMap<K, V> 91cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath implements SortedMap<K, V>, Cloneable { 92cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 93cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath final boolean hasStart, hasEnd; 94cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath final K start, end; 95cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 96cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath SubMap(boolean hasFirst, K first, boolean hasLast, K last) { 97cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath this.hasStart = hasFirst; 98cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath this.start = first; 99cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath this.hasEnd = hasLast; 100cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath this.end = last; 101cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath if (hasStart && hasEnd && compare(start, end) >= 0) { 102cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath throw new IllegalArgumentException(); 103cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 104cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 105cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 106cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath @Override 107cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public Set<java.util.Map.Entry<K, V>> entrySet() { 108cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return new AbstractSet<Entry<K, V>>() { 109cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 110cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath @Override 111cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public Iterator<java.util.Map.Entry<K, V>> iterator() { 112cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return new Iterator<Entry<K, V>>() { 113cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath int modCnt = RefSortedMap.this.modCnt; 114cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath int offset = SubMap.this.size() > 0 ? 115cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath bsearch(SubMap.this.firstKey()) - 1 : 116cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath entries.size(); 117cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 118cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public boolean hasNext() { 119cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath if (modCnt != RefSortedMap.this.modCnt) { 120cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath throw new ConcurrentModificationException(); 121cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 122cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return offset + 1 < entries.size() 123cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath && isInRange(entries.get(offset + 1).getKey()); 124cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 125cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 126cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public Map.Entry<K, V> next() { 127cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath if (modCnt != RefSortedMap.this.modCnt) { 128cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath throw new ConcurrentModificationException(); 129cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 130cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath if (!hasNext()) { 131cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath throw new NoSuchElementException(); 132cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 133cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath offset++; 134cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return entries.get(offset); 135cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 136cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 137cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public void remove() { 138cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath if (modCnt != RefSortedMap.this.modCnt) { 139cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath throw new ConcurrentModificationException(); 140cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 141cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath modCnt++; 142cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath RefSortedMap.this.modCnt++; 143cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath RefSortedMap.this.entries.remove(offset); 144cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath offset--; 145cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 146cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 147cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath }; 148cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 149cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 150cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath @Override 151cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public int size() { 152cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath try { 153cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath int lastIdx = bsearch(SubMap.this.lastKey()); 154cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath int firstIdx = bsearch(SubMap.this.firstKey()); 155cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return lastIdx - firstIdx + 1; 156cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } catch (NoSuchElementException e) { 157cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return 0; 158cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } catch (ArrayIndexOutOfBoundsException e) { 159cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return 0; 160cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 161cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 162cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 163cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath }; 164cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 165cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 166cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public Comparator<? super K> comparator() { 167cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return RefSortedMap.this.comparator(); 168cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 169cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 170cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public K firstKey() { 171cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath if (!hasStart) { 172cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath K res = RefSortedMap.this.firstKey(); 173cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath if (!isInRange(res)) { 174cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath throw new NoSuchElementException(); 175cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 176cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return res; 177cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 178cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath int idx = bsearch(start); 179cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath if (idx >= 0) { 180cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return start; 181cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 182cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath if (-idx - 1 >= entries.size() || !isInRange(entries.get(-idx - 1).getKey())) { 183cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath throw new NoSuchElementException(); 184cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 185cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return entries.get(-idx - 1).getKey(); 186cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 187cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 188cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public SortedMap<K, V> headMap(K key) { 189cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath if (!isInRange(key)) { 190cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath throw new IllegalArgumentException(); 191cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 192cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return new SubMap(hasStart, start, true, key); 193cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 194cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 195cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public K lastKey() { 196cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath if (!hasEnd) { 197cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath K res = RefSortedMap.this.lastKey(); 198cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath if (!isInRange(res)) { 199cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath throw new NoSuchElementException(); 200cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 201cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return res; 202cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 203cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath int idx = bsearch(end); 204cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath idx = idx >= 0 ? idx - 1 : -idx - 2; 205cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath if (idx < 0 || !isInRange(entries.get(idx).getKey())) { 206cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath throw new NoSuchElementException(); 207cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 208cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return entries.get(idx).getKey(); 209cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 210cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 211cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public SortedMap<K, V> subMap(K startKey, K endKey) { 212cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath if (!isInRange(startKey)) { 213cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath throw new IllegalArgumentException(); 214cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 215cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath if (!isInRange(endKey)) { 216cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath throw new IllegalArgumentException(); 217cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 218cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return new SubMap(true, startKey, true, endKey); 219cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 220cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 221cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public SortedMap<K, V> tailMap(K key) { 222cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath if (!isInRange(key)) { 223cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath throw new IllegalArgumentException(); 224cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 225cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return new SubMap(true, key, hasEnd, end); 226cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 227cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 228cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath private boolean isInRange(K key) { 229cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath if (hasStart && compare(key, start) < 0) { 230cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return false; 231cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 232cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath if (hasEnd && compare(key, end) >= 0) { 233cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return false; 234cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 235cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return true; 236cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 237cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 238cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 239cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 240cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public RefSortedMap() { 241cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath this((Comparator<? super K>) null); 242cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 243cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 244cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath @SuppressWarnings("unchecked") 245cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public int compare(K start, K end) { 246cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return comparator != null ? comparator.compare(start, end) 247cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath : ((Comparable<K>) start).compareTo(end); 248cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 249cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 250cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath @SuppressWarnings("unchecked") 251cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public RefSortedMap(Comparator<? super K> comparator) { 252cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath this.comparator = comparator; 253cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath cmp = createCmp(); 254cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 255cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 256cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public RefSortedMap(Map<? extends K, ? extends V> map) { 257cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath this(); 258cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath putAll(map); 259cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 260cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 261cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public RefSortedMap(SortedMap<K, ? extends V> map) { 262cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath this(map.comparator()); 263cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath putAll(map); 264cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 265cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 266cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public Comparator<? super K> comparator() { 267cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return comparator; 268cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 269cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 270cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public Set<Map.Entry<K, V>> entrySet() { 271cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return tailMap(firstKey()).entrySet(); 272cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 273cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 274cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public K firstKey() { 275cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return entries.get(0).getKey(); 276cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 277cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 278cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public SortedMap<K, V> headMap(K key) { 279cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return new SubMap(false, null, true, key); 280cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 281cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 282cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public Set<K> keySet() { 283cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return tailMap(firstKey()).keySet(); 284cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 285cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 286cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public K lastKey() { 287cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return entries.get(entries.size() - 1).getKey(); 288cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 289cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 290cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public SortedMap<K, V> subMap(K startKey, K endKey) { 291cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return new SubMap(true, startKey, true, endKey); 292cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 293cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 294cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public SortedMap<K, V> tailMap(K key) { 295cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return new SubMap(true, key, false, null); 296cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 297cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 298cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public Collection<V> values() { 299cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return tailMap(firstKey()).values(); 300cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 301cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 302cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public void clear() { 303cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath entries.clear(); 304cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 305cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 306cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public boolean containsKey(Object arg0) { 307cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return bsearch(arg0) >= 0; 308cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 309cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 310cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public boolean containsValue(Object arg0) { 311cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath for (V v : values()) { 312cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath if (arg0.equals(v)) { 313cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return true; 314cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 315cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 316cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return false; 317cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 318cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 319cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath @SuppressWarnings("unchecked") 320cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public V get(Object arg0) { 321cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath int idx = bsearch(arg0); 322cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return idx >= 0 ? entries.get(idx).getValue() : null; 323cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 324cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 325cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public boolean isEmpty() { 326cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return entries.isEmpty(); 327cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 328cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 329cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public V put(K arg0, V arg1) { 330cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath modCnt++; 331cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath int idx = bsearch(arg0); 332cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath if (idx >= 0) { 333cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return entries.get(idx).setValue(arg1); 334cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 335cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath entries.add(-idx - 1, new MapEntry<K, V>(arg0, arg1)); 336cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return null; 337cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 338cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 339cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public void putAll(Map<? extends K, ? extends V> arg0) { 340cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath for (Map.Entry<? extends K, ? extends V> e : arg0.entrySet()) { 341cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath put(e.getKey(), e.getValue()); 342cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 343cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 344cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 345cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath @SuppressWarnings("unchecked") 346cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public V remove(Object arg0) { 347cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath modCnt++; 348cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath int idx = bsearch(arg0); 349cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath if (idx < 0) { 350cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return null; 351cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 352cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return entries.remove(idx).getValue(); 353cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 354cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 355cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath transient private Comparator<MapEntry<K, V>> cmp = createCmp(); 356cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 357cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath Comparator<MapEntry<K, V>> createCmp() { 358cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return new Comparator<MapEntry<K, V>>() { 359cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 360cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public int compare(MapEntry<K, V> arg0, MapEntry<K, V> arg1) { 361cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return RefSortedMap.this.compare(arg0.getKey(), arg1.getKey()); 362cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 363cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 364cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath }; 365cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 366cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 367cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath @SuppressWarnings("unchecked") 368cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath private int bsearch(Object arg0) { 369cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return Collections.binarySearch(entries, new MapEntry<K, V>((K) arg0, null), cmp); 370cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 371cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 372cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public int size() { 373cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return entries.size(); 374cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 375cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 376cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath public RefSortedMap<K, V> clone() { 377cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath return new RefSortedMap<K, V>(this); 378cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 379cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 380cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath private void writeObject(ObjectOutputStream stream) throws IOException { 381cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath stream.defaultWriteObject(); 382cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath stream.writeInt(size()); 383cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath for (Map.Entry<K, V> e : entrySet()) { 384cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath stream.writeObject(e.getKey()); 385cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath stream.writeObject(e.getValue()); 386cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 387cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 388cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 389cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath @SuppressWarnings("unchecked") 390cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath private void readObject(ObjectInputStream stream) throws IOException, 391cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath ClassNotFoundException { 392cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 393cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath cmp = createCmp(); 394cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath stream.defaultReadObject(); 395cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath int size = stream.readInt(); 396cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath entries = new ArrayList<MapEntry<K, V>>(size); 397cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath for (int i = 0; i < size; i++) { 398cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath put((K) stream.readObject(), (V) stream.readObject()); 399cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 400cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath } 401cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath 402cb318c6f4fe5b0e20099fa85f1b95ccb2d24119fNarayan Kamath} 403