ArrayUtils.java revision e70e6aa62c6f3a9a79624a4f9d97df95edda0364
1/* 2 * Copyright (C) 2006 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 com.android.internal.util; 18 19import android.annotation.NonNull; 20import android.annotation.Nullable; 21import android.util.ArraySet; 22 23import dalvik.system.VMRuntime; 24 25import libcore.util.EmptyArray; 26 27import java.lang.reflect.Array; 28import java.util.ArrayList; 29import java.util.Arrays; 30import java.util.Collection; 31import java.util.Collections; 32import java.util.List; 33import java.util.Objects; 34import java.util.function.Function; 35 36/** 37 * ArrayUtils contains some methods that you can call to find out 38 * the most efficient increments by which to grow arrays. 39 */ 40public class ArrayUtils { 41 private static final int CACHE_SIZE = 73; 42 private static Object[] sCache = new Object[CACHE_SIZE]; 43 44 private ArrayUtils() { /* cannot be instantiated */ } 45 46 public static byte[] newUnpaddedByteArray(int minLen) { 47 return (byte[])VMRuntime.getRuntime().newUnpaddedArray(byte.class, minLen); 48 } 49 50 public static char[] newUnpaddedCharArray(int minLen) { 51 return (char[])VMRuntime.getRuntime().newUnpaddedArray(char.class, minLen); 52 } 53 54 public static int[] newUnpaddedIntArray(int minLen) { 55 return (int[])VMRuntime.getRuntime().newUnpaddedArray(int.class, minLen); 56 } 57 58 public static boolean[] newUnpaddedBooleanArray(int minLen) { 59 return (boolean[])VMRuntime.getRuntime().newUnpaddedArray(boolean.class, minLen); 60 } 61 62 public static long[] newUnpaddedLongArray(int minLen) { 63 return (long[])VMRuntime.getRuntime().newUnpaddedArray(long.class, minLen); 64 } 65 66 public static float[] newUnpaddedFloatArray(int minLen) { 67 return (float[])VMRuntime.getRuntime().newUnpaddedArray(float.class, minLen); 68 } 69 70 public static Object[] newUnpaddedObjectArray(int minLen) { 71 return (Object[])VMRuntime.getRuntime().newUnpaddedArray(Object.class, minLen); 72 } 73 74 @SuppressWarnings("unchecked") 75 public static <T> T[] newUnpaddedArray(Class<T> clazz, int minLen) { 76 return (T[])VMRuntime.getRuntime().newUnpaddedArray(clazz, minLen); 77 } 78 79 /** 80 * Checks if the beginnings of two byte arrays are equal. 81 * 82 * @param array1 the first byte array 83 * @param array2 the second byte array 84 * @param length the number of bytes to check 85 * @return true if they're equal, false otherwise 86 */ 87 public static boolean equals(byte[] array1, byte[] array2, int length) { 88 if (length < 0) { 89 throw new IllegalArgumentException(); 90 } 91 92 if (array1 == array2) { 93 return true; 94 } 95 if (array1 == null || array2 == null || array1.length < length || array2.length < length) { 96 return false; 97 } 98 for (int i = 0; i < length; i++) { 99 if (array1[i] != array2[i]) { 100 return false; 101 } 102 } 103 return true; 104 } 105 106 /** 107 * Returns an empty array of the specified type. The intent is that 108 * it will return the same empty array every time to avoid reallocation, 109 * although this is not guaranteed. 110 */ 111 @SuppressWarnings("unchecked") 112 public static <T> T[] emptyArray(Class<T> kind) { 113 if (kind == Object.class) { 114 return (T[]) EmptyArray.OBJECT; 115 } 116 117 int bucket = (kind.hashCode() & 0x7FFFFFFF) % CACHE_SIZE; 118 Object cache = sCache[bucket]; 119 120 if (cache == null || cache.getClass().getComponentType() != kind) { 121 cache = Array.newInstance(kind, 0); 122 sCache[bucket] = cache; 123 124 // Log.e("cache", "new empty " + kind.getName() + " at " + bucket); 125 } 126 127 return (T[]) cache; 128 } 129 130 /** 131 * Checks if given array is null or has zero elements. 132 */ 133 public static boolean isEmpty(@Nullable Collection<?> array) { 134 return array == null || array.isEmpty(); 135 } 136 137 /** 138 * Checks if given array is null or has zero elements. 139 */ 140 public static <T> boolean isEmpty(@Nullable T[] array) { 141 return array == null || array.length == 0; 142 } 143 144 /** 145 * Checks if given array is null or has zero elements. 146 */ 147 public static boolean isEmpty(@Nullable int[] array) { 148 return array == null || array.length == 0; 149 } 150 151 /** 152 * Checks if given array is null or has zero elements. 153 */ 154 public static boolean isEmpty(@Nullable long[] array) { 155 return array == null || array.length == 0; 156 } 157 158 /** 159 * Checks if given array is null or has zero elements. 160 */ 161 public static boolean isEmpty(@Nullable byte[] array) { 162 return array == null || array.length == 0; 163 } 164 165 /** 166 * Checks if given array is null or has zero elements. 167 */ 168 public static boolean isEmpty(@Nullable boolean[] array) { 169 return array == null || array.length == 0; 170 } 171 172 /** 173 * Checks that value is present as at least one of the elements of the array. 174 * @param array the array to check in 175 * @param value the value to check for 176 * @return true if the value is present in the array 177 */ 178 public static <T> boolean contains(@Nullable T[] array, T value) { 179 return indexOf(array, value) != -1; 180 } 181 182 /** 183 * Return first index of {@code value} in {@code array}, or {@code -1} if 184 * not found. 185 */ 186 public static <T> int indexOf(@Nullable T[] array, T value) { 187 if (array == null) return -1; 188 for (int i = 0; i < array.length; i++) { 189 if (Objects.equals(array[i], value)) return i; 190 } 191 return -1; 192 } 193 194 /** 195 * Test if all {@code check} items are contained in {@code array}. 196 */ 197 public static <T> boolean containsAll(@Nullable T[] array, T[] check) { 198 if (check == null) return true; 199 for (T checkItem : check) { 200 if (!contains(array, checkItem)) { 201 return false; 202 } 203 } 204 return true; 205 } 206 207 /** 208 * Test if any {@code check} items are contained in {@code array}. 209 */ 210 public static <T> boolean containsAny(@Nullable T[] array, T[] check) { 211 if (check == null) return false; 212 for (T checkItem : check) { 213 if (contains(array, checkItem)) { 214 return true; 215 } 216 } 217 return false; 218 } 219 220 public static boolean contains(@Nullable int[] array, int value) { 221 if (array == null) return false; 222 for (int element : array) { 223 if (element == value) { 224 return true; 225 } 226 } 227 return false; 228 } 229 230 public static boolean contains(@Nullable long[] array, long value) { 231 if (array == null) return false; 232 for (long element : array) { 233 if (element == value) { 234 return true; 235 } 236 } 237 return false; 238 } 239 240 @NonNull 241 public static <T> List<T> filter(@Nullable List<?> list, Class<T> c) { 242 if (isEmpty(list)) return Collections.emptyList(); 243 ArrayList<T> result = null; 244 for (int i = 0; i < list.size(); i++) { 245 final Object item = list.get(i); 246 if (c.isInstance(item)) { 247 result = add(result, (T) item); 248 } 249 } 250 return emptyIfNull(result); 251 } 252 253 public static <T> boolean any(@Nullable List<T> items, 254 java.util.function.Predicate<T> predicate) { 255 return find(items, predicate) != null; 256 } 257 258 @Nullable 259 public static <T> T find(@Nullable List<T> items, 260 java.util.function.Predicate<T> predicate) { 261 if (isEmpty(items)) return null; 262 for (int i = 0; i < items.size(); i++) { 263 final T item = items.get(i); 264 if (predicate.test(item)) return item; 265 } 266 return null; 267 } 268 269 public static long total(@Nullable long[] array) { 270 long total = 0; 271 if (array != null) { 272 for (long value : array) { 273 total += value; 274 } 275 } 276 return total; 277 } 278 279 public static int[] convertToIntArray(List<Integer> list) { 280 int[] array = new int[list.size()]; 281 for (int i = 0; i < list.size(); i++) { 282 array[i] = list.get(i); 283 } 284 return array; 285 } 286 287 /** 288 * Adds value to given array if not already present, providing set-like 289 * behavior. 290 */ 291 @SuppressWarnings("unchecked") 292 public static @NonNull <T> T[] appendElement(Class<T> kind, @Nullable T[] array, T element) { 293 return appendElement(kind, array, element, false); 294 } 295 296 /** 297 * Adds value to given array. 298 */ 299 @SuppressWarnings("unchecked") 300 public static @NonNull <T> T[] appendElement(Class<T> kind, @Nullable T[] array, T element, 301 boolean allowDuplicates) { 302 final T[] result; 303 final int end; 304 if (array != null) { 305 if (!allowDuplicates && contains(array, element)) return array; 306 end = array.length; 307 result = (T[])Array.newInstance(kind, end + 1); 308 System.arraycopy(array, 0, result, 0, end); 309 } else { 310 end = 0; 311 result = (T[])Array.newInstance(kind, 1); 312 } 313 result[end] = element; 314 return result; 315 } 316 317 /** 318 * Removes value from given array if present, providing set-like behavior. 319 */ 320 @SuppressWarnings("unchecked") 321 public static @Nullable <T> T[] removeElement(Class<T> kind, @Nullable T[] array, T element) { 322 if (array != null) { 323 if (!contains(array, element)) return array; 324 final int length = array.length; 325 for (int i = 0; i < length; i++) { 326 if (Objects.equals(array[i], element)) { 327 if (length == 1) { 328 return null; 329 } 330 T[] result = (T[])Array.newInstance(kind, length - 1); 331 System.arraycopy(array, 0, result, 0, i); 332 System.arraycopy(array, i + 1, result, i, length - i - 1); 333 return result; 334 } 335 } 336 } 337 return array; 338 } 339 340 /** 341 * Adds value to given array. 342 */ 343 public static @NonNull int[] appendInt(@Nullable int[] cur, int val, 344 boolean allowDuplicates) { 345 if (cur == null) { 346 return new int[] { val }; 347 } 348 final int N = cur.length; 349 if (!allowDuplicates) { 350 for (int i = 0; i < N; i++) { 351 if (cur[i] == val) { 352 return cur; 353 } 354 } 355 } 356 int[] ret = new int[N + 1]; 357 System.arraycopy(cur, 0, ret, 0, N); 358 ret[N] = val; 359 return ret; 360 } 361 362 /** 363 * Adds value to given array if not already present, providing set-like 364 * behavior. 365 */ 366 public static @NonNull int[] appendInt(@Nullable int[] cur, int val) { 367 return appendInt(cur, val, false); 368 } 369 370 /** 371 * Removes value from given array if present, providing set-like behavior. 372 */ 373 public static @Nullable int[] removeInt(@Nullable int[] cur, int val) { 374 if (cur == null) { 375 return null; 376 } 377 final int N = cur.length; 378 for (int i = 0; i < N; i++) { 379 if (cur[i] == val) { 380 int[] ret = new int[N - 1]; 381 if (i > 0) { 382 System.arraycopy(cur, 0, ret, 0, i); 383 } 384 if (i < (N - 1)) { 385 System.arraycopy(cur, i + 1, ret, i, N - i - 1); 386 } 387 return ret; 388 } 389 } 390 return cur; 391 } 392 393 /** 394 * Removes value from given array if present, providing set-like behavior. 395 */ 396 public static @Nullable String[] removeString(@Nullable String[] cur, String val) { 397 if (cur == null) { 398 return null; 399 } 400 final int N = cur.length; 401 for (int i = 0; i < N; i++) { 402 if (Objects.equals(cur[i], val)) { 403 String[] ret = new String[N - 1]; 404 if (i > 0) { 405 System.arraycopy(cur, 0, ret, 0, i); 406 } 407 if (i < (N - 1)) { 408 System.arraycopy(cur, i + 1, ret, i, N - i - 1); 409 } 410 return ret; 411 } 412 } 413 return cur; 414 } 415 416 /** 417 * Adds value to given array if not already present, providing set-like 418 * behavior. 419 */ 420 public static @NonNull long[] appendLong(@Nullable long[] cur, long val) { 421 if (cur == null) { 422 return new long[] { val }; 423 } 424 final int N = cur.length; 425 for (int i = 0; i < N; i++) { 426 if (cur[i] == val) { 427 return cur; 428 } 429 } 430 long[] ret = new long[N + 1]; 431 System.arraycopy(cur, 0, ret, 0, N); 432 ret[N] = val; 433 return ret; 434 } 435 436 /** 437 * Removes value from given array if present, providing set-like behavior. 438 */ 439 public static @Nullable long[] removeLong(@Nullable long[] cur, long val) { 440 if (cur == null) { 441 return null; 442 } 443 final int N = cur.length; 444 for (int i = 0; i < N; i++) { 445 if (cur[i] == val) { 446 long[] ret = new long[N - 1]; 447 if (i > 0) { 448 System.arraycopy(cur, 0, ret, 0, i); 449 } 450 if (i < (N - 1)) { 451 System.arraycopy(cur, i + 1, ret, i, N - i - 1); 452 } 453 return ret; 454 } 455 } 456 return cur; 457 } 458 459 public static @Nullable long[] cloneOrNull(@Nullable long[] array) { 460 return (array != null) ? array.clone() : null; 461 } 462 463 public static @Nullable <T> ArraySet<T> cloneOrNull(@Nullable ArraySet<T> array) { 464 return (array != null) ? new ArraySet<T>(array) : null; 465 } 466 467 public static @NonNull <T> ArraySet<T> add(@Nullable ArraySet<T> cur, T val) { 468 if (cur == null) { 469 cur = new ArraySet<>(); 470 } 471 cur.add(val); 472 return cur; 473 } 474 475 public static @Nullable <T> ArraySet<T> remove(@Nullable ArraySet<T> cur, T val) { 476 if (cur == null) { 477 return null; 478 } 479 cur.remove(val); 480 if (cur.isEmpty()) { 481 return null; 482 } else { 483 return cur; 484 } 485 } 486 487 public static @NonNull <T> ArrayList<T> add(@Nullable ArrayList<T> cur, T val) { 488 if (cur == null) { 489 cur = new ArrayList<>(); 490 } 491 cur.add(val); 492 return cur; 493 } 494 495 public static @Nullable <T> ArrayList<T> remove(@Nullable ArrayList<T> cur, T val) { 496 if (cur == null) { 497 return null; 498 } 499 cur.remove(val); 500 if (cur.isEmpty()) { 501 return null; 502 } else { 503 return cur; 504 } 505 } 506 507 public static int size(@Nullable Collection<?> cur) { 508 return cur != null ? cur.size() : 0; 509 } 510 511 public static @NonNull <I, O> List<O> map(@Nullable List<I> cur, 512 Function<? super I, ? extends O> f) { 513 if (cur == null || cur.isEmpty()) return Collections.emptyList(); 514 final ArrayList<O> result = new ArrayList<>(); 515 for (int i = 0; i < cur.size(); i++) { 516 result.add(f.apply(cur.get(i))); 517 } 518 return result; 519 } 520 521 /** 522 * Returns the given list, or an immutable empty list if the provided list is null 523 * 524 * @see Collections#emptyList 525 */ 526 public static @NonNull <T> List<T> emptyIfNull(@Nullable List<T> cur) { 527 return cur == null ? Collections.emptyList() : cur; 528 } 529 530 public static <T> boolean contains(@Nullable Collection<T> cur, T val) { 531 return (cur != null) ? cur.contains(val) : false; 532 } 533 534 public static @Nullable <T> T[] trimToSize(@Nullable T[] array, int size) { 535 if (array == null || size == 0) { 536 return null; 537 } else if (array.length == size) { 538 return array; 539 } else { 540 return Arrays.copyOf(array, size); 541 } 542 } 543 544 /** 545 * Returns true if the two ArrayLists are equal with respect to the objects they contain. 546 * The objects must be in the same order and be reference equal (== not .equals()). 547 */ 548 public static <T> boolean referenceEquals(ArrayList<T> a, ArrayList<T> b) { 549 if (a == b) { 550 return true; 551 } 552 553 final int sizeA = a.size(); 554 final int sizeB = b.size(); 555 if (a == null || b == null || sizeA != sizeB) { 556 return false; 557 } 558 559 boolean diff = false; 560 for (int i = 0; i < sizeA && !diff; i++) { 561 diff |= a.get(i) != b.get(i); 562 } 563 return !diff; 564 } 565 566 /** 567 * Removes elements that match the predicate in an efficient way that alters the order of 568 * elements in the collection. This should only be used if order is not important. 569 * @param collection The ArrayList from which to remove elements. 570 * @param predicate The predicate that each element is tested against. 571 * @return the number of elements removed. 572 */ 573 public static <T> int unstableRemoveIf(@Nullable ArrayList<T> collection, 574 @NonNull java.util.function.Predicate<T> predicate) { 575 if (collection == null) { 576 return 0; 577 } 578 579 final int size = collection.size(); 580 int leftIdx = 0; 581 int rightIdx = size - 1; 582 while (leftIdx <= rightIdx) { 583 // Find the next element to remove moving left to right. 584 while (leftIdx < size && !predicate.test(collection.get(leftIdx))) { 585 leftIdx++; 586 } 587 588 // Find the next element to keep moving right to left. 589 while (rightIdx > leftIdx && predicate.test(collection.get(rightIdx))) { 590 rightIdx--; 591 } 592 593 if (leftIdx >= rightIdx) { 594 // Done. 595 break; 596 } 597 598 Collections.swap(collection, leftIdx, rightIdx); 599 leftIdx++; 600 rightIdx--; 601 } 602 603 // leftIdx is now at the end. 604 for (int i = size - 1; i >= leftIdx; i--) { 605 collection.remove(i); 606 } 607 return size - leftIdx; 608 } 609} 610