HeapImpl.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
Greene, September 19, 1986 6:50:43 pm PDT
Russ Atkinson (RRA) September 23, 1986 2:43:30 pm PDT
DIRECTORY
Basics USING [CompareINT, Comparison],
Heap USING [CompareEvents, Event],
HeapPrivate USING [QueueBody, QueueRec];
HeapImpl:
CEDAR
PROGRAM
IMPORTS Basics
EXPORTS Heap = BEGIN OPEN Heap, HeapPrivate;
Queue: TYPE = REF QueueRec;
QueueRec: PUBLIC TYPE = HeapPrivate.QueueRec;
CreateQueue:
PUBLIC
PROC [compare: CompareEvents, conjectureSize:
CARDINAL ← 64]
RETURNS [heap: Queue] ~ {
heap ← NEW[QueueRec ← [compare: compare]];
heap.array ← NEW[QueueBody[PowerOf2[conjectureSize]]];
};
ChangeCompareProc:
PUBLIC
PROC [heap: Queue, compare: CompareEvents] ~ {
heap.compare ← compare;
};
PowerOf2:
PROC [in:
CARDINAL]
RETURNS [out:
CARDINAL ← 64] ~ {
UNTIL out >= in
DO
out ← out * 2;
ENDLOOP;
IF out > 32000 THEN out ← 32758;
};
InsertEvent:
PUBLIC
PROC [heap: Queue, event: Event] ~ {
oldSize: CARDINAL = heap.size;
array: REF QueueBody ← heap.array;
pL: Event ← event;
pos: CARDINAL ← heap.size ← oldSize + 1;
IF oldSize = array.max
THEN {
Must expand the array
newMax: NAT ← IF array.max < 16000 THEN array.max*2 ELSE array.max*2 - 10;
new: REF QueueBody ← NEW[QueueBody[newMax]];
IF newMax <= oldSize
THEN
ERROR;
In this case we really can't expand safely!
FOR i: CARDINAL IN [0..oldSize) DO new.data[i] ← array.data[i]; ENDLOOP;
heap.array ← array ← new;
};
Now bubble the event towards the "top" of the heap (decreasing indexes).
UNTIL pos = 1
DO
pH: Event ← array.data[pos/2 - 1];
IF heap.compare[pL, pH] = less THEN EXIT;
array.data[pos - 1] ← pH;
pos ← pos / 2;
ENDLOOP;
array.data[pos - 1] ← pL;
};
NextEvent:
PUBLIC
PROC [heap: Queue]
RETURNS [event: Event ←
NIL] ~ {
array: REF QueueBody ← heap.array;
size: CARDINAL = heap.size;
SELECT size
FROM
0 =>
If empty, the convention is to return NIL.
RETURN [NIL];
1 => {
The one element case is dead easy.
event ← array.data[0];
heap.size ← 0;
};
2 => {
The two element case also requires no comparisons!
event ← array.data[0];
array.data[0] ← array.data[1];
heap.size ← 1;
};
ENDCASE => {
There are at least three elements. The
lower: CARDINAL ← 2;
pos: CARDINAL ← 1;
event ← array.data[0];
Now move the hole "down" in the heap (increasing indexes).
UNTIL lower >= size
DO
eL: Event = array.data[lower-1];
eR: Event = array.data[lower];
IF heap.compare[eL, eR] # greater
THEN {
array.data[pos - 1] ← eR;
pos ← lower + 1;
}
ELSE {
array.data[pos - 1] ← eL;
pos ← lower;
};
lower ← pos*2;
ENDLOOP;
heap.size ← size - 1;
SELECT
TRUE
FROM
lower = size =>
array.data[pos - 1] ← array.data[lower - 1];
pos # size => {
Now bubble the event towards the "top" of the heap.
pL: Event ← array.data[size - 1];
UNTIL pos = 1
DO
pH: Event ← array.data[pos/2 - 1];
IF heap.compare[pL, pH] = less THEN EXIT;
array.data[pos - 1] ← pH;
pos ← pos / 2;
ENDLOOP;
array.data[pos - 1] ← pL;
};
ENDCASE;
};
};
PeekNextEvent:
PUBLIC
PROC [heap: Queue]
RETURNS [event: Event] ~ {
RETURN [IF heap.size = 0 THEN NIL ELSE heap.array.data[0]];
};
Empty:
PUBLIC
PROC [heap: Queue]
RETURNS [empty:
BOOL ←
FALSE] ~ {
RETURN [heap.size = 0];
};
Testing routines
RefIntCompareProc: CompareEvents = {
r1: REF INT ← NARROW[e1];
r2: REF INT ← NARROW[e2];
RETURN [Basics.CompareINT[r1^, r2^]];
};
InsertInt:
PROC [heap: Queue, int:
INT] = {
ref: REF INT ← NEW[INT ← int];
InsertEvent[heap, ref];
};
END.