ArrayUtils.java revision d66c95fa907dc9eb3d7238fbbf3dc6dbd4b243a0
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 public static long total(@Nullable long[] array) { 241 long total = 0; 242 if (array != null) { 243 for (long value : array) { 244 total += value; 245 } 246 } 247 return total; 248 } 249 250 public static int[] convertToIntArray(List<Integer> list) { 251 int[] array = new int[list.size()]; 252 for (int i = 0; i < list.size(); i++) { 253 array[i] = list.get(i); 254 } 255 return array; 256 } 257 258 /** 259 * Adds value to given array if not already present, providing set-like 260 * behavior. 261 */ 262 @SuppressWarnings("unchecked") 263 public static @NonNull <T> T[] appendElement(Class<T> kind, @Nullable T[] array, T element) { 264 return appendElement(kind, array, element, false); 265 } 266 267 /** 268 * Adds value to given array. 269 */ 270 @SuppressWarnings("unchecked") 271 public static @NonNull <T> T[] appendElement(Class<T> kind, @Nullable T[] array, T element, 272 boolean allowDuplicates) { 273 final T[] result; 274 final int end; 275 if (array != null) { 276 if (!allowDuplicates && contains(array, element)) return array; 277 end = array.length; 278 result = (T[])Array.newInstance(kind, end + 1); 279 System.arraycopy(array, 0, result, 0, end); 280 } else { 281 end = 0; 282 result = (T[])Array.newInstance(kind, 1); 283 } 284 result[end] = element; 285 return result; 286 } 287 288 /** 289 * Removes value from given array if present, providing set-like behavior. 290 */ 291 @SuppressWarnings("unchecked") 292 public static @Nullable <T> T[] removeElement(Class<T> kind, @Nullable T[] array, T element) { 293 if (array != null) { 294 if (!contains(array, element)) return array; 295 final int length = array.length; 296 for (int i = 0; i < length; i++) { 297 if (Objects.equals(array[i], element)) { 298 if (length == 1) { 299 return null; 300 } 301 T[] result = (T[])Array.newInstance(kind, length - 1); 302 System.arraycopy(array, 0, result, 0, i); 303 System.arraycopy(array, i + 1, result, i, length - i - 1); 304 return result; 305 } 306 } 307 } 308 return array; 309 } 310 311 /** 312 * Adds value to given array. 313 */ 314 public static @NonNull int[] appendInt(@Nullable int[] cur, int val, 315 boolean allowDuplicates) { 316 if (cur == null) { 317 return new int[] { val }; 318 } 319 final int N = cur.length; 320 if (!allowDuplicates) { 321 for (int i = 0; i < N; i++) { 322 if (cur[i] == val) { 323 return cur; 324 } 325 } 326 } 327 int[] ret = new int[N + 1]; 328 System.arraycopy(cur, 0, ret, 0, N); 329 ret[N] = val; 330 return ret; 331 } 332 333 /** 334 * Adds value to given array if not already present, providing set-like 335 * behavior. 336 */ 337 public static @NonNull int[] appendInt(@Nullable int[] cur, int val) { 338 return appendInt(cur, val, false); 339 } 340 341 /** 342 * Removes value from given array if present, providing set-like behavior. 343 */ 344 public static @Nullable int[] removeInt(@Nullable int[] cur, int val) { 345 if (cur == null) { 346 return null; 347 } 348 final int N = cur.length; 349 for (int i = 0; i < N; i++) { 350 if (cur[i] == val) { 351 int[] ret = new int[N - 1]; 352 if (i > 0) { 353 System.arraycopy(cur, 0, ret, 0, i); 354 } 355 if (i < (N - 1)) { 356 System.arraycopy(cur, i + 1, ret, i, N - i - 1); 357 } 358 return ret; 359 } 360 } 361 return cur; 362 } 363 364 /** 365 * Removes value from given array if present, providing set-like behavior. 366 */ 367 public static @Nullable String[] removeString(@Nullable String[] cur, String val) { 368 if (cur == null) { 369 return null; 370 } 371 final int N = cur.length; 372 for (int i = 0; i < N; i++) { 373 if (Objects.equals(cur[i], val)) { 374 String[] ret = new String[N - 1]; 375 if (i > 0) { 376 System.arraycopy(cur, 0, ret, 0, i); 377 } 378 if (i < (N - 1)) { 379 System.arraycopy(cur, i + 1, ret, i, N - i - 1); 380 } 381 return ret; 382 } 383 } 384 return cur; 385 } 386 387 /** 388 * Adds value to given array if not already present, providing set-like 389 * behavior. 390 */ 391 public static @NonNull long[] appendLong(@Nullable long[] cur, long val) { 392 if (cur == null) { 393 return new long[] { val }; 394 } 395 final int N = cur.length; 396 for (int i = 0; i < N; i++) { 397 if (cur[i] == val) { 398 return cur; 399 } 400 } 401 long[] ret = new long[N + 1]; 402 System.arraycopy(cur, 0, ret, 0, N); 403 ret[N] = val; 404 return ret; 405 } 406 407 /** 408 * Removes value from given array if present, providing set-like behavior. 409 */ 410 public static @Nullable long[] removeLong(@Nullable long[] cur, long val) { 411 if (cur == null) { 412 return null; 413 } 414 final int N = cur.length; 415 for (int i = 0; i < N; i++) { 416 if (cur[i] == val) { 417 long[] ret = new long[N - 1]; 418 if (i > 0) { 419 System.arraycopy(cur, 0, ret, 0, i); 420 } 421 if (i < (N - 1)) { 422 System.arraycopy(cur, i + 1, ret, i, N - i - 1); 423 } 424 return ret; 425 } 426 } 427 return cur; 428 } 429 430 public static @Nullable long[] cloneOrNull(@Nullable long[] array) { 431 return (array != null) ? array.clone() : null; 432 } 433 434 public static @Nullable <T> ArraySet<T> cloneOrNull(@Nullable ArraySet<T> array) { 435 return (array != null) ? new ArraySet<T>(array) : null; 436 } 437 438 public static @NonNull <T> ArraySet<T> add(@Nullable ArraySet<T> cur, T val) { 439 if (cur == null) { 440 cur = new ArraySet<>(); 441 } 442 cur.add(val); 443 return cur; 444 } 445 446 public static @Nullable <T> ArraySet<T> remove(@Nullable ArraySet<T> cur, T val) { 447 if (cur == null) { 448 return null; 449 } 450 cur.remove(val); 451 if (cur.isEmpty()) { 452 return null; 453 } else { 454 return cur; 455 } 456 } 457 458 public static @NonNull <T> ArrayList<T> add(@Nullable ArrayList<T> cur, T val) { 459 if (cur == null) { 460 cur = new ArrayList<>(); 461 } 462 cur.add(val); 463 return cur; 464 } 465 466 public static @Nullable <T> ArrayList<T> remove(@Nullable ArrayList<T> cur, T val) { 467 if (cur == null) { 468 return null; 469 } 470 cur.remove(val); 471 if (cur.isEmpty()) { 472 return null; 473 } else { 474 return cur; 475 } 476 } 477 478 public static int size(@Nullable Collection<?> cur) { 479 return cur != null ? cur.size() : 0; 480 } 481 482 public static @NonNull <I, O> List<O> map(@Nullable List<I> cur, 483 Function<? super I, ? extends O> f) { 484 if (cur == null || cur.isEmpty()) return Collections.emptyList(); 485 final ArrayList<O> result = new ArrayList<>(); 486 for (int i = 0; i < cur.size(); i++) { 487 result.add(f.apply(cur.get(i))); 488 } 489 return result; 490 } 491 492 /** 493 * Returns the given list, or an immutable empty list if the provided list is null 494 * 495 * @see Collections#emptyList 496 */ 497 public static @NonNull <T> List<T> emptyIfNull(@Nullable List<T> cur) { 498 return cur == null ? Collections.emptyList() : cur; 499 } 500 501 public static <T> boolean contains(@Nullable Collection<T> cur, T val) { 502 return (cur != null) ? cur.contains(val) : false; 503 } 504 505 public static @Nullable <T> T[] trimToSize(@Nullable T[] array, int size) { 506 if (array == null || size == 0) { 507 return null; 508 } else if (array.length == size) { 509 return array; 510 } else { 511 return Arrays.copyOf(array, size); 512 } 513 } 514 515 /** 516 * Returns true if the two ArrayLists are equal with respect to the objects they contain. 517 * The objects must be in the same order and be reference equal (== not .equals()). 518 */ 519 public static <T> boolean referenceEquals(ArrayList<T> a, ArrayList<T> b) { 520 if (a == b) { 521 return true; 522 } 523 524 final int sizeA = a.size(); 525 final int sizeB = b.size(); 526 if (a == null || b == null || sizeA != sizeB) { 527 return false; 528 } 529 530 boolean diff = false; 531 for (int i = 0; i < sizeA && !diff; i++) { 532 diff |= a.get(i) != b.get(i); 533 } 534 return !diff; 535 } 536 537 /** 538 * Removes elements that match the predicate in an efficient way that alters the order of 539 * elements in the collection. This should only be used if order is not important. 540 * @param collection The ArrayList from which to remove elements. 541 * @param predicate The predicate that each element is tested against. 542 * @return the number of elements removed. 543 */ 544 public static <T> int unstableRemoveIf(@Nullable ArrayList<T> collection, 545 @NonNull java.util.function.Predicate<T> predicate) { 546 if (collection == null) { 547 return 0; 548 } 549 550 final int size = collection.size(); 551 int leftIdx = 0; 552 int rightIdx = size - 1; 553 while (leftIdx <= rightIdx) { 554 // Find the next element to remove moving left to right. 555 while (leftIdx < size && !predicate.test(collection.get(leftIdx))) { 556 leftIdx++; 557 } 558 559 // Find the next element to keep moving right to left. 560 while (rightIdx > leftIdx && predicate.test(collection.get(rightIdx))) { 561 rightIdx--; 562 } 563 564 if (leftIdx >= rightIdx) { 565 // Done. 566 break; 567 } 568 569 Collections.swap(collection, leftIdx, rightIdx); 570 leftIdx++; 571 rightIdx--; 572 } 573 574 // leftIdx is now at the end. 575 for (int i = size - 1; i >= leftIdx; i--) { 576 collection.remove(i); 577 } 578 return size - leftIdx; 579 } 580} 581