jpaul.DataStructs
Interface WorkSet<T>

All Known Implementing Classes:

VerboseWorkSet, WorkList, WorkPriorityQueue, WorkStack

public interface WorkSet<T>

WorkSet is an ordered set-like data structure. In the current implementations, the order the elements are extracted from a WorkSet has some relation to the order the elements were inserted or to the elements' priorities. This data structure is useful for fixed point computations. In all the current WorkSet implementations the add/extract operations have O(1) complexity, except WorkPriorityQueue where they are logarithmic.

Version:

$Id: WorkSet.java,v 1.8 2005/08/11 18:01:11 salcianu Exp $

Author:

Alexandru Salcianu - salcianu@alum.mit.edu

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

Method Detail

add

boolean add(T elem)

Adds the element elem to this workset.

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

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

Adds all elements from elems to this workset.

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

T extract()

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.

Returns:

The first element from the workset.

clear

void clear()

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

isEmpty

boolean isEmpty()

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

contains

boolean contains(T e)

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

size

int size()

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