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