1324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/* 2324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver[The "BSD licence"] 3324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverCopyright (c) 2005-2008 Terence Parr 4324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverAll rights reserved. 5324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 6324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverRedistribution and use in source and binary forms, with or without 7324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvermodification, are permitted provided that the following conditions 8324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverare met: 9324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver1. Redistributions of source code must retain the above copyright 10324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvernotice, this list of conditions and the following disclaimer. 11324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver2. Redistributions in binary form must reproduce the above copyright 12324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvernotice, this list of conditions and the following disclaimer in the 13324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverdocumentation and/or other materials provided with the distribution. 14324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver3. The name of the author may not be used to endorse or promote products 15324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverderived from this software without specific prior written permission. 16324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 17324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverTHIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverIMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverOF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverIN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverINCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverNOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverDATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverTHEORY 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 GruverTHIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver*/ 28324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverpackage org.antlr.runtime.misc; 29324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 30324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport java.util.List; 31324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport java.util.ArrayList; 32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport java.util.NoSuchElementException; 33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** A queue that can dequeue and get(i) in O(1) and grow arbitrarily large. 35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * A linked list is fast at dequeue but slow at get(i). An array is 36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the reverse. This is O(1) for both operations. 37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * List grows until you dequeue last element at end of buffer. Then 39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * it resets to start filling at 0 again. If adds/removes are balanced, the 40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * buffer will not grow too large. 41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * No iterator stuff as that's not how we'll use it. 43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverpublic class FastQueue<T> { 45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** dynamically-sized buffer of elements */ 46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected List<T> data = new ArrayList<T>(); 47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** index of next element to fill */ 48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected int p = 0; 49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void reset() { p = 0; data.clear(); } 51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Get and remove first element in queue */ 53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public T remove() { 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver T o = get(0); 55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver p++; 56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // have we hit end of buffer? 57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( p == data.size() ) { 58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if so, it's an opportunity to start filling at index 0 again 59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver clear(); // size goes to 0, but retains memory 60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return o; 62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void add(T o) { data.add(o); } 65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int size() { return data.size() - p; } 67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public T head() { return get(0); } 69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Return element i elements ahead of current element. i==0 gets 71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * current element. This is not an absolute index into the data list 72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * since p defines the start of the real list. 73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public T get(int i) { 75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( p+i >= data.size() ) { 76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new NoSuchElementException("queue index "+(p+i)+" > size "+data.size()); 77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return data.get(p+i); 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void clear() { p = 0; data.clear(); } 82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Return string of current buffer contents; non-destructive */ 84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public String toString() { 85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver StringBuffer buf = new StringBuffer(); 86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = size(); 87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i=0; i<n; i++) { 88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append(get(i)); 89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( (i+1)<n ) buf.append(" "); 90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return buf.toString(); 92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver}