/******************************************************************************
Priority Queue
----------------------------------------------------
Copyright (c) Gunnar Gotshalks. All Rights Reserved.
Permission to use, copy, modify, and distribute this software
and its documentation for NON-COMMERCIAL purposes and
without fee is hereby granted.
*******************************************************************************/
package FlexOr.container;
import java.util.Enumeration;
/**
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).
@author Gunnar Gotshalks
@version 1.0 1999 Jan 16
@see SLList
@see Sequence
@see Container
*/
public class PriorityQueue extends Queue {
/**
Default constructor. Sets the defaultPriority to 0; The priority
comparison for larger integers to have higher priority.
@param capacity The maximum number of elements that can be stored.
@exception TooSmallException when capacity is < 2.
*/
public PriorityQueue(int capacity) {
if (capacity < 2) throw new TooSmallException();
// comparison = new PriorityItemGreaterThan();
// equalsTo = new PriorityItemEqual();
container = new Heap(capacity, new PriorityItemGreaterThan(),
new PriorityItemEqual());
DefaultPriority = 0;
}
/** Set all PriorityQueue parameters.
@param capacity The maximum number of elements that can be stored.
@param 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.
@param defaultPriority Determine priority level for default add.
@exception TooSmallException when capacity is < 2.
*/
public PriorityQueue(int capacity,
boolean highNumberhighPriority,
int defaultPriority) {
if (capacity < 2) throw new TooSmallException();
BinaryPredicate comparison;
if (highNumberhighPriority)
comparison = new PriorityItemGreaterThan();
else comparison = new PriorityItemLessThan();
container = new Heap(capacity, comparison, new PriorityItemEqual());
DefaultPriority = defaultPriority;
}
/*******************************************************************************
Defining the component objects
*******************************************************************************/
/** The queue storage area */
protected final int DefaultPriority;
/** Keep track of which serial number to use next. Mut be defined here as
Java does not permit static variables in inner classes -- Why not, a class is
a class is a class. Inner has only to do with scoping. */
protected int currentSerialNumber = 0;
/*******************************************************************************
Access Methods -- need to override some Queue methods as PriorityQueues deal
with Items.
*******************************************************************************/
/** 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
*/
synchronized public boolean contains(Object obj) {
Enumeration