1ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette/* 2ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * Copyright (C) 2014 The Android Open Source Project 3ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * 4ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * Licensed under the Apache License, Version 2.0 (the "License"); 5ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * you may not use this file except in compliance with the License. 6ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * You may obtain a copy of the License at 7ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * 8ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * http://www.apache.org/licenses/LICENSE-2.0 9ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * 10ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * Unless required by applicable law or agreed to in writing, software 11ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * distributed under the License is distributed on an "AS IS" BASIS, 12ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * See the License for the specific language governing permissions and 14ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * limitations under the License. 15ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette */ 16ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette 17ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverettepackage android.util; 18ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette 19ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viveretteimport com.android.internal.util.ArrayUtils; 20ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette 21ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viveretteimport libcore.util.EmptyArray; 22ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette 23ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette/** 24ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * Implements a growing array of int primitives. 25ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * 26ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * @hide 27ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette */ 28ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverettepublic class IntArray implements Cloneable { 29ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette private static final int MIN_CAPACITY_INCREMENT = 12; 30ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette 31ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette private int[] mValues; 32ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette private int mSize; 33ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette 34ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette /** 35ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * Creates an empty IntArray with the default initial capacity. 36ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette */ 37ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette public IntArray() { 38ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette this(10); 39ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette } 40ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette 41ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette /** 42ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * Creates an empty IntArray with the specified initial capacity. 43ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette */ 44ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette public IntArray(int initialCapacity) { 45ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette if (initialCapacity == 0) { 46ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette mValues = EmptyArray.INT; 47ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette } else { 48ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette mValues = ArrayUtils.newUnpaddedIntArray(initialCapacity); 49ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette } 50ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette mSize = 0; 51ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette } 52ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette 53ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette /** 54ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * Appends the specified value to the end of this array. 55ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette */ 56ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette public void add(int value) { 57ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette add(mSize, value); 58ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette } 59ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette 60ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette /** 61ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * Inserts a value at the specified position in this array. 62ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * 63ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * @throws IndexOutOfBoundsException when index < 0 || index > size() 64ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette */ 65ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette public void add(int index, int value) { 66ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette if (index < 0 || index > mSize) { 67ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette throw new IndexOutOfBoundsException(); 68ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette } 69ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette 70ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette ensureCapacity(1); 71ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette 72ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette if (mSize - index != 0) { 73ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette System.arraycopy(mValues, index, mValues, index + 1, mSize - index); 74ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette } 75ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette 76ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette mValues[index] = value; 77ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette mSize++; 78ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette } 79ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette 80ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette /** 81ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * Adds the values in the specified array to this array. 82ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette */ 83ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette public void addAll(IntArray values) { 84ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette final int count = values.mSize; 85ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette ensureCapacity(count); 86ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette 87ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette System.arraycopy(values.mValues, 0, mValues, mSize, count); 88ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette mSize += count; 89ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette } 90ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette 91ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette /** 92ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * Ensures capacity to append at least <code>count</code> values. 93ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette */ 94ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette private void ensureCapacity(int count) { 95ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette final int currentSize = mSize; 96ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette final int minCapacity = currentSize + count; 97ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette if (minCapacity >= mValues.length) { 98ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette final int targetCap = currentSize + (currentSize < (MIN_CAPACITY_INCREMENT / 2) ? 99ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette MIN_CAPACITY_INCREMENT : currentSize >> 1); 100ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette final int newCapacity = targetCap > minCapacity ? targetCap : minCapacity; 101ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette final int[] newValues = ArrayUtils.newUnpaddedIntArray(newCapacity); 102ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette System.arraycopy(mValues, 0, newValues, 0, currentSize); 103ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette mValues = newValues; 104ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette } 105ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette } 106ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette 107ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette /** 108ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * Removes all values from this array. 109ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette */ 110ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette public void clear() { 111ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette mSize = 0; 112ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette } 113ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette 114ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette @Override 115ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette public IntArray clone() throws CloneNotSupportedException { 116ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette final IntArray clone = (IntArray) super.clone(); 117ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette clone.mValues = mValues.clone(); 118ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette return clone; 119ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette } 120ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette 121ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette /** 122ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * Returns the value at the specified position in this array. 123ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette */ 124ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette public int get(int index) { 125ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette if (index >= mSize) { 126ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette throw new ArrayIndexOutOfBoundsException(mSize, index); 127ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette } 128ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette return mValues[index]; 129ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette } 130ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette 131ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette /** 132ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * Returns the index of the first occurrence of the specified value in this 133ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * array, or -1 if this array does not contain the value. 134ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette */ 135ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette public int indexOf(int value) { 136ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette final int n = mSize; 137ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette for (int i = 0; i < n; i++) { 138ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette if (mValues[i] == value) { 139ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette return i; 140ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette } 141ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette } 142ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette return -1; 143ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette } 144ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette 145ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette /** 146ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * Removes the value at the specified index from this array. 147ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette */ 148ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette public void remove(int index) { 149ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette if (index >= mSize) { 150ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette throw new ArrayIndexOutOfBoundsException(mSize, index); 151ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette } 152ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette System.arraycopy(mValues, index + 1, mValues, index, mSize - index - 1); 153ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette mSize--; 154ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette } 155ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette 156ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette /** 157ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette * Returns the number of values in this array. 158ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette */ 159ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette public int size() { 160ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette return mSize; 161ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette } 162ffb46bf2956d89e3190007ccf2ef3ce3eed005feAlan Viverette} 163