1324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/* 2324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * [The "BSD license"] 3324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Copyright (c) 2010 Terence Parr 4324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * All rights reserved. 5324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 6324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Redistribution and use in source and binary forms, with or without 7324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * modification, are permitted provided that the following conditions 8324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * are met: 9324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1. Redistributions of source code must retain the above copyright 10324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * notice, this list of conditions and the following disclaimer. 11324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 2. Redistributions in binary form must reproduce the above copyright 12324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * notice, this list of conditions and the following disclaimer in the 13324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * documentation and/or other materials provided with the distribution. 14324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 3. The name of the author may not be used to endorse or promote products 15324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * derived from this software without specific prior written permission. 16324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 17324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 28324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverpackage org.antlr.misc; 29324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 30324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport java.util.AbstractList; 31324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** An ArrayList based upon int members. Not quite a real implementation of a 33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * modifiable list as I don't do, for example, add(index,element). 34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * TODO: unused? 35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverpublic class IntArrayList extends AbstractList implements Cloneable { 37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver private static final int DEFAULT_CAPACITY = 10; 38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected int n = 0; 39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected int[] elements = null; 40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public IntArrayList() { 42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this(DEFAULT_CAPACITY); 43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public IntArrayList(int initialCapacity) { 46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver elements = new int[initialCapacity]; 47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Set the ith element. Like ArrayList, this does NOT affect size. */ 50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int set(int i, int newValue) { 51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( i>=n ) { 52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver setSize(i); // unlike definition of set in ArrayList, set size 53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int v = elements[i]; 55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver elements[i] = newValue; 56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return v; 57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean add(int o) { 60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( n>=elements.length ) { 61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver grow(); 62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver elements[n] = o; 64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver n++; 65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; 66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void setSize(int newSize) { 69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( newSize>=elements.length ) { 70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ensureCapacity(newSize); 71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver n = newSize; 73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected void grow() { 76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ensureCapacity((elements.length * 3)/2 + 1); 77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean contains(int v) { 80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < n; i++) { 81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int element = elements[i]; 82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( element == v ) { 83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; 84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void ensureCapacity(int newCapacity) { 90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int oldCapacity = elements.length; 91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (n>=oldCapacity) { 92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int oldData[] = elements; 93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver elements = new int[newCapacity]; 94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.arraycopy(oldData, 0, elements, 0, n); 95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public Object get(int i) { 99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return Utils.integer(element(i)); 100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int element(int i) { 103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return elements[i]; 104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int[] elements() { 107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int[] a = new int[n]; 108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.arraycopy(elements, 0, a, 0, n); 109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return a; 110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int size() { 113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return n; 114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int capacity() { 117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return elements.length; 118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean equals(Object o) { 121324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( o==null ) { 122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IntArrayList other = (IntArrayList)o; 125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( this.size()!=other.size() ) { 126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < n; i++) { 129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( elements[i] != other.elements[i] ) { 130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; 134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public Object clone() throws CloneNotSupportedException { 137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IntArrayList a = (IntArrayList)super.clone(); 138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver a.n = this.n; 139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.arraycopy(this.elements, 0, a.elements, 0, this.elements.length); 140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return a; 141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public String toString() { 144324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver StringBuffer buf = new StringBuffer(); 145324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < n; i++) { 146324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( i>0 ) { 147324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append(", "); 148324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 149324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append(elements[i]); 150324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 151324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return buf.toString(); 152324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 153324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 154