-- PPCommentTableImpl.mesa
-- last edit by Russ Atkinson, 30-May-81 21:36:01

DIRECTORY
  PPCommentTable;

PPCommentTableImpl: PROGRAM
    EXPORTS PPCommentTable
    = PUBLIC BEGIN OPEN PPCommentTable;

  Ref: TYPE = REF Node;
  Node: TYPE = RECORD [start: Index, text: Text, lastToken,prefix: Index];

  Table: TYPE = REF TableNode;
  TableNode: TYPE = RECORD [
    last: Ref,
    size: NAT, lastx: NAT,
    data: SEQUENCE max: NAT OF Ref];

  BreakTab: TYPE = REF BreakSequence;
  BreakSequence: TYPE = RECORD [
    size: NAT,
    indexes: SEQUENCE max: NAT OF Index
    ];

  TableOverflow: ERROR = CODE;
  TableOrder: ERROR = CODE;

  -- variables in the global frame
  commentTable: Table ← NIL;
  breakTable: BreakTab ← NIL;
  ending: Index ← 0;

  Reset: PROC = {
    commentTable ← NIL;
    breakTable ← NIL;
    ending ← 0;
    };

  AddComment: PROC [start: Index, text: Text, lastToken,prefix: Index] = {
    ref: Ref ← NEW[Node ← [start, text, lastToken, prefix]];
    size: NAT ← IF commentTable = NIL THEN 0 ELSE commentTable.size;
    max:  NAT ← IF commentTable = NIL THEN 0 ELSE commentTable.max;
    last: Ref ← IF size > 0 THEN commentTable[size-1] ELSE NIL;
    IF lastToken > start THEN RETURN;
    IF last # NIL THEN {
       IF last.start > start OR lastToken < last.lastToken
          THEN RETURN;
       IF last.start = start THEN {
          -- merge the blank line comment with the actual comment
          IF last.text # NIL THEN RETURN;
          ref.prefix ← prefix + last.prefix;
          commentTable[size-1] ← ref;
          RETURN};
       };      
    IF size >= max THEN {
       newMax: NAT ← IF max > (LAST[NAT]/2 - 2)
          THEN newMax ← LAST[NAT]
          ELSE newMax ← max*2 + 4;
       IF newMax <= size THEN ERROR TableOverflow;
       {newTable: Table ← NEW[TableNode[newMax]];
        newTable.last ← NIL;
        FOR i: NAT IN [0..size) DO
            newTable[i] ← commentTable[i];
            commentTable[i] ← NIL;
            ENDLOOP;
        commentTable ← newTable;
        }};
    commentTable[size] ← ref;
    commentTable.size ← size + 1;
    };

  AddBreakHint: PROC [index: Index] = {
    size: NAT ← IF breakTable = NIL THEN 0 ELSE breakTable.size;
    max:  NAT ← IF breakTable = NIL THEN 0 ELSE breakTable.max;
    last: Index ← IF size = 0 THEN 0 ELSE breakTable[size-1];
    IF index <= last THEN RETURN;
    IF size >= max THEN {
       -- must extend the table
       new: BreakTab ← NIL;
       nmax: NAT ← MAX[200, IF max < LAST[NAT]/2 THEN max+max ELSE LAST[NAT]];
       IF nmax <= max THEN ERROR TableOverflow;
       new ← NEW[BreakSequence[nmax]];
       FOR i: NAT IN [0..size) DO new[i] ← breakTable[i]; ENDLOOP;
       breakTable ← new;
       };
    breakTable[size] ← index;
    breakTable.size ← size + 1;
    };   

  FindNextComment: PROC [notBefore: Index] RETURNS [Ref] = {
    IF commentTable # NIL AND commentTable.size > 0 THEN {
       low: NAT ← 0;
       high: NAT ← commentTable.size-1;
       last: Ref ← commentTable.last;
       lastx: NAT ← commentTable.lastx;
       lval: Index ← 0;
       IF last # NIL THEN {
          lval ← last.start;
          IF notBefore = lval THEN RETURN [last];
          IF notBefore < lval
             THEN high ← lastx
             ELSE low ← lastx+1;
          };
       WHILE low < high DO
          lval ← (last ← commentTable[lastx ← (low+high)/2]).start;
          IF notBefore < lval THEN {high ← lastx; LOOP};
          IF notBefore > lval THEN {low ← lastx+1; LOOP};
          commentTable.lastx ← lastx;
          RETURN [commentTable.last ← last];
          ENDLOOP;
       IF high # lastx OR last = NIL
          THEN lval ← (last ← commentTable[lastx ← high]).start;
       IF notBefore <= lval
          THEN {commentTable.lastx ← lastx;
                RETURN [commentTable.last ← last]};
       };
    RETURN [NIL];
    };

  TestBreakHint: PROC [start: Index, next: Index] RETURNS [BOOLEAN] = {
    IF start = 0 OR next <= start THEN RETURN [TRUE];
    IF breakTable = NIL OR breakTable.size <= 1 THEN RETURN [FALSE];
    {low: NAT ← 0;
     high: NAT ← breakTable.size - 1;
     DO
        last: NAT ← (low+high)/2;
        lval: Index ← breakTable[last];
        IF low = high THEN RETURN [start < lval AND next > lval];
        IF start < lval THEN {
           IF next > lval THEN RETURN [TRUE];
           high ← last;
           LOOP};
        IF start >= lval THEN {low ← last+1; LOOP};
        ENDLOOP;
     }};

  Explode: PROC [ref: Ref]
      RETURNS [start: Index, text: Text, lastToken,prefix: Index] = {
    IF ref = NIL THEN RETURN [LAST[Index], NIL, LAST[Index], 0];
    RETURN [ref.start, ref.text, ref.lastToken, ref.prefix];
    };

  SetEnding: PROC [end: Index] = {ending ← end};

  GetEnding: PROC RETURNS [Index] = {RETURN [ending]};

  END.