<> <> <> <> <<>> 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 { <> 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; <> 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] ~ { 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]]; }; Empty: PUBLIC PROC [heap: Queue] RETURNS [empty: BOOL _ FALSE] ~ { RETURN [heap.size = 0]; }; <> <<>> 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.