

PriorityQueue: CEDAR DEFINITIONS = BEGIN


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];

MaxSize: NAT = 3*(LAST[NAT]/4);
PQempty: ERROR;
PQover: ERROR;


Create: PROC [pred: SortPred, data: REF м NIL] RETURNS [Ref];

Predict: PROC [size: INT, pred: SortPred, data: REF м NIL] RETURNS [Ref];

Top: PROC [pq: Ref] RETURNS [Item];

Size: PROC [pq: Ref] RETURNS [INT];

Empty: PROC [pq: Ref] RETURNS [BOOL];

Insert: PROC [pq: Ref, item: Item];

Remove: PROC [pq: Ref] RETURNS [Item];

Copy: PROC [pq: Ref] RETURNS [Ref];

END.
   ╝  
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.
Public types
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
largest size permitted in current implementation
empty priority queue error
priority queue overflow
Operations on PriorityQueueRef objects.
... creates a new priority queue with given sorting predicate
... 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).
... returns "best" element in queue (signal PQempty if empty)
... returns number of items in queue
... returns true if queue is empty, false if not empty
... inserts new item into the queue (signal PQover if resulting size goes over MaxSize)
... removes "best" item from queue (signal PQempty if empty)
... returns copy of queue
Э╩Н  ХNewlineDelimiter
Ц(cedarcode) styleЩ codeЪЬЩKЪЬ
╧eЬ=ЩHKЪЬ0Щ0ЧKШ KЪЬшЩшKШ KЪ╧nЬ╧kЬЯЬЯШ(KШ ЪЬЩKШ KЪЬЯЬЯЬШKЪЬЯЬЯ	ЬЯЬЯЬЯЬШNKЪЬЯЬЯЬШKЪЬЯЬЯЬЯЬЯЬЯЬШ>KЪЬЯЬЯЬШKШ ЪЮЬЯЬЯЬЯЬЯЬЯЬЯЬШIKЪЬЩKЪЬЯЬЩ5KЪЬ3Щ3ЧKШ ЪЬ	ЯЬЯЬЯЬШKЪЬ0Щ0ЧЪЮЬЯЬШKЪЬЩЧЪЮЬЯЬШKЪЬЩЧKШ ЧЪЬ'Щ'KШ Ъ
ЮЬЯЬЯЬЯЬЯЬШ=KЪЬ=Щ=KШ ЧЪЮЬЯЬЯЬЯЬЯЬЯЬШIKЪЬЪЩЪKШ ЧЪЮЬЯЬЯЬШ#KЪЬ=Щ=KШ ЧЪЮЬЯЬЯЬЯЬШ#KЪЬ$Щ$KШ ЧЪЮЬЯЬЯЬЯЬШ%KЪЬ6Щ6KШ ЧЪЮЬЯЬШ#KЪЬWЩWKШ ЧЪЮЬЯЬЯЬШ&KЪЬ<Щ<KШ ЧЪЮЬЯЬЯЬШ#KЪЬЩKШ ЧKЪЯЬШЧЧ ЕЧ    ·  
C  