1917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul/* 2917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Copyright (C) 2007 The Android Open Source Project 3917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 4917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Licensed under the Apache License, Version 2.0 (the "License"); 5917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * you may not use this file except in compliance with the License. 6917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * You may obtain a copy of the License at 7917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 8917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * http://www.apache.org/licenses/LICENSE-2.0 9917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 10917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Unless required by applicable law or agreed to in writing, software 11917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * distributed under the License is distributed on an "AS IS" BASIS, 12917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * See the License for the specific language governing permissions and 14917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * limitations under the License. 15917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 16917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 17917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgulpackage com.android.dexgen.util; 18917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 19917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgulimport java.util.Arrays; 20917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 21917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul/** 22917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Simple list of {@code int}s. 23917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 24917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgulpublic final class IntList extends MutabilityControl { 25917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** {@code non-null;} immutable, no-element instance */ 26917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public static final IntList EMPTY = new IntList(0); 27917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 28917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** {@code non-null;} array of elements */ 29917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul private int[] values; 30917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 31917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** {@code >= 0;} current size of the list */ 32917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul private int size; 33917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 34917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** whether the values are currently sorted */ 35917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul private boolean sorted; 36917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 37917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul static { 38917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul EMPTY.setImmutable(); 39917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 40917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 41917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 42917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Constructs a new immutable instance with the given element. 43917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 44917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param value the sole value in the list 45917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 46917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public static IntList makeImmutable(int value) { 47917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul IntList result = new IntList(1); 48917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 49917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul result.add(value); 50917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul result.setImmutable(); 51917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 52917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return result; 53917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 54917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 55917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 56917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Constructs a new immutable instance with the given elements. 57917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 58917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param value0 the first value in the list 59917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param value1 the second value in the list 60917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 61917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public static IntList makeImmutable(int value0, int value1) { 62917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul IntList result = new IntList(2); 63917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 64917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul result.add(value0); 65917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul result.add(value1); 66917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul result.setImmutable(); 67917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 68917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return result; 69917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 70917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 71917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 72917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Constructs an empty instance with a default initial capacity. 73917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 74917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public IntList() { 75917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul this(4); 76917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 77917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 78917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 79917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Constructs an empty instance. 80917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 81917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param initialCapacity {@code >= 0;} initial capacity of the list 82917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 83917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public IntList(int initialCapacity) { 84917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul super(true); 85917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 86917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul try { 87917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul values = new int[initialCapacity]; 88917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } catch (NegativeArraySizeException ex) { 89917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul // Translate the exception. 90917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul throw new IllegalArgumentException("size < 0"); 91917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 92917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 93917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul size = 0; 94917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul sorted = true; 95917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 96917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 97917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** {@inheritDoc} */ 98917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul @Override 99917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public int hashCode() { 100917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int result = 0; 101917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 102917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul for (int i = 0; i < size; i++) { 103917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul result = (result * 31) + values[i]; 104917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 105917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 106917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return result; 107917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 108917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 109917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** {@inheritDoc} */ 110917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul @Override 111917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public boolean equals(Object other) { 112917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (other == this) { 113917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return true; 114917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 115917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 116917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (! (other instanceof IntList)) { 117917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return false; 118917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 119917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 120917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul IntList otherList = (IntList) other; 121917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 122917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (sorted != otherList.sorted) { 123917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return false; 124917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 125917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 126917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (size != otherList.size) { 127917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return false; 128917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 129917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 130917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul for (int i = 0; i < size; i++) { 131917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (values[i] != otherList.values[i]) { 132917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return false; 133917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 134917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 135917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 136917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return true; 137917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 138917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 139917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** {@inheritDoc} */ 140917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul @Override 141917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public String toString() { 142917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul StringBuffer sb = new StringBuffer(size * 5 + 10); 143917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 144917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul sb.append('{'); 145917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 146917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul for (int i = 0; i < size; i++) { 147917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (i != 0) { 148917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul sb.append(", "); 149917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 150917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul sb.append(values[i]); 151917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 152917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 153917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul sb.append('}'); 154917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 155917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return sb.toString(); 156917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 157917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 158917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 159917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Gets the number of elements in this list. 160917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 161917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public int size() { 162917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return size; 163917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 164917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 165917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 166917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Gets the indicated value. 167917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 168917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param n {@code >= 0, < size();} which element 169917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @return the indicated element's value 170917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 171917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public int get(int n) { 172917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (n >= size) { 173917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul throw new IndexOutOfBoundsException("n >= size()"); 174917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 175917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 176917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul try { 177917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return values[n]; 178917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } catch (ArrayIndexOutOfBoundsException ex) { 179917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul // Translate exception. 180917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul throw new IndexOutOfBoundsException("n < 0"); 181917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 182917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 183917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 184917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 185917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Sets the value at the given index. 186917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 187917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param n {@code >= 0, < size();} which element 188917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param value value to store 189917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 190917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public void set(int n, int value) { 191917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul throwIfImmutable(); 192917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 193917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (n >= size) { 194917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul throw new IndexOutOfBoundsException("n >= size()"); 195917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 196917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 197917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul try { 198917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul values[n] = value; 199917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul sorted = false; 200917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } catch (ArrayIndexOutOfBoundsException ex) { 201917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul // Translate the exception. 202917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (n < 0) { 203917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul throw new IllegalArgumentException("n < 0"); 204917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 205917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 206917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 207917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 208917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 209917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Adds an element to the end of the list. This will increase the 210917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * list's capacity if necessary. 211917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 212917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param value the value to add 213917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 214917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public void add(int value) { 215917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul throwIfImmutable(); 216917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 217917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul growIfNeeded(); 218917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 219917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul values[size++] = value; 220917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 221917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (sorted && (size > 1)) { 222917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul sorted = (value >= values[size - 2]); 223917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 224917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 225917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 226917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 227917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Inserts element into specified index, moving elements at and above 228917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * that index up one. May not be used to insert at an index beyond the 229917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * current size (that is, insertion as a last element is legal but 230917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * no further). 231917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 232917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param n {@code >= 0, <=size();} index of where to insert 233917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param value value to insert 234917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 235917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public void insert(int n, int value) { 236917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (n > size) { 237917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul throw new IndexOutOfBoundsException("n > size()"); 238917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 239917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 240917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul growIfNeeded(); 241917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 242917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul System.arraycopy (values, n, values, n+1, size - n); 243917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul values[n] = value; 244917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul size++; 245917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 246917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul sorted = sorted 247917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul && (n == 0 || value > values[n-1]) 248917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul && (n == (size - 1) || value < values[n+1]); 249917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 250917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 251917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 252917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Removes an element at a given index, shifting elements at greater 253917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * indicies down one. 254917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 255917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param n {@code >=0, < size();} index of element to remove 256917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 257917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public void removeIndex(int n) { 258917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (n >= size) { 259917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul throw new IndexOutOfBoundsException("n >= size()"); 260917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 261917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 262917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul System.arraycopy (values, n + 1, values, n, size - n - 1); 263917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul size--; 264917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 265917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul // sort status is unchanged 266917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 267917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 268917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 269917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Increases size of array if needed 270917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 271917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul private void growIfNeeded() { 272917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (size == values.length) { 273917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul // Resize. 274917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int[] newv = new int[size * 3 / 2 + 10]; 275917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul System.arraycopy(values, 0, newv, 0, size); 276917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul values = newv; 277917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 278917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 279917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 280917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 281917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Returns the last element in the array without modifying the array 282917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 283917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @return last value in the array. 284917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @exception IndexOutOfBoundsException if stack is empty. 285917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 286917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public int top() { 287917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return get(size - 1); 288917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 289917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 290917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 291917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Pops an element off the end of the list and decreasing the size by one. 292917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 293917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @return value from what was the last element. 294917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @exception IndexOutOfBoundsException if stack is empty. 295917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 296917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public int pop() { 297917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul throwIfImmutable(); 298917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 299917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int result; 300917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 301917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul result = get(size-1); 302917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul size--; 303917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 304917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return result; 305917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 306917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 307917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 308917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Pops N elements off the end of the list and decreasing the size by N. 309917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 310917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param n {@code >= 0;} number of elements to remove from end. 311917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @exception IndexOutOfBoundsException if stack is smaller than N 312917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 313917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public void pop(int n) { 314917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul throwIfImmutable(); 315917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 316917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul size -= n; 317917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 318917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 319917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 320917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Shrinks the size of the list. 321917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 322917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param newSize {@code >= 0;} the new size 323917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 324917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public void shrink(int newSize) { 325917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (newSize < 0) { 326917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul throw new IllegalArgumentException("newSize < 0"); 327917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 328917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 329917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (newSize > size) { 330917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul throw new IllegalArgumentException("newSize > size"); 331917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 332917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 333917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul throwIfImmutable(); 334917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 335917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul size = newSize; 336917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 337917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 338917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 339917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Makes and returns a mutable copy of the list. 340917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 341917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @return {@code non-null;} an appropriately-constructed instance 342917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 343917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public IntList mutableCopy() { 344917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int sz = size; 345917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul IntList result = new IntList(sz); 346917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 347917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul for (int i = 0; i < sz; i++) { 348917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul result.add(values[i]); 349917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 350917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 351917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return result; 352917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 353917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 354917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 355917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Sorts the elements in the list in-place. 356917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 357917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public void sort() { 358917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul throwIfImmutable(); 359917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 360917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (!sorted) { 361917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul Arrays.sort(values, 0, size); 362917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul sorted = true; 363917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 364917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 365917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 366917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 367917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Returns the index of the given value, or -1 if the value does not 368917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * appear in the list. This will do a binary search if the list is 369917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * sorted or a linear search if not. 370917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param value value to find 371917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @return index of value or -1 372917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 373917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public int indexOf(int value) { 374917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int ret = binarysearch(value); 375917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 376917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return ret >= 0 ? ret : -1; 377917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 378917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 379917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 380917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 381917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Performs a binary search on a sorted list, returning the index of 382917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * the given value if it is present or 383917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * {@code (-(insertion point) - 1)} if the value is not present. 384917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * If the list is not sorted, then reverts to linear search and returns 385917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * {@code -size()} if the element is not found. 386917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 387917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param value value to find 388917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @return index of value or {@code (-(insertion point) - 1)} if the 389917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * value is not present 390917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 391917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public int binarysearch(int value) { 392917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int sz = size; 393917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 394917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (!sorted) { 395917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul // Linear search. 396917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul for (int i = 0; i < sz; i++) { 397917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (values[i] == value) { 398917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return i; 399917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 400917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 401917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 402917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return -sz; 403917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 404917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 405917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /* 406917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Binary search. This variant does only one value comparison 407917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * per iteration but does one more iteration on average than 408917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * the variant that includes a value equality check per 409917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * iteration. 410917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 411917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 412917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int min = -1; 413917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int max = sz; 414917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 415917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul while (max > (min + 1)) { 416917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /* 417917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * The guessIdx calculation is equivalent to ((min + max) 418917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * / 2) but won't go wonky when min and max are close to 419917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Integer.MAX_VALUE. 420917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 421917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int guessIdx = min + ((max - min) >> 1); 422917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int guess = values[guessIdx]; 423917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 424917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (value <= guess) { 425917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul max = guessIdx; 426917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } else { 427917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul min = guessIdx; 428917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 429917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 430917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 431917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if ((max != sz)) { 432917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return (value == values[max]) ? max : (-max - 1); 433917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } else { 434917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return -sz - 1; 435917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 436917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 437917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 438917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 439917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 440917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Returns whether or not the given value appears in the list. 441917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * This will do a binary search if the list is sorted or a linear 442917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * search if not. 443917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 444917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @see #sort 445917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 446917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param value value to look for 447917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @return whether the list contains the given value 448917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 449917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public boolean contains(int value) { 450917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return indexOf(value) >= 0; 451917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 452917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul} 453