-- PriorityQueueImpl.mesa -- Russ Atkinson, August 27, 1982 12:28 pm -- Paul Rovner, May 31, 1983 11:53 am -- This module defines the implementation for priority queues as described by PriorityQueue. A PriorityQueue.Ref object is created with a given sorting predicate. Inserting an item costs O(log n), and removing the 'best' item costs O(log n), where n is the number of items in the queue, and 'best' is determined by the sorting predicate (if Pred(X, Y), then X is 'better' than Y). This enables a non-stable, non-in-place, sort costing O(n log n) to be simply written. -- A priority queue is a balanced binary tree where every element is 'better' than its descendents, and the minimum depth of the tree differs from the maximum depth by at most one. The tree is implemented by keeping the elements in an array, with the left son of a[i] in a[i*2], and the right son in a[i*2+1]. The root of the tree, a[1], is the 'best' element. Note that in this implementation a[0] is never used. -- The items to be inserted or deleted are represented via references to the objects, so there is no dependence on the item type. Of course, we pay for this at runtime, but this isn't CLU. A PriorityQueue.Ref variable is actually a reference to counted storage. DIRECTORY PriorityQueue; PriorityQueueImpl: CEDAR MONITOR LOCKS pq USING pq: Cvt EXPORTS PriorityQueue = BEGIN OPEN PriorityQueue; -- The following invariant must be maintained: -- for all i in [2..Size]: Pred[Stuff[i/2], Stuff[i]] PQempty: PUBLIC ERROR = CODE; PQover: PUBLIC ERROR = CODE; Seq: TYPE = REF SeqRep; SeqRep: TYPE = RECORD [elements: SEQUENCE space: CARDINAL OF Item]; Cvt: TYPE = REF Rep; Rep: PUBLIC TYPE = MONITORED RECORD [pred: SortPred, data: REF, size: CARDINAL, seq: Seq]; Create: PUBLIC PROC [pred: SortPred, data: REF _ NIL] RETURNS [Ref] = { -- create a priority queue object, initially empty pq: Cvt _ NEW[Rep _ [pred: pred, data: data, size: 0, seq: NIL]]; RETURN [pq]; }; Predict: PUBLIC PROC [size: INT, pred: SortPred, data: REF _ NIL] RETURNS [Cvt] = -- create an empty priority queue, to hold size items {pq: Cvt _ Create[pred, data]; IF size > MaxSize THEN RETURN WITH ERROR PQover; IF size <= 0 THEN size _ 4 ELSE size _ size + 1; {seq: Seq _ NEW[SeqRep[size]]; pq.size _ 0; pq.seq _ seq; RETURN [pq]}}; Top: PUBLIC ENTRY PROC [pq: Cvt] RETURNS [Item] = { -- return the "best" item without modifying the queue ENABLE UNWIND => NULL; IF pq.size = 0 THEN RETURN WITH ERROR PQempty; RETURN [pq.seq[1]]; }; Size: PUBLIC ENTRY PROC [pq: Cvt] RETURNS [INT] = { -- return the number of items in the queue ENABLE UNWIND => NULL; RETURN [pq.size]; }; Empty: PUBLIC ENTRY PROC [pq: Cvt] RETURNS [BOOL] = { -- return true if the queue is empty, false if not ENABLE UNWIND => NULL; RETURN [pq.size = 0]; }; Insert: PUBLIC ENTRY PROC [pq: Cvt, item: Item] = { -- insert a new item into the queue ENABLE UNWIND => NULL; size: CARDINAL _ 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: CARDINAL _ IF a = NIL THEN 0 ELSE a.space; maxCard: CARDINAL = MaxSize; -- to aid the poor little compiler -- overflow check -- unfortunately, we can't get more than LAST[CARDINAL] words! IF size = MaxSize THEN RETURN WITH ERROR PQover; size _ size + 1; -- Must first check for room in array. If there is not -- enough room, then allocate new storage, copy, and free -- the old storage. 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: CARDINAL IN [1..size) DO seq[i] _ a[i]; ENDLOOP; pq.seq _ a _ seq; }; -- Insert item by shuffling items down until invariant holds -- (assuming that a[son] will hold item). { son: CARDINAL _ size; dad: CARDINAL _ son/2; WHILE dad > 0 AND pred[item, a[dad], data] DO -- item is better than a[dad], so shuffle a[dad] down 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: Cvt] RETURNS [Item] = { -- remove the "best" item in the queue ENABLE UNWIND => NULL; size: CARDINAL _ 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; -- Remove top item from the array and prepare to move bottom item 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]; -- Restore the invariant by moving the item down -- (better items move up) { dad: CARDINAL _ 1; -- current index for moving item maxdad: CARDINAL _ size / 2; -- highest index for father item WHILE dad <= maxdad DO son: CARDINAL _ dad + dad; sonItem: Item _ a[son]; IF son < size THEN { -- must find better of the two sons nson: CARDINAL _ 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 the saved best item RETURN [best]; }; Copy: PUBLIC ENTRY PROC [pq: Cvt] RETURNS [Cvt] = { -- return a copy of the priority queue ENABLE UNWIND => NULL; size: CARDINAL _ pq.size; npq: Cvt _ Predict[size, pq.pred, pq.data]; src: Seq _ pq.seq; dst: Seq _ npq.seq; FOR i: CARDINAL IN [1..size) DO dst[i] _ src[i]; ENDLOOP; npq.size _ size; RETURN [npq]; }; END.