-- MCrossSorterImpl.Mesa
-- A simple interface for sorting a collection of objects based on a  string key
-- last edited July 1, 1982 5:48 pm by Paul Rovner

DIRECTORY
	Atom USING[GetPName],
        FileUtilDefs USING[UpperCase],
	MCrossRefDefs,
	MCrossSorter,
	Rope USING[ROPE, Size, Fetch],
	SafeStorage USING[NewZone];

MCrossSorterImpl: PROGRAM 
  IMPORTS Atom, FileUtilDefs, Rope, SafeStorage
  EXPORTS MCrossSorter
= BEGIN OPEN FileUtilDefs, MCrossSorter, MCrossRefDefs;

-- ERRORS
  NotInitialized: PUBLIC ERROR = CODE;

-- CONSTANTS
  SortTableLength: CARDINAL = 256;

-- TYPES
  SortTable: TYPE = REF ASortTable;
  ASortTable: TYPE = ARRAY SortTableIndex OF RECORD[first, last: TokenHandle];
  SortTableIndex: TYPE = [0..SortTableLength);

-- VARIABLES
  sortTables: ARRAY [0..1] OF SortTable ← [NIL, NIL];
  lastKeyIndex: CARDINAL ← 0;
  initialized: BOOLEAN ← FALSE;
  sortTableZone: ZONE ← SafeStorage.NewZone[];


-- PUBLIC PROCEDURES

  Initialize: PUBLIC PROC[keyLength: CARDINAL] =
    { Clear[];
      IF initialized THEN
        { sortTables[0] ← NIL;
          sortTables[1] ← NIL};
      IF keyLength = 0 THEN keyLength ← 1;
      lastKeyIndex ← keyLength - 1;
      sortTables ← [sortTableZone.NEW[ASortTable], sortTableZone.NEW[ASortTable]];
      sortTables[0]↑ ← ALL[[NIL, NIL]];
      sortTables[1]↑ ← ALL[[NIL, NIL]];
      initialized ← TRUE;
    };

  Finalize: PUBLIC PROC =
    { Clear[];
      IF initialized THEN
        { sortTables[0] ← NIL;
          sortTables[1] ← NIL;
          initialized ← FALSE};
    };

  Clear: PUBLIC PROC =
    { i: SortTableIndex;
      k: [0..1];
      IF ~initialized THEN RETURN;
      FOR k IN [0..1] DO
         FOR i IN SortTableIndex DO sortTables[k][i] ← [NIL, NIL]; ENDLOOP;
       ENDLOOP;
    };

  Enter: PUBLIC PROC[token: TokenHandle] =
    { Insert[sortTables[lastKeyIndex MOD 2],
             token,
             GetSTI[Atom.GetPName[token.name], lastKeyIndex]];
    };

  Enumerate: PUBLIC PROC[leafProc: PROC[token: TokenHandle] RETURNS[stop: BOOLEAN],
			 order: SortOrder ← unordered]
	RETURNS[stopped: BOOLEAN] =
    { i: SortTableIndex;
      st: SortTable = sortTables[0];

      IF ~initialized THEN ERROR NotInitialized;
      IF order # unordered THEN Sort[];
      IF order = decreasing THEN
        FOR i DECREASING IN SortTableIndex DO
          leaf: TokenHandle;
          st[i].first ← ReverseEntryList[st[i].first];
          FOR leaf ← st[i].first, leaf.next UNTIL leaf = NIL DO
             IF leafProc[leaf] THEN
               { st[i].first ← ReverseEntryList[st[i].first]; RETURN[TRUE]};
            ENDLOOP;
          st[i].first ← ReverseEntryList[st[i].first];  -- otherwise can't enumerate again
         ENDLOOP
       ELSE
        FOR i IN SortTableIndex DO
          leaf: TokenHandle;
          FOR leaf ← st[i].first, leaf.next UNTIL leaf = NIL DO
             IF leafProc[leaf] THEN RETURN[TRUE];
            ENDLOOP;
          ENDLOOP;
      RETURN[FALSE];
    };



-- PRIVATE PROCEDURES

  GetSTI: PROC[key: Rope.ROPE, chi: CARDINAL] RETURNS[SortTableIndex]=
    INLINE { IF Rope.Size[key] <= chi THEN RETURN[FIRST[SortTableIndex]];
             RETURN[LOOPHOLE[UpperCase[Rope.Fetch[key, chi]]]]};

  ReverseEntryList: PROC[this: TokenHandle] RETURNS[last: TokenHandle ← NIL] =
    INLINE { UNTIL this = NIL DO
               next: TokenHandle ← this.next;
               this.next ← last;
               last ← this;
               this ← next;
              ENDLOOP};

  Sort: PROC =
    { FOR k: CARDINAL DECREASING IN [0..lastKeyIndex) DO
        oldST: SortTable = sortTables[(k+1) MOD 2];
        newST: SortTable = sortTables[k MOD 2];
        FOR i: SortTableIndex IN SortTableIndex DO
          entry: TokenHandle ← oldST[i].first;
          oldST[i] ← [NIL, NIL];
          UNTIL entry = NIL DO
            next: TokenHandle = entry.next;
            Insert[newST, entry, GetSTI[Atom.GetPName[entry.name], k]];
            entry ← next;
           ENDLOOP;
         ENDLOOP;
       ENDLOOP;
    };

  Insert: PROC[st: SortTable, entry: TokenHandle, sti: SortTableIndex] =
    INLINE { IF st[sti].first = NIL THEN st[sti].first ← entry
              ELSE st[sti].last.next ← entry;
             st[sti].last ← entry;
             entry.next ← NIL};


END.