-- RightFeaturePQ.mesa

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

-- last modified by E. McCreight, September 28, 1984  10:10 AM
-- customized for RightFeature by E. McCreight,
--    May 6, 1982  2:34 PM
-- written by E. McCreight, February 8, 1982  2:04 PM

DIRECTORY
  ppdefs,
  ChipNetDefs;

RightFeaturePQ: DEFINITIONS IMPORTS ChipNetDefs =
  BEGIN
  checkTree: PRIVATE BOOLEAN = FALSE;

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

  RightFeaturePQHandle: TYPE = LONG POINTER TO PQObject ← NIL;
  PQHandle: PRIVATE TYPE = RightFeaturePQHandle;
  maxNSeqs: CARDINAL = 16;
  PQObject: PRIVATE TYPE = RECORD [
    zone: UNCOUNTED ZONE,
    size: LONG INTEGER ← 0,
    topSeq: [0..maxNSeqs) ← 0,
    s: ARRAY [0..maxNSeqs) OF PQSeqPtr ← ALL[NIL]
    ];

  PQSeqPtr: PRIVATE TYPE = LONG POINTER TO PQSeq ← NIL;
  maxItemsPerSeq: CARDINAL = 16000;
    -- WARNING: This many Items must fit in no more than 32700 words,
    --    because of free storage package limitations!!
  PQSeq: PRIVATE TYPE = RECORD[
    heap: SEQUENCE max: [0..maxItemsPerSeq] OF Item
    ];

  RightFeaturePQUnderflow: SIGNAL;

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

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

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

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

  MapEqualRightFeaturePQ: PROCEDURE[p: PQHandle,
    proc: PROCEDURE[Item]];

  DeleteEqualRightFeaturePQ: PROCEDURE[p: PQHandle];

  RightFeaturePQSize: PROCEDURE[p: PQHandle] RETURNS[LONG INTEGER] =
    INLINE
    {RETURN[p.size]};

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

  ValLess: PROCEDURE[item1, item2: Item] RETURNS[BOOLEAN] = INLINE
    {RETURN[item1.cover.x2<item2.cover.x2]};


  END. -- of RightFeaturePQ