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