jpaul.DataStructs
Class WorkStack<T>

java.lang.Object
  extended by jpaul.DataStructs.WorkStack<T>
All Implemented Interfaces:
java.io.Serializable, WorkSet<T>

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

WorkStack is a WorkSet with LIFO order. Good for algorithms that like to iterate over the most-recently changed spots. The add/extract operations have O(1) complexity.

Version:
$Id: WorkStack.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
WorkStack()
           
 
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)
          Adds elem to the underlying list.
 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

WorkStack

public WorkStack()
Method Detail

addToOrder

protected void addToOrder(T elem)
Adds elem to the underlying list. Subclasses will have to choose whether they want to perform the addition at the head, respectively at the tail of the list. Precondition: elem is not already in the list.


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


Copyright 2005 Alexandru Salcianu - salcianu@alum.mit.edu