1579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/* 2579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Copyright (C) 2007 The Android Open Source Project 3579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 4579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * you may not use this file except in compliance with the License. 6579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * You may obtain a copy of the License at 7579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 8579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 10579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * See the License for the specific language governing permissions and 14579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * limitations under the License. 15579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 16579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 17579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpackage com.android.dx.util; 18579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 19579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.Arrays; 20579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 21579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/** 22579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Simple list of {@code int}s. 23579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 24579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpublic final class IntList extends MutabilityControl { 25579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@code non-null;} immutable, no-element instance */ 26579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static final IntList EMPTY = new IntList(0); 27579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 28579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@code non-null;} array of elements */ 29579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private int[] values; 30579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 31579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@code >= 0;} current size of the list */ 32579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private int size; 33579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 34579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** whether the values are currently sorted */ 35579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private boolean sorted; 36579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 37579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson static { 38579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson EMPTY.setImmutable(); 39579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 40579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 41579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 42579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Constructs a new immutable instance with the given element. 43579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 44579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param value the sole value in the list 45579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 46579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static IntList makeImmutable(int value) { 47579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson IntList result = new IntList(1); 48579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 49579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result.add(value); 50579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result.setImmutable(); 51579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 52579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return result; 53579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 54579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 55579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 56579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Constructs a new immutable instance with the given elements. 57579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 58579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param value0 the first value in the list 59579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param value1 the second value in the list 60579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 61579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static IntList makeImmutable(int value0, int value1) { 62579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson IntList result = new IntList(2); 63579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 64579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result.add(value0); 65579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result.add(value1); 66579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result.setImmutable(); 67579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 68579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return result; 69579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 70579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 71579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 72579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Constructs an empty instance with a default initial capacity. 73579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 74579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public IntList() { 75579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this(4); 76579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 77579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 78579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 79579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Constructs an empty instance. 80579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 81579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param initialCapacity {@code >= 0;} initial capacity of the list 82579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 83579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public IntList(int initialCapacity) { 84579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson super(true); 85579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 86579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson try { 87579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson values = new int[initialCapacity]; 88579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } catch (NegativeArraySizeException ex) { 89579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Translate the exception. 90579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new IllegalArgumentException("size < 0"); 91579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 92579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 93579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson size = 0; 94579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sorted = true; 95579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 96579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 97579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@inheritDoc} */ 98579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson @Override 99579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public int hashCode() { 100579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int result = 0; 101579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 102579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < size; i++) { 103579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result = (result * 31) + values[i]; 104579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 105579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 106579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return result; 107579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 108579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 109579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@inheritDoc} */ 110579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson @Override 111579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public boolean equals(Object other) { 112579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (other == this) { 113579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return true; 114579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 115579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 116579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (! (other instanceof IntList)) { 117579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return false; 118579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 119579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 120579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson IntList otherList = (IntList) other; 121579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 122579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (sorted != otherList.sorted) { 123579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return false; 124579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 125579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 126579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (size != otherList.size) { 127579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return false; 128579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 129579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 130579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < size; i++) { 131579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (values[i] != otherList.values[i]) { 132579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return false; 133579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 134579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 135579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 136579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return true; 137579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 138579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 139579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@inheritDoc} */ 140579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson @Override 141579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public String toString() { 142579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson StringBuffer sb = new StringBuffer(size * 5 + 10); 143579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 144579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append('{'); 145579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 146579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < size; i++) { 147579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (i != 0) { 148579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append(", "); 149579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 150579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append(values[i]); 151579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 152579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 153579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sb.append('}'); 154579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 155579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return sb.toString(); 156579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 157579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 158579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 159579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Gets the number of elements in this list. 160579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 161579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public int size() { 162579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return size; 163579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 164579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 165579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 166579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Gets the indicated value. 167579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 168579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param n {@code >= 0, < size();} which element 169579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return the indicated element's value 170579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 171579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public int get(int n) { 172579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (n >= size) { 173579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new IndexOutOfBoundsException("n >= size()"); 174579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 175579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 176579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson try { 177579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return values[n]; 178579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } catch (ArrayIndexOutOfBoundsException ex) { 179579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Translate exception. 180579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new IndexOutOfBoundsException("n < 0"); 181579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 182579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 183579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 184579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 185579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Sets the value at the given index. 186579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 187579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param n {@code >= 0, < size();} which element 188579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param value value to store 189579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 190579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void set(int n, int value) { 191579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throwIfImmutable(); 192579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 193579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (n >= size) { 194579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new IndexOutOfBoundsException("n >= size()"); 195579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 196579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 197579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson try { 198579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson values[n] = value; 199579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sorted = false; 200579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } catch (ArrayIndexOutOfBoundsException ex) { 201579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Translate the exception. 202579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (n < 0) { 203579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new IllegalArgumentException("n < 0"); 204579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 205579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 206579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 207579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 208579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 209579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Adds an element to the end of the list. This will increase the 210579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * list's capacity if necessary. 211579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 212579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param value the value to add 213579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 214579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void add(int value) { 215579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throwIfImmutable(); 216579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 217579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson growIfNeeded(); 218579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 219579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson values[size++] = value; 220579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 221579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (sorted && (size > 1)) { 222579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sorted = (value >= values[size - 2]); 223579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 224579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 225579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 226579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 227579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Inserts element into specified index, moving elements at and above 228579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * that index up one. May not be used to insert at an index beyond the 229579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * current size (that is, insertion as a last element is legal but 230579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * no further). 231579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 232579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param n {@code >= 0, <=size();} index of where to insert 233579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param value value to insert 234579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 235579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void insert(int n, int value) { 236579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (n > size) { 237579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new IndexOutOfBoundsException("n > size()"); 238579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 239579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 240579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson growIfNeeded(); 241579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 242579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson System.arraycopy (values, n, values, n+1, size - n); 243579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson values[n] = value; 244579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson size++; 245579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 246579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sorted = sorted 247579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson && (n == 0 || value > values[n-1]) 248579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson && (n == (size - 1) || value < values[n+1]); 249579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 250579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 251579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 252579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Removes an element at a given index, shifting elements at greater 253579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * indicies down one. 254579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 255579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param n {@code >=0, < size();} index of element to remove 256579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 257579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void removeIndex(int n) { 258579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (n >= size) { 259579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new IndexOutOfBoundsException("n >= size()"); 260579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 261579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 262579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson System.arraycopy (values, n + 1, values, n, size - n - 1); 263579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson size--; 264579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 265579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // sort status is unchanged 266579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 267579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 268579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 269579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Increases size of array if needed 270579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 271579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void growIfNeeded() { 272579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (size == values.length) { 273579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Resize. 274579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int[] newv = new int[size * 3 / 2 + 10]; 275579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson System.arraycopy(values, 0, newv, 0, size); 276579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson values = newv; 277579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 278579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 279579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 280579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 281579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Returns the last element in the array without modifying the array 282579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 283579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return last value in the array 284579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @throws IndexOutOfBoundsException if stack is empty 285579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 286579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public int top() { 287579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return get(size - 1); 288579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 289579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 290579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 291579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Pops an element off the end of the list and decreasing the size by one. 292579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 293579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return value from what was the last element 294579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @throws IndexOutOfBoundsException if stack is empty 295579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 296579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public int pop() { 297579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throwIfImmutable(); 298579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 299579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int result; 300579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 301579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result = get(size-1); 302579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson size--; 303579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 304579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return result; 305579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 306579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 307579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 308579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Pops N elements off the end of the list and decreasing the size by N. 309579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 310579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param n {@code >= 0;} number of elements to remove from end 311579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @throws IndexOutOfBoundsException if stack is smaller than N 312579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 313579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void pop(int n) { 314579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throwIfImmutable(); 315579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 316579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson size -= n; 317579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 318579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 319579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 320579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Shrinks the size of the list. 321579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 322579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param newSize {@code >= 0;} the new size 323579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 324579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void shrink(int newSize) { 325579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (newSize < 0) { 326579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new IllegalArgumentException("newSize < 0"); 327579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 328579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 329579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (newSize > size) { 330579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new IllegalArgumentException("newSize > size"); 331579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 332579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 333579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throwIfImmutable(); 334579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 335579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson size = newSize; 336579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 337579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 338579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 339579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Makes and returns a mutable copy of the list. 340579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 341579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} an appropriately-constructed instance 342579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 343579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public IntList mutableCopy() { 344579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int sz = size; 345579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson IntList result = new IntList(sz); 346579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 347579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < sz; i++) { 348579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result.add(values[i]); 349579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 350579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 351579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return result; 352579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 353579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 354579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 355579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Sorts the elements in the list in-place. 356579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 357579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public void sort() { 358579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throwIfImmutable(); 359579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 360579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (!sorted) { 361579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson Arrays.sort(values, 0, size); 362579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson sorted = true; 363579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 364579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 365579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 366579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 367579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Returns the index of the given value, or -1 if the value does not 368579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * appear in the list. This will do a binary search if the list is 369579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * sorted or a linear search if not. 370579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 371579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param value value to find 372579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return index of value or -1 373579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 374579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public int indexOf(int value) { 375579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int ret = binarysearch(value); 376579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 377579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return ret >= 0 ? ret : -1; 378579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 379579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 380579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 381579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 382579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Performs a binary search on a sorted list, returning the index of 383579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * the given value if it is present or 384579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * {@code (-(insertion point) - 1)} if the value is not present. 385579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * If the list is not sorted, then reverts to linear search and returns 386579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * {@code -size()} if the element is not found. 387579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 388579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param value value to find 389579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return index of value or {@code (-(insertion point) - 1)} if the 390579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * value is not present 391579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 392579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public int binarysearch(int value) { 393579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int sz = size; 394579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 395579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (!sorted) { 396579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Linear search. 397579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < sz; i++) { 398579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (values[i] == value) { 399579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return i; 400579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 401579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 402579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 403579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return -sz; 404579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 405579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 406579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 407579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Binary search. This variant does only one value comparison 408579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * per iteration but does one more iteration on average than 409579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * the variant that includes a value equality check per 410579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * iteration. 411579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 412579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 413579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int min = -1; 414579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int max = sz; 415579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 416579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson while (max > (min + 1)) { 417579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 418579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * The guessIdx calculation is equivalent to ((min + max) 419579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * / 2) but won't go wonky when min and max are close to 420579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Integer.MAX_VALUE. 421579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 422579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int guessIdx = min + ((max - min) >> 1); 423579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int guess = values[guessIdx]; 424579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 425579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (value <= guess) { 426579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson max = guessIdx; 427579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 428579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson min = guessIdx; 429579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 430579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 431579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 432579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if ((max != sz)) { 433579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return (value == values[max]) ? max : (-max - 1); 434579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 435579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return -sz - 1; 436579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 437579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 438579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 439579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 440579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 441579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Returns whether or not the given value appears in the list. 442579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * This will do a binary search if the list is sorted or a linear 443579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * search if not. 444579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 445579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @see #sort 446579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 447579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param value value to look for 448579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return whether the list contains the given value 449579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 450579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public boolean contains(int value) { 451579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return indexOf(value) >= 0; 452579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 453579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson} 454