<<>> <> <> <> <> < CompareInt.>> <<>> DIRECTORY Heap, HeapPrivate USING [QueueBody, QueueRec], Rope; HeapImpl: CEDAR PROGRAM EXPORTS Heap = BEGIN OPEN Heap, HeapPrivate; Queue: TYPE = REF QueueRec; QueueRec: PUBLIC TYPE = HeapPrivate.QueueRec; Overflow: PUBLIC ERROR = CODE; CreateQueue: PUBLIC PROC [compare: CompareEvents, conjectureSize: CARDINAL Ź 64, reusable: Queue Ź NIL] RETURNS [heap: Queue] ~ { IF reusable # NIL THEN { heap Ź reusable; heap.compare Ź compare } ELSE { heap Ź NEW[QueueRec Ź [compare: compare]]; heap.array Ź NEW[QueueBody[PowerOf2[conjectureSize]]]; }; }; PowerOf2: PROC [in: CARDINAL] RETURNS [out: CARDINAL Ź 64] ~ { UNTIL out >= in DO out Ź out * 2; ENDLOOP; IF out > largestHeap THEN out Ź largestHeap; }; largestHeap: NAT = 10000000; --Was 32758 in the D-world InsertEvent: PUBLIC PROC [heap: Queue, event: Event] ~ TRUSTED { oldSize: CARDINAL = heap.size; array: REF QueueBody Ź heap.array; pL: Event Ź event; pos: CARDINAL Ź heap.size Ź oldSize + 1; IF oldSize = array.max THEN { <> newMax: NAT; new: REF QueueBody; IF array.max = largestHeap THEN {heap.size Ź oldSize; ERROR Overflow}; newMax Ź IF array.max < largestHeap/2 THEN array.max*2 ELSE largestHeap; new Ź NEW[QueueBody[newMax]]; FOR i: CARDINAL IN [0..oldSize) DO new.data[i] Ź array.data[i]; ENDLOOP; heap.array Ź array Ź new; }; <> 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] ~ TRUSTED { array: REF QueueBody Ź heap.array; size: CARDINAL = heap.size; SELECT size FROM 0 => <> RETURN [NIL]; 1 => { <> event Ź array.data[0]; heap.size Ź 0; }; 2 => { <> event Ź array.data[0]; array.data[0] Ź array.data[1]; heap.size Ź 1; }; ENDCASE => { <> lower: CARDINAL Ź 2; pos: CARDINAL Ź 1; event Ź array.data[0]; <> 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 => { <> 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]]; }; Erase: PUBLIC PROC [heap: Queue] ~ { heap.size Ź 0; }; Empty: PUBLIC PROC [heap: Queue] RETURNS [empty: BOOL Ź FALSE] ~ { RETURN [heap.size = 0]; }; GetSize: PUBLIC PROC [heap: Queue] RETURNS [CARDINAL] ~ { RETURN [heap.size]; }; <> <<>> <> <> <> <> <<};>> <<>> <> <> <> <<};>> <<>> <> <> <> <<>> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <<}>> <<>> END.