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 android.util;
18
19import com.android.internal.util.ArrayUtils;
20import com.android.internal.util.Preconditions;
21import java.util.Arrays;
22import libcore.util.EmptyArray;
23
24/**
25 * Implements a growing array of int primitives.
26 *
27 * @hide
28 */
29public class IntArray implements Cloneable {
30    private static final int MIN_CAPACITY_INCREMENT = 12;
31
32    private int[] mValues;
33    private int mSize;
34
35    private  IntArray(int[] array, int size) {
36        mValues = array;
37        mSize = Preconditions.checkArgumentInRange(size, 0, array.length, "size");
38    }
39
40    /**
41     * Creates an empty IntArray with the default initial capacity.
42     */
43    public IntArray() {
44        this(10);
45    }
46
47    /**
48     * Creates an empty IntArray with the specified initial capacity.
49     */
50    public IntArray(int initialCapacity) {
51        if (initialCapacity == 0) {
52            mValues = EmptyArray.INT;
53        } else {
54            mValues = ArrayUtils.newUnpaddedIntArray(initialCapacity);
55        }
56        mSize = 0;
57    }
58
59    /**
60     * Creates an IntArray wrapping the given primitive int array.
61     */
62    public static IntArray wrap(int[] array) {
63        return new IntArray(array, array.length);
64    }
65
66    /**
67     * Creates an IntArray from the given primitive int array, copying it.
68     */
69    public static IntArray fromArray(int[] array, int size) {
70        return wrap(Arrays.copyOf(array, size));
71    }
72
73    /**
74     * Changes the size of this IntArray. If this IntArray is shrinked, the backing array capacity
75     * is unchanged. If the new size is larger than backing array capacity, a new backing array is
76     * created from the current content of this IntArray padded with 0s.
77     */
78    public void resize(int newSize) {
79        Preconditions.checkArgumentNonnegative(newSize);
80        if (newSize <= mValues.length) {
81            Arrays.fill(mValues, newSize, mValues.length, 0);
82        } else {
83            ensureCapacity(newSize - mSize);
84        }
85        mSize = newSize;
86    }
87
88    /**
89     * Appends the specified value to the end of this array.
90     */
91    public void add(int value) {
92        add(mSize, value);
93    }
94
95    /**
96     * Inserts a value at the specified position in this array. If the specified index is equal to
97     * the length of the array, the value is added at the end.
98     *
99     * @throws IndexOutOfBoundsException when index &lt; 0 || index &gt; size()
100     */
101    public void add(int index, int value) {
102        ensureCapacity(1);
103        int rightSegment = mSize - index;
104        mSize++;
105        checkBounds(index);
106
107        if (rightSegment != 0) {
108            // Move by 1 all values from the right of 'index'
109            System.arraycopy(mValues, index, mValues, index + 1, rightSegment);
110        }
111
112        mValues[index] = value;
113    }
114
115    /**
116     * Searches the array for the specified value using the binary search algorithm. The array must
117     * be sorted (as by the {@link Arrays#sort(int[], int, int)} method) prior to making this call.
118     * If it is not sorted, the results are undefined. If the range contains multiple elements with
119     * the specified value, there is no guarantee which one will be found.
120     *
121     * @param value The value to search for.
122     * @return index of the search key, if it is contained in the array; otherwise, <i>(-(insertion
123     *         point) - 1)</i>. The insertion point is defined as the point at which the key would
124     *         be inserted into the array: the index of the first element greater than the key, or
125     *         {@link #size()} if all elements in the array are less than the specified key.
126     *         Note that this guarantees that the return value will be >= 0 if and only if the key
127     *         is found.
128     */
129    public int binarySearch(int value) {
130        return ContainerHelpers.binarySearch(mValues, mSize, value);
131    }
132
133    /**
134     * Adds the values in the specified array to this array.
135     */
136    public void addAll(IntArray values) {
137        final int count = values.mSize;
138        ensureCapacity(count);
139
140        System.arraycopy(values.mValues, 0, mValues, mSize, count);
141        mSize += count;
142    }
143
144    /**
145     * Ensures capacity to append at least <code>count</code> values.
146     */
147    private void ensureCapacity(int count) {
148        final int currentSize = mSize;
149        final int minCapacity = currentSize + count;
150        if (minCapacity >= mValues.length) {
151            final int targetCap = currentSize + (currentSize < (MIN_CAPACITY_INCREMENT / 2) ?
152                    MIN_CAPACITY_INCREMENT : currentSize >> 1);
153            final int newCapacity = targetCap > minCapacity ? targetCap : minCapacity;
154            final int[] newValues = ArrayUtils.newUnpaddedIntArray(newCapacity);
155            System.arraycopy(mValues, 0, newValues, 0, currentSize);
156            mValues = newValues;
157        }
158    }
159
160    /**
161     * Removes all values from this array.
162     */
163    public void clear() {
164        mSize = 0;
165    }
166
167    @Override
168    public IntArray clone() throws CloneNotSupportedException {
169        final IntArray clone = (IntArray) super.clone();
170        clone.mValues = mValues.clone();
171        return clone;
172    }
173
174    /**
175     * Returns the value at the specified position in this array.
176     */
177    public int get(int index) {
178        checkBounds(index);
179        return mValues[index];
180    }
181
182    /**
183     * Sets the value at the specified position in this array.
184     */
185    public void set(int index, int value) {
186        checkBounds(index);
187        mValues[index] = value;
188    }
189
190    /**
191     * Returns the index of the first occurrence of the specified value in this
192     * array, or -1 if this array does not contain the value.
193     */
194    public int indexOf(int value) {
195        final int n = mSize;
196        for (int i = 0; i < n; i++) {
197            if (mValues[i] == value) {
198                return i;
199            }
200        }
201        return -1;
202    }
203
204    /**
205     * Removes the value at the specified index from this array.
206     */
207    public void remove(int index) {
208        checkBounds(index);
209        System.arraycopy(mValues, index + 1, mValues, index, mSize - index - 1);
210        mSize--;
211    }
212
213    /**
214     * Returns the number of values in this array.
215     */
216    public int size() {
217        return mSize;
218    }
219
220    /**
221     * Returns a new array with the contents of this IntArray.
222     */
223    public int[] toArray() {
224        return Arrays.copyOf(mValues, mSize);
225    }
226
227    private void checkBounds(int index) {
228        if (index < 0 || mSize <= index) {
229            throw new ArrayIndexOutOfBoundsException(mSize, index);
230        }
231    }
232}
233