-- 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^];
  };

}.