FlexOr.container
Class PriorityQueue

java.lang.Object
  FlexOr.container.Queue
      FlexOr.container.PriorityQueue

All Implemented Interfaces:

Container, java.lang.Cloneable

public class PriorityQueue
extends Queue

PriorityQueue extends Queue since it is a queue if all priorities are equal. A heap is used as the storage model as using a Sequence would make add O(size) in time or remove O(size) in time. The default add stores objects with a user specified DefaultPriority at PriorityQueue creation time. A new add method is provided to add objects with different priorities.

Using a PriorityQueue as a Queue is relatively inefficient as both add and remove are O(log(size)) in time instead of O(1).

Version:

1.0 1999 Jan 16

Author:

Gunnar Gotshalks

See Also:

SLList, Sequence, Container

Constructor Summary

PriorityQueue(int capacity)
Default constructor.

PriorityQueue(int capacity, boolean highNumberhighPriority, int defaultPriority)
Set all PriorityQueue parameters.

Method Summary

void	add(java.lang.Object obj) Add obj with DefaultPriority.
void	add(java.lang.Object obj, int priority) Add obj with a specific priority.
java.lang.Object	clone() Return a shallow copy of the queue.
boolean	contains(java.lang.Object obj) Determines whether a datum is in the tree irrespective of priority.
java.util.Enumeration<java.lang.Object>	elements() Returns an enumerator over the contents of the queue.
java.lang.Object	remove() Return the first element in the queue.

Methods inherited from class FlexOr.container.Queue

addWait, equals, isEmpty, isFull, removeAll, removeWait, size, toString

Methods inherited from class java.lang.Object

getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

PriorityQueue

public PriorityQueue(int capacity)

Default constructor. Sets the defaultPriority to 0; The priority comparison for larger integers to have higher priority.

Parameters:

capacity - The maximum number of elements that can be stored.

Throws:

TooSmallException - when capacity is < 2.

PriorityQueue

public PriorityQueue(int capacity,
                     boolean highNumberhighPriority,
                     int defaultPriority)

Set all PriorityQueue parameters.

Parameters:

capacity - The maximum number of elements that can be stored.

highNumberhighPriority - Determine whether larger integers mean higher or lower priority. Set to True if you want larger integers to be higher priority. Set to false if you want smaller integers to be higher priority.

defaultPriority - Determine priority level for default add.

Throws:

TooSmallException - when capacity is < 2.

Method Detail

contains

public boolean contains(java.lang.Object obj)

Determines whether a datum is in the tree irrespective of priority. O(size) due to linear search.

Requires: True
Ensures: contains(obj) => result = true
      not contains(obj) => result = false

Specified by:

contains in interface Container

Overrides:

contains in class Queue

elements

public java.util.Enumeration<java.lang.Object> elements()

Returns an enumerator over the contents of the queue.

Specified by:

elements in interface Container

Overrides:

elements in class Queue

Throws:

NoSuchElementException - when nextElement is called with an empty enumeration sequence.

add

public void add(java.lang.Object obj)

Add obj with DefaultPriority.

Requires: size < Capacity
Ensures: subsequence(DefaultPriority) = subsequence(DefaultPriority) ^ obj

Specified by:

add in interface Container

Overrides:

add in class Queue

Throws:

ContainerFullException - when container already contains Capacity elements.

add

public void add(java.lang.Object obj,
                int priority)

Add obj with a specific priority.

Requires: size < Capacity
Ensures: subsequence(priority) = subsequence(priority) ^ obj

Throws:

ContainerFullException - when container already contains Capacity elements.

remove

public java.lang.Object remove()

Return the first element in the queue.

Requires: isEmpty = false
Ensures: old sequence = obj ^ sequence

Specified by:

remove in interface Container

Overrides:

remove in class Queue

Throws:

ContainerEmptyException - when container is empty. elements.

clone

public java.lang.Object clone()

Return a shallow copy of the queue.

Requires: True
Ensures: result = copy of queue

Specified by:

clone in interface Container

Overrides:

clone in class Queue