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;
20
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    /**
36     * Creates an empty IntArray with the default initial capacity.
37     */
38    public IntArray() {
39        this(10);
40    }
41
42    /**
43     * Creates an empty IntArray with the specified initial capacity.
44     */
45    public IntArray(int initialCapacity) {
46        if (initialCapacity == 0) {
47            mValues = EmptyArray.INT;
48        } else {
49            mValues = ArrayUtils.newUnpaddedIntArray(initialCapacity);
50        }
51        mSize = 0;
52    }
53
54    /**
55     * Appends the specified value to the end of this array.
56     */
57    public void add(int value) {
58        add(mSize, value);
59    }
60
61    /**
62     * Inserts a value at the specified position in this array.
63     *
64     * @throws IndexOutOfBoundsException when index < 0 || index > size()
65     */
66    public void add(int index, int value) {
67        if (index < 0 || index > mSize) {
68            throw new IndexOutOfBoundsException();
69        }
70
71        ensureCapacity(1);
72
73        if (mSize - index != 0) {
74            System.arraycopy(mValues, index, mValues, index + 1, mSize - index);
75        }
76
77        mValues[index] = value;
78        mSize++;
79    }
80
81    /**
82     * Searches the array for the specified value using the binary search algorithm. The array must
83     * be sorted (as by the {@link Arrays#sort(int[], int, int)} method) prior to making this call.
84     * If it is not sorted, the results are undefined. If the range contains multiple elements with
85     * the specified value, there is no guarantee which one will be found.
86     *
87     * @param value The value to search for.
88     * @return index of the search key, if it is contained in the array; otherwise, <i>(-(insertion
89     *         point) - 1)</i>. The insertion point is defined as the point at which the key would
90     *         be inserted into the array: the index of the first element greater than the key, or
91     *         {@link #size()} if all elements in the array are less than the specified key.
92     *         Note that this guarantees that the return value will be >= 0 if and only if the key
93     *         is found.
94     */
95    public int binarySearch(int value) {
96        return ContainerHelpers.binarySearch(mValues, mSize, value);
97    }
98
99    /**
100     * Adds the values in the specified array to this array.
101     */
102    public void addAll(IntArray values) {
103        final int count = values.mSize;
104        ensureCapacity(count);
105
106        System.arraycopy(values.mValues, 0, mValues, mSize, count);
107        mSize += count;
108    }
109
110    /**
111     * Ensures capacity to append at least <code>count</code> values.
112     */
113    private void ensureCapacity(int count) {
114        final int currentSize = mSize;
115        final int minCapacity = currentSize + count;
116        if (minCapacity >= mValues.length) {
117            final int targetCap = currentSize + (currentSize < (MIN_CAPACITY_INCREMENT / 2) ?
118                    MIN_CAPACITY_INCREMENT : currentSize >> 1);
119            final int newCapacity = targetCap > minCapacity ? targetCap : minCapacity;
120            final int[] newValues = ArrayUtils.newUnpaddedIntArray(newCapacity);
121            System.arraycopy(mValues, 0, newValues, 0, currentSize);
122            mValues = newValues;
123        }
124    }
125
126    /**
127     * Removes all values from this array.
128     */
129    public void clear() {
130        mSize = 0;
131    }
132
133    @Override
134    public IntArray clone() throws CloneNotSupportedException {
135        final IntArray clone = (IntArray) super.clone();
136        clone.mValues = mValues.clone();
137        return clone;
138    }
139
140    /**
141     * Returns the value at the specified position in this array.
142     */
143    public int get(int index) {
144        if (index >= mSize) {
145            throw new ArrayIndexOutOfBoundsException(mSize, index);
146        }
147        return mValues[index];
148    }
149
150    /**
151     * Returns the index of the first occurrence of the specified value in this
152     * array, or -1 if this array does not contain the value.
153     */
154    public int indexOf(int value) {
155        final int n = mSize;
156        for (int i = 0; i < n; i++) {
157            if (mValues[i] == value) {
158                return i;
159            }
160        }
161        return -1;
162    }
163
164    /**
165     * Removes the value at the specified index from this array.
166     */
167    public void remove(int index) {
168        if (index >= mSize) {
169            throw new ArrayIndexOutOfBoundsException(mSize, index);
170        }
171        System.arraycopy(mValues, index + 1, mValues, index, mSize - index - 1);
172        mSize--;
173    }
174
175    /**
176     * Returns the number of values in this array.
177     */
178    public int size() {
179        return mSize;
180    }
181
182    /**
183     * Returns a new array with the contents of this IntArray.
184     */
185    public int[] toArray() {
186        return Arrays.copyOf(mValues, mSize);
187    }
188}
189