13447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein/* 2324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver [The "BSD licence"] 3324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Copyright (c) 2005-2008 Terence Parr 43447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein All rights reserved. 53447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 63447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Redistribution and use in source and binary forms, with or without 73447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein modification, are permitted provided that the following conditions 83447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein are met: 93447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1. Redistributions of source code must retain the above copyright 10324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver notice, this list of conditions and the following disclaimer. 113447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 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. 143447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 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. 163447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 173447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 183447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 193447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 203447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 213447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 223447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 233447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 243447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 253447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 263447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver*/ 283447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinpackage org.antlr.runtime.misc; 293447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 303447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein/** A dynamic array that uses int not Integer objects. In principle this 313447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * is more efficient in time, but certainly in space. 323447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 333447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * This is simple enough that you can access the data array directly, 343447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * but make sure that you append elements only with add() so that you 353447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * get dynamic sizing. Make sure to call ensureCapacity() when you are 363447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * manually adding new elements. 373447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 383447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * Doesn't impl List because it doesn't return objects and I mean this 393447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * really as just an array not a List per se. Manipulate the elements 403447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * at will. This has stack methods too. 413447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 423447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * When runtime can be 1.5, I'll make this generic. 433447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 443447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinpublic class IntArray { 453447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public static final int INITIAL_SIZE = 10; 463447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public int[] data; 473447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected int p = -1; 483447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 493447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void add(int v) { 503447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein ensureCapacity(p+1); 513447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein data[++p] = v; 523447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 533447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 543447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void push(int v) { 553447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein add(v); 563447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 573447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 583447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public int pop() { 593447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int v = data[p]; 603447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein p--; 613447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return v; 623447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 633447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 643447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** This only tracks elements added via push/add. */ 653447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public int size() { 663447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return p; 673447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 683447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 693447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void clear() { 703447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein p = -1; 713447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 723447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 733447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void ensureCapacity(int index) { 743447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( data==null ) { 753447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein data = new int[INITIAL_SIZE]; 763447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 773447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein else if ( (index+1)>=data.length ) { 783447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int newSize = data.length*2; 793447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( index>newSize ) { 803447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein newSize = index+1; 813447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 823447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int[] newData = new int[newSize]; 833447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein System.arraycopy(data, 0, newData, 0, data.length); 843447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein data = newData; 853447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 863447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 873447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein} 88