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

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
              net.sf.zig_project.gpl.common.queue.LinkedDuplexQueue

All Implemented Interfaces:

LinearQueue, Queue

Direct Known Subclasses:

LinearQueueTest.CheckedDuplexQueue

public class LinkedDuplexQueue

extends LinkedFifoQueue

Provides an implementation suitable for either LIFO or FIFO operations. This Queue is backed as a Double Linked List in memory. Hence, all of the basic methods will operate in O(1) time, including:

• LinkedQueue.addLast(Object)
• LinkedQueue.removeLast()
• LinkedQueue.peekLast()
• LinkedQueue.addFirst(Object)
• LinkedQueue.removeFirst()
• LinkedQueue.peekFirst()
• LinkedFifoQueue.clear()

Version:

December 7, 2004

Author:

Frank Ziglar

Nested Class Summary

protected static class

LinkedDuplexQueue.DuplexEntry Thin wrapper for holding an element in a double linked list.

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

LinkedQueue.LinkedSequencer, LinkedQueue.QueueEntry

Field Summary

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

last

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

first

Constructor Summary

LinkedDuplexQueue()

Method Summary

protected void	addFirstEntry(LinkedQueue.QueueEntry qe) Adds an entry to the beginning of the Queue.
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.
protected LinkedQueue.QueueEntry	createEntryFor(Object o)
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 par) Unlinks a QueueEntry out of the current Queue.

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

clear, lastEntry

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

addFirst, addLast, contains, 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

Constructor Detail

LinkedDuplexQueue

public LinkedDuplexQueue()

Method Detail

createEntryFor

protected LinkedQueue.QueueEntry createEntryFor(Object o)

Overrides:

createEntryFor in class LinkedQueue

addLastEntry

protected void addLastEntry(LinkedQueue.QueueEntry qe)

Description copied from class: LinkedFifoQueue

Adds an entry to the end of the current Queue.

Overrides:

addLastEntry in class LinkedFifoQueue

Parameters:

qe - the entry to add

addFirstEntry

protected void addFirstEntry(LinkedQueue.QueueEntry qe)

Description copied from class: LinkedQueue

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.

Overrides:

addFirstEntry in class LinkedQueue

Parameters:

qe - the entry to add

See Also:

LinkedQueue.addUnique(LinkedQueue.QueueEntry)

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 LinkedFifoQueue

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 LinkedFifoQueue

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.

Overrides:

removeLastEntry in class LinkedFifoQueue

unlink

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

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 LinkedFifoQueue