<> <> <> <> <> <> <> 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] = { <> ENABLE UNWIND => NULL; IF pq.size = 0 THEN RETURN WITH ERROR PQempty; RETURN [pq.seq[1]]; }; Size: PUBLIC ENTRY PROC [pq: Ref] RETURNS [INT] = { <> ENABLE UNWIND => NULL; RETURN [pq.size]; }; Empty: PUBLIC ENTRY PROC [pq: Ref] RETURNS [BOOL] = { <> ENABLE UNWIND => NULL; 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)>> ENABLE UNWIND => 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 <> IF size = MaxSize THEN RETURN WITH ERROR PQover; size _ size + 1; <> 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)>> ENABLE UNWIND => 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.