-- 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.