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