<<>> <> <> <> <> <> <> <> <> DIRECTORY PriorityQueue; PriorityQueueImpl: CEDAR MONITOR LOCKS pq USING pq: Ref EXPORTS PriorityQueue = BEGIN OPEN PriorityQueue; <> <> PQempty: PUBLIC ERROR = CODE; PQover: PUBLIC ERROR = CODE; IsPriorityQueue: PUBLIC PROC [ref: REF] RETURNS [BOOL] = { <<... returns TRUE iff the ref resulted from a Create operation>> WITH ref SELECT FROM pq: Ref => RETURN [TRUE]; ENDCASE => RETURN [FALSE]; }; Create: PUBLIC PROC [pred: SortPred, data: REF Ź NIL] RETURNS [Ref] = { <<... creates a new priority queue with given sorting predicate>> pq: Ref Ź NEW[Rep Ź [pred: pred, data: data, size: 0, seq: NIL]]; RETURN [pq]; }; Predict: PUBLIC PROC [size: INT, pred: SortPred, data: REF Ź NIL] RETURNS [Ref] = { <<... is just like create, but also uses a predicted size>> pq: Ref Ź Create[pred, data]; IF size > MaxSize THEN size Ź MaxSize; IF size > 0 THEN { seq: Seq Ź NEW[SeqRep[size+1]]; pq.seq Ź seq; }; pq.size Ź 0; RETURN [pq]; }; Top: PUBLIC ENTRY PROC [pq: Ref] RETURNS [Item] = { <> IF pq.size = 0 THEN RETURN WITH ERROR PQempty; RETURN [pq.seq[1]]; }; Size: PUBLIC ENTRY PROC [pq: Ref] RETURNS [INT] = { <> RETURN [pq.size]; }; Empty: PUBLIC ENTRY PROC [pq: Ref] RETURNS [BOOL] = { <> RETURN [pq.size = 0]; }; Insert: PUBLIC ENTRY PROC [pq: Ref, item: Item] = { <<... inserts new item into the queue (signal PQover if resulting size goes over MaxSize)>> < NULL; >> size: NAT Ź pq.size; -- figure out new size a: Seq Ź pq.seq; -- grab the descriptor pred: SortPred Ź pq.pred; -- and the predicate data: REF Ź pq.data; -- and the predicate's data space: NAT Ź IF a = NIL THEN 0 ELSE a.space; maxCard: NAT = MaxSize; -- to aid the poor little compiler <> size Ź size + 1; IF size >= MaxSize THEN RETURN WITH ERROR PQover; <> IF size >= space THEN { seq: Seq Ź NIL; IF space = 0 THEN space Ź 1; SELECT space FROM < 2048 => space Ź space + space; < maxCard-1024 => space Ź space + 1024; ENDCASE => space Ź MaxSize; seq Ź NEW[SeqRep[space]]; FOR i: NAT IN [1..size) DO seq[i] Ź a[i]; ENDLOOP; pq.seq Ź a Ź seq; }; { <> son: NAT Ź size; dad: NAT Ź son/2; WHILE dad > 0 AND pred[item, a[dad], data] DO <> a[son] Ź a[dad]; son Ź dad; dad Ź son/2; ENDLOOP; a[son] Ź item; -- finally insert the new item pq.size Ź size; -- also update the size }; }; Remove: PUBLIC ENTRY PROC [pq: Ref] RETURNS [Item] = { <<... removes "best" item from queue (signal PQempty if empty)>> < NULL;>> size: NAT Ź pq.size; -- current size of pq a: Seq Ź pq.seq; -- desc to real stuff best: Item Ź NIL; -- holder for best item item: Item Ź NIL; -- holder for moving item pred: SortPred Ź pq.pred; -- comparison predicate data: REF Ź pq.data; -- and the predicate's data IF size = 0 THEN RETURN WITH ERROR PQempty; <> best Ź a[1]; -- remember best item item Ź a[size]; -- get moving item a[size] Ź NIL; size Ź size - 1; -- new size of pq pq.size Ź size; -- also update size in pq IF size = 0 THEN RETURN [best]; <> { dad: NAT Ź 1; -- current index for moving item maxdad: NAT Ź size / 2; -- highest index for father item WHILE dad <= maxdad DO son: NAT Ź dad + dad; sonItem: Item Ź a[son]; IF son < size THEN { <> nson: NAT Ź son + 1; nsonItem: Item Ź a[nson]; IF pred[nsonItem, sonItem, data] THEN { son Ź nson; sonItem Ź nsonItem; }; }; IF pred[item, sonItem, data] THEN EXIT; a[dad] Ź sonItem; dad Ź son; ENDLOOP; a[dad] Ź item; }; <> RETURN [best]; }; Copy: PUBLIC ENTRY PROC [pq: Ref] RETURNS [Ref] = { <<... returns copy of queue>> ENABLE UNWIND => NULL; size: NAT Ź pq.size; npq: Ref Ź Predict[size, pq.pred, pq.data]; src: Seq Ź pq.seq; dst: Seq Ź npq.seq; FOR i: NAT IN [1..size) DO dst[i] Ź src[i]; ENDLOOP; npq.size Ź size; RETURN [npq]; }; END.