jpaul.DataStructs
Class WorkList<T>

java.lang.Object
  jpaul.DataStructs.WorkList<T>

All Implemented Interfaces:

java.io.Serializable, WorkSet<T>

public class WorkList<T>
extends java.lang.Object
implements java.io.Serializable

WorkList is a WorkSet with FIFO order. Good for algorithms that work on levels. The add/extract operations have O(1) complexity.

Version:

$Id: WorkList.java,v 1.7 2006/03/14 02:29:31 salcianu Exp $

Author:

Alexandru Salcianu - salcianu@alum.mit.edu

See Also:

Serialized Form

Field Summary

protected java.util.LinkedList<T>

list List that provides the order of the elements from this workset.

Constructor Summary

WorkList()

Method Summary

boolean	add(T elem) Adds the element elem to this workset.
boolean	addAll(java.util.Collection<T> elems) Adds all elements from elems to this workset.
protected void	addToOrder(T elem) Overrides the abstract method WorkSetAbstr.addToOrder(T).
void	clear() Removes all elements from the workset. Complexity: O(1).
boolean	contains(T e) Checks whether this workset contains the element e. Complexity: O(1).
T	extract() Returns the first element of this workset (according to the order specific to this workset.
protected T	extractInOrder() Overrides WorkSetAbstr.extractInOrder().
boolean	isEmpty() Checks whether this workset is empty. Complexity: O(1).
int	size() Returns the size of this workset. Invariant: isEmpty() iff size() == 0. Complexity: O(1).
java.lang.String	toString()
protected java.util.Collection<T>	underlyingOrder() Returns the underlying ordered collection.

Methods inherited from class java.lang.Object

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

Field Detail

list

protected java.util.LinkedList<T> list

List that provides the order of the elements from this workset.

Constructor Detail

WorkList

public WorkList()

Method Detail

addToOrder

protected void addToOrder(T elem)

Overrides the abstract method WorkSetAbstr.addToOrder(T). Add elem at the tail of the list, to implement FIFO order.

extractInOrder

protected T extractInOrder()

Overrides WorkSetAbstr.extractInOrder(). States that we always extract elements from the head of the list. Therefore, subclasses define the extraction order by overriding WorkSetAbstr.addToOrder(T).

underlyingOrder

protected java.util.Collection<T> underlyingOrder()

Returns the underlying ordered collection. Useful for factoring out the code for clear and toString.

add

public boolean add(T elem)

Description copied from interface: WorkSet

Adds the element elem to this workset.

Specified by:

add in interface WorkSet<T>

Returns:

true if elem was not already in the workset. If elem was already in the workset, the workset does not change in any way, and add returns false.

addAll

public boolean addAll(java.util.Collection<T> elems)

Description copied from interface: WorkSet

Adds all elements from elems to this workset.

Specified by:

addAll in interface WorkSet<T>

Returns:

true if any of the added elements was not already in this workset. Otherwise, the workset does not change in any way, and add returns false.

extract

public T extract()

Description copied from interface: WorkSet

Returns the first element of this workset (according to the order specific to this workset. The element is removed from the workset. Throws a NoSuchElementException if the workset is empty.

Specified by:

extract in interface WorkSet<T>

Returns:

The first element from the workset.

clear

public void clear()

Description copied from interface: WorkSet

Removes all elements from the workset.
Complexity: O(1).

Specified by:

clear in interface WorkSet<T>

isEmpty

public boolean isEmpty()

Description copied from interface: WorkSet

Checks whether this workset is empty.
Complexity: O(1).

Specified by:

isEmpty in interface WorkSet<T>

contains

public boolean contains(T e)

Description copied from interface: WorkSet

Checks whether this workset contains the element e.
Complexity: O(1).

Specified by:

contains in interface WorkSet<T>

size

public int size()

Description copied from interface: WorkSet

Returns the size of this workset.
Invariant: isEmpty() iff size() == 0.
Complexity: O(1).

Specified by:

size in interface WorkSet<T>

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object