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
17package 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 */
29public 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     * Primitive float version of {@link #append(Object[], int, Object)}.
101     */
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     */
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     */
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     */
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     */
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     */
205    public static int growSize(int currentSize) {
206        return currentSize <= 4 ? 8 : currentSize * 2;
207    }
208
209    // Uninstantiable
210    private GrowingArrayUtils() {}
211}
212