1 /* 2 * Copyright (C) 2014 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 /** 20 * A helper class that aims to provide comparable growth performance to ArrayList, but on primitive 21 * arrays. Common array operations are implemented for efficient use in dynamic containers. 22 * 23 * All methods in this class assume that the length of an array is equivalent to its capacity and 24 * NOT the number of elements in the array. The current size of the array is always passed in as a 25 * parameter. 26 * 27 * @hide 28 */ 29 public final class GrowingArrayUtils { 30 31 /** 32 * Appends an element to the end of the array, growing the array if there is no more room. 33 * @param array The array to which to append the element. This must NOT be null. 34 * @param currentSize The number of elements in the array. Must be less than or equal to 35 * array.length. 36 * @param element The element to append. 37 * @return the array to which the element was appended. This may be different than the given 38 * array. 39 */ append(T[] array, int currentSize, T element)40 public static <T> T[] append(T[] array, int currentSize, T element) { 41 assert currentSize <= array.length; 42 43 if (currentSize + 1 > array.length) { 44 @SuppressWarnings("unchecked") 45 T[] newArray = ArrayUtils.newUnpaddedArray( 46 (Class<T>) array.getClass().getComponentType(), growSize(currentSize)); 47 System.arraycopy(array, 0, newArray, 0, currentSize); 48 array = newArray; 49 } 50 array[currentSize] = element; 51 return array; 52 } 53 54 /** 55 * Primitive int version of {@link #append(Object[], int, Object)}. 56 */ append(int[] array, int currentSize, int element)57 public static int[] append(int[] array, int currentSize, int element) { 58 assert currentSize <= array.length; 59 60 if (currentSize + 1 > array.length) { 61 int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize)); 62 System.arraycopy(array, 0, newArray, 0, currentSize); 63 array = newArray; 64 } 65 array[currentSize] = element; 66 return array; 67 } 68 69 /** 70 * Primitive long version of {@link #append(Object[], int, Object)}. 71 */ append(long[] array, int currentSize, long element)72 public static long[] append(long[] array, int currentSize, long element) { 73 assert currentSize <= array.length; 74 75 if (currentSize + 1 > array.length) { 76 long[] newArray = ArrayUtils.newUnpaddedLongArray(growSize(currentSize)); 77 System.arraycopy(array, 0, newArray, 0, currentSize); 78 array = newArray; 79 } 80 array[currentSize] = element; 81 return array; 82 } 83 84 /** 85 * Primitive boolean version of {@link #append(Object[], int, Object)}. 86 */ append(boolean[] array, int currentSize, boolean element)87 public static boolean[] append(boolean[] array, int currentSize, boolean element) { 88 assert currentSize <= array.length; 89 90 if (currentSize + 1 > array.length) { 91 boolean[] newArray = ArrayUtils.newUnpaddedBooleanArray(growSize(currentSize)); 92 System.arraycopy(array, 0, newArray, 0, currentSize); 93 array = newArray; 94 } 95 array[currentSize] = element; 96 return array; 97 } 98 99 /** 100 * Primitive float version of {@link #append(Object[], int, Object)}. 101 */ append(float[] array, int currentSize, float element)102 public static float[] append(float[] array, int currentSize, float element) { 103 assert currentSize <= array.length; 104 105 if (currentSize + 1 > array.length) { 106 float[] newArray = ArrayUtils.newUnpaddedFloatArray(growSize(currentSize)); 107 System.arraycopy(array, 0, newArray, 0, currentSize); 108 array = newArray; 109 } 110 array[currentSize] = element; 111 return array; 112 } 113 114 /** 115 * Inserts an element into the array at the specified index, growing the array if there is no 116 * more room. 117 * 118 * @param array The array to which to append the element. Must NOT be null. 119 * @param currentSize The number of elements in the array. Must be less than or equal to 120 * array.length. 121 * @param element The element to insert. 122 * @return the array to which the element was appended. This may be different than the given 123 * array. 124 */ insert(T[] array, int currentSize, int index, T element)125 public static <T> T[] insert(T[] array, int currentSize, int index, T element) { 126 assert currentSize <= array.length; 127 128 if (currentSize + 1 <= array.length) { 129 System.arraycopy(array, index, array, index + 1, currentSize - index); 130 array[index] = element; 131 return array; 132 } 133 134 @SuppressWarnings("unchecked") 135 T[] newArray = ArrayUtils.newUnpaddedArray((Class<T>)array.getClass().getComponentType(), 136 growSize(currentSize)); 137 System.arraycopy(array, 0, newArray, 0, index); 138 newArray[index] = element; 139 System.arraycopy(array, index, newArray, index + 1, array.length - index); 140 return newArray; 141 } 142 143 /** 144 * Primitive int version of {@link #insert(Object[], int, int, Object)}. 145 */ insert(int[] array, int currentSize, int index, int element)146 public static int[] insert(int[] array, int currentSize, int index, int element) { 147 assert currentSize <= array.length; 148 149 if (currentSize + 1 <= array.length) { 150 System.arraycopy(array, index, array, index + 1, currentSize - index); 151 array[index] = element; 152 return array; 153 } 154 155 int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize)); 156 System.arraycopy(array, 0, newArray, 0, index); 157 newArray[index] = element; 158 System.arraycopy(array, index, newArray, index + 1, array.length - index); 159 return newArray; 160 } 161 162 /** 163 * Primitive long version of {@link #insert(Object[], int, int, Object)}. 164 */ insert(long[] array, int currentSize, int index, long element)165 public static long[] insert(long[] array, int currentSize, int index, long element) { 166 assert currentSize <= array.length; 167 168 if (currentSize + 1 <= array.length) { 169 System.arraycopy(array, index, array, index + 1, currentSize - index); 170 array[index] = element; 171 return array; 172 } 173 174 long[] newArray = ArrayUtils.newUnpaddedLongArray(growSize(currentSize)); 175 System.arraycopy(array, 0, newArray, 0, index); 176 newArray[index] = element; 177 System.arraycopy(array, index, newArray, index + 1, array.length - index); 178 return newArray; 179 } 180 181 /** 182 * Primitive boolean version of {@link #insert(Object[], int, int, Object)}. 183 */ insert(boolean[] array, int currentSize, int index, boolean element)184 public static boolean[] insert(boolean[] array, int currentSize, int index, boolean element) { 185 assert currentSize <= array.length; 186 187 if (currentSize + 1 <= array.length) { 188 System.arraycopy(array, index, array, index + 1, currentSize - index); 189 array[index] = element; 190 return array; 191 } 192 193 boolean[] newArray = ArrayUtils.newUnpaddedBooleanArray(growSize(currentSize)); 194 System.arraycopy(array, 0, newArray, 0, index); 195 newArray[index] = element; 196 System.arraycopy(array, index, newArray, index + 1, array.length - index); 197 return newArray; 198 } 199 200 /** 201 * Given the current size of an array, returns an ideal size to which the array should grow. 202 * This is typically double the given size, but should not be relied upon to do so in the 203 * future. 204 */ growSize(int currentSize)205 public static int growSize(int currentSize) { 206 return currentSize <= 4 ? 8 : currentSize * 2; 207 } 208 209 // Uninstantiable GrowingArrayUtils()210 private GrowingArrayUtils() {} 211 } 212