-- CellInstPQ.mesa

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

-- last modified by E. McCreight, May 6, 1982  2:36 PM
-- written by E. McCreight, February 8, 1982  2:04 PM
-- customized by E. McCreight, February 8, 1982  3:36 PM

DIRECTORY
  ppdefs,
  ChipNetDefs;

CellInstPQ: DEFINITIONS =
  BEGIN
  checkTree: PRIVATE BOOLEAN = FALSE;

  Domain: PRIVATE TYPE = ChipNetDefs.Coord;
  Item: PRIVATE TYPE = ChipNetDefs.CellInstPt;

  CellInstPQHandle: TYPE = LONG POINTER TO PQObject ← NIL;
  PQHandle: PRIVATE TYPE = CellInstPQHandle;
  PQObject: PRIVATE TYPE = RECORD [
    zone: UNCOUNTED ZONE,
    size: CARDINAL ← 0,
    s: PQSeqPtr
    ];

  PQSeqPtr: PRIVATE TYPE = LONG POINTER TO PQSeq ← NIL;
  PQSeq: PRIVATE TYPE = RECORD[
    heap: SEQUENCE max: CARDINAL OF Item
    ];

  CellInstPQUnderflow: SIGNAL;

  NewCellInstPQ: PROCEDURE[zone: UNCOUNTED ZONE,
    max: CARDINAL ← 50]
    RETURNS[PQHandle];

  DestroyCellInstPQ: PROCEDURE[p: PQHandle]
    RETURNS[PQHandle];

  InsertCellInstPQ: PROCEDURE[p: PQHandle, item: Item];

  ExtractCellInstPQ: PROCEDURE[p: PQHandle] RETURNS[item: Item];

  CellInstPQSize: PROCEDURE[p: PQHandle] RETURNS[CARDINAL] =
    INLINE
    {RETURN[p.size]};

  CellInstPQMin: PROCEDURE[p: PQHandle] RETURNS[item: Item] =
    INLINE
    {RETURN[p.s.heap[0]]};

  Val: PROCEDURE[item: Item] RETURNS[Domain] = INLINE
    {RETURN[item.x]};

  END. -- of CellInstPQ