ArrayUtils.java revision 4288419787120ce85a241a4b315d7d2123aa2d4a
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 that value is present as at least one of the elements of the array. 166 * @param array the array to check in 167 * @param value the value to check for 168 * @return true if the value is present in the array 169 */ 170 public static <T> boolean contains(@Nullable T[] array, T value) { 171 return indexOf(array, value) != -1; 172 } 173 174 /** 175 * Return first index of {@code value} in {@code array}, or {@code -1} if 176 * not found. 177 */ 178 public static <T> int indexOf(@Nullable T[] array, T value) { 179 if (array == null) return -1; 180 for (int i = 0; i < array.length; i++) { 181 if (Objects.equals(array[i], value)) return i; 182 } 183 return -1; 184 } 185 186 /** 187 * Test if all {@code check} items are contained in {@code array}. 188 */ 189 public static <T> boolean containsAll(@Nullable T[] array, T[] check) { 190 if (check == null) return true; 191 for (T checkItem : check) { 192 if (!contains(array, checkItem)) { 193 return false; 194 } 195 } 196 return true; 197 } 198 199 /** 200 * Test if any {@code check} items are contained in {@code array}. 201 */ 202 public static <T> boolean containsAny(@Nullable T[] array, T[] check) { 203 if (check == null) return false; 204 for (T checkItem : check) { 205 if (contains(array, checkItem)) { 206 return true; 207 } 208 } 209 return false; 210 } 211 212 public static boolean contains(@Nullable int[] array, int value) { 213 if (array == null) return false; 214 for (int element : array) { 215 if (element == value) { 216 return true; 217 } 218 } 219 return false; 220 } 221 222 public static boolean contains(@Nullable long[] array, long value) { 223 if (array == null) return false; 224 for (long element : array) { 225 if (element == value) { 226 return true; 227 } 228 } 229 return false; 230 } 231 232 public static long total(@Nullable long[] array) { 233 long total = 0; 234 if (array != null) { 235 for (long value : array) { 236 total += value; 237 } 238 } 239 return total; 240 } 241 242 public static int[] convertToIntArray(List<Integer> list) { 243 int[] array = new int[list.size()]; 244 for (int i = 0; i < list.size(); i++) { 245 array[i] = list.get(i); 246 } 247 return array; 248 } 249 250 /** 251 * Adds value to given array if not already present, providing set-like 252 * behavior. 253 */ 254 @SuppressWarnings("unchecked") 255 public static @NonNull <T> T[] appendElement(Class<T> kind, @Nullable T[] array, T element) { 256 final T[] result; 257 final int end; 258 if (array != null) { 259 if (contains(array, element)) return array; 260 end = array.length; 261 result = (T[])Array.newInstance(kind, end + 1); 262 System.arraycopy(array, 0, result, 0, end); 263 } else { 264 end = 0; 265 result = (T[])Array.newInstance(kind, 1); 266 } 267 result[end] = element; 268 return result; 269 } 270 271 /** 272 * Removes value from given array if present, providing set-like behavior. 273 */ 274 @SuppressWarnings("unchecked") 275 public static @Nullable <T> T[] removeElement(Class<T> kind, @Nullable T[] array, T element) { 276 if (array != null) { 277 if (!contains(array, element)) return array; 278 final int length = array.length; 279 for (int i = 0; i < length; i++) { 280 if (Objects.equals(array[i], element)) { 281 if (length == 1) { 282 return null; 283 } 284 T[] result = (T[])Array.newInstance(kind, length - 1); 285 System.arraycopy(array, 0, result, 0, i); 286 System.arraycopy(array, i + 1, result, i, length - i - 1); 287 return result; 288 } 289 } 290 } 291 return array; 292 } 293 294 /** 295 * Adds value to given array if not already present, providing set-like 296 * behavior. 297 */ 298 public static @NonNull int[] appendInt(@Nullable int[] cur, int val) { 299 if (cur == null) { 300 return new int[] { val }; 301 } 302 final int N = cur.length; 303 for (int i = 0; i < N; i++) { 304 if (cur[i] == val) { 305 return cur; 306 } 307 } 308 int[] ret = new int[N + 1]; 309 System.arraycopy(cur, 0, ret, 0, N); 310 ret[N] = val; 311 return ret; 312 } 313 314 /** 315 * Removes value from given array if present, providing set-like behavior. 316 */ 317 public static @Nullable int[] removeInt(@Nullable int[] cur, int val) { 318 if (cur == null) { 319 return null; 320 } 321 final int N = cur.length; 322 for (int i = 0; i < N; i++) { 323 if (cur[i] == val) { 324 int[] ret = new int[N - 1]; 325 if (i > 0) { 326 System.arraycopy(cur, 0, ret, 0, i); 327 } 328 if (i < (N - 1)) { 329 System.arraycopy(cur, i + 1, ret, i, N - i - 1); 330 } 331 return ret; 332 } 333 } 334 return cur; 335 } 336 337 /** 338 * Removes value from given array if present, providing set-like behavior. 339 */ 340 public static @Nullable String[] removeString(@Nullable String[] cur, String val) { 341 if (cur == null) { 342 return null; 343 } 344 final int N = cur.length; 345 for (int i = 0; i < N; i++) { 346 if (Objects.equals(cur[i], val)) { 347 String[] ret = new String[N - 1]; 348 if (i > 0) { 349 System.arraycopy(cur, 0, ret, 0, i); 350 } 351 if (i < (N - 1)) { 352 System.arraycopy(cur, i + 1, ret, i, N - i - 1); 353 } 354 return ret; 355 } 356 } 357 return cur; 358 } 359 360 /** 361 * Adds value to given array if not already present, providing set-like 362 * behavior. 363 */ 364 public static @NonNull long[] appendLong(@Nullable long[] cur, long val) { 365 if (cur == null) { 366 return new long[] { val }; 367 } 368 final int N = cur.length; 369 for (int i = 0; i < N; i++) { 370 if (cur[i] == val) { 371 return cur; 372 } 373 } 374 long[] ret = new long[N + 1]; 375 System.arraycopy(cur, 0, ret, 0, N); 376 ret[N] = val; 377 return ret; 378 } 379 380 /** 381 * Removes value from given array if present, providing set-like behavior. 382 */ 383 public static @Nullable long[] removeLong(@Nullable long[] cur, long val) { 384 if (cur == null) { 385 return null; 386 } 387 final int N = cur.length; 388 for (int i = 0; i < N; i++) { 389 if (cur[i] == val) { 390 long[] ret = new long[N - 1]; 391 if (i > 0) { 392 System.arraycopy(cur, 0, ret, 0, i); 393 } 394 if (i < (N - 1)) { 395 System.arraycopy(cur, i + 1, ret, i, N - i - 1); 396 } 397 return ret; 398 } 399 } 400 return cur; 401 } 402 403 public static @Nullable long[] cloneOrNull(@Nullable long[] array) { 404 return (array != null) ? array.clone() : null; 405 } 406 407 public static @Nullable <T> ArraySet<T> cloneOrNull(@Nullable ArraySet<T> array) { 408 return (array != null) ? new ArraySet<T>(array) : null; 409 } 410 411 public static @NonNull <T> ArraySet<T> add(@Nullable ArraySet<T> cur, T val) { 412 if (cur == null) { 413 cur = new ArraySet<>(); 414 } 415 cur.add(val); 416 return cur; 417 } 418 419 public static @Nullable <T> ArraySet<T> remove(@Nullable ArraySet<T> cur, T val) { 420 if (cur == null) { 421 return null; 422 } 423 cur.remove(val); 424 if (cur.isEmpty()) { 425 return null; 426 } else { 427 return cur; 428 } 429 } 430 431 public static <T> boolean contains(@Nullable ArraySet<T> cur, T val) { 432 return (cur != null) ? cur.contains(val) : false; 433 } 434 435 public static @NonNull <T> ArrayList<T> add(@Nullable ArrayList<T> cur, T val) { 436 if (cur == null) { 437 cur = new ArrayList<>(); 438 } 439 cur.add(val); 440 return cur; 441 } 442 443 public static @Nullable <T> ArrayList<T> remove(@Nullable ArrayList<T> cur, T val) { 444 if (cur == null) { 445 return null; 446 } 447 cur.remove(val); 448 if (cur.isEmpty()) { 449 return null; 450 } else { 451 return cur; 452 } 453 } 454 455 public static <T> boolean contains(@Nullable Collection<T> cur, T val) { 456 return (cur != null) ? cur.contains(val) : false; 457 } 458 459 public static @Nullable <T> T[] trimToSize(@Nullable T[] array, int size) { 460 if (array == null || size == 0) { 461 return null; 462 } else if (array.length == size) { 463 return array; 464 } else { 465 return Arrays.copyOf(array, size); 466 } 467 } 468 469 /** 470 * Returns true if the two ArrayLists are equal with respect to the objects they contain. 471 * The objects must be in the same order and be reference equal (== not .equals()). 472 */ 473 public static <T> boolean referenceEquals(ArrayList<T> a, ArrayList<T> b) { 474 if (a == b) { 475 return true; 476 } 477 478 final int sizeA = a.size(); 479 final int sizeB = b.size(); 480 if (a == null || b == null || sizeA != sizeB) { 481 return false; 482 } 483 484 boolean diff = false; 485 for (int i = 0; i < sizeA && !diff; i++) { 486 diff |= a.get(i) != b.get(i); 487 } 488 return !diff; 489 } 490 491 /** 492 * Removes elements that match the predicate in an efficient way that alters the order of 493 * elements in the collection. This should only be used if order is not important. 494 * @param collection The ArrayList from which to remove elements. 495 * @param predicate The predicate that each element is tested against. 496 * @return the number of elements removed. 497 */ 498 public static <T> int unstableRemoveIf(@Nullable ArrayList<T> collection, 499 @NonNull java.util.function.Predicate<T> predicate) { 500 if (collection == null) { 501 return 0; 502 } 503 504 final int size = collection.size(); 505 int leftIdx = 0; 506 int rightIdx = size - 1; 507 while (leftIdx <= rightIdx) { 508 // Find the next element to remove moving left to right. 509 while (leftIdx < size && !predicate.test(collection.get(leftIdx))) { 510 leftIdx++; 511 } 512 513 // Find the next element to keep moving right to left. 514 while (rightIdx > leftIdx && predicate.test(collection.get(rightIdx))) { 515 rightIdx--; 516 } 517 518 if (leftIdx >= rightIdx) { 519 // Done. 520 break; 521 } 522 523 Collections.swap(collection, leftIdx, rightIdx); 524 leftIdx++; 525 rightIdx--; 526 } 527 528 // leftIdx is now at the end. 529 for (int i = size - 1; i >= leftIdx; i--) { 530 collection.remove(i); 531 } 532 return size - leftIdx; 533 } 534} 535