PriorityQueue.mesa
Copyright Ó 1985, 1986, 1991 by Xerox Corporation. All rights reserved.
Russ Atkinson, February 5, 1985 11:50:13 am PST
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.