-- CellInstPQImpl.mesa

-- A generic package to organize items
-- in a priority queue, sorted by increasing order of
-- Val.

-- written by E. McCreight, February 8, 1982  2:04 PM
-- last modified by E. McCreight, February 8, 1982  2:20 PM
-- customized by E. McCreight, February 8, 1982  3:46 PM

DIRECTORY
  CellInstPQ;

CellInstPQImpl: PROGRAM
  IMPORTS CellInstPQ
  EXPORTS CellInstPQ SHARES CellInstPQ =
  BEGIN OPEN CellInstPQ;

  CellInstPQUnderflow: PUBLIC SIGNAL = CODE;


  NewCellInstPQ: PUBLIC PROCEDURE[zone: UNCOUNTED ZONE,
    max: CARDINAL ← 50]
    RETURNS[PQHandle] =
    {RETURN[zone.NEW[PQObject ← [zone: zone, size: 0,
      s: zone.NEW[PQSeq[max]]]]]};


  DestroyCellInstPQ: PUBLIC PROCEDURE[p: PQHandle]
    RETURNS[PQHandle] =
    BEGIN
    zone: UNCOUNTED ZONE ← p.zone;
    zone.FREE[@p.s];
    zone.FREE[@p];
    RETURN[NIL];
    END; -- of DestroyCellInstPQ


  InsertCellInstPQ: PUBLIC PROCEDURE[p: PQHandle, item: Item] =
    BEGIN
    i, j: CARDINAL;
    pqs: PQSeqPtr ← GrowingPQ[p];
    p.size ← p.size+1;
    FOR j ← p.size-1, i WHILE j>0 DO
      i ← (j-1)/2;
      IF Val[item]>=Val[pqs.heap[i]] THEN EXIT
      ELSE pqs.heap[j] ← pqs.heap[i];
      ENDLOOP;
    pqs.heap[j] ← item;
    END;

  ExtractCellInstPQ: PUBLIC PROCEDURE[p: PQHandle]
    RETURNS[item: Item] =
    BEGIN
    pqs: PQSeqPtr ← ShrinkingPQ[p];
    result: Item ← pqs.heap[0];
    IF (p.size ← p.size-1)>0 THEN
      BEGIN
      i, j: CARDINAL;
      r: CARDINAL ← p.size-1; -- max index
      item: Item ← pqs.heap[p.size];
      FOR i ← 0, j  DO
        j ← i+i+1;
        IF j>r THEN EXIT;
        IF j<r AND Val[pqs.heap[j+1]]<Val[pqs.heap[j]] THEN j ← j+1;
        IF Val[item]<=Val[pqs.heap[j]] THEN EXIT
        ELSE pqs.heap[i] ← pqs.heap[j];
        ENDLOOP;
      pqs.heap[i] ← item;
      END;
    RETURN[result];
    END;


  GrowingPQ: PROCEDURE[p: PQHandle] RETURNS[PQSeqPtr] =
    BEGIN
    IF p.size>=p.s.max THEN
      BEGIN
      oldSeq: PQSeqPtr ← p.s;
      newSeq: PQSeqPtr ←
        p.zone.NEW[PQSeq[MAX[(15*p.size)/10, 50]]];
      FOR i: CARDINAL IN [0..p.size) DO
        newSeq[i] ← oldSeq[i];
        ENDLOOP;
      p.s ← newSeq;
      p.zone.FREE[@oldSeq];
      END;
    RETURN[p.s];
    END;


  ShrinkingPQ: PROCEDURE[p: PQHandle] RETURNS[PQSeqPtr] =
    BEGIN
    WHILE p.size<1 DO SIGNAL CellInstPQUnderflow ENDLOOP;
    IF MAX[p.size, 50]<p.s.max/2 THEN
      BEGIN
      oldSeq: PQSeqPtr ← p.s;
      newSeq: PQSeqPtr ←
        p.zone.NEW[PQSeq[MAX[(15*p.size)/10, 50]]];
      FOR i: CARDINAL IN [0..p.size) DO
        newSeq[i] ← oldSeq[i];
        ENDLOOP;
      p.s ← newSeq;
      p.zone.FREE[@oldSeq];
      END;
    RETURN[p.s];
    END;

  END. -- of CellInstPQImpl