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