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