PriorityQueueImpl.mesa
Copyright © 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.
DIRECTORY
PriorityQueue;
PriorityQueueImpl: CEDAR MONITOR LOCKS pq USING pq: Ref
EXPORTS PriorityQueue
= BEGIN OPEN PriorityQueue;
The following invariant must be maintained:
for all i in [2..Size]: pred[seq[i/2], seq[i]]
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] = {
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: Ref] RETURNS [INT] = {
return the number of items in the queue
ENABLE UNWIND => NULL;
RETURN [pq.size];
};
Empty: PUBLIC ENTRY PROC [pq: Ref] RETURNS [BOOL] = {
return true if the queue is empty, false if not
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
overflow check (unfortunately, we can't get more than LAST[NAT] 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: NAT 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: NAT ← size;
dad: NAT ← 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: 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;
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: 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 {
must find better of the two sons
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 the saved best 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.