-- PriorityQueue.mesa
-- Russ Atkinson, August 27, 1982 11:52 am

-- A PriorityQueue is a mutable collection of items such that one can insert items in any order and retrieve them in a user-specified best-first order. Each priority queue is monitorized to protect against simultaneous access clashes.

PriorityQueue: CEDAR DEFINITIONS = BEGIN

-- Public types
Ref: TYPE = REF Rep;
Rep: TYPE;
Item: TYPE = REF;

SortPred: TYPE = PROC [x: Item, y: Item, data: REF ← NIL] RETURNS [BOOL];
-- type or sorting predicate
-- a sorting predicate should return TRUE if x is "better" than y
-- data will be as given to Create or Predict

MaxSize: INT = LAST[CARDINAL]-1; -- largest size permitted in current implementation
PQempty: ERROR; -- empty priority queue error
PQover: ERROR; -- priority queue overflow

-- Operations on PriorityQueueRef objects.

Create: -- create a new priority queue with given sorting predicate
PROC [pred: SortPred, data: REF ← NIL] RETURNS [Ref];

Predict: -- like create, but also uses a predicted size
PROC [size: INT, pred: SortPred, data: REF ← NIL] RETURNS [Ref];

Top: -- return "best" element in queue (signal PQempty if empty)
PROC [pq: Ref] RETURNS [Item];

Size: -- return number of items in queue
PROC [pq: Ref] RETURNS [INT];

Empty: -- return true if queue is empty, false if not empty
PROC [pq: Ref] RETURNS [BOOL];

Insert: -- insert new item into the queue
PROC [pq: Ref, item: Item];

Remove: -- remove "best" item from queue (signal PQempty if empty)
PROC [pq: Ref] RETURNS [Item];

Copy: -- return copy of queue
PROC [pq: Ref] RETURNS [Ref];

END.