PriorityQueue.mesa
Copyright Ó 1985, 1986, 1991 by Xerox Corporation. All rights reserved.
Russ Atkinson, February 5, 1985 11:50:13 am PST
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 = MONITORED RECORD [pred: SortPred, data: REF, size: NAT, seq: Seq];
Seq: TYPE = REF SeqRep;
SeqRep: TYPE = RECORD [elements: SEQUENCE space: NAT OF Item];
Item: TYPE = REF;
SortPred: TYPE = PROC [x: Item, y: Item, data: REF ¬ NIL] RETURNS [BOOL];
type or sorting predicate
a SortPred should return TRUE if x is "better" than y
data will be same ref as given to Create or Predict
MaxSize: NAT = 3*(LAST[NAT]/4);
largest size permitted in current implementation
PQempty: ERROR;
empty priority queue error
PQover: ERROR;
priority queue overflow
Operations on PriorityQueueRef objects.
Create: PROC [pred: SortPred, data: REF ¬ NIL] RETURNS [Ref];
... creates a new priority queue with given sorting predicate
Predict: PROC [size: INT, pred: SortPred, data: REF ¬ NIL] RETURNS [Ref];
... is just like create, but also uses a predicted size. If size > MaxSize, then MaxSize is used instead (the error, if any, will be detected by Insert).
Top: PROC [pq: Ref] RETURNS [Item];
... returns "best" element in queue (signal PQempty if empty)
Size: PROC [pq: Ref] RETURNS [INT];
... returns number of items in queue
Empty: PROC [pq: Ref] RETURNS [BOOL];
... returns true if queue is empty, false if not empty
Insert: PROC [pq: Ref, item: Item];
... inserts new item into the queue (signal PQover if resulting size goes over MaxSize)
Remove: PROC [pq: Ref] RETURNS [Item];
... removes "best" item from queue (signal PQempty if empty)
Copy: PROC [pq: Ref] RETURNS [Ref];
... returns copy of queue
END.