--CellsTry

--this module attempts to make an initial ordering of the columns

DIRECTORY
  IODefs: FROM "IODefs",
  CellsDefs: FROM "CellsDefs";

CellsTry:PROGRAM IMPORTS IODefs, CellsDefs EXPORTS CellsDefs=
BEGIN OPEN CellsDefs;

Error:SIGNAL=CODE;
Space:CHARACTER=' ;
Ret:CHARACTER='
;

Id:TYPE=INTEGER;
Signal:TYPE=INTEGER;
Group:TYPE=INTEGER;
Remember:TYPE=INTEGER;

maxGroup:INTEGER=500;
maxIds:INTEGER=2000;
maxSignal:INTEGER=signalMax;

GroupEntry:TYPE=RECORD[active,chain:Id];
Ids:TYPE=RECORD[sig:Signal, chain:Id, active:BOOLEAN];
Use:TYPE=RECORD[total,used:[0..256)];
RememberEntry:TYPE=RECORD[type:INTEGER, me,friend,other:Signal];

groupsType:TYPE=ARRAY [0..maxGroup) OF GroupEntry;
  -- a group is all the ids connecting to a particular track signal
idsType:TYPE=ARRAY [0..maxIds) OF Ids;
  --ids are list storage for constructing groups
useType:TYPE=ARRAY [0..maxSignal) OF Use;
  --to keep track of how many instances of a signal name exits
rememberType:TYPE=ARRAY [0..maxGroup) OF RememberEntry;
columnListType:TYPE=ARRAY [0..maxSignal) OF Signal;
groups:LONG POINTER TO groupsType;
ids:LONG POINTER TO idsType;
use:LONG POINTER TO useType;
remember:LONG POINTER TO rememberType;
columnList:LONG POINTER TO columnListType;
nextId:Id;
nextRemember:Remember;
groupEnd:INTEGER←0;

ClusterColumns:PUBLIC PROCEDURE=
  {SigToGroups; MakeUseCounts; Reduce; Rebuild; FixEnds; NumberColumns};

SigToGroups:PROCEDURE=BEGIN
  ids↑←ALL[[0,-1,FALSE]];
  nextId←0;
  groups↑←ALL[[0,-1]];
  groupEnd←0;
  FOR s:Signal IN [0..maxSignal) DO
    IF sig[s].def=NIL THEN LOOP;
    groupEnd←MAX[groupEnd,s+1];
    Append[s,s];
    SELECT sig[s].def.s.type FROM
      norPullUp=>BEGIN
        base:Signal←sig[s].def.s.e;
        --Append[base,base];
        FOR j:TList←sig[s].def.next, j.next UNTIL j=NIL DO
          IF j.s.type=norPullDown
            THEN {Append[j.s.d,j.s.d]; Append[j.s.d,base]};
          ENDLOOP;
        END;
      pass1=>BEGIN
        --Append[sig[s].def.s.d,sig[s].def.s.d];
        Append[sig[s].def.s.d,sig[s].def.s.g];
        Append[sig[s].def.s.d,sig[s].def.s.e];
        END;
      ENDCASE;
    ENDLOOP;
  FOR s:Signal IN [0..maxSignal) DO
    IF sig[s].def=NIL THEN LOOP;
    SELECT sig[s].def.s.type FROM
      wire=>BEGIN
        base:Signal←sig[s].def.s.e;
        FOR j:TList←sig[s].def.next, j.next UNTIL j=NIL DO
          t:Id=groups[base].chain;
          q:Id=groups[j.s.d].chain;
          l:Id←-1;
          FOR k:Id←q,ids[k].chain UNTIL k=-1 DO l←k; ENDLOOP;
          groups[base].chain←q;
          --groupEnd←MAX[groupEnd,base];
          IF l#-1 THEN ids[l].chain←t;
          groups[j.s.d].chain←-1;
          --groupEnd←MAX[groupEnd,j.s.d];
          SubstituteX[base,j.s.d];
          ENDLOOP;
        END;
      ENDCASE;
    ENDLOOP;
  MakeActiveCounts[];
  END;

