ArrayMap.java revision b6bdb0f02df1004307d25ae86e09cdbbc6865e75
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 // If this is immutable, use the sentinal EMPTY_IMMUTABLE_INTS 259 // instance instead of the usual EmptyArray.INT. The reference 260 // is checked later to see if the array is allowed to grow. 261 mHashes = immutable ? EMPTY_IMMUTABLE_INTS : EmptyArray.INT; 262 mArray = EmptyArray.OBJECT; 263 mSize = 0; 264 } 265 266 /** 267 * Create a new ArrayMap with the mappings from the given ArrayMap. 268 */ 269 public ArrayMap(ArrayMap map) { 270 this(); 271 if (map != null) { 272 putAll(map); 273 } 274 } 275 276 /** 277 * Make the array map empty. All storage is released. 278 */ 279 @Override 280 public void clear() { 281 if (mSize > 0) { 282 freeArrays(mHashes, mArray, mSize); 283 mHashes = EmptyArray.INT; 284 mArray = EmptyArray.OBJECT; 285 mSize = 0; 286 } 287 } 288 289 /** 290 * @hide 291 * Like {@link #clear}, but doesn't reduce the capacity of the ArrayMap. 292 */ 293 public void erase() { 294 if (mSize > 0) { 295 final int N = mSize<<1; 296 final Object[] array = mArray; 297 for (int i=0; i<N; i++) { 298 array[i] = null; 299 } 300 mSize = 0; 301 } 302 } 303 304 /** 305 * Ensure the array map can hold at least <var>minimumCapacity</var> 306 * items. 307 */ 308 public void ensureCapacity(int minimumCapacity) { 309 if (mHashes.length < minimumCapacity) { 310 final int[] ohashes = mHashes; 311 final Object[] oarray = mArray; 312 allocArrays(minimumCapacity); 313 if (mSize > 0) { 314 System.arraycopy(ohashes, 0, mHashes, 0, mSize); 315 System.arraycopy(oarray, 0, mArray, 0, mSize<<1); 316 } 317 freeArrays(ohashes, oarray, mSize); 318 } 319 } 320 321 /** 322 * Check whether a key exists in the array. 323 * 324 * @param key The key to search for. 325 * @return Returns true if the key exists, else false. 326 */ 327 @Override 328 public boolean containsKey(Object key) { 329 return indexOfKey(key) >= 0; 330 } 331 332 /** 333 * Returns the index of a key in the set. 334 * 335 * @param key The key to search for. 336 * @return Returns the index of the key if it exists, else a negative integer. 337 */ 338 public int indexOfKey(Object key) { 339 return key == null ? indexOfNull() : indexOf(key, key.hashCode()); 340 } 341 342 int indexOfValue(Object value) { 343 final int N = mSize*2; 344 final Object[] array = mArray; 345 if (value == null) { 346 for (int i=1; i<N; i+=2) { 347 if (array[i] == null) { 348 return i>>1; 349 } 350 } 351 } else { 352 for (int i=1; i<N; i+=2) { 353 if (value.equals(array[i])) { 354 return i>>1; 355 } 356 } 357 } 358 return -1; 359 } 360 361 /** 362 * Check whether a value exists in the array. This requires a linear search 363 * through the entire array. 364 * 365 * @param value The value to search for. 366 * @return Returns true if the value exists, else false. 367 */ 368 @Override 369 public boolean containsValue(Object value) { 370 return indexOfValue(value) >= 0; 371 } 372 373 /** 374 * Retrieve a value from the array. 375 * @param key The key of the value to retrieve. 376 * @return Returns the value associated with the given key, 377 * or null if there is no such key. 378 */ 379 @Override 380 public V get(Object key) { 381 final int index = indexOfKey(key); 382 return index >= 0 ? (V)mArray[(index<<1)+1] : null; 383 } 384 385 /** 386 * Return the key at the given index in the array. 387 * @param index The desired index, must be between 0 and {@link #size()}-1. 388 * @return Returns the key stored at the given index. 389 */ 390 public K keyAt(int index) { 391 return (K)mArray[index << 1]; 392 } 393 394 /** 395 * Return the value at the given index in the array. 396 * @param index The desired index, must be between 0 and {@link #size()}-1. 397 * @return Returns the value stored at the given index. 398 */ 399 public V valueAt(int index) { 400 return (V)mArray[(index << 1) + 1]; 401 } 402 403 /** 404 * Set the value at a given index in the array. 405 * @param index The desired index, must be between 0 and {@link #size()}-1. 406 * @param value The new value to store at this index. 407 * @return Returns the previous value at the given index. 408 */ 409 public V setValueAt(int index, V value) { 410 index = (index << 1) + 1; 411 V old = (V)mArray[index]; 412 mArray[index] = value; 413 return old; 414 } 415 416 /** 417 * Return true if the array map contains no items. 418 */ 419 @Override 420 public boolean isEmpty() { 421 return mSize <= 0; 422 } 423 424 /** 425 * Add a new value to the array map. 426 * @param key The key under which to store the value. If 427 * this key already exists in the array, its value will be replaced. 428 * @param value The value to store for the given key. 429 * @return Returns the old value that was stored for the given key, or null if there 430 * was no such key. 431 */ 432 @Override 433 public V put(K key, V value) { 434 final int hash; 435 int index; 436 if (key == null) { 437 hash = 0; 438 index = indexOfNull(); 439 } else { 440 hash = key.hashCode(); 441 index = indexOf(key, hash); 442 } 443 if (index >= 0) { 444 index = (index<<1) + 1; 445 final V old = (V)mArray[index]; 446 mArray[index] = value; 447 return old; 448 } 449 450 index = ~index; 451 if (mSize >= mHashes.length) { 452 final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1)) 453 : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE); 454 455 if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n); 456 457 final int[] ohashes = mHashes; 458 final Object[] oarray = mArray; 459 allocArrays(n); 460 461 if (mHashes.length > 0) { 462 if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0"); 463 System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length); 464 System.arraycopy(oarray, 0, mArray, 0, oarray.length); 465 } 466 467 freeArrays(ohashes, oarray, mSize); 468 } 469 470 if (index < mSize) { 471 if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index) 472 + " to " + (index+1)); 473 System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index); 474 System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1); 475 } 476 477 mHashes[index] = hash; 478 mArray[index<<1] = key; 479 mArray[(index<<1)+1] = value; 480 mSize++; 481 return null; 482 } 483 484 /** 485 * Special fast path for appending items to the end of the array without validation. 486 * The array must already be large enough to contain the item. 487 * @hide 488 */ 489 public void append(K key, V value) { 490 int index = mSize; 491 final int hash = key == null ? 0 : key.hashCode(); 492 if (index >= mHashes.length) { 493 throw new IllegalStateException("Array is full"); 494 } 495 if (index > 0 && mHashes[index-1] > hash) { 496 RuntimeException e = new RuntimeException("here"); 497 e.fillInStackTrace(); 498 Log.w(TAG, "New hash " + hash 499 + " is before end of array hash " + mHashes[index-1] 500 + " at index " + index + " key " + key, e); 501 put(key, value); 502 return; 503 } 504 mSize = index+1; 505 mHashes[index] = hash; 506 index <<= 1; 507 mArray[index] = key; 508 mArray[index+1] = value; 509 } 510 511 /** 512 * The use of the {@link #append} function can result in invalid array maps, in particular 513 * an array map where the same key appears multiple times. This function verifies that 514 * the array map is valid, throwing IllegalArgumentException if a problem is found. The 515 * main use for this method is validating an array map after unpacking from an IPC, to 516 * protect against malicious callers. 517 * @hide 518 */ 519 public void validate() { 520 final int N = mSize; 521 if (N <= 1) { 522 // There can't be dups. 523 return; 524 } 525 int basehash = mHashes[0]; 526 int basei = 0; 527 for (int i=1; i<N; i++) { 528 int hash = mHashes[i]; 529 if (hash != basehash) { 530 basehash = hash; 531 basei = i; 532 continue; 533 } 534 // We are in a run of entries with the same hash code. Go backwards through 535 // the array to see if any keys are the same. 536 final Object cur = mArray[i<<1]; 537 for (int j=i-1; j>=basei; j--) { 538 final Object prev = mArray[j<<1]; 539 if (cur == prev) { 540 throw new IllegalArgumentException("Duplicate key in ArrayMap: " + cur); 541 } 542 if (cur != null && prev != null && cur.equals(prev)) { 543 throw new IllegalArgumentException("Duplicate key in ArrayMap: " + cur); 544 } 545 } 546 } 547 } 548 549 /** 550 * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>array</var> 551 * @param array The array whose contents are to be retrieved. 552 */ 553 public void putAll(ArrayMap<? extends K, ? extends V> array) { 554 final int N = array.mSize; 555 ensureCapacity(mSize + N); 556 if (mSize == 0) { 557 if (N > 0) { 558 System.arraycopy(array.mHashes, 0, mHashes, 0, N); 559 System.arraycopy(array.mArray, 0, mArray, 0, N<<1); 560 mSize = N; 561 } 562 } else { 563 for (int i=0; i<N; i++) { 564 put(array.keyAt(i), array.valueAt(i)); 565 } 566 } 567 } 568 569 /** 570 * Remove an existing key from the array map. 571 * @param key The key of the mapping to remove. 572 * @return Returns the value that was stored under the key, or null if there 573 * was no such key. 574 */ 575 @Override 576 public V remove(Object key) { 577 final int index = indexOfKey(key); 578 if (index >= 0) { 579 return removeAt(index); 580 } 581 582 return null; 583 } 584 585 /** 586 * Remove the key/value mapping at the given index. 587 * @param index The desired index, must be between 0 and {@link #size()}-1. 588 * @return Returns the value that was stored at this index. 589 */ 590 public V removeAt(int index) { 591 final Object old = mArray[(index << 1) + 1]; 592 if (mSize <= 1) { 593 // Now empty. 594 if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0"); 595 freeArrays(mHashes, mArray, mSize); 596 mHashes = EmptyArray.INT; 597 mArray = EmptyArray.OBJECT; 598 mSize = 0; 599 } else { 600 if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) { 601 // Shrunk enough to reduce size of arrays. We don't allow it to 602 // shrink smaller than (BASE_SIZE*2) to avoid flapping between 603 // that and BASE_SIZE. 604 final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2); 605 606 if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n); 607 608 final int[] ohashes = mHashes; 609 final Object[] oarray = mArray; 610 allocArrays(n); 611 612 mSize--; 613 if (index > 0) { 614 if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0"); 615 System.arraycopy(ohashes, 0, mHashes, 0, index); 616 System.arraycopy(oarray, 0, mArray, 0, index << 1); 617 } 618 if (index < mSize) { 619 if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize 620 + " to " + index); 621 System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index); 622 System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1, 623 (mSize - index) << 1); 624 } 625 } else { 626 mSize--; 627 if (index < mSize) { 628 if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize 629 + " to " + index); 630 System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index); 631 System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1, 632 (mSize - index) << 1); 633 } 634 mArray[mSize << 1] = null; 635 mArray[(mSize << 1) + 1] = null; 636 } 637 } 638 return (V)old; 639 } 640 641 /** 642 * Return the number of items in this array map. 643 */ 644 @Override 645 public int size() { 646 return mSize; 647 } 648 649 /** 650 * {@inheritDoc} 651 * 652 * <p>This implementation returns false if the object is not a map, or 653 * if the maps have different sizes. Otherwise, for each key in this map, 654 * values of both maps are compared. If the values for any key are not 655 * equal, the method returns false, otherwise it returns true. 656 */ 657 @Override 658 public boolean equals(Object object) { 659 if (this == object) { 660 return true; 661 } 662 if (object instanceof Map) { 663 Map<?, ?> map = (Map<?, ?>) object; 664 if (size() != map.size()) { 665 return false; 666 } 667 668 try { 669 for (int i=0; i<mSize; i++) { 670 K key = keyAt(i); 671 V mine = valueAt(i); 672 Object theirs = map.get(key); 673 if (mine == null) { 674 if (theirs != null || !map.containsKey(key)) { 675 return false; 676 } 677 } else if (!mine.equals(theirs)) { 678 return false; 679 } 680 } 681 } catch (NullPointerException ignored) { 682 return false; 683 } catch (ClassCastException ignored) { 684 return false; 685 } 686 return true; 687 } 688 return false; 689 } 690 691 /** 692 * {@inheritDoc} 693 */ 694 @Override 695 public int hashCode() { 696 final int[] hashes = mHashes; 697 final Object[] array = mArray; 698 int result = 0; 699 for (int i = 0, v = 1, s = mSize; i < s; i++, v+=2) { 700 Object value = array[v]; 701 result += hashes[i] ^ (value == null ? 0 : value.hashCode()); 702 } 703 return result; 704 } 705 706 /** 707 * {@inheritDoc} 708 * 709 * <p>This implementation composes a string by iterating over its mappings. If 710 * this map contains itself as a key or a value, the string "(this Map)" 711 * will appear in its place. 712 */ 713 @Override 714 public String toString() { 715 if (isEmpty()) { 716 return "{}"; 717 } 718 719 StringBuilder buffer = new StringBuilder(mSize * 28); 720 buffer.append('{'); 721 for (int i=0; i<mSize; i++) { 722 if (i > 0) { 723 buffer.append(", "); 724 } 725 Object key = keyAt(i); 726 if (key != this) { 727 buffer.append(key); 728 } else { 729 buffer.append("(this Map)"); 730 } 731 buffer.append('='); 732 Object value = valueAt(i); 733 if (value != this) { 734 buffer.append(value); 735 } else { 736 buffer.append("(this Map)"); 737 } 738 } 739 buffer.append('}'); 740 return buffer.toString(); 741 } 742 743 // ------------------------------------------------------------------------ 744 // Interop with traditional Java containers. Not as efficient as using 745 // specialized collection APIs. 746 // ------------------------------------------------------------------------ 747 748 private MapCollections<K, V> getCollection() { 749 if (mCollections == null) { 750 mCollections = new MapCollections<K, V>() { 751 @Override 752 protected int colGetSize() { 753 return mSize; 754 } 755 756 @Override 757 protected Object colGetEntry(int index, int offset) { 758 return mArray[(index<<1) + offset]; 759 } 760 761 @Override 762 protected int colIndexOfKey(Object key) { 763 return indexOfKey(key); 764 } 765 766 @Override 767 protected int colIndexOfValue(Object value) { 768 return indexOfValue(value); 769 } 770 771 @Override 772 protected Map<K, V> colGetMap() { 773 return ArrayMap.this; 774 } 775 776 @Override 777 protected void colPut(K key, V value) { 778 put(key, value); 779 } 780 781 @Override 782 protected V colSetValue(int index, V value) { 783 return setValueAt(index, value); 784 } 785 786 @Override 787 protected void colRemoveAt(int index) { 788 removeAt(index); 789 } 790 791 @Override 792 protected void colClear() { 793 clear(); 794 } 795 }; 796 } 797 return mCollections; 798 } 799 800 /** 801 * Determine if the array map contains all of the keys in the given collection. 802 * @param collection The collection whose contents are to be checked against. 803 * @return Returns true if this array map contains a key for every entry 804 * in <var>collection</var>, else returns false. 805 */ 806 public boolean containsAll(Collection<?> collection) { 807 return MapCollections.containsAllHelper(this, collection); 808 } 809 810 /** 811 * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>map</var> 812 * @param map The map whose contents are to be retrieved. 813 */ 814 @Override 815 public void putAll(Map<? extends K, ? extends V> map) { 816 ensureCapacity(mSize + map.size()); 817 for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { 818 put(entry.getKey(), entry.getValue()); 819 } 820 } 821 822 /** 823 * Remove all keys in the array map that exist in the given collection. 824 * @param collection The collection whose contents are to be used to remove keys. 825 * @return Returns true if any keys were removed from the array map, else false. 826 */ 827 public boolean removeAll(Collection<?> collection) { 828 return MapCollections.removeAllHelper(this, collection); 829 } 830 831 /** 832 * Remove all keys in the array map that do <b>not</b> exist in the given collection. 833 * @param collection The collection whose contents are to be used to determine which 834 * keys to keep. 835 * @return Returns true if any keys were removed from the array map, else false. 836 */ 837 public boolean retainAll(Collection<?> collection) { 838 return MapCollections.retainAllHelper(this, collection); 839 } 840 841 /** 842 * Return a {@link java.util.Set} for iterating over and interacting with all mappings 843 * in the array map. 844 * 845 * <p><b>Note:</b> this is a very inefficient way to access the array contents, it 846 * requires generating a number of temporary objects.</p> 847 * 848 * <p><b>Note:</b></p> the semantics of this 849 * Set are subtly different than that of a {@link java.util.HashMap}: most important, 850 * the {@link java.util.Map.Entry Map.Entry} object returned by its iterator is a single 851 * object that exists for the entire iterator, so you can <b>not</b> hold on to it 852 * after calling {@link java.util.Iterator#next() Iterator.next}.</p> 853 */ 854 @Override 855 public Set<Map.Entry<K, V>> entrySet() { 856 return getCollection().getEntrySet(); 857 } 858 859 /** 860 * Return a {@link java.util.Set} for iterating over and interacting with all keys 861 * in the array map. 862 * 863 * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it 864 * requires generating a number of temporary objects.</p> 865 */ 866 @Override 867 public Set<K> keySet() { 868 return getCollection().getKeySet(); 869 } 870 871 /** 872 * Return a {@link java.util.Collection} for iterating over and interacting with all values 873 * in the array map. 874 * 875 * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it 876 * requires generating a number of temporary objects.</p> 877 */ 878 @Override 879 public Collection<V> values() { 880 return getCollection().getValues(); 881 } 882} 883