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