SubstituteX:PROCEDURE[new,old:Signal]=BEGIN
  t,f:Id;
  IF new=old THEN Error;
  FOR g:Group IN [0..maxGroup) DO
    FOR i:Id←groups[g].chain,ids[i].chain UNTIL i=-1 DO
      IF ~(ids[i].sig=old AND ids[i].active) THEN LOOP;
      t←-1;
      FOR j:Id←groups[g].chain,f UNTIL j=-1 DO
        f←ids[j].chain;
        IF ids[j].sig=new THEN
          {IF t=-1 THEN groups[g].chain←f ELSE ids[t].chain←f};
        t←j;
        ENDLOOP;
      ids[i].sig←new;
      ENDLOOP;
    ENDLOOP;
  END;

Append:PROCEDURE[from,to:Signal]=BEGIN
  t:Id=nextId;
  FOR i:Id ←groups[to].chain,ids[i].chain UNTIL i=-1
      DO IF ids[i].sig=from THEN RETURN; ENDLOOP;
  nextId←nextId+1;
  IF nextId>=maxIds THEN {Error; RETURN};
  ids[t]←[from,groups[to].chain,TRUE];
  groups[to].chain←t;
  END;

MakeActiveCounts:PROCEDURE=BEGIN
  FOR g:Group IN [0..groupEnd) DO
    n:INTEGER←0;
    FOR i:Id ←groups[g].chain,ids[i].chain UNTIL i=-1 DO
       IF ids[i].active THEN n←n+1;
       ENDLOOP;
    groups[g].active←n;
    ENDLOOP;
  END;

MakeUseCounts:PROCEDURE=BEGIN
  use↑←ALL[[0,0]];
  FOR g:Group IN [0..groupEnd) DO IF groups[g].active=0 THEN LOOP;
    FOR i:Id ←groups[g].chain,ids[i].chain UNTIL i=-1 DO
      IF ~ids[i].active THEN LOOP;
      use[ids[i].sig].total←use[ids[i].sig].total+1;
      ENDLOOP;
    ENDLOOP;
  END;

Reduce:PROCEDURE=BEGIN
remember↑←ALL[[0,0,0,-1]];  nextRemember←0;
PrintGroups[];
FOR g:Group IN [0..groupEnd) DO
  IF groups[g].active=1 THEN BEGIN
    friend:Signal←ids[groups[g].chain].sig;
    IF use[g].total=0 THEN BEGIN
       IF g=friend THEN Error;
       RememberMe[4,g,friend,-1];
       END;
    KillGroup[g];
    END;
  ENDLOOP;
DO
  FOR hard:INTEGER IN [0..2] DO
    progress:BOOLEAN←FALSE;
    PrintGroups[];
    --PrintUse[];
    PrintRemember[];
    FOR s:Signal IN [0..maxSignal) DO
      excess:INTEGER=use[s].total-use[s].used;
      IF hard=2 THEN
      {IF excess>0 AND ReduceParallelUses[s] THEN progress←TRUE}
      ELSE SELECT excess FROM
        0=>NULL;
        1=>{ReduceSingleUses[s]; progress←TRUE};
        2=>IF hard=1 AND ReduceDoubleUses[s] THEN progress←TRUE;
        ENDCASE;
      ENDLOOP;
    IF progress THEN EXIT;
    IF hard=2 THEN BEGIN
      FOR g:Group IN [0..groupEnd) DO
        IF groups[g].active#0 THEN {ReduceRandomly[g]; progress←TRUE; EXIT};
        ENDLOOP;
      IF progress THEN EXIT;
      RETURN;
      END;
    ENDLOOP;
  ENDLOOP;
  END;

