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. hHeapImpl.mesa Copyright c 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 Must expand the array In this case we really can't expand safely! Now bubble the event towards the "top" of the heap (decreasing indexes). If empty, the convention is to return NIL. The one element case is dead easy. The two element case also requires no comparisons! There are at least three elements. The Now move the hole "down" in the heap (increasing indexes). Now bubble the event towards the "top" of the heap. Testing routines ΚΫ˜codešœ ™ Kšœ Οmœ1™šžœ ž˜K˜Kšžœ˜—Kšžœ žœ ˜ K˜—K˜šŸ œžœžœ ˜8Kšœ žœ ˜Kšœžœ˜"Kšœ˜Kšœžœ˜(šžœžœ˜K™Kš œžœžœžœ žœ˜JKšœžœ žœ˜,šžœžœžœ˜ K™+—Kš žœžœžœžœžœ˜HKšœ˜Kšœ˜—K™Hšžœ ž˜Kšœ"˜"Kšžœžœžœ˜)Kšœ˜K˜Kšžœ˜—Kšœ˜K˜K˜—š Ÿ œžœžœžœžœ˜EKšœžœ˜"Kšœžœ ˜šžœž˜šœ˜Kšœ&žœ™*Kšžœžœ˜ —˜K™"Kšœ˜Kšœ˜K˜—˜K™2Kšœ˜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˜šŸ œžœžœžœ˜CKš žœžœžœžœžœ˜;K˜—K˜š Ÿœžœžœžœ žœžœ˜BKšžœ˜K˜—K˜™K™šŸœ˜$Kšœžœžœžœ˜Kšœžœžœžœ˜Kšžœ˜%K˜K˜—šŸ œžœžœ˜+Kš œžœžœžœžœ˜Kšœ˜K˜—K™—Kšžœ˜K˜K˜—…— φ9