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 17 package com.android.internal.util; 18 19 import java.lang.reflect.Array; 20 21 // XXX these should be changed to reflect the actual memory allocator we use. 22 // it looks like right now objects want to be powers of 2 minus 8 23 // and the array size eats another 4 bytes 24 25 /** 26 * ArrayUtils contains some methods that you can call to find out 27 * the most efficient increments by which to grow arrays. 28 */ 29 public class ArrayUtils 30 { 31 private static Object[] EMPTY = new Object[0]; 32 private static final int CACHE_SIZE = 73; 33 private static Object[] sCache = new Object[CACHE_SIZE]; 34 35 private ArrayUtils() { /* cannot be instantiated */ } 36 37 public static int idealByteArraySize(int need) { 38 for (int i = 4; i < 32; i++) 39 if (need <= (1 << i) - 12) 40 return (1 << i) - 12; 41 42 return need; 43 } 44 45 public static int idealBooleanArraySize(int need) { 46 return idealByteArraySize(need); 47 } 48 49 public static int idealShortArraySize(int need) { 50 return idealByteArraySize(need * 2) / 2; 51 } 52 53 public static int idealCharArraySize(int need) { 54 return idealByteArraySize(need * 2) / 2; 55 } 56 57 public static int idealIntArraySize(int need) { 58 return idealByteArraySize(need * 4) / 4; 59 } 60 61 public static int idealFloatArraySize(int need) { 62 return idealByteArraySize(need * 4) / 4; 63 } 64 65 public static int idealObjectArraySize(int need) { 66 return idealByteArraySize(need * 4) / 4; 67 } 68 69 public static int idealLongArraySize(int need) { 70 return idealByteArraySize(need * 8) / 8; 71 } 72 73 /** 74 * Checks if the beginnings of two byte arrays are equal. 75 * 76 * @param array1 the first byte array 77 * @param array2 the second byte array 78 * @param length the number of bytes to check 79 * @return true if they're equal, false otherwise 80 */ 81 public static boolean equals(byte[] array1, byte[] array2, int length) { 82 if (length < 0) { 83 throw new IllegalArgumentException(); 84 } 85 86 if (array1 == array2) { 87 return true; 88 } 89 if (array1 == null || array2 == null || array1.length < length || array2.length < length) { 90 return false; 91 } 92 for (int i = 0; i < length; i++) { 93 if (array1[i] != array2[i]) { 94 return false; 95 } 96 } 97 return true; 98 } 99 100 /** 101 * Returns an empty array of the specified type. The intent is that 102 * it will return the same empty array every time to avoid reallocation, 103 * although this is not guaranteed. 104 */ 105 public static <T> T[] emptyArray(Class<T> kind) { 106 if (kind == Object.class) { 107 return (T[]) EMPTY; 108 } 109 110 int bucket = ((System.identityHashCode(kind) / 8) & 0x7FFFFFFF) % CACHE_SIZE; 111 Object cache = sCache[bucket]; 112 113 if (cache == null || cache.getClass().getComponentType() != kind) { 114 cache = Array.newInstance(kind, 0); 115 sCache[bucket] = cache; 116 117 // Log.e("cache", "new empty " + kind.getName() + " at " + bucket); 118 } 119 120 return (T[]) cache; 121 } 122 123 /** 124 * Checks that value is present as at least one of the elements of the array. 125 * @param array the array to check in 126 * @param value the value to check for 127 * @return true if the value is present in the array 128 */ 129 public static <T> boolean contains(T[] array, T value) { 130 return indexOf(array, value) != -1; 131 } 132 133 /** 134 * Return first index of {@code value} in {@code array}, or {@code -1} if 135 * not found. 136 */ 137 public static <T> int indexOf(T[] array, T value) { 138 for (int i = 0; i < array.length; i++) { 139 if (array[i] == null) { 140 if (value == null) return i; 141 } else { 142 if (value != null && array[i].equals(value)) return i; 143 } 144 } 145 return -1; 146 } 147 148 /** 149 * Test if all {@code check} items are contained in {@code array}. 150 */ 151 public static <T> boolean containsAll(T[] array, T[] check) { 152 for (T checkItem : check) { 153 if (!contains(array, checkItem)) { 154 return false; 155 } 156 } 157 return true; 158 } 159 160 public static boolean contains(int[] array, int value) { 161 for (int element : array) { 162 if (element == value) { 163 return true; 164 } 165 } 166 return false; 167 } 168 169 public static long total(long[] array) { 170 long total = 0; 171 for (long value : array) { 172 total += value; 173 } 174 return total; 175 } 176 177 /** 178 * Appends an element to a copy of the array and returns the copy. 179 * @param array The original array, or null to represent an empty array. 180 * @param element The element to add. 181 * @return A new array that contains all of the elements of the original array 182 * with the specified element added at the end. 183 */ 184 @SuppressWarnings("unchecked") 185 public static <T> T[] appendElement(Class<T> kind, T[] array, T element) { 186 final T[] result; 187 final int end; 188 if (array != null) { 189 end = array.length; 190 result = (T[])Array.newInstance(kind, end + 1); 191 System.arraycopy(array, 0, result, 0, end); 192 } else { 193 end = 0; 194 result = (T[])Array.newInstance(kind, 1); 195 } 196 result[end] = element; 197 return result; 198 } 199 200 /** 201 * Removes an element from a copy of the array and returns the copy. 202 * If the element is not present, then the original array is returned unmodified. 203 * @param array The original array, or null to represent an empty array. 204 * @param element The element to remove. 205 * @return A new array that contains all of the elements of the original array 206 * except the first copy of the specified element removed. If the specified element 207 * was not present, then returns the original array. Returns null if the result 208 * would be an empty array. 209 */ 210 @SuppressWarnings("unchecked") 211 public static <T> T[] removeElement(Class<T> kind, T[] array, T element) { 212 if (array != null) { 213 final int length = array.length; 214 for (int i = 0; i < length; i++) { 215 if (array[i] == element) { 216 if (length == 1) { 217 return null; 218 } 219 T[] result = (T[])Array.newInstance(kind, length - 1); 220 System.arraycopy(array, 0, result, 0, i); 221 System.arraycopy(array, i + 1, result, i, length - i - 1); 222 return result; 223 } 224 } 225 } 226 return array; 227 } 228 229 public static int[] appendInt(int[] cur, int val) { 230 if (cur == null) { 231 return new int[] { val }; 232 } 233 final int N = cur.length; 234 for (int i = 0; i < N; i++) { 235 if (cur[i] == val) { 236 return cur; 237 } 238 } 239 int[] ret = new int[N + 1]; 240 System.arraycopy(cur, 0, ret, 0, N); 241 ret[N] = val; 242 return ret; 243 } 244 245 public static int[] removeInt(int[] cur, int val) { 246 if (cur == null) { 247 return null; 248 } 249 final int N = cur.length; 250 for (int i = 0; i < N; i++) { 251 if (cur[i] == val) { 252 int[] ret = new int[N - 1]; 253 if (i > 0) { 254 System.arraycopy(cur, 0, ret, 0, i); 255 } 256 if (i < (N - 1)) { 257 System.arraycopy(cur, i + 1, ret, i, N - i - 1); 258 } 259 return ret; 260 } 261 } 262 return cur; 263 } 264 } 265