ReduceRandomly:PROCEDURE[g:Group]=BEGIN
  FOR i:Id←groups[g].chain,ids[i].chain UNTIL i=-1 DO
      IF ~ids[i].active THEN LOOP;
      ids[i].active←FALSE;
      use[ids[i].sig].used←use[ids[i].sig].used+1;
      DecrementActive[g];
      RETURN;
      ENDLOOP;
  Error;
  END;

ReduceSingleUses:PROCEDURE[s:Signal]=BEGIN --s occurs exactly once
  FOR g:Group IN [0..groupEnd) DO IF groups[g].active=0 THEN LOOP;
    FOR i:Id←groups[g].chain,ids[i].chain UNTIL i=-1 DO
      friend,other:Signal;
      IF ~(ids[i].sig=s AND ids[i].active) THEN LOOP;
      use[s].used←use[s].total;
      ids[i].active←FALSE;
      [friend,other]←AnyMember[g];
      RememberMe[1,s,friend,other];
      DecrementActive[g];
      RETURN;
      ENDLOOP;
    ENDLOOP;
  Error;
  END;

ReduceDoubleUses:PROCEDURE[s:Signal] RETURNS[progress:BOOLEAN]=BEGIN
  friend,other:Signal;
  FOR g:Group IN [0..groupEnd) DO IF groups[g].active#2 THEN LOOP;
    FOR i:Id←groups[g].chain,ids[i].chain UNTIL i=-1 DO
      IF ~(ids[i].sig=s AND ids[i].active) THEN LOOP;
      use[s].used←use[s].total;
      ids[i].active←FALSE;
      [friend,other]←AnyMember[g];
      RememberMe[2,s,friend,other];
      groups[g].active←0;
      Substitute[friend,s];
      RETURN[TRUE];
      ENDLOOP;
    ENDLOOP;
  RETURN[FALSE];
  END;

