org.eigenbase.util
Class ArrayQueue<E>

java.lang.Object
  java.util.AbstractCollection<E>
      org.eigenbase.util.ArrayQueue<E>

All Implemented Interfaces:

Iterable<E>, Collection<E>

public class ArrayQueue<E>
extends AbstractCollection<E>
implements Collection<E>

ArrayQueue is a queue implementation backed by an array. Grows by doubling the existing size, but never shrinks. Queue entries are allowed to wrap around array boundaries. ArrayQueue does not allow null entries.

Contains the necessary methods to implement JDK 1.5's Queue interface. Also, some methods can be removed by extending JDK 1.5's AbstractQueue class.

Offering (adding) items to the queue, polling (removing) items from the queue, and peeking at the head of the queue are normally constant time operations. The exception is that growing the queue is an O(N) operation and can occur when offering an item to the queue.

The Iterator returned by iterator() behaves somewhat inconsistently with the general contract of Iterator. Read the documentation for that method carefully.

Since:

Sep 16, 2004

Version:

$Id: //open/dev/farrago/src/org/eigenbase/util/ArrayQueue.java#13 $

Author:

Stephan Zuercher

Field Summary

private int	capacity The current capacity (not size) of this queue.
private static int	DEFAULT_CAPACITY
private int	end The current position for the next element added to the queue.
private E[]	queue The queue contents.
private int	start The current position of the head element of the queue.

Constructor Summary

ArrayQueue()
Constructs an empty ArrayQueue with the default initial capacity of DEFAULT_CAPACITY.

ArrayQueue(Collection<? extends E> c)
Constructs an ArrayQueue with the given contents.

ArrayQueue(int capacity)
Constructs an empty ArrayQueue with the specified initial capacity.

ArrayQueue(int capacity, Collection<? extends E> c)
Constructs an ArrayQueue with the given contents and initial capacity.

Method Summary

boolean	add(E o) Adds the specified element to this queue.
boolean	addAll(Collection<? extends E> c) Adds all of the elements in the specified collection to this queue.
void	clear() Removes all elements from the queue.
private void	copyQueueToArray(E[] otherQueue) Copies the contents of the queue into an array.
Object	element() Retrieves, but does not remove, the head of the queue.
boolean	equals(Object o) Compares two queues for equality.
private void	grow() Grows the queue to twice the current capacity.
private int	increment(int index) Increments the given index by one modulo the queue's capacity.
Iterator<E>	iterator() Returns an iterator over the elements in the queue in proper sequence.
boolean	offer(E o) Inserts the specified element into this queue.
E	peek() Retrieves, but does not remove the head of this queue, returning null if this queue is empty.
E	poll() Retrieves and removes the head of this queue, returning null if this queue is empty.
E	remove() Retrieves and removes the head of the queue.
boolean	remove(Object o) Unsupported operation.
boolean	removeAll(Collection c) Unsupported operation.
boolean	retainAll(Collection<?> c) Unsupported operation.
int	size() Returns the number of elements currently in the queue.

Methods inherited from class java.util.AbstractCollection

contains, containsAll, isEmpty, toArray, toArray, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Collection

contains, containsAll, hashCode, isEmpty, toArray, toArray

Field Detail

DEFAULT_CAPACITY

private static final int DEFAULT_CAPACITY

See Also:

Constant Field Values

capacity

private int capacity

