MODULE BM;

IMPORT Algorithm, AlgsBase, StringSearchAlgClass, StringSearchIE,
       Text, Thread, ZeusPanel;

TYPE T = StringSearchAlgClass.T BRANDED OBJECT OVERRIDES run := Run; END;

PROCEDURE Run (alg: T) RAISES {Thread.Alerted} =
  VAR
    pattern, str: TEXT;                  (* pattern and string *)
    m, n        : CARDINAL;              (* their length *)
    i, j        : INTEGER               := 0;
    skip        : ARRAY CHAR OF INTEGER;
  BEGIN
    AlgsBase.GetData(alg, pattern, str);
    m := Text.Length(pattern);
    n := Text.Length(str);
    IF m = 0 OR n = 0 THEN RETURN; END;
    StringSearchIE.Setup(alg, pattern, str);
    skip := InitSkip(pattern);
    n := Text.Length(pattern) - 1;
    m := Text.Length(str) - 1;
    i := n;
    j := n;
    REPEAT
      StringSearchIE.Probe(alg, j, i);
      IF Text.GetChar(pattern, j) = Text.GetChar(str, i) THEN
        StringSearchIE.Result(alg, TRUE);
        StringSearchIE.PartialMatch(alg, j, i, n - j + 1);
        DEC(i);
        DEC(j);
      ELSE
        StringSearchIE.Result(alg, FALSE);
        StringSearchIE.PartialMatchClear(alg);
        i := i + skip[Text.GetChar(str, i)];
        j := n;
        StringSearchIE.SlideTo(alg, i - n);
      END;
      IF j < 0 THEN
        StringSearchIE.CompleteMatch(alg, i + 1);
        INC(i, n + 2);
        j := n;
        StringSearchIE.SlideTo(alg, i - n);
      END;
    UNTIL i > m;
  END Run;

PROCEDURE InitSkip (pattern: TEXT): ARRAY CHAR OF INTEGER =
  VAR
    n   := Text.Length(pattern);
    skip:  ARRAY CHAR OF INTEGER ;
  BEGIN
    FOR c := FIRST(CHAR) TO LAST(CHAR) DO
      skip[c] := n;
    END;
    FOR j := 0 TO n - 1 DO
      skip[Text.GetChar(pattern, j)] := n - j - 1;
    END;
    RETURN (skip);
  END InitSkip;

PROCEDURE New (): Algorithm.T =
  BEGIN
    RETURN
      NEW(
        T, data := ZeusPanel.NewForm("stringsearchinput.fv")).init();
  END New;

BEGIN
  ZeusPanel.RegisterAlg(New, "BoyerMoore", "StringSearch");
END BM.