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