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

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

All Implemented Interfaces:

LinearQueue, Queue

Direct Known Subclasses:

LinearQueueTest.CheckedFifoQueue, LinkedDuplexQueue

public class LinkedFifoQueue

extends LinkedQueue

Provides a FIFO oriented implementation of a LinkedQueue. By default

• These methods will operate in O(1) time
  • LinkedQueue.addLast(Object)
  • LinkedQueue.removeFirst()
  • LinkedQueue.peekFirst()
  • LinkedQueue.addFirst(Object)
  • LinkedQueue.peekLast()
  • clear()
• However these methods will operate in O(n) time
  • LinkedQueue.removeLast()

Version:

October 10, 2004

Author:

Frank Ziglar

Nested Class Summary

Nested classes inherited from class net.sf.zig_project.gpl.common.queue.LinkedQueue

LinkedQueue.LinkedSequencer, LinkedQueue.QueueEntry

Field Summary

protected LinkedQueue.QueueEntry

last

Fields inherited from class net.sf.zig_project.gpl.common.queue.LinkedQueue

first

Constructor Summary

LinkedFifoQueue()

Method Summary

protected void	addLastEntry(LinkedQueue.QueueEntry qe) Adds an entry to the end of the current Queue.
protected boolean	addUnique(LinkedQueue.QueueEntry qe) Called by addEntry methods to do any special setup.
void	clear() Empties the Queue.
protected LinkedQueue.QueueEntry	lastEntry() Retrieves the last entry from the Queue.
protected LinkedQueue.QueueEntry	removeFirstEntry() Removes the first QueueEntry from the Queue.
protected 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.LinkedQueue

addFirst, addFirstEntry, addLast, contains, createEntryFor, elements, firstEntry, isEmpty, peekFirst, peekLast, remove, removeEntryOf, removeFirst, removeLast

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

last

protected LinkedQueue.QueueEntry last

Constructor Detail

LinkedFifoQueue

public LinkedFifoQueue()

Method Detail

lastEntry

protected LinkedQueue.QueueEntry lastEntry()

Description copied from class: LinkedQueue

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

Specified by:

lastEntry in class LinkedQueue

Returns:

the last entry in the Queue

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.

Specified by:

clear in interface Queue

Overrides:

clear in class LinkedQueue

addLastEntry

protected void addLastEntry(LinkedQueue.QueueEntry qe)

Adds an entry to the end of the current Queue.

Specified by:

addLastEntry in class LinkedQueue

Parameters:

qe - the entry to add

See Also:

LinkedQueue.addUnique(LinkedQueue.QueueEntry)

unlink

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

Description copied from class: LinkedQueue

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

Overrides:

unlink in class LinkedQueue

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

removeLastEntry

protected LinkedQueue.QueueEntry removeLastEntry()

Description copied from class: LinkedQueue

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.

Specified by:

removeLastEntry in class LinkedQueue

Returns:

the first QueueEntry in the Queue.

addUnique

protected boolean addUnique(LinkedQueue.QueueEntry qe)

Description copied from class: LinkedQueue

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.

Overrides:

addUnique in class LinkedQueue

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()

Description copied from class: LinkedQueue

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.

Overrides:

removeFirstEntry in class LinkedQueue

Returns:

the first QueueEntry in the Queue.