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 19f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viveretteimport com.android.internal.util.ArrayUtils; 20776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinskiimport libcore.util.EmptyArray; 21f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 22f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette/** 23f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Implements a growing array of long primitives. 24f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * 25f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * @hide 26f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 27f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverettepublic class LongArray implements Cloneable { 28f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette private static final int MIN_CAPACITY_INCREMENT = 12; 29f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 30f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette private long[] mValues; 31f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette private int mSize; 32f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 33f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 34f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Creates an empty LongArray with the default initial capacity. 35f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 36f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public LongArray() { 37f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette this(10); 38f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 39f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 40f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 41f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Creates an empty LongArray with the specified initial capacity. 42f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 43f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public LongArray(int initialCapacity) { 44f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette if (initialCapacity == 0) { 45776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mValues = EmptyArray.LONG; 46f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } else { 47776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mValues = ArrayUtils.newUnpaddedLongArray(initialCapacity); 48f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 49f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette mSize = 0; 50f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 51f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 52f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 53f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Appends the specified value to the end of this array. 54f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 55f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public void add(long value) { 56f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette add(mSize, value); 57f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 58f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 59f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 60f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Inserts a value at the specified position in this array. 61f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * 62f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * @throws IndexOutOfBoundsException when index < 0 || index > size() 63f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 64f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public void add(int index, long value) { 65f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette if (index < 0 || index > mSize) { 66f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette throw new IndexOutOfBoundsException(); 67f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 68f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 69f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette ensureCapacity(1); 70f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 71f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette if (mSize - index != 0) { 72f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette System.arraycopy(mValues, index, mValues, index + 1, mSize - index); 73f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 74f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 75f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette mValues[index] = value; 76f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette mSize++; 77f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 78f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 79f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 80f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Adds the values in the specified array to this array. 81f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 82f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public void addAll(LongArray values) { 83f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette final int count = values.mSize; 84f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette ensureCapacity(count); 85f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 86db24d142f5202c79128d98cd031be8c34c0731f7Alan Viverette System.arraycopy(values.mValues, 0, mValues, mSize, count); 87f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette mSize += count; 88f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 89f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 90f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 91f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Ensures capacity to append at least <code>count</code> values. 92f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 93f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette private void ensureCapacity(int count) { 94f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette final int currentSize = mSize; 95f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette final int minCapacity = currentSize + count; 96f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette if (minCapacity >= mValues.length) { 97f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette final int targetCap = currentSize + (currentSize < (MIN_CAPACITY_INCREMENT / 2) ? 98f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette MIN_CAPACITY_INCREMENT : currentSize >> 1); 99f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette final int newCapacity = targetCap > minCapacity ? targetCap : minCapacity; 100776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski final long[] newValues = ArrayUtils.newUnpaddedLongArray(newCapacity); 101f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette System.arraycopy(mValues, 0, newValues, 0, currentSize); 102f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette mValues = newValues; 103f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 104f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 105f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 106f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 107f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Removes all values from this array. 108f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 109f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public void clear() { 110f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette mSize = 0; 111f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 112f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 113f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette @Override 114f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public LongArray clone() { 115f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette LongArray clone = null; 116f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette try { 117f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette clone = (LongArray) super.clone(); 118f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette clone.mValues = mValues.clone(); 119f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } catch (CloneNotSupportedException cnse) { 120f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /* ignore */ 121f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 122f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette return clone; 123f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 124f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 125f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 126f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Returns the value at the specified position in this array. 127f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 128f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public long get(int index) { 129db24d142f5202c79128d98cd031be8c34c0731f7Alan Viverette if (index >= mSize) { 130db24d142f5202c79128d98cd031be8c34c0731f7Alan Viverette throw new ArrayIndexOutOfBoundsException(mSize, index); 131db24d142f5202c79128d98cd031be8c34c0731f7Alan Viverette } 132f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette return mValues[index]; 133f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 134f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 135f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 136f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Returns the index of the first occurrence of the specified value in this 137f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * array, or -1 if this array does not contain the value. 138f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 139f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public int indexOf(long value) { 140f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette final int n = mSize; 141f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette for (int i = 0; i < n; i++) { 142f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette if (mValues[i] == value) { 143f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette return i; 144f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 145f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 146f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette return -1; 147f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 148f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 149f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 150f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Removes the value at the specified index from this array. 151f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 152f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public void remove(int index) { 153db24d142f5202c79128d98cd031be8c34c0731f7Alan Viverette if (index >= mSize) { 154db24d142f5202c79128d98cd031be8c34c0731f7Alan Viverette throw new ArrayIndexOutOfBoundsException(mSize, index); 155db24d142f5202c79128d98cd031be8c34c0731f7Alan Viverette } 1568e3feb15c5aec2c72b0ef120a1da325e1e8f0ddaSvetoslav System.arraycopy(mValues, index + 1, mValues, index, mSize - index - 1); 1578e3feb15c5aec2c72b0ef120a1da325e1e8f0ddaSvetoslav mSize--; 158f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 159f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 160f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 161f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Returns the number of values in this array. 162f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 163f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public int size() { 164f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette return mSize; 165f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 166f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette} 167