WorkStack

Overview

Package

Class

Tree

Deprecated

Index

Help

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

jpaul.DataStructs
Class WorkStack<T>

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

All Implemented Interfaces:: java.io.Serializable, WorkSet<T>

public class WorkStack<T>
extends java.lang.Object
implements java.io.Serializable
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.