-- ChipSortLists.mesa

-- A Chipmonk package that sorts Chipmonk object
-- lists in increasing order by smallest x, and within equal
-- smallest x in increasing order by smallest y.

-- last modified by E. McCreight, November 1, 1982  4:37 PM
-- written by E. McCreight, October 13, 1981  3:15 PM

DIRECTORY
  ChipNetDefs,
  ChipOrient,
  ppdefs;

ChipSortLists: PROGRAM IMPORTS ChipOrient
  EXPORTS ChipNetDefs =
  BEGIN OPEN ppdefs, ChipOrient, ChipNetDefs;


  SortListPtrSeq: PUBLIC PROCEDURE[lps: ListPtrSeqPtr,
    less: PROCEDURE[lp1, lp2: listPtr] RETURNS[BOOLEAN]
    ] =
    BEGIN
    r, l: CellIndex;
    IF lps.count=0 THEN RETURN; -- Nothing to sort.
    r ← lps.count-1; -- max legal index
    l ← (r+1)/2;
    WHILE r>0 DO
      i, j: CellIndex;
      item: listPtr;
      IF l>0 THEN {l ← l-1; item ← lps.lp[l]}
      ELSE
        BEGIN
        item ← lps.lp[r];
        lps.lp[r] ← lps.lp[0];
        r ← r-1;
        END;
      FOR i ← l, j DO
        j ← i+i+1; -- I'd like to say 2*i+1 but
          -- I don't trust the optimizer
        IF j>r THEN EXIT;
        IF j<r THEN
          BEGIN
          IF less[lps.lp[j], lps.lp[j+1]] THEN j ← j+1;
          END;
        IF less[item, lps.lp[j]] THEN lps.lp[i] ← lps.lp[j]
        ELSE EXIT;
        ENDLOOP;
      lps.lp[i] ← item;
      ENDLOOP;
    END; -- of SortListPtrSeq

  orientToSortClass: PUBLIC ARRAY orientationIndex OF SortClass ←
    [minX, maxX, -- [0..1]
    minX, maxX, -- [2..3] (really illegal)
    maxY, minY, -- [4..5]
    maxY, minY, -- [6..7] (really illegal)
    maxX, minX, -- [8..9]
    maxX, minX, -- [10..11] (really illegal)
    minY, maxY, -- [12..13]
    minY, maxY -- [14..15] (really illegal)
    ];

  SortOrder: PUBLIC ARRAY SortClass OF
    PROCEDURE[lp1, lp2: listPtr] RETURNS[BOOLEAN] ←
    [minX: ByMinX, maxX: ByMaxX,
    minY: ByMinY, maxY: ByMaxY
    ];

  ByMinX: PROCEDURE[lp1, lp2: listPtr] RETURNS[BOOLEAN] =
    {RETURN[lp1.lx<lp2.lx]};

  ByMinY: PROCEDURE[lp1, lp2: listPtr] RETURNS[BOOLEAN] =
    {RETURN[lp1.ly<lp2.ly]};

  ByMaxX: PROCEDURE[lp1, lp2: listPtr] RETURNS[BOOLEAN] =
    {RETURN[lp2.lx+lp2.ob.size[Rot90[lp2.idx]]<
      lp1.lx+lp1.ob.size[Rot90[lp1.idx]]]};

  ByMaxY: PROCEDURE[lp1, lp2: listPtr] RETURNS[BOOLEAN] =
    {RETURN[lp2.ly+lp2.ob.size[1-Rot90[lp2.idx]]<
      lp1.ly+lp1.ob.size[1-Rot90[lp1.idx]]]};

  END. -- of ChipSortLists