1f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 2f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Copyright (C) 2007 The Android Open Source Project 3f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 4f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 5f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * you may not use this file except in compliance with the License. 6f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * You may obtain a copy of the License at 7f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 8f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 9f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 10f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 11f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 12f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * See the License for the specific language governing permissions and 14f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * limitations under the License. 15f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 16f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 17f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpackage com.android.dx.util; 18f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 19f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.Arrays; 20f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 21f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/** 2299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Simple list of {@code int}s. 23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 24f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpublic final class IntList extends MutabilityControl { 2599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} immutable, no-element instance */ 26f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public static final IntList EMPTY = new IntList(0); 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 2899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} array of elements */ 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int[] values; 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 3199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code >= 0;} current size of the list */ 32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int size; 33f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** whether the values are currently sorted */ 35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean sorted; 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project static { 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project EMPTY.setImmutable(); 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs a new immutable instance with the given element. 43de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 44f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param value the sole value in the list 45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public static IntList makeImmutable(int value) { 47f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList result = new IntList(1); 48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(value); 50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.setImmutable(); 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 55f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 56f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs a new immutable instance with the given elements. 57de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param value0 the first value in the list 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param value1 the second value in the list 60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public static IntList makeImmutable(int value0, int value1) { 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList result = new IntList(2); 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(value0); 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(value1); 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.setImmutable(); 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs an empty instance with a default initial capacity. 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 74f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public IntList() { 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this(4); 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 78f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 79f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs an empty instance. 80de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 8199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param initialCapacity {@code >= 0;} initial capacity of the list 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public IntList(int initialCapacity) { 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project super(true); 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project values = new int[initialCapacity]; 88f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } catch (NegativeArraySizeException ex) { 89f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Translate the exception. 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalArgumentException("size < 0"); 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project size = 0; 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sorted = true; 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project @Override 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int hashCode() { 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int result = 0; 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < size; i++) { 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result = (result * 31) + values[i]; 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project @Override 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public boolean equals(Object other) { 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (other == this) { 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (! (other instanceof IntList)) { 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList otherList = (IntList) other; 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (sorted != otherList.sorted) { 123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (size != otherList.size) { 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < size; i++) { 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (values[i] != otherList.values[i]) { 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 136f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project @Override 141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public String toString() { 142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project StringBuffer sb = new StringBuffer(size * 5 + 10); 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sb.append('{'); 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < size; i++) { 147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (i != 0) { 148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sb.append(", "); 149f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sb.append(values[i]); 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sb.append('}'); 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return sb.toString(); 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the number of elements in this list. 160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int size() { 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return size; 163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 165f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 166f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the indicated value. 167de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 16899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param n {@code >= 0, < size();} which element 169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return the indicated element's value 170f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int get(int n) { 172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (n >= size) { 173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IndexOutOfBoundsException("n >= size()"); 174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return values[n]; 178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } catch (ArrayIndexOutOfBoundsException ex) { 179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Translate exception. 180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IndexOutOfBoundsException("n < 0"); 181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 184f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 185f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Sets the value at the given index. 186de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 18799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param n {@code >= 0, < size();} which element 188f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param value value to store 189f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 190f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void set(int n, int value) { 191f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throwIfImmutable(); 192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 193f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (n >= size) { 194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IndexOutOfBoundsException("n >= size()"); 195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 197f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 198f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project values[n] = value; 199f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sorted = false; 200f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } catch (ArrayIndexOutOfBoundsException ex) { 201f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Translate the exception. 202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (n < 0) { 203f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalArgumentException("n < 0"); 204f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 205f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 206f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 208f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 209f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adds an element to the end of the list. This will increase the 210f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * list's capacity if necessary. 211de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 212f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param value the value to add 213f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 214f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void add(int value) { 215f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throwIfImmutable(); 216f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 217f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project growIfNeeded(); 218f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 219f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project values[size++] = value; 220f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 221f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (sorted && (size > 1)) { 222f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sorted = (value >= values[size - 2]); 223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 224f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 225f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 227f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Inserts element into specified index, moving elements at and above 228f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * that index up one. May not be used to insert at an index beyond the 229f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * current size (that is, insertion as a last element is legal but 230f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * no further). 231f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 23299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param n {@code >= 0, <=size();} index of where to insert 233f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param value value to insert 234f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 235f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void insert(int n, int value) { 236f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (n > size) { 237f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IndexOutOfBoundsException("n > size()"); 238f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 239f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 240f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project growIfNeeded(); 241f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 242f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project System.arraycopy (values, n, values, n+1, size - n); 243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project values[n] = value; 244f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project size++; 245f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 246f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sorted = sorted 247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && (n == 0 || value > values[n-1]) 248f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && (n == (size - 1) || value < values[n+1]); 249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 251f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 252f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Removes an element at a given index, shifting elements at greater 253f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * indicies down one. 254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 25599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param n {@code >=0, < size();} index of element to remove 256f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 257f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void removeIndex(int n) { 258f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (n >= size) { 259f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IndexOutOfBoundsException("n >= size()"); 260f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 261f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 262f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project System.arraycopy (values, n + 1, values, n, size - n - 1); 263f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project size--; 264f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 265f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // sort status is unchanged 266f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 267f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 268f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 269f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Increases size of array if needed 270f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 271f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void growIfNeeded() { 272f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (size == values.length) { 273f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Resize. 274f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int[] newv = new int[size * 3 / 2 + 10]; 275f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project System.arraycopy(values, 0, newv, 0, size); 276f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project values = newv; 277f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 278f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 279f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 280f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 281f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns the last element in the array without modifying the array 282f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 283ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein * @return last value in the array 284ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein * @throws IndexOutOfBoundsException if stack is empty 285f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 286f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int top() { 287f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return get(size - 1); 288f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 289f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 290f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 291f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Pops an element off the end of the list and decreasing the size by one. 292f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 293ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein * @return value from what was the last element 294ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein * @throws IndexOutOfBoundsException if stack is empty 295f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 296f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int pop() { 297f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throwIfImmutable(); 298f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 299f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int result; 300f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 301f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result = get(size-1); 302f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project size--; 303f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 304de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro return result; 305f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 306f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 307f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 308f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Pops N elements off the end of the list and decreasing the size by N. 309f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 310ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein * @param n {@code >= 0;} number of elements to remove from end 311ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein * @throws IndexOutOfBoundsException if stack is smaller than N 312f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 313f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void pop(int n) { 314f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throwIfImmutable(); 315f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 316f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project size -= n; 317f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 318f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 319f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 320f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Shrinks the size of the list. 321de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 32299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param newSize {@code >= 0;} the new size 323f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 324f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void shrink(int newSize) { 325f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (newSize < 0) { 326f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalArgumentException("newSize < 0"); 327f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 328f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 329f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (newSize > size) { 330f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalArgumentException("newSize > size"); 331f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 332f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 333f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throwIfImmutable(); 334f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 335f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project size = newSize; 336f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 337f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 338f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 339f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Makes and returns a mutable copy of the list. 340de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 34199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} an appropriately-constructed instance 342f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 343f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public IntList mutableCopy() { 344f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = size; 345f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList result = new IntList(sz); 346f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 347f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 348f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(values[i]); 349f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 350f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 351f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 352f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 353f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 354f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 355f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Sorts the elements in the list in-place. 356f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 357f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void sort() { 358f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throwIfImmutable(); 359f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 360f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!sorted) { 361f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Arrays.sort(values, 0, size); 362f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sorted = true; 363f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 364f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 365f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 366f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 367f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns the index of the given value, or -1 if the value does not 368f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * appear in the list. This will do a binary search if the list is 369f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * sorted or a linear search if not. 370ccf5cff3faefcf1d44d0ebc141a1f7e7dcee3c62Dan Bornstein * 371f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param value value to find 372f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return index of value or -1 373f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 374f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int indexOf(int value) { 375f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ret = binarysearch(value); 376f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 377f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return ret >= 0 ? ret : -1; 378f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 379f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 380f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 381f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 382f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Performs a binary search on a sorted list, returning the index of 383f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the given value if it is present or 38499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code (-(insertion point) - 1)} if the value is not present. 385f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If the list is not sorted, then reverts to linear search and returns 38699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code -size()} if the element is not found. 387f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 388f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param value value to find 38999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return index of value or {@code (-(insertion point) - 1)} if the 390f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * value is not present 391f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 392f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int binarysearch(int value) { 393f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = size; 394f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 395f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!sorted) { 396f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Linear search. 397f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 398f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (values[i] == value) { 399f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return i; 400f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 401f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 402f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 403f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return -sz; 404f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 405f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 406f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 407f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Binary search. This variant does only one value comparison 408f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * per iteration but does one more iteration on average than 409f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the variant that includes a value equality check per 410f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * iteration. 411f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 412f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 413f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int min = -1; 414f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int max = sz; 415f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 416f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (max > (min + 1)) { 417f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 418f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The guessIdx calculation is equivalent to ((min + max) 419f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * / 2) but won't go wonky when min and max are close to 420f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Integer.MAX_VALUE. 421f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 422f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int guessIdx = min + ((max - min) >> 1); 423f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int guess = values[guessIdx]; 424f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 425f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (value <= guess) { 426f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project max = guessIdx; 427f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 428f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project min = guessIdx; 429f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 430f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 431f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 432f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if ((max != sz)) { 433f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return (value == values[max]) ? max : (-max - 1); 434f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 435f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return -sz - 1; 436f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 437f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 438f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 439f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 440f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 441f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns whether or not the given value appears in the list. 442f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * This will do a binary search if the list is sorted or a linear 443f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * search if not. 444de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 445f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @see #sort 446de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 447f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param value value to look for 448f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return whether the list contains the given value 449f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 450f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public boolean contains(int value) { 451f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return indexOf(value) >= 0; 452f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 453f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 454