The current capacity (not size) of this queue. Equal to {link #queue}.length.

queue

private E[] queue

The queue contents. Treated as a circular buffer.

start

private int start

The current position of the head element of the queue.

end

private int end

The current position for the next element added to the queue.

Constructor Detail

ArrayQueue

public ArrayQueue(int capacity)

Constructs an empty ArrayQueue with the specified initial capacity.

Parameters:

capacity - the initial capacity of this queue

ArrayQueue

public ArrayQueue()

Constructs an empty ArrayQueue with the default initial capacity of DEFAULT_CAPACITY.

ArrayQueue

public ArrayQueue(Collection<? extends E> c)

Constructs an ArrayQueue with the given contents. The initial capacity of the queue is 10 or c.size() whichever is larger. The queue is populated with the elements of c in the order in which c's iterator returns them.

Parameters:

c - a collection to use as the default contents of the queue

Throws:

NullPointerException - if c or any of its elements are null

ArrayQueue

public ArrayQueue(int capacity,
                  Collection<? extends E> c)

Constructs an ArrayQueue with the given contents and initial capacity. If capacity is smaller than c.size(), the initial capacity will be c.size(). The queue is populated with the elements of c in the order in which c's iterator returns them.

Parameters:

capacity - the initial capacity of this queue

c - a collection to use as the default contents of the queue

Throws:

NullPointerException - if c or any of its elements are null

Method Detail

offer

public boolean offer(E o)

Inserts the specified element into this queue. The queue's capacity may grow as a result of this call.

Parameters:

o - the element to insert

Returns:

false if o is null, otherwise true since it's always possible to add an element to this queue.

peek

public E peek()

Retrieves, but does not remove the head of this queue, returning null if this queue is empty.

Returns:

the head of the queue or null if the queue is empty

poll

public E poll()

Retrieves and removes the head of this queue, returning null if this queue is empty.

Returns:

the head of the queue or null if the queue is empty

size

public int size()

Returns the number of elements currently in the queue.

Specified by:

size in interface Collection<E>

Specified by:

size in class AbstractCollection<E>

Returns:

the number of elements currently in the queue

iterator

public Iterator<E> iterator()

Returns an iterator over the elements in the queue in proper sequence. The returned Iterator is a "weakly consistent" iterator. It will never throw ConcurrentModificationException and guarantees to traverse elements as they existed upon construction of the iterator, but will never reflect any modifications subsequent to construction.

Specified by:

iterator in interface Iterable<E>

Specified by:

iterator in interface Collection<E>

Specified by:

iterator in class AbstractCollection<E>

Returns:

an iterator over the elements in this queue in proper order

remove

public boolean remove(Object o)

Unsupported operation.

Specified by:

remove in interface Collection<E>

Overrides:

remove in class AbstractCollection<E>

removeAll

public boolean removeAll(Collection c)

Unsupported operation.

Specified by:

removeAll in interface Collection<E>

Overrides:

removeAll in class AbstractCollection<E>

retainAll

public boolean retainAll(Collection<?> c)

Unsupported operation.

Specified by:

retainAll in interface Collection<E>

Overrides:

retainAll in class AbstractCollection<E>

grow

private void grow()

Grows the queue to twice the current capacity.

equals

public boolean equals(Object o)

Compares two queues for equality. The queues are not modified by this method. Concurrent modification of either this queue or the one being compared to has undefined results. Each element, in the proper order, must match in the two queues using the elements' equals method.

Specified by:

equals in interface Collection<E>

Overrides:

equals in class Object

Parameters:

o - the queue to compare this queue to

Returns:

true if the queues have the same elements in the same order, false otherwise

Throws:

ClassCastException - if o is not an ArrayQueue.

copyQueueToArray

private void copyQueueToArray(E[] otherQueue)

Copies the contents of the queue into an array. The elements are copied such that the first element of the queue ends up in otherQueue[0]. Elements are copied in order.

Parameters:

otherQueue - the array to copy data into, otherQueue.length must be greater than or equal to size().

increment

private int increment(int index)

Increments the given index by one modulo the queue's capacity.

Parameters:

index - the index value to increment

Returns:

the index mod capacity

add

public boolean add(E o)

Adds the specified element to this queue. This implementation returns true if offer succeeds, else throws an IllegalStateException.

Specified by:

add in interface Collection<E>

Overrides:

add in class AbstractCollection<E>

Parameters:

o - the element

Returns:

true (as per the general contract of Collection.add(Object)).

Throws:

NullPointerException - if o is null

IllegalStateException - if the call to offer(Object) fails

addAll

public boolean addAll(Collection<? extends E> c)

Adds all of the elements in the specified collection to this queue. Attempts to addAll of a queue to itself result in IllegalArgumentException. Further, the behavior of this operation is undefined if the specified collection is modified while the operation is in progress.

This implementation iterates over the specified collection, and adds each element returned by the iterator to this collection, in turn. A runtime exception encountered while trying to add an element (including, in particular, a null element) may result in only some of the elements having been successfully added when the associated exception is thrown.

Specified by:

addAll in interface Collection<E>

Overrides:

addAll in class AbstractCollection<E>

Parameters:

c - collection to add to the queue

Returns:

true if this queue changed as a result of the call

Throws:

IllegalArgumentException - if this == c

NullPointerException - if c or any of its elements are null.

IllegalStateException - if the call to add(Object) does

clear

public void clear()

Removes all elements from the queue. The queue will be empty and contain no references to its previous contents after this call returns. This method calls poll() repeatedly until it returns null.

Specified by:

clear in interface Collection<E>

Overrides:

clear in class AbstractCollection<E>

element

public Object element()

Retrieves, but does not remove, the head of the queue. Returns the result of peek() unless the queue is empty.

Returns:

the head of this queue

Throws:

NoSuchElementException - if the queue is empty

remove

public E remove()

Retrieves and removes the head of the queue. Returns the result of poll() unless the queue is empty.

Returns:

the head of the queue

Throws:

NoSuchElementException - if the queue is empty