--Lexicon.mesa 

DIRECTORY
  SystemDefs: FROM "systemdefs" USING [AllocateHeapNode, AllocateHeapString],
  IODefs: FROM "iodefs" USING [WriteLine],
  LexiconDefs: FROM "lexicondefs",
  StringDefs: FROM "stringdefs" USING [AppendString];

Lexicon: PROGRAM
  IMPORTS SystemDefs, IODefs, StringDefs
  EXPORTS LexiconDefs =

  BEGIN
	
  Node: TYPE = RECORD[llink, rlink: NodePtr, string: STRING];
  NodePtr: TYPE = POINTER TO Node;
  Comparative: TYPE = {lessThan, equalTo, greaterThan};

  root: NodePtr ← NIL;
		
  FindString: PUBLIC PROCEDURE [s: STRING] RETURNS [BOOLEAN] =
    BEGIN RETURN[SearchForString[root, s]]; END;

  SearchForString: PROCEDURE [n: NodePtr, s: STRING]
    RETURNS [found: BOOLEAN] =
    BEGIN
    IF n = NIL THEN RETURN[FALSE];
    SELECT LexicalCompare[s, n.string] FROM
        lessThan     =>  found ← SearchForString[n.llink, s];
        equalTo      =>  found ← TRUE;
        greaterThan  =>  found ← SearchForString[n.rlink, s];
        ENDCASE;
    RETURN[found];
    END;

  AddString: PUBLIC PROCEDURE [s: STRING] =
    BEGIN InsertString[root, s]; END;

  InsertString: PROCEDURE [n: NodePtr, s: STRING] =
    BEGIN
    NewNode: PROCEDURE RETURNS [n: NodePtr] =
      BEGIN OPEN SystemDefs;
      n ← AllocateHeapNode[SIZE[Node]];
      n↑ ← Node[string: AllocateHeapString[s.length], llink: NIL, rlink: NIL];
      StringDefs.AppendString[n.string, s];
      RETURN;
      END;

    IF n = NIL THEN root ← NewNode[]	-- then just return
    ELSE
      SELECT LexicalCompare[s, n.string] FROM
        lessThan     =>  IF n.llink # NIL THEN InsertString[n.llink, s]
                         ELSE n.llink ← NewNode[];
        equalTo      =>  NULL;		-- already there; just return
        greaterThan  =>  IF n.rlink # NIL  THEN InsertString[n.rlink, s]
                         ELSE n.rlink ← NewNode[];
        ENDCASE;
    END;

  LexicalCompare: PROCEDURE [s1, s2: STRING] RETURNS [c: Comparative] =
    BEGIN
    n: CARDINAL = MIN[s1.length, s2.length];
    i: CARDINAL;
    FOR i IN [0..n) DO
      SELECT LowerCase[s1[i]] FROM
        <LowerCase[s2[i]]  =>  RETURN[lessThan];
        >LowerCase[s2[i]]  =>  RETURN[greaterThan];
        ENDCASE;
      ENDLOOP;
    c ← SELECT s1.length FROM
      <s2.length   =>  lessThan,      -- s1 is shorter than s2
      >s2.length   =>  greaterThan,   -- s1 is longer than s2
      ENDCASE      =>  equalTo;       -- lengths are the same
    RETURN[c];
    END;

  lower: PACKED ARRAY CHARACTER['A .. 'Z] OF CHARACTER =
['a,'b,'c,'d,'e,'f,'g,'h,'i,'j,'k,'l,'m,'n,'o,'p,'q,'r,'s,'t,'u,'v,'w,'x,'y,'z];

  LowerCase: PROCEDURE [c: CHARACTER] RETURNS [CHARACTER] =
    BEGIN RETURN[IF c IN ['A..'Z] THEN lower[c] ELSE c]; END;

  PrintLexicon: PUBLIC PROCEDURE =
    BEGIN PrintNode[root] END;

  PrintNode: PROCEDURE[n: NodePtr] =
    BEGIN
    IF n = NIL THEN RETURN;
    PrintNode[n.llink];
    IODefs.WriteLine[n.string];
    PrintNode[n.rlink];
    END;

  END.