jpaul.DataStructs
Class WorkPriorityQueue<T>

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

All Implemented Interfaces:

java.io.Serializable, WorkSet<T>

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

WorkPriorityQueue is a WorkSet whose elements are extracted in the increasing order of their priorities. The add/extract operations have logarithmic complexity. (Note that from a linguistic perspective, a PriorityQueue provides elements according to their inverse priorities: smallest priorities first)

Version:

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

Author:

Alexandru Salcianu - salcianu@alum.mit.edu

See Also:

Serialized Form

Constructor Summary

WorkPriorityQueue(java.util.Comparator<T> comp)
Creates a WorkPriorityQueue.

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() Returns the first element from the underlying ordered collection.
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

Constructor Detail

WorkPriorityQueue

public WorkPriorityQueue(java.util.Comparator<T> comp)

Creates a WorkPriorityQueue.

Parameters:

comp - Comparator used to determine the priority order between the elements of this WorkSet.

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

Returns the first element from the underlying ordered collection. The returned element is removed from the underlying ordered collection.

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