ArrayMap.java revision 4e9c07c0de199169374bded403805c92f1c1c6c1
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 17package android.util; 18 19import libcore.util.EmptyArray; 20 21import java.util.Collection; 22import java.util.Map; 23import java.util.Set; 24 25/** 26 * ArrayMap is a generic key->value mapping data structure that is 27 * designed to be more memory efficient than a traditional {@link java.util.HashMap}. 28 * It keeps its mappings in an array data structure -- an integer array of hash 29 * codes for each item, and an Object array of the key/value pairs. This allows it to 30 * avoid having to create an extra object for every entry put in to the map, and it 31 * also tries to control the growth of the size of these arrays more aggressively 32 * (since growing them only requires copying the entries in the array, not rebuilding 33 * a hash map). 34 * 35 * <p>Note that this implementation is not intended to be appropriate for data structures 36 * that may contain large numbers of items. It is generally slower than a traditional 37 * HashMap, since lookups require a binary search and adds and removes require inserting 38 * and deleting entries in the array. For containers holding up to hundreds of items, 39 * the performance difference is not significant, less than 50%.</p> 40 * 41 * <p>Because this container is intended to better balance memory use, unlike most other 42 * standard Java containers it will shrink its array as items are removed from it. Currently 43 * you have no control over this shrinking -- if you set a capacity and then remove an 44 * item, it may reduce the capacity to better match the current size. In the future an 45 * explicit call to set the capacity should turn off this aggressive shrinking behavior.</p> 46 */ 47public final class ArrayMap<K, V> implements Map<K, V> { 48 private static final boolean DEBUG = false; 49 private static final String TAG = "ArrayMap"; 50 51 /** 52 * The minimum amount by which the capacity of a ArrayMap will increase. 53 * This is tuned to be relatively space-efficient. 54 */ 55 private static final int BASE_SIZE = 4; 56 57 /** 58 * Maximum number of entries to have in array caches. 59 */ 60 private static final int CACHE_SIZE = 10; 61 62 /** 63 * @hide Special immutable empty ArrayMap. 64 */ 65 public static final ArrayMap EMPTY = new ArrayMap(true); 66 67 /** 68 * Caches of small array objects to avoid spamming garbage. The cache 69 * Object[] variable is a pointer to a linked list of array objects. 70 * The first entry in the array is a pointer to the next array in the 71 * list; the second entry is a pointer to the int[] hash code array for it. 72 */ 73 static Object[] mBaseCache; 74 static int mBaseCacheSize; 75 static Object[] mTwiceBaseCache; 76 static int mTwiceBaseCacheSize; 77 78 /** 79 * Special hash array value that indicates the container is immutable. 80 */ 81 static final int[] EMPTY_IMMUTABLE_INTS = new int[0]; 82 83 int[] mHashes; 84 Object[] mArray; 85 int mSize; 86 MapCollections<K, V> mCollections; 87 88 int indexOf(Object key, int hash) { 89 final int N = mSize; 90 91 // Important fast case: if nothing is in here, nothing to look for. 92 if (N == 0) { 93 return ~0; 94 } 95 96 int index = ContainerHelpers.binarySearch(mHashes, N, hash); 97 98 // If the hash code wasn't found, then we have no entry for this key. 99 if (index < 0) { 100 return index; 101 } 102 103 // If the key at the returned index matches, that's what we want. 104 if (key.equals(mArray[index<<1])) { 105 return index; 106 } 107 108 // Search for a matching key after the index. 109 int end; 110 for (end = index + 1; end < N && mHashes[end] == hash; end++) { 111 if (key.equals(mArray[end << 1])) return end; 112 } 113 114 // Search for a matching key before the index. 115 for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) { 116 if (key.equals(mArray[i << 1])) return i; 117 } 118 119 // Key not found -- return negative value indicating where a 120 // new entry for this key should go. We use the end of the 121 // hash chain to reduce the number of array entries that will 122 // need to be copied when inserting. 123 return ~end; 124 } 125 126 int indexOfNull() { 127 final int N = mSize; 128 129 // Important fast case: if nothing is in here, nothing to look for. 130 if (N == 0) { 131 return ~0; 132 } 133 134 int index = ContainerHelpers.binarySearch(mHashes, N, 0); 135 136 // If the hash code wasn't found, then we have no entry for this key. 137 if (index < 0) { 138 return index; 139 } 140 141 // If the key at the returned index matches, that's what we want. 142 if (null == mArray[index<<1]) { 143 return index; 144 } 145 146 // Search for a matching key after the index. 147 int end; 148 for (end = index + 1; end < N && mHashes[end] == 0; end++) { 149 if (null == mArray[end << 1]) return end; 150 } 151 152 // Search for a matching key before the index. 153 for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) { 154 if (null == mArray[i << 1]) return i; 155 } 156 157 // Key not found -- return negative value indicating where a 158 // new entry for this key should go. We use the end of the 159 // hash chain to reduce the number of array entries that will 160 // need to be copied when inserting. 161 return ~end; 162 } 163 164 private void allocArrays(final int size) { 165 if (mHashes == EMPTY_IMMUTABLE_INTS) { 166 throw new UnsupportedOperationException("ArrayMap is immutable"); 167 } 168 if (size == (BASE_SIZE*2)) { 169 synchronized (ArrayMap.class) { 170 if (mTwiceBaseCache != null) { 171 final Object[] array = mTwiceBaseCache; 172 mArray = array; 173 mTwiceBaseCache = (Object[])array[0]; 174 mHashes = (int[])array[1]; 175 array[0] = array[1] = null; 176 mTwiceBaseCacheSize--; 177 if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes 178 + " now have " + mTwiceBaseCacheSize + " entries"); 179 return; 180 } 181 } 182 } else if (size == BASE_SIZE) { 183 synchronized (ArrayMap.class) { 184 if (mBaseCache != null) { 185 final Object[] array = mBaseCache; 186 mArray = array; 187 mBaseCache = (Object[])array[0]; 188 mHashes = (int[])array[1]; 189 array[0] = array[1] = null; 190 mBaseCacheSize--; 191 if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes 192 + " now have " + mBaseCacheSize + " entries"); 193 return; 194 } 195 } 196 } 197 198 mHashes = new int[size]; 199 mArray = new Object[size<<1]; 200 } 201 202 private static void freeArrays(final int[] hashes, final Object[] array, final int size) { 203 if (hashes.length == (BASE_SIZE*2)) { 204 synchronized (ArrayMap.class) { 205 if (mTwiceBaseCacheSize < CACHE_SIZE) { 206 array[0] = mTwiceBaseCache; 207 array[1] = hashes; 208 for (int i=(size<<1)-1; i>=2; i--) { 209 array[i] = null; 210 } 211 mTwiceBaseCache = array; 212 mTwiceBaseCacheSize++; 213 if (DEBUG) Log.d(TAG, "Storing 2x cache " + array 214 + " now have " + mTwiceBaseCacheSize + " entries"); 215 } 216 } 217 } else if (hashes.length == BASE_SIZE) { 218 synchronized (ArrayMap.class) { 219 if (mBaseCacheSize < CACHE_SIZE) { 220 array[0] = mBaseCache; 221 array[1] = hashes; 222 for (int i=(size<<1)-1; i>=2; i--) { 223 array[i] = null; 224 } 225 mBaseCache = array; 226 mBaseCacheSize++; 227 if (DEBUG) Log.d(TAG, "Storing 1x cache " + array 228 + " now have " + mBaseCacheSize + " entries"); 229 } 230 } 231 } 232 } 233 234 /** 235 * Create a new empty ArrayMap. The default capacity of an array map is 0, and 236 * will grow once items are added to it. 237 */ 238 public ArrayMap() { 239 mHashes = EmptyArray.INT; 240 mArray = EmptyArray.OBJECT; 241 mSize = 0; 242 } 243 244 /** 245 * Create a new ArrayMap with a given initial capacity. 246 */ 247 public ArrayMap(int capacity) { 248 if (capacity == 0) { 249 mHashes = EmptyArray.INT; 250 mArray = EmptyArray.OBJECT; 251 } else { 252 allocArrays(capacity); 253 } 254 mSize = 0; 255 } 256 257 private ArrayMap(boolean immutable) { 258 mHashes = EmptyArray.INT; 259 mArray = EmptyArray.OBJECT; 260 mSize = 0; 261 } 262 263 /** 264 * Create a new ArrayMap with the mappings from the given ArrayMap. 265 */ 266 public ArrayMap(ArrayMap map) { 267 this(); 268 if (map != null) { 269 putAll(map); 270 } 271 } 272 273 /** 274 * Make the array map empty. All storage is released. 275 */ 276 @Override 277 public void clear() { 278 if (mSize > 0) { 279 freeArrays(mHashes, mArray, mSize); 280 mHashes = EmptyArray.INT; 281 mArray = EmptyArray.OBJECT; 282 mSize = 0; 283 } 284 } 285 286 /** 287 * @hide 288 * Like {@link #clear}, but doesn't reduce the capacity of the ArrayMap. 289 */ 290 public void erase() { 291 if (mSize > 0) { 292 final int N = mSize<<1; 293 final Object[] array = mArray; 294 for (int i=0; i<N; i++) { 295 array[i] = null; 296 } 297 mSize = 0; 298 } 299 } 300 301 /** 302 * Ensure the array map can hold at least <var>minimumCapacity</var> 303 * items. 304 */ 305 public void ensureCapacity(int minimumCapacity) { 306 if (mHashes.length < minimumCapacity) { 307 final int[] ohashes = mHashes; 308 final Object[] oarray = mArray; 309 allocArrays(minimumCapacity); 310 if (mSize > 0) { 311 System.arraycopy(ohashes, 0, mHashes, 0, mSize); 312 System.arraycopy(oarray, 0, mArray, 0, mSize<<1); 313 } 314 freeArrays(ohashes, oarray, mSize); 315 } 316 } 317 318 /** 319 * Check whether a key exists in the array. 320 * 321 * @param key The key to search for. 322 * @return Returns true if the key exists, else false. 323 */ 324 @Override 325 public boolean containsKey(Object key) { 326 return indexOfKey(key) >= 0; 327 } 328 329 /** 330 * Returns the index of a key in the set. 331 * 332 * @param key The key to search for. 333 * @return Returns the index of the key if it exists, else a negative integer. 334 */ 335 public int indexOfKey(Object key) { 336 return key == null ? indexOfNull() : indexOf(key, key.hashCode()); 337 } 338 339 int indexOfValue(Object value) { 340 final int N = mSize*2; 341 final Object[] array = mArray; 342 if (value == null) { 343 for (int i=1; i<N; i+=2) { 344 if (array[i] == null) { 345 return i>>1; 346 } 347 } 348 } else { 349 for (int i=1; i<N; i+=2) { 350 if (value.equals(array[i])) { 351 return i>>1; 352 } 353 } 354 } 355 return -1; 356 } 357 358 /** 359 * Check whether a value exists in the array. This requires a linear search 360 * through the entire array. 361 * 362 * @param value The value to search for. 363 * @return Returns true if the value exists, else false. 364 */ 365 @Override 366 public boolean containsValue(Object value) { 367 return indexOfValue(value) >= 0; 368 } 369 370 /** 371 * Retrieve a value from the array. 372 * @param key The key of the value to retrieve. 373 * @return Returns the value associated with the given key, 374 * or null if there is no such key. 375 */ 376 @Override 377 public V get(Object key) { 378 final int index = indexOfKey(key); 379 return index >= 0 ? (V)mArray[(index<<1)+1] : null; 380 } 381 382 /** 383 * Return the key at the given index in the array. 384 * @param index The desired index, must be between 0 and {@link #size()}-1. 385 * @return Returns the key stored at the given index. 386 */ 387 public K keyAt(int index) { 388 return (K)mArray[index << 1]; 389 } 390 391 /** 392 * Return the value at the given index in the array. 393 * @param index The desired index, must be between 0 and {@link #size()}-1. 394 * @return Returns the value stored at the given index. 395 */ 396 public V valueAt(int index) { 397 return (V)mArray[(index << 1) + 1]; 398 } 399 400 /** 401 * Set the value at a given index in the array. 402 * @param index The desired index, must be between 0 and {@link #size()}-1. 403 * @param value The new value to store at this index. 404 * @return Returns the previous value at the given index. 405 */ 406 public V setValueAt(int index, V value) { 407 index = (index << 1) + 1; 408 V old = (V)mArray[index]; 409 mArray[index] = value; 410 return old; 411 } 412 413 /** 414 * Return true if the array map contains no items. 415 */ 416 @Override 417 public boolean isEmpty() { 418 return mSize <= 0; 419 } 420 421 /** 422 * Add a new value to the array map. 423 * @param key The key under which to store the value. If 424 * this key already exists in the array, its value will be replaced. 425 * @param value The value to store for the given key. 426 * @return Returns the old value that was stored for the given key, or null if there 427 * was no such key. 428 */ 429 @Override 430 public V put(K key, V value) { 431 final int hash; 432 int index; 433 if (key == null) { 434 hash = 0; 435 index = indexOfNull(); 436 } else { 437 hash = key.hashCode(); 438 index = indexOf(key, hash); 439 } 440 if (index >= 0) { 441 index = (index<<1) + 1; 442 final V old = (V)mArray[index]; 443 mArray[index] = value; 444 return old; 445 } 446 447 index = ~index; 448 if (mSize >= mHashes.length) { 449 final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1)) 450 : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE); 451 452 if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n); 453 454 final int[] ohashes = mHashes; 455 final Object[] oarray = mArray; 456 allocArrays(n); 457 458 if (mHashes.length > 0) { 459 if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0"); 460 System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length); 461 System.arraycopy(oarray, 0, mArray, 0, oarray.length); 462 } 463 464 freeArrays(ohashes, oarray, mSize); 465 } 466 467 if (index < mSize) { 468 if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index) 469 + " to " + (index+1)); 470 System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index); 471 System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1); 472 } 473 474 mHashes[index] = hash; 475 mArray[index<<1] = key; 476 mArray[(index<<1)+1] = value; 477 mSize++; 478 return null; 479 } 480 481 /** 482 * Special fast path for appending items to the end of the array without validation. 483 * The array must already be large enough to contain the item. 484 * @hide 485 */ 486 public void append(K key, V value) { 487 int index = mSize; 488 final int hash = key == null ? 0 : key.hashCode(); 489 if (index >= mHashes.length) { 490 throw new IllegalStateException("Array is full"); 491 } 492 if (index > 0 && mHashes[index-1] > hash) { 493 RuntimeException e = new RuntimeException("here"); 494 e.fillInStackTrace(); 495 Log.w(TAG, "New hash " + hash 496 + " is before end of array hash " + mHashes[index-1] 497 + " at index " + index + " key " + key, e); 498 put(key, value); 499 return; 500 } 501 mSize = index+1; 502 mHashes[index] = hash; 503 index <<= 1; 504 mArray[index] = key; 505 mArray[index+1] = value; 506 } 507 508 /** 509 * The use of the {@link #append} function can result in invalid array maps, in particular 510 * an array map where the same key appears multiple times. This function verifies that 511 * the array map is valid, throwing IllegalArgumentException if a problem is found. The 512 * main use for this method is validating an array map after unpacking from an IPC, to 513 * protect against malicious callers. 514 * @hide 515 */ 516 public void validate() { 517 final int N = mSize; 518 if (N <= 1) { 519 // There can't be dups. 520 return; 521 } 522 int basehash = mHashes[0]; 523 int basei = 0; 524 for (int i=1; i<N; i++) { 525 int hash = mHashes[i]; 526 if (hash != basehash) { 527 basehash = hash; 528 basei = i; 529 continue; 530 } 531 // We are in a run of entries with the same hash code. Go backwards through 532 // the array to see if any keys are the same. 533 final Object cur = mArray[i<<1]; 534 for (int j=i-1; j>=basei; j--) { 535 final Object prev = mArray[j<<1]; 536 if (cur == prev) { 537 throw new IllegalArgumentException("Duplicate key in ArrayMap: " + cur); 538 } 539 if (cur != null && prev != null && cur.equals(prev)) { 540 throw new IllegalArgumentException("Duplicate key in ArrayMap: " + cur); 541 } 542 } 543 } 544 } 545 546 /** 547 * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>array</var> 548 * @param array The array whose contents are to be retrieved. 549 */ 550 public void putAll(ArrayMap<? extends K, ? extends V> array) { 551 final int N = array.mSize; 552 ensureCapacity(mSize + N); 553 if (mSize == 0) { 554 if (N > 0) { 555 System.arraycopy(array.mHashes, 0, mHashes, 0, N); 556 System.arraycopy(array.mArray, 0, mArray, 0, N<<1); 557 mSize = N; 558 } 559 } else { 560 for (int i=0; i<N; i++) { 561 put(array.keyAt(i), array.valueAt(i)); 562 } 563 } 564 } 565 566 /** 567 * Remove an existing key from the array map. 568 * @param key The key of the mapping to remove. 569 * @return Returns the value that was stored under the key, or null if there 570 * was no such key. 571 */ 572 @Override 573 public V remove(Object key) { 574 final int index = indexOfKey(key); 575 if (index >= 0) { 576 return removeAt(index); 577 } 578 579 return null; 580 } 581 582 /** 583 * Remove the key/value mapping at the given index. 584 * @param index The desired index, must be between 0 and {@link #size()}-1. 585 * @return Returns the value that was stored at this index. 586 */ 587 public V removeAt(int index) { 588 final Object old = mArray[(index << 1) + 1]; 589 if (mSize <= 1) { 590 // Now empty. 591 if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0"); 592 freeArrays(mHashes, mArray, mSize); 593 mHashes = EmptyArray.INT; 594 mArray = EmptyArray.OBJECT; 595 mSize = 0; 596 } else { 597 if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) { 598 // Shrunk enough to reduce size of arrays. We don't allow it to 599 // shrink smaller than (BASE_SIZE*2) to avoid flapping between 600 // that and BASE_SIZE. 601 final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2); 602 603 if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n); 604 605 final int[] ohashes = mHashes; 606 final Object[] oarray = mArray; 607 allocArrays(n); 608 609 mSize--; 610 if (index > 0) { 611 if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0"); 612 System.arraycopy(ohashes, 0, mHashes, 0, index); 613 System.arraycopy(oarray, 0, mArray, 0, index << 1); 614 } 615 if (index < mSize) { 616 if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize 617 + " to " + index); 618 System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index); 619 System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1, 620 (mSize - index) << 1); 621 } 622 } else { 623 mSize--; 624 if (index < mSize) { 625 if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize 626 + " to " + index); 627 System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index); 628 System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1, 629 (mSize - index) << 1); 630 } 631 mArray[mSize << 1] = null; 632 mArray[(mSize << 1) + 1] = null; 633 } 634 } 635 return (V)old; 636 } 637 638 /** 639 * Return the number of items in this array map. 640 */ 641 @Override 642 public int size() { 643 return mSize; 644 } 645 646 /** 647 * {@inheritDoc} 648 * 649 * <p>This implementation returns false if the object is not a map, or 650 * if the maps have different sizes. Otherwise, for each key in this map, 651 * values of both maps are compared. If the values for any key are not 652 * equal, the method returns false, otherwise it returns true. 653 */ 654 @Override 655 public boolean equals(Object object) { 656 if (this == object) { 657 return true; 658 } 659 if (object instanceof Map) { 660 Map<?, ?> map = (Map<?, ?>) object; 661 if (size() != map.size()) { 662 return false; 663 } 664 665 try { 666 for (int i=0; i<mSize; i++) { 667 K key = keyAt(i); 668 V mine = valueAt(i); 669 Object theirs = map.get(key); 670 if (mine == null) { 671 if (theirs != null || !map.containsKey(key)) { 672 return false; 673 } 674 } else if (!mine.equals(theirs)) { 675 return false; 676 } 677 } 678 } catch (NullPointerException ignored) { 679 return false; 680 } catch (ClassCastException ignored) { 681 return false; 682 } 683 return true; 684 } 685 return false; 686 } 687 688 /** 689 * {@inheritDoc} 690 */ 691 @Override 692 public int hashCode() { 693 final int[] hashes = mHashes; 694 final Object[] array = mArray; 695 int result = 0; 696 for (int i = 0, v = 1, s = mSize; i < s; i++, v+=2) { 697 Object value = array[v]; 698 result += hashes[i] ^ (value == null ? 0 : value.hashCode()); 699 } 700 return result; 701 } 702 703 /** 704 * {@inheritDoc} 705 * 706 * <p>This implementation composes a string by iterating over its mappings. If 707 * this map contains itself as a key or a value, the string "(this Map)" 708 * will appear in its place. 709 */ 710 @Override 711 public String toString() { 712 if (isEmpty()) { 713 return "{}"; 714 } 715 716 StringBuilder buffer = new StringBuilder(mSize * 28); 717 buffer.append('{'); 718 for (int i=0; i<mSize; i++) { 719 if (i > 0) { 720 buffer.append(", "); 721 } 722 Object key = keyAt(i); 723 if (key != this) { 724 buffer.append(key); 725 } else { 726 buffer.append("(this Map)"); 727 } 728 buffer.append('='); 729 Object value = valueAt(i); 730 if (value != this) { 731 buffer.append(value); 732 } else { 733 buffer.append("(this Map)"); 734 } 735 } 736 buffer.append('}'); 737 return buffer.toString(); 738 } 739 740 // ------------------------------------------------------------------------ 741 // Interop with traditional Java containers. Not as efficient as using 742 // specialized collection APIs. 743 // ------------------------------------------------------------------------ 744 745 private MapCollections<K, V> getCollection() { 746 if (mCollections == null) { 747 mCollections = new MapCollections<K, V>() { 748 @Override 749 protected int colGetSize() { 750 return mSize; 751 } 752 753 @Override 754 protected Object colGetEntry(int index, int offset) { 755 return mArray[(index<<1) + offset]; 756 } 757 758 @Override 759 protected int colIndexOfKey(Object key) { 760 return indexOfKey(key); 761 } 762 763 @Override 764 protected int colIndexOfValue(Object value) { 765 return indexOfValue(value); 766 } 767 768 @Override 769 protected Map<K, V> colGetMap() { 770 return ArrayMap.this; 771 } 772 773 @Override 774 protected void colPut(K key, V value) { 775 put(key, value); 776 } 777 778 @Override 779 protected V colSetValue(int index, V value) { 780 return setValueAt(index, value); 781 } 782 783 @Override 784 protected void colRemoveAt(int index) { 785 removeAt(index); 786 } 787 788 @Override 789 protected void colClear() { 790 clear(); 791 } 792 }; 793 } 794 return mCollections; 795 } 796 797 /** 798 * Determine if the array map contains all of the keys in the given collection. 799 * @param collection The collection whose contents are to be checked against. 800 * @return Returns true if this array map contains a key for every entry 801 * in <var>collection</var>, else returns false. 802 */ 803 public boolean containsAll(Collection<?> collection) { 804 return MapCollections.containsAllHelper(this, collection); 805 } 806 807 /** 808 * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>map</var> 809 * @param map The map whose contents are to be retrieved. 810 */ 811 @Override 812 public void putAll(Map<? extends K, ? extends V> map) { 813 ensureCapacity(mSize + map.size()); 814 for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { 815 put(entry.getKey(), entry.getValue()); 816 } 817 } 818 819 /** 820 * Remove all keys in the array map that exist in the given collection. 821 * @param collection The collection whose contents are to be used to remove keys. 822 * @return Returns true if any keys were removed from the array map, else false. 823 */ 824 public boolean removeAll(Collection<?> collection) { 825 return MapCollections.removeAllHelper(this, collection); 826 } 827 828 /** 829 * Remove all keys in the array map that do <b>not</b> exist in the given collection. 830 * @param collection The collection whose contents are to be used to determine which 831 * keys to keep. 832 * @return Returns true if any keys were removed from the array map, else false. 833 */ 834 public boolean retainAll(Collection<?> collection) { 835 return MapCollections.retainAllHelper(this, collection); 836 } 837 838 /** 839 * Return a {@link java.util.Set} for iterating over and interacting with all mappings 840 * in the array map. 841 * 842 * <p><b>Note:</b> this is a very inefficient way to access the array contents, it 843 * requires generating a number of temporary objects.</p> 844 * 845 * <p><b>Note:</b></p> the semantics of this 846 * Set are subtly different than that of a {@link java.util.HashMap}: most important, 847 * the {@link java.util.Map.Entry Map.Entry} object returned by its iterator is a single 848 * object that exists for the entire iterator, so you can <b>not</b> hold on to it 849 * after calling {@link java.util.Iterator#next() Iterator.next}.</p> 850 */ 851 @Override 852 public Set<Map.Entry<K, V>> entrySet() { 853 return getCollection().getEntrySet(); 854 } 855 856 /** 857 * Return a {@link java.util.Set} for iterating over and interacting with all keys 858 * in the array map. 859 * 860 * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it 861 * requires generating a number of temporary objects.</p> 862 */ 863 @Override 864 public Set<K> keySet() { 865 return getCollection().getKeySet(); 866 } 867 868 /** 869 * Return a {@link java.util.Collection} for iterating over and interacting with all values 870 * in the array map. 871 * 872 * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it 873 * requires generating a number of temporary objects.</p> 874 */ 875 @Override 876 public Collection<V> values() { 877 return getCollection().getValues(); 878 } 879} 880