-- CGAreaImpl.mesa
-- Last edit by Doug Wyatt, August 31, 1982 6:44 pm

-- Based on PriorityQueueImpl by Russ Atkinson - October 2, 1980 3:13 PM

-- 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.

DIRECTORY
CGArea,
CGStorage USING [pZone, qZone],
GraphicsBasic USING [Box, Trap, Vec],
Real USING [CompareREAL];

CGAreaImpl: CEDAR PROGRAM
IMPORTS CGStorage, Real
EXPORTS CGArea = { OPEN CGArea, GraphicsBasic;

repZone: ZONE = CGStorage.qZone;
boxZone: ZONE = CGStorage.qZone;
dataZone: ZONE = CGStorage.pZone; -- use prefixed zone for sequences
trapZone: ZONE = CGStorage.qZone;

nullBox: Box = [0,0,0,0];

-- The following invariant must be maintained:
-- for all i in [2..Size]: Pred[Stuff[i/2], Stuff[i]]

Error: PUBLIC ERROR[type: ErrorType] = CODE;

-- Sorting predicate for Items
Pred: PROC[a,b: Item] RETURNS[BOOLEAN] = INLINE {
RETURN[SELECT Real.CompareREAL[a.ybot,b.ybot] FROM
less => TRUE, greater => FALSE, equal => a.xbotL<=b.xbotL,
ENDCASE => ERROR] };

New: PUBLIC PROC [size: NAT] RETURNS [Ref] = {
-- create an empty priority queue, to hold size items
self: Ref ← repZone.NEW[Rep ← [size: 0, box: NIL, data: NIL]];
IF size = 0 THEN size ← 4 ELSE size ← size + 1;
self.box ← boxZone.NEW[Box ← nullBox];
self.data ← dataZone.NEW[DataRep[size]];
RETURN[self];
}; -- create

NextY: PUBLIC PROC [self: Ref] RETURNS [REAL] = {
-- return the lowest y of the "best" item in the queue
IF self.size = 0 THEN ERROR Error[emptyQueue];
RETURN [self.data[1].ybot];
}; -- nexty

InsertLine: PUBLIC PROC [self: Ref, p,q: Vec] = {
IF p.y<=q.y THEN Insert[self,[
ybot: p.y, xbotL: p.x, xbotR: p.x,
ytop: q.y, xtopL: q.x, xtopR: q.x,
line: TRUE]]
ELSE Insert[self,[
ybot: q.y, xbotL: q.x, xbotR: q.x,
ytop: p.y, xtopL: p.x, xtopR: p.x,
line: TRUE]]
};

Insert: PUBLIC PROC [self: Ref, trap: Trap] = {
-- insert a new item into the queue
size: NAT ← self.size + 1; -- figure out new size
a: Data ← self.data; -- grab the descriptor
space: NAT ← IF a = NIL THEN 0 ELSE a.space;

-- 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 {
data: Data ← NIL;
IF space = 0 THEN space ← 1;
IF space > 2048 THEN space ← space + 1024 ELSE space ← 2*space;
data ← NEW[DataRep[space]];
FOR i: NAT IN [1..size) DO
data[i] ← a[i];
ENDLOOP;
self.data ← a ← data;
};

-- Insert item by shuffling items down until invariant holds
-- (assuming that a[son] will hold item).
{ son: NAT ← size;
dad: NAT ← son/2;
item: Item ← a[son];
IF item=NIL THEN item ← a[son] ← trapZone.NEW[Trap];
item^ ← trap; -- store new item
WHILE dad > 0 AND Pred[item, a[dad]] DO
-- item is better than a[dad], so shuffle a[dad] down
a[son] ← a[dad];
a[dad] ← item;
son ← dad;
dad ← son/2;
ENDLOOP;
self.size ← size; -- update the size
};

-- update bounding box
{ box: REF Box ← self.box;
IF size = 1 THEN { -- first item
box.xmin ← MIN[trap.xbotL,trap.xtopL];
box.xmax ← MAX[trap.xbotR,trap.xtopR];
box.ymin ← trap.ybot;
box.ymax ← trap.ytop }
ELSE {
box.xmin ← MIN[box.xmin,trap.xbotL,trap.xtopL];
box.xmax ← MAX[box.xmax,trap.xbotR,trap.xtopR];
box.ymin ← MIN[box.ymin,trap.ybot];
box.ymax ← MAX[box.ymax,trap.ytop] };
};
}; -- insert

Remove: PUBLIC PROC [self: Ref] RETURNS [Trap] = {
-- remove the "best" item in the queue
size: NAT ← self.size; -- current size of queue
a: Data ← self.data; -- desc to real stuff
best: Item ← NIL; -- holder for best item
item: Item ← NIL; -- holder for moving item
IF size = 0 THEN ERROR Error[emptyQueue];

-- 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] ← best;
size ← size - 1; -- new size of queue
self.size ← size; -- also update size in self
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
-- determine if son replaces dad
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] THEN { son ← nson; sonItem ← nsonItem };
};
IF Pred[item, sonItem] THEN EXIT;
a[dad] ← sonItem;
dad ← son;
ENDLOOP;
a[dad] ← item;
};

-- Return the saved best item
RETURN [best^];
};

}.