1 /* 2 * Copyright (C) 2013 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package android.util; 18 19 import android.annotation.Nullable; 20 21 import java.lang.reflect.Array; 22 import java.util.Collection; 23 import java.util.Iterator; 24 import java.util.Map; 25 import java.util.NoSuchElementException; 26 import java.util.Objects; 27 import java.util.Set; 28 29 /** 30 * Helper for writing standard Java collection interfaces to a data 31 * structure like {@link ArrayMap}. 32 * @hide 33 */ 34 abstract class MapCollections<K, V> { 35 EntrySet mEntrySet; 36 KeySet mKeySet; 37 ValuesCollection mValues; 38 39 final class ArrayIterator<T> implements Iterator<T> { 40 final int mOffset; 41 int mSize; 42 int mIndex; 43 boolean mCanRemove = false; 44 ArrayIterator(int offset)45 ArrayIterator(int offset) { 46 mOffset = offset; 47 mSize = colGetSize(); 48 } 49 50 @Override hasNext()51 public boolean hasNext() { 52 return mIndex < mSize; 53 } 54 55 @Override next()56 public T next() { 57 if (!hasNext()) throw new NoSuchElementException(); 58 Object res = colGetEntry(mIndex, mOffset); 59 mIndex++; 60 mCanRemove = true; 61 return (T)res; 62 } 63 64 @Override remove()65 public void remove() { 66 if (!mCanRemove) { 67 throw new IllegalStateException(); 68 } 69 mIndex--; 70 mSize--; 71 mCanRemove = false; 72 colRemoveAt(mIndex); 73 } 74 } 75 76 final class MapIterator implements Iterator<Map.Entry<K, V>>, Map.Entry<K, V> { 77 int mEnd; 78 int mIndex; 79 boolean mEntryValid = false; 80 MapIterator()81 MapIterator() { 82 mEnd = colGetSize() - 1; 83 mIndex = -1; 84 } 85 86 @Override hasNext()87 public boolean hasNext() { 88 return mIndex < mEnd; 89 } 90 91 @Override next()92 public Map.Entry<K, V> next() { 93 if (!hasNext()) throw new NoSuchElementException(); 94 mIndex++; 95 mEntryValid = true; 96 return this; 97 } 98 99 @Override remove()100 public void remove() { 101 if (!mEntryValid) { 102 throw new IllegalStateException(); 103 } 104 colRemoveAt(mIndex); 105 mIndex--; 106 mEnd--; 107 mEntryValid = false; 108 } 109 110 @Override getKey()111 public K getKey() { 112 if (!mEntryValid) { 113 throw new IllegalStateException( 114 "This container does not support retaining Map.Entry objects"); 115 } 116 return (K)colGetEntry(mIndex, 0); 117 } 118 119 @Override getValue()120 public V getValue() { 121 if (!mEntryValid) { 122 throw new IllegalStateException( 123 "This container does not support retaining Map.Entry objects"); 124 } 125 return (V)colGetEntry(mIndex, 1); 126 } 127 128 @Override setValue(V object)129 public V setValue(V object) { 130 if (!mEntryValid) { 131 throw new IllegalStateException( 132 "This container does not support retaining Map.Entry objects"); 133 } 134 return colSetValue(mIndex, object); 135 } 136 137 @Override equals(Object o)138 public final boolean equals(Object o) { 139 if (!mEntryValid) { 140 throw new IllegalStateException( 141 "This container does not support retaining Map.Entry objects"); 142 } 143 if (!(o instanceof Map.Entry)) { 144 return false; 145 } 146 Map.Entry<?, ?> e = (Map.Entry<?, ?>) o; 147 return Objects.equals(e.getKey(), colGetEntry(mIndex, 0)) 148 && Objects.equals(e.getValue(), colGetEntry(mIndex, 1)); 149 } 150 151 @Override hashCode()152 public final int hashCode() { 153 if (!mEntryValid) { 154 throw new IllegalStateException( 155 "This container does not support retaining Map.Entry objects"); 156 } 157 final Object key = colGetEntry(mIndex, 0); 158 final Object value = colGetEntry(mIndex, 1); 159 return (key == null ? 0 : key.hashCode()) ^ 160 (value == null ? 0 : value.hashCode()); 161 } 162 163 @Override toString()164 public final String toString() { 165 return getKey() + "=" + getValue(); 166 } 167 } 168 169 final class EntrySet implements Set<Map.Entry<K, V>> { 170 @Override add(Map.Entry<K, V> object)171 public boolean add(Map.Entry<K, V> object) { 172 throw new UnsupportedOperationException(); 173 } 174 175 @Override addAll(Collection<? extends Map.Entry<K, V>> collection)176 public boolean addAll(Collection<? extends Map.Entry<K, V>> collection) { 177 int oldSize = colGetSize(); 178 for (Map.Entry<K, V> entry : collection) { 179 colPut(entry.getKey(), entry.getValue()); 180 } 181 return oldSize != colGetSize(); 182 } 183 184 @Override clear()185 public void clear() { 186 colClear(); 187 } 188 189 @Override contains(Object o)190 public boolean contains(Object o) { 191 if (!(o instanceof Map.Entry)) 192 return false; 193 Map.Entry<?, ?> e = (Map.Entry<?, ?>) o; 194 int index = colIndexOfKey(e.getKey()); 195 if (index < 0) { 196 return false; 197 } 198 Object foundVal = colGetEntry(index, 1); 199 return Objects.equals(foundVal, e.getValue()); 200 } 201 202 @Override containsAll(Collection<?> collection)203 public boolean containsAll(Collection<?> collection) { 204 Iterator<?> it = collection.iterator(); 205 while (it.hasNext()) { 206 if (!contains(it.next())) { 207 return false; 208 } 209 } 210 return true; 211 } 212 213 @Override isEmpty()214 public boolean isEmpty() { 215 return colGetSize() == 0; 216 } 217 218 @Override iterator()219 public Iterator<Map.Entry<K, V>> iterator() { 220 return new MapIterator(); 221 } 222 223 @Override remove(Object object)224 public boolean remove(Object object) { 225 throw new UnsupportedOperationException(); 226 } 227 228 @Override removeAll(Collection<?> collection)229 public boolean removeAll(Collection<?> collection) { 230 throw new UnsupportedOperationException(); 231 } 232 233 @Override retainAll(Collection<?> collection)234 public boolean retainAll(Collection<?> collection) { 235 throw new UnsupportedOperationException(); 236 } 237 238 @Override size()239 public int size() { 240 return colGetSize(); 241 } 242 243 @Override toArray()244 public Object[] toArray() { 245 throw new UnsupportedOperationException(); 246 } 247 248 @Override toArray(T[] array)249 public <T> T[] toArray(T[] array) { 250 throw new UnsupportedOperationException(); 251 } 252 253 @Override equals(@ullable Object object)254 public boolean equals(@Nullable Object object) { 255 return equalsSetHelper(this, object); 256 } 257 258 @Override hashCode()259 public int hashCode() { 260 int result = 0; 261 for (int i=colGetSize()-1; i>=0; i--) { 262 final Object key = colGetEntry(i, 0); 263 final Object value = colGetEntry(i, 1); 264 result += ( (key == null ? 0 : key.hashCode()) ^ 265 (value == null ? 0 : value.hashCode()) ); 266 } 267 return result; 268 } 269 }; 270 271 final class KeySet implements Set<K> { 272 273 @Override add(K object)274 public boolean add(K object) { 275 throw new UnsupportedOperationException(); 276 } 277 278 @Override addAll(Collection<? extends K> collection)279 public boolean addAll(Collection<? extends K> collection) { 280 throw new UnsupportedOperationException(); 281 } 282 283 @Override clear()284 public void clear() { 285 colClear(); 286 } 287 288 @Override contains(Object object)289 public boolean contains(Object object) { 290 return colIndexOfKey(object) >= 0; 291 } 292 293 @Override containsAll(Collection<?> collection)294 public boolean containsAll(Collection<?> collection) { 295 return containsAllHelper(colGetMap(), collection); 296 } 297 298 @Override isEmpty()299 public boolean isEmpty() { 300 return colGetSize() == 0; 301 } 302 303 @Override iterator()304 public Iterator<K> iterator() { 305 return new ArrayIterator<K>(0); 306 } 307 308 @Override remove(Object object)309 public boolean remove(Object object) { 310 int index = colIndexOfKey(object); 311 if (index >= 0) { 312 colRemoveAt(index); 313 return true; 314 } 315 return false; 316 } 317 318 @Override removeAll(Collection<?> collection)319 public boolean removeAll(Collection<?> collection) { 320 return removeAllHelper(colGetMap(), collection); 321 } 322 323 @Override retainAll(Collection<?> collection)324 public boolean retainAll(Collection<?> collection) { 325 return retainAllHelper(colGetMap(), collection); 326 } 327 328 @Override size()329 public int size() { 330 return colGetSize(); 331 } 332 333 @Override toArray()334 public Object[] toArray() { 335 return toArrayHelper(0); 336 } 337 338 @Override toArray(T[] array)339 public <T> T[] toArray(T[] array) { 340 return toArrayHelper(array, 0); 341 } 342 343 @Override equals(@ullable Object object)344 public boolean equals(@Nullable Object object) { 345 return equalsSetHelper(this, object); 346 } 347 348 @Override hashCode()349 public int hashCode() { 350 int result = 0; 351 for (int i=colGetSize()-1; i>=0; i--) { 352 Object obj = colGetEntry(i, 0); 353 result += obj == null ? 0 : obj.hashCode(); 354 } 355 return result; 356 } 357 }; 358 359 final class ValuesCollection implements Collection<V> { 360 361 @Override add(V object)362 public boolean add(V object) { 363 throw new UnsupportedOperationException(); 364 } 365 366 @Override addAll(Collection<? extends V> collection)367 public boolean addAll(Collection<? extends V> collection) { 368 throw new UnsupportedOperationException(); 369 } 370 371 @Override clear()372 public void clear() { 373 colClear(); 374 } 375 376 @Override contains(Object object)377 public boolean contains(Object object) { 378 return colIndexOfValue(object) >= 0; 379 } 380 381 @Override containsAll(Collection<?> collection)382 public boolean containsAll(Collection<?> collection) { 383 Iterator<?> it = collection.iterator(); 384 while (it.hasNext()) { 385 if (!contains(it.next())) { 386 return false; 387 } 388 } 389 return true; 390 } 391 392 @Override isEmpty()393 public boolean isEmpty() { 394 return colGetSize() == 0; 395 } 396 397 @Override iterator()398 public Iterator<V> iterator() { 399 return new ArrayIterator<V>(1); 400 } 401 402 @Override remove(Object object)403 public boolean remove(Object object) { 404 int index = colIndexOfValue(object); 405 if (index >= 0) { 406 colRemoveAt(index); 407 return true; 408 } 409 return false; 410 } 411 412 @Override removeAll(Collection<?> collection)413 public boolean removeAll(Collection<?> collection) { 414 int N = colGetSize(); 415 boolean changed = false; 416 for (int i=0; i<N; i++) { 417 Object cur = colGetEntry(i, 1); 418 if (collection.contains(cur)) { 419 colRemoveAt(i); 420 i--; 421 N--; 422 changed = true; 423 } 424 } 425 return changed; 426 } 427 428 @Override retainAll(Collection<?> collection)429 public boolean retainAll(Collection<?> collection) { 430 int N = colGetSize(); 431 boolean changed = false; 432 for (int i=0; i<N; i++) { 433 Object cur = colGetEntry(i, 1); 434 if (!collection.contains(cur)) { 435 colRemoveAt(i); 436 i--; 437 N--; 438 changed = true; 439 } 440 } 441 return changed; 442 } 443 444 @Override size()445 public int size() { 446 return colGetSize(); 447 } 448 449 @Override toArray()450 public Object[] toArray() { 451 return toArrayHelper(1); 452 } 453 454 @Override toArray(T[] array)455 public <T> T[] toArray(T[] array) { 456 return toArrayHelper(array, 1); 457 } 458 }; 459 containsAllHelper(Map<K, V> map, Collection<?> collection)460 public static <K, V> boolean containsAllHelper(Map<K, V> map, Collection<?> collection) { 461 Iterator<?> it = collection.iterator(); 462 while (it.hasNext()) { 463 if (!map.containsKey(it.next())) { 464 return false; 465 } 466 } 467 return true; 468 } 469 removeAllHelper(Map<K, V> map, Collection<?> collection)470 public static <K, V> boolean removeAllHelper(Map<K, V> map, Collection<?> collection) { 471 int oldSize = map.size(); 472 Iterator<?> it = collection.iterator(); 473 while (it.hasNext()) { 474 map.remove(it.next()); 475 } 476 return oldSize != map.size(); 477 } 478 retainAllHelper(Map<K, V> map, Collection<?> collection)479 public static <K, V> boolean retainAllHelper(Map<K, V> map, Collection<?> collection) { 480 int oldSize = map.size(); 481 Iterator<K> it = map.keySet().iterator(); 482 while (it.hasNext()) { 483 if (!collection.contains(it.next())) { 484 it.remove(); 485 } 486 } 487 return oldSize != map.size(); 488 } 489 toArrayHelper(int offset)490 public Object[] toArrayHelper(int offset) { 491 final int N = colGetSize(); 492 Object[] result = new Object[N]; 493 for (int i=0; i<N; i++) { 494 result[i] = colGetEntry(i, offset); 495 } 496 return result; 497 } 498 toArrayHelper(T[] array, int offset)499 public <T> T[] toArrayHelper(T[] array, int offset) { 500 final int N = colGetSize(); 501 if (array.length < N) { 502 @SuppressWarnings("unchecked") T[] newArray 503 = (T[]) Array.newInstance(array.getClass().getComponentType(), N); 504 array = newArray; 505 } 506 for (int i=0; i<N; i++) { 507 array[i] = (T)colGetEntry(i, offset); 508 } 509 if (array.length > N) { 510 array[N] = null; 511 } 512 return array; 513 } 514 equalsSetHelper(Set<T> set, Object object)515 public static <T> boolean equalsSetHelper(Set<T> set, Object object) { 516 if (set == object) { 517 return true; 518 } 519 if (object instanceof Set) { 520 Set<?> s = (Set<?>) object; 521 522 try { 523 return set.size() == s.size() && set.containsAll(s); 524 } catch (NullPointerException ignored) { 525 return false; 526 } catch (ClassCastException ignored) { 527 return false; 528 } 529 } 530 return false; 531 } 532 getEntrySet()533 public Set<Map.Entry<K, V>> getEntrySet() { 534 if (mEntrySet == null) { 535 mEntrySet = new EntrySet(); 536 } 537 return mEntrySet; 538 } 539 getKeySet()540 public Set<K> getKeySet() { 541 if (mKeySet == null) { 542 mKeySet = new KeySet(); 543 } 544 return mKeySet; 545 } 546 getValues()547 public Collection<V> getValues() { 548 if (mValues == null) { 549 mValues = new ValuesCollection(); 550 } 551 return mValues; 552 } 553 colGetSize()554 protected abstract int colGetSize(); colGetEntry(int index, int offset)555 protected abstract Object colGetEntry(int index, int offset); colIndexOfKey(Object key)556 protected abstract int colIndexOfKey(Object key); colIndexOfValue(Object key)557 protected abstract int colIndexOfValue(Object key); colGetMap()558 protected abstract Map<K, V> colGetMap(); colPut(K key, V value)559 protected abstract void colPut(K key, V value); colSetValue(int index, V value)560 protected abstract V colSetValue(int index, V value); colRemoveAt(int index)561 protected abstract void colRemoveAt(int index); colClear()562 protected abstract void colClear(); 563 } 564