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

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

All Implemented Interfaces:

LinearQueue, Queue

Direct Known Subclasses:

LinkedFifoQueue

public abstract class LinkedQueue

extends LinearQueueBase

Queues Objects using a Linked List implementation. ordering of elements within the Queue are dependant on the implementation, such as LinkedFifoQueue. LinkedQueues are ideal for Queues that will be used temporarily, to store a set of Objects to be processed, then shrink as each Object is processed.

Version:

January 20, 2005

Author:

Frank Ziglar

Nested Class Summary

protected static class	LinkedQueue.LinkedSequencer Provides an enumerable implementation of the elements within a LinkedQueue.
protected static class	LinkedQueue.QueueEntry A thin wrapper to store Objects into a LinkedList structure.

Field Summary

protected LinkedQueue.QueueEntry

first

Constructor Summary

LinkedQueue()

Method Summary

void	addFirst(Object o) Adds an Object to the beginning of the Queue.
protected void	addFirstEntry(LinkedQueue.QueueEntry qe) Adds an entry to the beginning of the Queue.
void	addLast(Object o) Adds an Object to the end of the Queue.
protected abstract void	addLastEntry(LinkedQueue.QueueEntry qe) Adds an entry to the end of the Queue.
protected boolean	addUnique(LinkedQueue.QueueEntry qe) Called by addEntry methods to do any special setup.
void	clear() Empties the Queue.
boolean	contains(Object o) Determines if the Queue contains a copy of the specified Object.
protected LinkedQueue.QueueEntry	createEntryFor(Object o)
Enumeration	elements() Retrieves a list of the elements currently in the queue in a form suitable to enumerate over.
protected LinkedQueue.QueueEntry	firstEntry() Retrieves the first entry from the Queue.
boolean	isEmpty() Determines if the Queue is empty.
protected abstract LinkedQueue.QueueEntry	lastEntry() Retrieves the last entry from the Queue.
Object	peekFirst() Retrieves the first Object in the Queue.
Object	peekLast() Retrieves the last Object in the Queue.
Object	remove(Object o) Removes the first instance of the specified Object found in the Queue.
protected LinkedQueue.QueueEntry	removeEntryOf(Object o) Removes the first entry from the Queue that contains the specified Object.
Object	removeFirst() Removes the first Object in the Queue.
protected LinkedQueue.QueueEntry	removeFirstEntry() Removes the first QueueEntry from the Queue.
Object	removeLast() Removes the last Object in the Queue.
protected abstract LinkedQueue.QueueEntry	removeLastEntry() Removes the last QueueEntry from the Queue.
protected void	unlink(LinkedQueue.QueueEntry entry, LinkedQueue.QueueEntry parent) Unlinks a QueueEntry out of the current Queue.

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

add, addSet, appendFlat, appendFlat, appendUnrolled, appendUnrolled, bulkMoveTest, prependFlat, prependFlat, prependUnrolled, prependUnrolled, toString, transferTo

Methods inherited from class java.lang.Object

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

Field Detail

first

protected LinkedQueue.QueueEntry first

Constructor Detail

LinkedQueue

public LinkedQueue()

Method Detail

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.

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

firstEntry

protected LinkedQueue.QueueEntry firstEntry()

Retrieves the first entry from the Queue. This operation does not actually remove the entry from the Queue.

Returns:

the first entry in the Queue

lastEntry

protected abstract LinkedQueue.QueueEntry lastEntry()

Retrieves the last entry from the Queue. This operation does not actually remove the entry from the Queue.

Returns:

the last entry in the Queue

createEntryFor

protected LinkedQueue.QueueEntry createEntryFor(Object o)

addFirst

public void addFirst(Object o)

Description copied from interface: LinearQueue

Adds an Object to the beginning of the Queue.

Parameters:

o - the Object to add

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

addLastEntry

protected abstract void addLastEntry(LinkedQueue.QueueEntry qe)

Adds an entry to the end of the Queue.

Parameters:

qe - the entry to add

See Also:

addUnique(LinkedQueue.QueueEntry)

addFirstEntry

protected void addFirstEntry(LinkedQueue.QueueEntry qe)

Adds an entry to the beginning of the Queue. The default for this operation is to complete in constant time for a single entry. The time complexity will increase linearly with the number of entries linked to the given entry.

Parameters:

qe - the entry to add

See Also:

addUnique(LinkedQueue.QueueEntry)

addUnique

protected boolean addUnique(LinkedQueue.QueueEntry qe)

Called by addEntry methods to do any special setup. If the Queue is empty, the entry is added and made the unique entry of the Queue.

Parameters:

qe - the entry to add to the Queue

Returns:

true if the entry was added as a unique entry, otherwise false if the entry still needs to be added

removeFirstEntry

protected LinkedQueue.QueueEntry removeFirstEntry()

Removes the first QueueEntry from the Queue. It is acceptable for implementations to either return null or throw a NullPointerException if the Queue is empty. The default implementation is to throw a NullPointerException.

Returns:

the first QueueEntry in the Queue.

Throws:

NullPointerException - if the Queue is empty

removeLastEntry

protected abstract LinkedQueue.QueueEntry removeLastEntry()

Removes the last QueueEntry from the Queue. It is acceptable for implementations to either return null or throw a NullPointerException if the Queue is empty.

Returns:

the first QueueEntry in the Queue.

Throws:

NullPointerException - if the Queue is empty

removeFirst

public Object removeFirst()

Description copied from interface: LinearQueue

Removes the first Object in the Queue.

Returns:

the previous first Object in the Queue, or null if the Queue was empty

removeLast

public Object removeLast()

Description copied from interface: LinearQueue

Removes the last Object in the Queue.

Returns:

the previous last Object in the Queue, or null if the Queue was empty

contains

public boolean contains(Object o)

Description copied from interface: Queue

Determines if the Queue contains a copy of the specified Object.

Parameters:

o - an Object to look for copies of

Returns:

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

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

unlink

protected void unlink(LinkedQueue.QueueEntry entry,
                      LinkedQueue.QueueEntry parent)

Unlinks a QueueEntry out of the current Queue. This method is called by remove(Object), but generally not by more specialized implementations, such as removeFirstEntry() or removeLastEntry().

Parameters:

entry - the entry to unlink

parent - the parent of entry. if parent==null it is assumed that first==entry. Otherwise it is assumed that parent.next==entry

Throws:

NullPointerException - if entry==null

removeEntryOf

protected LinkedQueue.QueueEntry removeEntryOf(Object o)

Removes the first entry from the Queue that contains the specified Object.

Parameters:

o - the Object to search for copies of.

Returns:

the first QueueEntry containing a copy of o, or null if no instances of o could be found.

remove

public Object remove(Object o)

Removes the first instance of the specified Object found in the Queue.

Parameters:

o - a copy of the Object to remove

Returns:

the copy of o removed, or null if no copies were found

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