ReduceParallelUses:PROCEDURE[s:Signal] RETURNS[progress:BOOLEAN]=BEGIN
  FOR g:Group IN [0..groupEnd) DO IF groups[g].active=0 THEN LOOP;
    FOR i:Id←groups[g].chain,ids[i].chain UNTIL i=-1 DO
      IF ~(ids[i].sig=s AND ids[i].active) THEN LOOP;
      FOR j:Id←groups[g].chain,ids[j].chain UNTIL j=-1 DO
        IF ~(ids[j].active AND i#j AND Verify[s,ids[j].sig]) THEN LOOP;
        RememberMe[3,s,ids[j].sig,-1];
        Remove[s];
        RETURN[TRUE];
        ENDLOOP;
      ENDLOOP;
    ENDLOOP;
  RETURN[FALSE];
  END;

AnyMember:PROCEDURE[g:Group] RETURNS[a,b:Signal]=BEGIN
  a←b←-1;
  FOR i:Id←groups[g].chain,ids[i].chain UNTIL i=-1 DO
    IF ~ids[i].active THEN LOOP;
    IF a=-1 THEN a←ids[i].sig ELSE {b←ids[i].sig; RETURN};
    ENDLOOP;
  IF a=-1 THEN Error;
  END;

DecrementActive:PROCEDURE[g:Group]=BEGIN
  groups[g].active←groups[g].active-1;
  IF groups[g].active=1 THEN KillGroup[g];
  END;

KillGroup:PROCEDURE[g:Group]=BEGIN
  FOR j:Id←groups[g].chain,ids[j].chain UNTIL j=-1 DO
    IF ~ids[j].active THEN LOOP; 
    ids[j].active←FALSE;
    use[ids[j].sig].used←use[ids[j].sig].used+1;
    groups[g].active←0;
    RETURN;
    ENDLOOP;
  Error;
  END;

Substitute:PROCEDURE[new,old:Signal]=BEGIN
  FOR g:Group IN [0..groupEnd) DO
    IF groups[g].active=0 THEN LOOP;
    FOR i:Id←groups[g].chain,ids[i].chain UNTIL i=-1 DO
      IF ~(ids[i].sig=old AND ids[i].active) THEN LOOP;
      ids[i].sig←new;
      FOR j:Id←groups[g].chain,ids[j].chain UNTIL j=-1 DO
        IF j#i AND ids[j].sig=new AND ids[j].active THEN BEGIN
          ids[j].active←FALSE; use[new].used←use[new].used+1;
          DecrementActive[g];
          END;
        ENDLOOP;
      ENDLOOP;
    ENDLOOP;
  END;

debug:Signal←-1;

Verify:PROCEDURE[s,t:Signal] RETURNS[BOOLEAN]=BEGIN
  sFound,tFound:BOOLEAN;
  IF s=debug THEN Error;
  FOR g:Group IN [0..groupEnd) DO IF groups[g].active=0 THEN LOOP;
    sFound←tFound←FALSE;
    FOR i:Id←groups[g].chain,ids[i].chain UNTIL i=-1 DO
      IF ~ids[i].active THEN LOOP;
      SELECT ids[i].sig FROM s=>sFound←TRUE; t=>tFound←TRUE; ENDCASE;
      ENDLOOP;
    IF sFound AND ~tFound THEN BEGIN
       IF s=debug THEN Error;
       RETURN[FALSE];
       END;
    ENDLOOP;
  RETURN[TRUE];
  END;

Remove:PROCEDURE[s:Signal]=BEGIN
  FOR g:Group IN [0..groupEnd) DO IF groups[g].active=0 THEN LOOP;
    FOR i:Id←groups[g].chain,ids[i].chain UNTIL i=-1 DO
      IF ~(ids[i].active AND ids[i].sig=s) THEN LOOP;
      ids[i].active←FALSE;
      DecrementActive[g];
      ENDLOOP;
    ENDLOOP;
  use[s].used←use[s].total;
  END;

RememberMe:PROCEDURE[type:INTEGER, me,friend,other:Signal]=BEGIN
  IF ~(me IN [0..signalMax) AND friend IN [0..signalMax)) THEN Error;
  begin←friend;
  remember[nextRemember]←[type,me,friend,other];
  nextRemember←nextRemember+1;
  END;

last:Signal;

Rebuild:PROCEDURE=BEGIN
  columnList↑←ALL[-1];
  last←begin;
  FOR s:Remember DECREASING IN [0..nextRemember) DO
    me:Signal=remember[s].me;
    friend:Signal=remember[s].friend;
    IF remember[s].type=0 THEN LOOP;
    IF columnList[me]#-1 THEN Error;
    Mid[me,friend]
    ENDLOOP;
  END;

Front:PROCEDURE[s:Signal]={columnList[s]←begin; begin←s};
Back:PROCEDURE[s:Signal]={columnList[last]←s; last←s};
Mid:PROCEDURE[s,t:Signal]=BEGIN
  q:Signal=columnList[t];
  IF q=-1 THEN BEGIN
    IF t#last THEN columnList[last]←t;
    last←s;
    END;
  columnList[s]←q;
  columnList[t]←s;
  END;

FixEnds:PROCEDURE=BEGIN
  FOR s:Signal←begin,columnList[s] UNTIL s=-1 DO last←s; ENDLOOP;
  FOR s:Signal IN [0..maxSignal) DO SELECT sig[s].fixed FROM
    hi=> FixEnd[s,TRUE];lo=> FixEnd[s,FALSE]; ENDCASE; ENDLOOP;
  END;

FixEnd:PROCEDURE[f:Signal,hi:BOOLEAN]=BEGIN
  back:Signal←-1;
  FOR s:Signal←begin,columnList[s] UNTIL s=-1 DO
    IF f#s THEN {back←s; LOOP};
    IF back=-1 THEN begin←columnList[s]
      ELSE {columnList[back]←columnList[s]; IF s=last THEN last←back};
    columnList[s]←-1;
    IF hi THEN Back[f] ELSE Front[f];
    RETURN;
    ENDLOOP;
  Error;
  END;

begin:Signal←-1;

NumberColumns:PROCEDURE=BEGIN
  c:INTEGER←0;
  column↑←ALL[0];
  FOR s:Signal←begin,columnList[s] UNTIL s=-1 DO
    sig[s].columnNum←c; column[c]←s; c←c+1;
    ENDLOOP;
  PrintColumns[];
  END;

PrintColumns:PROCEDURE=BEGIN OPEN IODefs;
IF chip THEN RETURN;
  FOR c:INTEGER IN [0..maxSignal) UNTIL column[c]=0 DO
    WriteChar[Ret];
    WriteDecimal[c];
    WriteChar[Space];
    WriteString[Lookup2[column[c]]];
    ENDLOOP;
  END;

PrintGroups:PROCEDURE=BEGIN OPEN IODefs;
k:INTEGER;
IF chip THEN RETURN;
  FOR g:Group IN [0..groupEnd) DO IF groups[g].chain=-1 THEN LOOP;
    WriteChar[Ret];
    WriteDecimal[g];
    WriteChar[Space];
    WriteDecimal[groups[g].active];
    WriteChar[Space];
    k←0;
    FOR i:Id←groups[g].chain,ids[i].chain UNTIL i=-1 OR (k←k+1)>30 DO
      WriteChar[Space];
      WriteChar[IF ids[i].active THEN Space ELSE 'X];
      WriteChar[Space];
      --WriteDecimal[ids[i].sig];
      WriteString[Lookup2[ids[i].sig]];
      ENDLOOP;
    ENDLOOP;
  END;

PrintUse:PROCEDURE=BEGIN OPEN IODefs;
IF chip THEN RETURN;
  FOR s:Group IN [0..maxSignal) DO IF use[s].total=0 THEN LOOP;
    WriteChar[Ret];
    WriteDecimal[s];
    WriteChar[Space];
    WriteString[Lookup2[s]];
    WriteChar[Space];
    WriteDecimal[use[s].total];
    WriteChar[Space];
    WriteDecimal[use[s].used];
    ENDLOOP;
  END;

PrintRemember:PROCEDURE=BEGIN OPEN IODefs;
  FOR s:Remember IN [0..nextRemember) DO
    WriteChar[Ret];
    WriteDecimal[s];
    WriteChar[Space];
    WriteDecimal[remember[s].type];
    WriteChar[Space];
    WriteString[Lookup2[remember[s].me]];
    WriteChar[Space];
    WriteString[Lookup2[remember[s].friend]];
    ENDLOOP;
  END;


InitStorage:PROCEDURE=BEGIN
groups←zone.NEW[groupsType];
ids←zone.NEW[idsType];
use←zone.NEW[useType];
remember←zone.NEW[rememberType];
columnList←zone.NEW[columnListType];
END;

InitStorage;


END..

Rebuild:PROCEDURE=BEGIN
  columnList←ALL[-1];
  last←begin;
  FOR s:Remember DECREASING IN [0..nextRemember) DO
    me:Signal=remember[s].me;
    friend:Signal=remember[s].friend;
    other:Signal=remember[s].other;
    upSide:BOOLEAN←FALSE;
    IF remember[s].type=0 THEN LOOP;
    IF columnList[me]#-1 THEN Error;
    SELECT other FROM
      -2,-1 => {Back[me]; LOOP};
      -3 => {Front[me]; LOOP};
      -4 => upSide←FALSE;
      -5 => upSide←TRUE;
      ENDCASE=>FOR s:Signal←friend,columnList[s] UNTIL s=-1
          DO IF s=other THEN {upSide←TRUE; EXIT}; ENDLOOP;
    IF upSide
    THEN IF last=friend THEN Back[me] ELSE Mid[me,friend]
    ELSE
      IF friend=begin
      THEN Front[me]
      ELSE FOR t:Signal←begin,columnList[t] UNTIL t=-1 DO
        IF columnList[t]=friend THEN {Mid[me,t]; EXIT}; 
        ENDLOOP;
    ENDLOOP;
  END;