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] = { WITH ref SELECT FROM pq: Ref => RETURN [TRUE]; ENDCASE => RETURN [FALSE]; }; Create: PUBLIC PROC [pred: SortPred, data: REF _ NIL] RETURNS [Ref] = { 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] = { 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] = { 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] = { 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] = { 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. ˆPriorityQueueImpl.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Russ Atkinson, February 5, 1985 11:47:32 am PST 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. The following invariant must be maintained: for all i in [2..Size]: pred[seq[i/2], seq[i]] ... returns TRUE iff the ref resulted from a Create operation ... creates a new priority queue with given sorting predicate ... is just like create, but also uses a predicted size return the "best" item without modifying the queue return the number of items in the queue return true if the queue is empty, false if not ... inserts new item into the queue (signal PQover if resulting size goes over MaxSize) overflow check (unfortunately, we can't get more than LAST[NAT] words!) Must first check for room in array. If there is not enough room, then allocate new storage, copy, and free the old storage. Insert item by shuffling items down until invariant holds (assuming that a[son] will hold item). item is better than a[dad], so shuffle a[dad] down ... removes "best" item from queue (signal PQempty if empty) Remove top item from the array and prepare to move bottom item Restore the invariant by moving the item down (better items move up) must find better of the two sons Return the saved best item ... returns copy of queue Κž˜codešœ™Kšœ Οmœ1™™>Kšœ ˜,Kšœ ˜)Kšœ žœ˜Kšœ ˜(Kšœ ˜0Kšžœ žœžœ˜K˜KšœD™Dšœ˜Kšœžœ  ˜:Kšœžœ  ˜:šžœž˜Kšœžœ ˜K˜šžœ žœ˜Kšœ ™ Kšœžœ ˜K˜šžœžœ˜'K˜ K˜K˜—K˜—Kšžœžœžœ˜'K˜K˜ Kšžœ˜—K˜K˜K˜—Kšœ™Kšžœ˜K˜K˜—š Ÿœžœžœžœ žœ ˜3Kšœ™Kšžœžœžœ˜Kšœžœ ˜K˜+K˜K˜šžœžœžœ ž˜K˜Kšžœ˜—K˜Kšžœ˜ K˜K˜—Kšžœ˜K˜K˜——…— r˜