org.jutil.java.collections
Interface PriorityQueue

All Known Implementing Classes:

SkipListPQ, BinomialHeap

public interface PriorityQueue

A PriorityQueue is a container of objects with an associated priority/ordering, that allows the retrieval of the element with the smallest value. The order of the elements is determined by a Comparator.

Version:

$Revision: 1.2 $

Author:

Tom Schrijvers, Marko van Dooren

Method Summary

void	add(java.lang.Object element) public behavior pre element != null; post nbExplicitOccurrences(element) == \old(nbExplicitOccurrences(element)) + 1; Add the given object to this PriorityQueue.
void	clear() public behavior post isEmpty(); Remove all elements.
java.util.Comparator	getComparator() public behavior post \result != null; Return the comparator that is used to determine the order of the elements.
boolean	isEmpty() public behavior post \result == (size() == 0); Check whether or not this PriorityQueue is empty.
java.lang.Object	min() public behavior pre ! isEmpty(); // The result is in this PriorityQueue. post nbExplicitOccurrences(\result) > 0; // The result is the minimum element. post (\forall Object o; nbExplicitOccurrences(o) > 0; ExtendedComparator.ensureExtended(getComparator()).notGreater(o,\result)); Return the smallest object in this PriorityQueue.
int	nbExplicitOccurrences(java.lang.Object element) public behavior post \result >= 0; Return the number of times the given element itself is in this PriorityQueue.
java.lang.Object	pop() public behavior pre ! isEmpty(); // The minimum is returned. post \result == \old(min()); // The instance that is returned, is removed. post nbExplicitOccurrences(\result) == \old(nbExplicitOccurrences(\result)) - 1; Return the smallest object in this PriorityQueue and remove it.
int	size() public behavior post \result == (\sum Object o; ; nbExplicitOccurrences(o)); Return the size of this PriorityQueue.

Method Detail

add

public void add(java.lang.Object element)

public behavior

pre element != null;

post nbExplicitOccurrences(element) == \old(nbExplicitOccurrences(element)) + 1;
Add the given object to this PriorityQueue.

Parameters:

element - The object to be added.

min

public java.lang.Object min()

public behavior

pre ! isEmpty();

// The result is in this PriorityQueue.
post nbExplicitOccurrences(\result) > 0;
// The result is the minimum element.
post (\forall Object o; nbExplicitOccurrences(o) > 0;
ExtendedComparator.ensureExtended(getComparator()).notGreater(o,\result));
Return the smallest object in this PriorityQueue.

pop

public java.lang.Object pop()

public behavior

pre ! isEmpty();

// The minimum is returned.
post \result == \old(min());
// The instance that is returned, is removed.
post nbExplicitOccurrences(\result) == \old(nbExplicitOccurrences(\result)) - 1;
Return the smallest object in this PriorityQueue and remove it.

isEmpty

public boolean isEmpty()

public behavior

post \result == (size() == 0);
Check whether or not this PriorityQueue is empty.

size

public int size()

public behavior

post \result == (\sum Object o; ; nbExplicitOccurrences(o));
Return the size of this PriorityQueue.

getComparator

public java.util.Comparator getComparator()

public behavior

post \result != null;
Return the comparator that is used to determine the order of the elements.

nbExplicitOccurrences

public int nbExplicitOccurrences(java.lang.Object element)

public behavior

post \result >= 0;
Return the number of times the given element itself is in this PriorityQueue.

Parameters:

element - The object of which the number of explicit occurrences is requested.

clear

public void clear()

public behavior

post isEmpty();
Remove all elements.