net.sf.zig_project.gpl.common.queue
Class ArrayQueue

java.lang.Object
  net.sf.zig_project.gpl.common.queue.LinearQueueBase
      net.sf.zig_project.gpl.common.queue.ArrayQueue

All Implemented Interfaces:

LinearQueue, Queue

Direct Known Subclasses:

DynamicArrayQueue

public class ArrayQueue

extends LinearQueueBase

Provides an array backed Queue. This Queue stores elements in an array, in a fashion that ensures all Queue operations operate in O(1) time. This includes all methods defined by LinearQueue. It can also retrieve arbitary indexies in O(1) time. However, inserations and removals to arbitrary indexies may require O(n) time.

Direct instansiations of this class are fixed length. For arbitrary length Queues, a subclass should be used, such as DynamicArrayQueue.

The documentation here makes reference to physical and relative indices. Users of this class need only concern themselves with relative indices, which are in the range of 0 to size(). Subclasses may need to consider physical indices, which specify a specific index within the backing array itself.

Version:

December 5, 2004

Author:

Frank Ziglar

Nested Class Summary

protected static class

ArrayQueue.ArraySequencer An Enumerable interface for ArrayQueue.

Field Summary

protected int	begin
protected int	end
protected Object[]	entries

Constructor Summary

ArrayQueue(int size)
Constructs a Queue with the specified size

Method Summary

void	addFirst(Object o) Inserts the provided Object into the beginning of the queue, so that it is the new first element.
void	addLast(Object o) Adds an Object to the end of the Queue.
void	addSet(Enumeration e) Adds an enumerable set of elements to the end of the queue.
int	availableRoom() Returns the amount of room available in this queue for elements to be added.
protected void	bulkMoveTest(LinearQueue q)
void	clear() Empties the Queue.
boolean	contains(Object o) Determines if this Queue contains a copy of o.
protected int	decIndex(int idx) Decrements a physical index within the queue wrapping it if necessary.
Enumeration	elements() Retrieves a list of the elements currently in the queue in a form suitable to enumerate over.
void	ensureRoom(int rm)
protected int	firstIndexOf(Object o) Searches the queue for the first copy of o.
protected int	incIndex(int idx) Increments a physical index within the queue wrapping it if necessary.
void	insert(Object o, int index) Inserts the specified object into the queue at the new relative index.
boolean	isEmpty() Determines if the Queue is empty.
protected void	overflow(int rm) This method is called when the queue is too full to continue an add operation.
Object	peek(int index) Retrieves the Object located within the queue at the specified relative index.
Object	peekFirst() Retrieves the first Object in the Queue.
Object	peekLast() Retrieves the last Object in the Queue.
protected int	physicalIndex(int relative) Retrieves the physical index for a given relative index.
Object	remove(int relative_index) Removes an Object from the queue located at the specified relative index.
Object	remove(Object o) Removes the first relative copy of o from the queue.
Object	removeFirst() Removes the first element in the Queue.
protected Object	removeIndex(int idx) Removes an Object from the queue located at the specified physical index.
Object	removeLast() Removes the last element in the Queue.
void	replace(Object o, int idx) Replaces the Object in the queue at the provided relative index with the new Object.
int	size() The current size of the queue.
String	toString() Makes a String representation of all the current contents of the queue.
String	toString(String ele_sep) Makes a String representation of all the current contents of the queue.

Methods inherited from class net.sf.zig_project.gpl.common.queue.LinearQueueBase

add, appendFlat, appendFlat, appendUnrolled, appendUnrolled, prependFlat, prependFlat, prependUnrolled, prependUnrolled, transferTo

Methods inherited from class java.lang.Object

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

Field Detail

entries

protected Object[] entries

begin

protected int begin

end

protected int end

Constructor Detail

ArrayQueue

public ArrayQueue(int size)

Constructs a Queue with the specified size

Parameters:

size - the size of the array of the queue

Method Detail

isEmpty

public boolean isEmpty()

Description copied from interface: Queue

Determines if the Queue is empty. An empty queue contains no elements.

Returns:

true only if the Queue is empty

clear

public void clear()

Description copied from interface: Queue

Empties the Queue. All elements are cleared out, and the Queue will be empty after this call.

bulkMoveTest

protected void bulkMoveTest(LinearQueue q)

Overrides:

bulkMoveTest in class LinearQueueBase

ensureRoom

public void ensureRoom(int rm)

addLast

public void addLast(Object o)

Description copied from interface: LinearQueue

Adds an Object to the end of the Queue.

Parameters:

o - the Object to add

addSet

public void addSet(Enumeration e)

