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