LongArray.java revision f0aed09ed8153043e40b3ac99788d47ba0831306
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; 20f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 21f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette/** 22f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Implements a growing array of long primitives. 23f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * 24f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * @hide 25f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 26f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverettepublic class LongArray implements Cloneable { 27f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette private static final int MIN_CAPACITY_INCREMENT = 12; 28f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 29f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette private long[] mValues; 30f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette private int mSize; 31f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 32f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 33f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Creates an empty LongArray with the default initial capacity. 34f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 35f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public LongArray() { 36f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette this(10); 37f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 38f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 39f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 40f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Creates an empty LongArray with the specified initial capacity. 41f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 42f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public LongArray(int initialCapacity) { 43f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette if (initialCapacity == 0) { 44f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette mValues = ContainerHelpers.EMPTY_LONGS; 45f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } else { 46f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity); 47f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette mValues = new long[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 86f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette System.arraycopy(mValues, mSize, values.mValues, 0, 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; 100f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette final long[] newValues = new long[ArrayUtils.idealLongArraySize(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 @SuppressWarnings("unchecked") 115f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public LongArray clone() { 116f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette LongArray clone = null; 117f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette try { 118f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette clone = (LongArray) super.clone(); 119f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette clone.mValues = mValues.clone(); 120f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } catch (CloneNotSupportedException cnse) { 121f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /* ignore */ 122f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 123f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette return clone; 124f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 125f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 126f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 127f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Returns the value at the specified position in this array. 128f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 129f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public long get(int index) { 130f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette return mValues[index]; 131f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 132f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 133f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 134f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Returns the index of the first occurrence of the specified value in this 135f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * array, or -1 if this array does not contain the value. 136f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 137f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public int indexOf(long value) { 138f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette final int n = mSize; 139f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette for (int i = 0; i < n; i++) { 140f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette if (mValues[i] == value) { 141f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette return i; 142f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 143f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 144f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette return -1; 145f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 146f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 147f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 148f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Removes the value at the specified index from this array. 149f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 150f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public void remove(int index) { 151f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette System.arraycopy(mValues, index, mValues, index + 1, mSize - index); 152f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 153f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette 154f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette /** 155f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette * Returns the number of values in this array. 156f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette */ 157f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette public int size() { 158f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette return mSize; 159f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette } 160f0aed09ed8153043e40b3ac99788d47ba0831306Alan Viverette} 161