1776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski/* 2776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * Copyright (C) 2014 The Android Open Source Project 3776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * 4776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * Licensed under the Apache License, Version 2.0 (the "License"); 5776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * you may not use this file except in compliance with the License. 6776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * You may obtain a copy of the License at 7776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * 8776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * http://www.apache.org/licenses/LICENSE-2.0 9776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * 10776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * Unless required by applicable law or agreed to in writing, software 11776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * distributed under the License is distributed on an "AS IS" BASIS, 12776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * See the License for the specific language governing permissions and 14776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * limitations under the License. 15776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski */ 16776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 17776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinskipackage com.android.internal.util; 18776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 19776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski/** 20776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * A helper class that aims to provide comparable growth performance to ArrayList, but on primitive 21776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * arrays. Common array operations are implemented for efficient use in dynamic containers. 22776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * 23776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * All methods in this class assume that the length of an array is equivalent to its capacity and 24776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * NOT the number of elements in the array. The current size of the array is always passed in as a 25776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * parameter. 26776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * 27776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * @hide 28776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski */ 29776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinskipublic final class GrowingArrayUtils { 30776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 31776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski /** 32776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * Appends an element to the end of the array, growing the array if there is no more room. 33776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * @param array The array to which to append the element. This must NOT be null. 34776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * @param currentSize The number of elements in the array. Must be less than or equal to 35776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * array.length. 36776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * @param element The element to append. 37776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * @return the array to which the element was appended. This may be different than the given 38776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * array. 39776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski */ 40776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski public static <T> T[] append(T[] array, int currentSize, T element) { 41776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski assert currentSize <= array.length; 42776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 43776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski if (currentSize + 1 > array.length) { 44776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski @SuppressWarnings("unchecked") 45776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski T[] newArray = ArrayUtils.newUnpaddedArray( 46776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski (Class<T>) array.getClass().getComponentType(), growSize(currentSize)); 47776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski System.arraycopy(array, 0, newArray, 0, currentSize); 48776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski array = newArray; 49776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski } 50776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski array[currentSize] = element; 51776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski return array; 52776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski } 53776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 54776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski /** 55776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * Primitive int version of {@link #append(Object[], int, Object)}. 56776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski */ 57776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski public static int[] append(int[] array, int currentSize, int element) { 58776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski assert currentSize <= array.length; 59776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 60776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski if (currentSize + 1 > array.length) { 61776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize)); 62776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski System.arraycopy(array, 0, newArray, 0, currentSize); 63776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski array = newArray; 64776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski } 65776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski array[currentSize] = element; 66776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski return array; 67776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski } 68776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 69776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski /** 70776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * Primitive long version of {@link #append(Object[], int, Object)}. 71776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski */ 72776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski public static long[] append(long[] array, int currentSize, long element) { 73776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski assert currentSize <= array.length; 74776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 75776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski if (currentSize + 1 > array.length) { 76776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski long[] newArray = ArrayUtils.newUnpaddedLongArray(growSize(currentSize)); 77776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski System.arraycopy(array, 0, newArray, 0, currentSize); 78776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski array = newArray; 79776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski } 80776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski array[currentSize] = element; 81776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski return array; 82776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski } 83776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 84776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski /** 85776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * Primitive boolean version of {@link #append(Object[], int, Object)}. 86776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski */ 87776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski public static boolean[] append(boolean[] array, int currentSize, boolean element) { 88776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski assert currentSize <= array.length; 89776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 90776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski if (currentSize + 1 > array.length) { 91776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski boolean[] newArray = ArrayUtils.newUnpaddedBooleanArray(growSize(currentSize)); 92776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski System.arraycopy(array, 0, newArray, 0, currentSize); 93776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski array = newArray; 94776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski } 95776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski array[currentSize] = element; 96776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski return array; 97776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski } 98776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 99776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski /** 100dbee9bb342cdfaa5155b1918f90262c05e2464cbTeng-Hui Zhu * Primitive float version of {@link #append(Object[], int, Object)}. 101dbee9bb342cdfaa5155b1918f90262c05e2464cbTeng-Hui Zhu */ 102dbee9bb342cdfaa5155b1918f90262c05e2464cbTeng-Hui Zhu public static float[] append(float[] array, int currentSize, float element) { 103dbee9bb342cdfaa5155b1918f90262c05e2464cbTeng-Hui Zhu assert currentSize <= array.length; 104dbee9bb342cdfaa5155b1918f90262c05e2464cbTeng-Hui Zhu 105dbee9bb342cdfaa5155b1918f90262c05e2464cbTeng-Hui Zhu if (currentSize + 1 > array.length) { 106dbee9bb342cdfaa5155b1918f90262c05e2464cbTeng-Hui Zhu float[] newArray = ArrayUtils.newUnpaddedFloatArray(growSize(currentSize)); 107dbee9bb342cdfaa5155b1918f90262c05e2464cbTeng-Hui Zhu System.arraycopy(array, 0, newArray, 0, currentSize); 108dbee9bb342cdfaa5155b1918f90262c05e2464cbTeng-Hui Zhu array = newArray; 109dbee9bb342cdfaa5155b1918f90262c05e2464cbTeng-Hui Zhu } 110dbee9bb342cdfaa5155b1918f90262c05e2464cbTeng-Hui Zhu array[currentSize] = element; 111dbee9bb342cdfaa5155b1918f90262c05e2464cbTeng-Hui Zhu return array; 112dbee9bb342cdfaa5155b1918f90262c05e2464cbTeng-Hui Zhu } 113dbee9bb342cdfaa5155b1918f90262c05e2464cbTeng-Hui Zhu 114dbee9bb342cdfaa5155b1918f90262c05e2464cbTeng-Hui Zhu /** 115776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * Inserts an element into the array at the specified index, growing the array if there is no 116776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * more room. 117776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * 118776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * @param array The array to which to append the element. Must NOT be null. 119776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * @param currentSize The number of elements in the array. Must be less than or equal to 120776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * array.length. 121776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * @param element The element to insert. 122776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * @return the array to which the element was appended. This may be different than the given 123776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * array. 124776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski */ 125776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski public static <T> T[] insert(T[] array, int currentSize, int index, T element) { 126776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski assert currentSize <= array.length; 127776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 128776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski if (currentSize + 1 <= array.length) { 129776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski System.arraycopy(array, index, array, index + 1, currentSize - index); 130776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski array[index] = element; 131776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski return array; 132776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski } 133776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 134776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski @SuppressWarnings("unchecked") 135776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski T[] newArray = ArrayUtils.newUnpaddedArray((Class<T>)array.getClass().getComponentType(), 136776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski growSize(currentSize)); 137776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski System.arraycopy(array, 0, newArray, 0, index); 138776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski newArray[index] = element; 139776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski System.arraycopy(array, index, newArray, index + 1, array.length - index); 140776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski return newArray; 141776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski } 142776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 143776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski /** 144776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * Primitive int version of {@link #insert(Object[], int, int, Object)}. 145776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski */ 146776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski public static int[] insert(int[] array, int currentSize, int index, int element) { 147776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski assert currentSize <= array.length; 148776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 149776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski if (currentSize + 1 <= array.length) { 150776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski System.arraycopy(array, index, array, index + 1, currentSize - index); 151776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski array[index] = element; 152776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski return array; 153776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski } 154776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 155776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize)); 156776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski System.arraycopy(array, 0, newArray, 0, index); 157776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski newArray[index] = element; 158776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski System.arraycopy(array, index, newArray, index + 1, array.length - index); 159776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski return newArray; 160776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski } 161776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 162776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski /** 163776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * Primitive long version of {@link #insert(Object[], int, int, Object)}. 164776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski */ 165776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski public static long[] insert(long[] array, int currentSize, int index, long element) { 166776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski assert currentSize <= array.length; 167776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 168776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski if (currentSize + 1 <= array.length) { 169776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski System.arraycopy(array, index, array, index + 1, currentSize - index); 170776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski array[index] = element; 171776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski return array; 172776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski } 173776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 174776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski long[] newArray = ArrayUtils.newUnpaddedLongArray(growSize(currentSize)); 175776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski System.arraycopy(array, 0, newArray, 0, index); 176776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski newArray[index] = element; 177776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski System.arraycopy(array, index, newArray, index + 1, array.length - index); 178776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski return newArray; 179776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski } 180776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 181776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski /** 182776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * Primitive boolean version of {@link #insert(Object[], int, int, Object)}. 183776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski */ 184776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski public static boolean[] insert(boolean[] array, int currentSize, int index, boolean element) { 185776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski assert currentSize <= array.length; 186776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 187776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski if (currentSize + 1 <= array.length) { 188776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski System.arraycopy(array, index, array, index + 1, currentSize - index); 189776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski array[index] = element; 190776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski return array; 191776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski } 192776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 193776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski boolean[] newArray = ArrayUtils.newUnpaddedBooleanArray(growSize(currentSize)); 194776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski System.arraycopy(array, 0, newArray, 0, index); 195776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski newArray[index] = element; 196776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski System.arraycopy(array, index, newArray, index + 1, array.length - index); 197776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski return newArray; 198776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski } 199776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 200776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski /** 201776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * Given the current size of an array, returns an ideal size to which the array should grow. 202776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * This is typically double the given size, but should not be relied upon to do so in the 203776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski * future. 204776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski */ 205776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski public static int growSize(int currentSize) { 206776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski return currentSize <= 4 ? 8 : currentSize * 2; 207776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski } 208776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 209776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski // Uninstantiable 210776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski private GrowingArrayUtils() {} 211776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski} 212