lava.util
Class FifoQueue

java.lang.Object
  |
  +--lava.util.FifoQueue

All Implemented Interfaces:

java.util.Enumeration

public class FifoQueue

extends java.lang.Object

implements java.util.Enumeration

A FifoQueue is a first-in, first-out Object queue. Unlike queues in the real world, this FifoQueue expands as needed and cannot overflow (except where Java runs out of memory, of course).

Objects are dequeued off the front of the queue using the nextElement method. Objects are enqueued to the back of the queue by the addElement method. Additional methods are also available for searching and manipulating the queue.

Queue expansion:

Whenever the queue must grow, its internal storage area simply doubles in size. In most situations, this will provide relatively efficient queue growth. If, however, you are able to predict ahead of time how large this queue must eventually be, you may optimize the the queue by passing in an "initial queue capacity" parameter during construction. You can also force queue capacity expansion by calling the ensureCapacity method.

FifoQueue does not automatically reduce its capacity when objects are dequeued. This may result in an undesirable waste of memory, especially if you are certain that the queue is not going to grow again. At any time, you can minimize the storage requirements of an active queue by calling its trimToSize method.

A note on design:

FifoQueue is essentially a sliding vector. Its first implementation was originally just a subclass of java.util.Vector. Unfortunately, the internal mechanisms of Sun's Vector class prevents it from supporting FifoQueues very efficiently. Due to this limitation, Vector is no longer used as a superclass.*

Because of the similarity between the two ideas, however, the names of FifoQueue's public methods have been chosen to resemble those of the Vector class. Thus, if you're already familiar with Vector, then you already know how to use FifoQueue. They are completely interchangeable.

*FifoQueue uses a circular Object array, which is significantly more efficient than the linear array used in Sun's Vector class if you intend to remove elements from the front or near the front of the queue. This is because in a linear array, such as is used by java.util.Vector, all the values in the array must be shifted every time the element at the head of the queue is removed.

Constructor Summary

FifoQueue()
Initializes an empty FifoQueue, using a default initial capacity.

FifoQueue(int dc)
Prepares an empty FifoQueue with the specified initial capacity.

Method Summary

void	addElement(java.lang.Object object) Adds an element to the end of this queue.
int	capacity() Returns the current capacity of this queue.
java.lang.Object	clone() Clones this queue.
boolean	contains(java.lang.Object obj) Tells if this queue contains the specified object.
void	copyInto(java.lang.Object[] dest) Copies the elements of this queue into a destination array.
java.lang.Object	elementAt(int index) Returns the element at the specified index in the queue.
void	ensureCapacity(int capacity) Guarantees that this queue will be able to buffer at least the indicated number of elements.
java.lang.Object	firstElement() Returns the next element in the queue without removing it.
boolean	hasMoreElements() Determines whether this queue contains more elements.
int	indexOf(java.lang.Object obj) See indexOf(Object,int).
int	indexOf(java.lang.Object obj, int index) Searches this queue for an object equal to the given object.
void	insertElementAt(java.lang.Object obj, int index) Inserts an object into the queue at the specified index.
boolean	isEmpty() Determines if this queue is empty.
java.lang.Object	lastElement() Returns the last element in this queue without removing it.
int	lastIndexOf(java.lang.Object obj) See lastIndexOf(Object,int).
int	lastIndexOf(java.lang.Object obj, int index) Searches this queue for an object equal to the given object.
java.lang.Object	nextElement() Removes the element at the head of the queue and returns it.
void	removeAllElements() Empties the queue.
boolean	removeElement(java.lang.Object obj) Removes the specified object from the queue.
void	removeElementAt(int index) Deletes the element at the specified index.
void	setElementAt(java.lang.Object obj, int index) Replaces the element at the specified index with the given object.
void	setSize(int size) Sets the number of elements contained in this queue.
int	size() Returns the number of elements currently buffered in this queue.
java.lang.String	toString() Generates a string representation of this queue.
void	trimToSize() Minimizes the amount of memory used to store this queue.

Methods inherited from class java.lang.Object

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

Constructor Detail

FifoQueue

public FifoQueue(int dc)

Prepares an empty FifoQueue with the specified initial capacity.

Parameters:

dc - the initial capacity

FifoQueue

public FifoQueue()

Initializes an empty FifoQueue, using a default initial capacity.

Method Detail

isEmpty

public boolean isEmpty()

Determines if this queue is empty.

Returns:

true if this queue is empty; false otherwise

hasMoreElements

public boolean hasMoreElements()

Determines whether this queue contains more elements.

Specified by:

hasMoreElements in interface java.util.Enumeration

Returns:

true if there are more elements, false otherwise

nextElement

public java.lang.Object nextElement()

Removes the element at the head of the queue and returns it.

Specified by:

nextElement in interface java.util.Enumeration

Returns:

the element at the head of the queue, or null if the queue is empty

addElement

public void addElement(java.lang.Object object)

Adds an element to the end of this queue.

Parameters:

object - the element to add

capacity

public final int capacity()

Returns the current capacity of this queue.

Returns:

the current capacity of this queue

size

public final int size()

Returns the number of elements currently buffered in this queue.

Returns:

the current capacity of this queue

indexOf

public int indexOf(java.lang.Object obj,
                   int index)

Searches this queue for an object equal to the given object. If obj is null, the search is for an element whose value is also null; otherwise the object's equals method is used to determine equality. Searching begins with the object specified by index, and precedes forwards.

Parameters:

obj - the object to search for

index - the index to begin searching from (Default value: 0)

Returns:

the index of the matching object in the queue, or -1 if no match is found

indexOf

public final int indexOf(java.lang.Object obj)

See indexOf(Object,int).

lastIndexOf

public int lastIndexOf(java.lang.Object obj,
                       int index)

Searches this queue for an object equal to the given object. If obj is null, the search is for an element whose value is also null; otherwise the object's equals method is used to determine equality. Searching begins with the object specified by index, and precedes backwards.

Parameters:

obj - the object to search for

index - the index to begin searching from (Default value: tail, where tail is the index of the last element)

Returns:

the index of the matching object in the queue, or -1 if no match is found

lastIndexOf

public final int lastIndexOf(java.lang.Object obj)

See lastIndexOf(Object,int).

elementAt

public java.lang.Object elementAt(int index)

Returns the element at the specified index in the queue.

Parameters:

index - the index of the element

Returns:

the element at the specified index

firstElement

public java.lang.Object firstElement()

Returns the next element in the queue without removing it.

Returns:

the next element in the queue

Throws:

java.util.NoSuchElementException - if the queue is empty

clone

public java.lang.Object clone()

Clones this queue. The cloned queue is completely independent of the original queue, except that the pointers in the new queue still point to the same Objects.

Overrides:

clone in class java.lang.Object

Returns:

the clone

contains

public boolean contains(java.lang.Object obj)

Tells if this queue contains the specified object. Uses the equals method to determine a match.

Parameters:

obj - the object to search for

Returns:

true if the object is in this queue, false otherwise

insertElementAt

public void insertElementAt(java.lang.Object obj,
                            int index)

Inserts an object into the queue at the specified index.

Parameters:

obj - the object to insert

index - the index at which to perform the insertion

Throws:

java.lang.ArrayIndexOutOfBoundsException - if (index < 0 || index > size())

lastElement

public java.lang.Object lastElement()

Returns the last element in this queue without removing it.

Returns:

the last element in this queue

Throws:

java.util.NoSuchElementException - if this queue is empty

removeAllElements

public void removeAllElements()

Empties the queue.

removeElementAt

public void removeElementAt(int index)

Deletes the element at the specified index.

Parameters:

index - the index

removeElement

public boolean removeElement(java.lang.Object obj)

Removes the specified object from the queue. This is done by searching for the object, using the indexOf(Object) method, and then deleting the match if one is found. If no match is found, the queue is unchanged.

Overrideable methods employed:

• indexOf(Object)

Parameters:

obj - the object

Returns:

true if the object was found and removed, false otherwise

setElementAt

public final void setElementAt(java.lang.Object obj,
                               int index)

Replaces the element at the specified index with the given object.

Parameters:

obj - the new object

index - the index

setSize

public final void setSize(int size)

Sets the number of elements contained in this queue. If the new size is smaller than the current number of elements in the queue, then the elements at the end of the queue will be discarded. If the new size is larger, then the queue will be padded at the end with null elements.

Parameters:

size - the new size

toString

public final java.lang.String toString()

Generates a string representation of this queue. The form is "{s1, s2, ...}", where s1, s2, ... are the results of the toString method returned by each queued object, or "null" for elements that are null.

Overrides:

toString in class java.lang.Object

Returns:

the string representation

trimToSize

public final void trimToSize()

Minimizes the amount of memory used to store this queue.

ensureCapacity

public final void ensureCapacity(int capacity)

Guarantees that this queue will be able to buffer at least the indicated number of elements.

Parameters:

capacity - the minimum capacity of this queue

copyInto

public final void copyInto(java.lang.Object[] dest)

Copies the elements of this queue into a destination array. Of course, the array must be sufficiently large and of the proper type.

Parameters:

dest - the destination array