MCrossSorterImpl.Mesa
A simple interface for sorting a collection of objects based on a string key
last edited October 11, 1983 11:53 pm by Paul Rovner
DIRECTORY
Atom USING[GetPName],
FileUtilDefs USING[UpperCase],
MCrossRefDefs,
MCrossSorter,
Rope USING[ROPE, Size, Fetch];
MCrossSorterImpl:
PROGRAM
IMPORTS Atom, FileUtilDefs, Rope
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;
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 ← [NEW[ASortTable], 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.