Adds an enumerable set of elements to the end of the queue. The last element in the Enumeration will be the last element. This method is overridden in order to provide a more efficient method for bulk array copying, if supported by the Enumeration.

Overrides:

addSet in class LinearQueueBase

overflow

protected void overflow(int rm)

This method is called when the queue is too full to continue an add operation.

Parameters:

rm - the amount of additional room required

availableRoom

public int availableRoom()

Returns the amount of room available in this queue for elements to be added. The returned value is dependant on the capacity of the underlying array.

size

public int size()

The current size of the queue. This is a count of the number of elements currently contained within the queue.

Returns:

the number of elements within the queue

incIndex

protected final int incIndex(int idx)

Increments a physical index within the queue wrapping it if necessary.

Parameters:

idx - index to increment

Returns:

incremented value of the physical index

decIndex

protected final int decIndex(int idx)

Decrements a physical index within the queue wrapping it if necessary.

Parameters:

idx - index to decrement

Returns:

decremented value of the physical index

firstIndexOf

protected int firstIndexOf(Object o)

Searches the queue for the first copy of o. If no copy is found, returns -1. Otherwise, this method returns the physical index of the copy in the queue.

Parameters:

o - a copy of the Object to search for

Returns:

the physical index of the relative first copy of o, or -1 if no match was found

removeFirst

public Object removeFirst()

Removes the first element in the Queue. This method works with addLast(java.lang.Object) to emulate a FIFO queue.

Returns:

the previous first element of the queue, or null if the queue was empty

removeLast

public Object removeLast()

Removes the last element in the Queue. This method works with addLast(java.lang.Object) to emulate a LIFO queue.

Returns:

the previous last element in the queue, or null if the queue was empty

peek

public Object peek(int index)

Retrieves the Object located within the queue at the specified relative index.

Parameters:

index - the relative index to look up

Returns:

the Object located at the relative index

Throws:

IndexOutOfBoundsException - if the index is not a legal relative index

peekFirst

public Object peekFirst()

Description copied from interface: LinearQueue

Retrieves the first Object in the Queue. This does not actually remove the Object from the Queue.

Returns:

the first Object in the Queue

peekLast

public Object peekLast()

Description copied from interface: LinearQueue

Retrieves the last Object in the Queue. This does not actually remove the Object from the Queue.

Returns:

the last Object in the Queue

contains

public boolean contains(Object o)

Determines if this Queue contains a copy of o.

Parameters:

o - an Object to look for copies of

Returns:

true if at least one copy of o was found in the queue

remove

public Object remove(Object o)

Removes the first relative copy of o from the queue.

Parameters:

o - a copy of the Object to be removed

Returns:

the first relative copy of o from removed from the queue, or null if no copies were found.

remove

public Object remove(int relative_index)

Removes an Object from the queue located at the specified relative index.

Parameters:

relative_index - the relative index to remove from the queue

Returns:

the Object removed from the queue

Throws:

IndexOutOfBoundsException - if the index is not a legal relative index

removeIndex

protected Object removeIndex(int idx)

Removes an Object from the queue located at the specified physical index.

Parameters:

idx - the physical index to remove from the queue

Returns:

the Object removed from the queue

replace

public void replace(Object o,
                    int idx)

Replaces the Object in the queue at the provided relative index with the new Object.

Parameters:

o - the new Object to place into the queue

idx - the relative index of the object to be replaced

physicalIndex

protected int physicalIndex(int relative)

Retrieves the physical index for a given relative index.

Parameters:

relative - the relative index to convert

Returns:

the physical index

Throws:

IndexOutOfBoundsException - if the relative index is not contained within this queue

addFirst

public void addFirst(Object o)

Inserts the provided Object into the beginning of the queue, so that it is the new first element.

Parameters:

o - the Object to be inserted

insert

public void insert(Object o,
                   int index)

Inserts the specified object into the queue at the new relative index. Any higher ranked elements are incremented by their relative index.

Parameters:

o - the Object be inserted into the queue

index - the relative index at which to insert the Object

elements

public Enumeration elements()

Description copied from interface: Queue

Retrieves a list of the elements currently in the queue in a form suitable to enumerate over. Operations on the Enumeration after this queue has been modified are not anticipated, and may cause unforseen problems.

Returns:

an Enumeration of the elements in the queue

toString

public String toString()

Makes a String representation of all the current contents of the queue. The are listed as they are represented in the array of the queue, putting each element on the same line.

Overrides:

toString in class LinearQueueBase

Returns:

a String representation of the contents of the Queue

toString

public String toString(String ele_sep)

Makes a String representation of all the current contents of the queue. The are listed as they are represented in the array of the queue, seperating each with the given seperator.

Parameters:

ele_sep - the seperator to use between each element in the list