1f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette/* 2f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Copyright (C) 2013 The Android Open Source Project 3f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * 4f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Licensed under the Apache License, Version 2.0 (the "License"); 5f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * you may not use this file except in compliance with the License. 6f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * You may obtain a copy of the License at 7f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * 8f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * http://www.apache.org/licenses/LICENSE-2.0 9f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * 10f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Unless required by applicable law or agreed to in writing, software 11f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * distributed under the License is distributed on an "AS IS" BASIS, 12f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * See the License for the specific language governing permissions and 14f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * limitations under the License. 15f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 16f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 17f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverettepackage android.util; 18f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 199669e3af6500ffd1041df7c4197865a001cdc055Eugene Suslaimport android.annotation.Nullable; 209669e3af6500ffd1041df7c4197865a001cdc055Eugene Susla 21f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viveretteimport com.android.internal.util.ArrayUtils; 22112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichiimport com.android.internal.util.Preconditions; 239669e3af6500ffd1041df7c4197865a001cdc055Eugene Susla 24776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinskiimport libcore.util.EmptyArray; 25f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 269669e3af6500ffd1041df7c4197865a001cdc055Eugene Suslaimport java.util.Arrays; 279669e3af6500ffd1041df7c4197865a001cdc055Eugene Susla 28f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette/** 29f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Implements a growing array of long primitives. 30f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * 31f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * @hide 32f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 33f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverettepublic class LongArray implements Cloneable { 34f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette private static final int MIN_CAPACITY_INCREMENT = 12; 35f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 36f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette private long[] mValues; 37f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette private int mSize; 38f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 39112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi private LongArray(long[] array, int size) { 40112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi mValues = array; 41112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi mSize = Preconditions.checkArgumentInRange(size, 0, array.length, "size"); 42112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi } 43112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi 44f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 45f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Creates an empty LongArray with the default initial capacity. 46f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 47f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public LongArray() { 48f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette this(10); 49f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 50f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 51f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 52f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Creates an empty LongArray with the specified initial capacity. 53f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 54f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public LongArray(int initialCapacity) { 55f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette if (initialCapacity == 0) { 56776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mValues = EmptyArray.LONG; 57f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } else { 58776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mValues = ArrayUtils.newUnpaddedLongArray(initialCapacity); 59f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 60f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette mSize = 0; 61f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 62f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 63f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 64112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi * Creates an LongArray wrapping the given primitive long array. 65112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi */ 66112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi public static LongArray wrap(long[] array) { 67112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi return new LongArray(array, array.length); 68112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi } 69112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi 70112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi /** 71112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi * Creates an LongArray from the given primitive long array, copying it. 72112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi */ 73112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi public static LongArray fromArray(long[] array, int size) { 74112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi return wrap(Arrays.copyOf(array, size)); 75112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi } 76112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi 77112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi /** 78112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi * Changes the size of this LongArray. If this LongArray is shrinked, the backing array capacity 79112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi * is unchanged. If the new size is larger than backing array capacity, a new backing array is 80112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi * created from the current content of this LongArray padded with 0s. 81112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi */ 82112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi public void resize(int newSize) { 83112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi Preconditions.checkArgumentNonnegative(newSize); 84112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi if (newSize <= mValues.length) { 85112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi Arrays.fill(mValues, newSize, mValues.length, 0); 86112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi } else { 87112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi ensureCapacity(newSize - mSize); 88112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi } 89112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi mSize = newSize; 90112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi } 91112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi 92112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi /** 93f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Appends the specified value to the end of this array. 94f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 95f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public void add(long value) { 96f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette add(mSize, value); 97f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 98f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 99f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 100112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi * Inserts a value at the specified position in this array. If the specified index is equal to 101112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi * the length of the array, the value is added at the end. 102f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * 103f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * @throws IndexOutOfBoundsException when index < 0 || index > size() 104f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 105f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public void add(int index, long value) { 106f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette ensureCapacity(1); 107112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi int rightSegment = mSize - index; 108112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi mSize++; 109112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi checkBounds(index); 110f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 111112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi if (rightSegment != 0) { 112112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi // Move by 1 all values from the right of 'index' 113112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi System.arraycopy(mValues, index, mValues, index + 1, rightSegment); 114f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 115f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 116f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette mValues[index] = value; 117f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 118f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 119f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 120f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Adds the values in the specified array to this array. 121f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 122f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public void addAll(LongArray values) { 123f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette final int count = values.mSize; 124f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette ensureCapacity(count); 125f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 126db24d142f5202c79128d98cd031be8c34c0731f7Alan Viverette System.arraycopy(values.mValues, 0, mValues, mSize, count); 127f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette mSize += count; 128f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 129f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 130f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 131f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Ensures capacity to append at least <code>count</code> values. 132f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 133f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette private void ensureCapacity(int count) { 134f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette final int currentSize = mSize; 135f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette final int minCapacity = currentSize + count; 136f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette if (minCapacity >= mValues.length) { 137f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette final int targetCap = currentSize + (currentSize < (MIN_CAPACITY_INCREMENT / 2) ? 138f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette MIN_CAPACITY_INCREMENT : currentSize >> 1); 139f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette final int newCapacity = targetCap > minCapacity ? targetCap : minCapacity; 140776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski final long[] newValues = ArrayUtils.newUnpaddedLongArray(newCapacity); 141f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette System.arraycopy(mValues, 0, newValues, 0, currentSize); 142f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette mValues = newValues; 143f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 144f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 145f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 146f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 147f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Removes all values from this array. 148f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 149f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public void clear() { 150f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette mSize = 0; 151f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 152f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 153f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette @Override 154f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public LongArray clone() { 155f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette LongArray clone = null; 156f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette try { 157f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette clone = (LongArray) super.clone(); 158f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette clone.mValues = mValues.clone(); 159f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } catch (CloneNotSupportedException cnse) { 160f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /* ignore */ 161f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 162f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette return clone; 163f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 164f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 165f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 166f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Returns the value at the specified position in this array. 167f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 168f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public long get(int index) { 169112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi checkBounds(index); 170f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette return mValues[index]; 171f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 172f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 173f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 174112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi * Sets the value at the specified position in this array. 175112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi */ 176112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi public void set(int index, long value) { 177112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi checkBounds(index); 178112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi mValues[index] = value; 179112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi } 180112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi 181112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi /** 182f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Returns the index of the first occurrence of the specified value in this 183f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * array, or -1 if this array does not contain the value. 184f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 185f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public int indexOf(long value) { 186f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette final int n = mSize; 187f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette for (int i = 0; i < n; i++) { 188f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette if (mValues[i] == value) { 189f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette return i; 190f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 191f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 192f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette return -1; 193f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 194f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 195f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 196f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Removes the value at the specified index from this array. 197f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 198f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public void remove(int index) { 199112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi checkBounds(index); 2008e3feb15c5aec2c72b0ef120a1da325e1e8f0ddaSvetoslav System.arraycopy(mValues, index + 1, mValues, index, mSize - index - 1); 2018e3feb15c5aec2c72b0ef120a1da325e1e8f0ddaSvetoslav mSize--; 202f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 203f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 204f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 205f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Returns the number of values in this array. 206f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 207f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public int size() { 208f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette return mSize; 209f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 210112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi 211112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi /** 212112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi * Returns a new array with the contents of this LongArray. 213112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi */ 214112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi public long[] toArray() { 215112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi return Arrays.copyOf(mValues, mSize); 216112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi } 217112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi 218112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi private void checkBounds(int index) { 219112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi if (index < 0 || mSize <= index) { 220112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi throw new ArrayIndexOutOfBoundsException(mSize, index); 221112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi } 222112962a6b09310c58093b9a8af341cbeaa612a48Hugo Benichi } 2239669e3af6500ffd1041df7c4197865a001cdc055Eugene Susla 2249669e3af6500ffd1041df7c4197865a001cdc055Eugene Susla /** 2259669e3af6500ffd1041df7c4197865a001cdc055Eugene Susla * Test if each element of {@code a} equals corresponding element from {@code b} 2269669e3af6500ffd1041df7c4197865a001cdc055Eugene Susla */ 2279669e3af6500ffd1041df7c4197865a001cdc055Eugene Susla public static boolean elementsEqual(@Nullable LongArray a, @Nullable LongArray b) { 2289669e3af6500ffd1041df7c4197865a001cdc055Eugene Susla if (a == null || b == null) return a == b; 2299669e3af6500ffd1041df7c4197865a001cdc055Eugene Susla if (a.mSize != b.mSize) return false; 2309669e3af6500ffd1041df7c4197865a001cdc055Eugene Susla for (int i = 0; i < a.mSize; i++) { 2319669e3af6500ffd1041df7c4197865a001cdc055Eugene Susla if (a.get(i) != b.get(i)) { 2329669e3af6500ffd1041df7c4197865a001cdc055Eugene Susla return false; 2339669e3af6500ffd1041df7c4197865a001cdc055Eugene Susla } 2349669e3af6500ffd1041df7c4197865a001cdc055Eugene Susla } 2359669e3af6500ffd1041df7c4197865a001cdc055Eugene Susla return true; 2369669e3af6500ffd1041df7c4197865a001cdc055Eugene Susla } 237f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette} 238