org.antlr.runtime.misc
Class FastQueue<T>

java.lang.Object
  extended by org.antlr.runtime.misc.FastQueue<T>
Direct Known Subclasses:
LookaheadStream

public class FastQueue<T>
extends java.lang.Object

A queue that can dequeue and get(i) in O(1) and grow arbitrarily large. A linked list is fast at dequeue but slow at get(i). An array is the reverse. This is O(1) for both operations. List grows until you dequeue last element at end of buffer. Then it resets to start filling at 0 again. If adds/removes are balanced, the buffer will not grow too large. No iterator stuff as that's not how we'll use it.


Field Summary
protected  java.util.List<T> data
          dynamically-sized buffer of elements
protected  int p
          index of next element to fill
 
Constructor Summary
FastQueue()
           
 
Method Summary
 void add(T o)
           
 void clear()
           
 T get(int i)
          Return element i elements ahead of current element.
 T head()
           
 T remove()
          Get and remove first element in queue
 void reset()
           
 int size()
           
 java.lang.String toString()
          Return string of current buffer contents; non-destructive
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

data

protected java.util.List<T> data
dynamically-sized buffer of elements


p

protected int p
index of next element to fill

Constructor Detail

FastQueue

public FastQueue()
Method Detail

reset

public void reset()

remove

public T remove()
Get and remove first element in queue


add

public void add(T o)

size

public int size()

head

public T head()

get

public T get(int i)
Return element i elements ahead of current element. i==0 gets current element. This is not an absolute index into the data list since p defines the start of the real list.


clear

public void clear()

toString

public java.lang.String toString()
Return string of current buffer contents; non-destructive

Overrides:
toString in class java.lang.Object


Copyright © 2013. All Rights Reserved.