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 */ 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 */ 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 */ 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 */ 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 * Inserts an element into the array at the specified index, growing the array if there is no 101 * more room. 102 * 103 * @param array The array to which to append the element. Must NOT be null. 104 * @param currentSize The number of elements in the array. Must be less than or equal to 105 * array.length. 106 * @param element The element to insert. 107 * @return the array to which the element was appended. This may be different than the given 108 * array. 109 */ 110 public static <T> T[] insert(T[] array, int currentSize, int index, T element) { 111 assert currentSize <= array.length; 112 113 if (currentSize + 1 <= array.length) { 114 System.arraycopy(array, index, array, index + 1, currentSize - index); 115 array[index] = element; 116 return array; 117 } 118 119 @SuppressWarnings("unchecked") 120 T[] newArray = ArrayUtils.newUnpaddedArray((Class<T>)array.getClass().getComponentType(), 121 growSize(currentSize)); 122 System.arraycopy(array, 0, newArray, 0, index); 123 newArray[index] = element; 124 System.arraycopy(array, index, newArray, index + 1, array.length - index); 125 return newArray; 126 } 127 128 /** 129 * Primitive int version of {@link #insert(Object[], int, int, Object)}. 130 */ 131 public static int[] insert(int[] array, int currentSize, int index, int element) { 132 assert currentSize <= array.length; 133 134 if (currentSize + 1 <= array.length) { 135 System.arraycopy(array, index, array, index + 1, currentSize - index); 136 array[index] = element; 137 return array; 138 } 139 140 int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize)); 141 System.arraycopy(array, 0, newArray, 0, index); 142 newArray[index] = element; 143 System.arraycopy(array, index, newArray, index + 1, array.length - index); 144 return newArray; 145 } 146 147 /** 148 * Primitive long version of {@link #insert(Object[], int, int, Object)}. 149 */ 150 public static long[] insert(long[] array, int currentSize, int index, long element) { 151 assert currentSize <= array.length; 152 153 if (currentSize + 1 <= array.length) { 154 System.arraycopy(array, index, array, index + 1, currentSize - index); 155 array[index] = element; 156 return array; 157 } 158 159 long[] newArray = ArrayUtils.newUnpaddedLongArray(growSize(currentSize)); 160 System.arraycopy(array, 0, newArray, 0, index); 161 newArray[index] = element; 162 System.arraycopy(array, index, newArray, index + 1, array.length - index); 163 return newArray; 164 } 165 166 /** 167 * Primitive boolean version of {@link #insert(Object[], int, int, Object)}. 168 */ 169 public static boolean[] insert(boolean[] array, int currentSize, int index, boolean element) { 170 assert currentSize <= array.length; 171 172 if (currentSize + 1 <= array.length) { 173 System.arraycopy(array, index, array, index + 1, currentSize - index); 174 array[index] = element; 175 return array; 176 } 177 178 boolean[] newArray = ArrayUtils.newUnpaddedBooleanArray(growSize(currentSize)); 179 System.arraycopy(array, 0, newArray, 0, index); 180 newArray[index] = element; 181 System.arraycopy(array, index, newArray, index + 1, array.length - index); 182 return newArray; 183 } 184 185 /** 186 * Given the current size of an array, returns an ideal size to which the array should grow. 187 * This is typically double the given size, but should not be relied upon to do so in the 188 * future. 189 */ 190 public static int growSize(int currentSize) { 191 return currentSize <= 4 ? 8 : currentSize * 2; 192 } 193 194 // Uninstantiable 195 private GrowingArrayUtils() {} 196 } 197
