/* Martin Richards' TRIPOS Pattern Matching algorithm in C */
/* This is a direct transliteration of the BCPL code 87:7:7 */
/*
 * Reference:
 *
 *          Martin Richards,
 *                "A Compact Function for Regular Expression
 *                            Pattern Matching"
 *          [Software--Practice and Experience, Vol 9, 527-534 (1979)]
 */


#include <exec/types.h>

/*** Static Variables: ***/

#define Endstreamch 0xFF

UBYTE   *Work = NULL;    int Wp = 0,     Succflag = FALSE;
char     *Pat = 0;       UBYTE *Aux = 0;
UBYTE    Ch = 0;          int PatP = 0,   Patlen = 0,
        Errflag = FALSE;


/*** The Interpreter: ***/

Match(Pat, Aux, Str) UBYTE *Aux; char *Pat, *Str; {/*$(1*/
    UBYTE W[128];
    int S = 0;
/* declare local BCPL vars */
    int N, I; UBYTE P, Q; char K;
/***********************/
    Work = W;
    Wp = 0;
    Succflag = FALSE;
    Put(1);
    if (!(Aux[0]==0)) Put(Aux[0]);
  do {/*$(2*/
    for (N=1; N <= Wp; N++) { /* first complete the closure: */
        P=Work[N];
        K = Pat[P]; Q = Aux[P];
        switch(K)
        {
         case '#':  Put(P+1);
         case '%':  Put(Q);
         default:   break;
         case '(':
         case '|':  Put(P+1);
                    if (Q != 0) Put(Q);
        }
    }
    if (S >= Str[0]) return Succflag;
    if (Wp == 0) return FALSE;
    Ch = Str[++S];

    /* now deal with match items: */
    N = Wp;
    Wp = 0; Succflag = FALSE;

    for (I = 1; I <= N; I++) {
        P = Work[I];
        K = Pat[P];
        switch(K) {
         case '#':
         case '|':
         case '%':
         case '(':
                    break; /* BCPL was 'loop' */
         case '\'': K = Pat[P+1];
         default:  if (Ch != K) break; /* 'loop' */
         case '?':  /* successful match */
                    Put(Aux[P]);
                    break; /* 'loop' */
        }
    }
  }/*$)2*/ while (TRUE);
}/*$)1*/ /*** end Match ***/


Put(N) int N; {
    int I; /* not needed by BCPL */
    if (N == 0)
        Succflag = TRUE;
    else {
        for (I = 1; I <= Wp; I++) if (Work[I] == N) return;
        Work[++Wp] = N;
    }
}


/*** The Compiler: ***/

Rch() {
    if (PatP >= Patlen)
        Ch = Endstreamch;
    else {
        Ch = Pat[++PatP];
    }
}

Nextitem() {
    if (Ch == '\'') Rch();
    Rch();
}

int Prim()
{   int A = PatP; UBYTE Op = Ch;
    Nextitem();
    switch(Op) {
     case Endstreamch:
     case ')':
     case '|':  Errflag = TRUE;
     default:   return A;
     case '#':  Setexits(Prim(), A);
                return A;
     case '(':  A = Exp(A);
                if (Ch != ')') Errflag = TRUE;
                Nextitem();
                return A;
    }
}

int Exp(AltP) int AltP;
{/*$(1*/
    int Exits = 0, A;
    do/*$(2*/{ A = Prim();
        if (Ch == '|' || Ch == ')' || Ch == Endstreamch)
            {   Exits = Join(Exits, A);
                if (Ch != '|') return Exits;
                Aux[AltP] = PatP;
                AltP = PatP;
                Nextitem();
            }
        else Setexits(A, PatP);
    }/*$)2*/ while (TRUE);
}/*$)1*/


Setexits(List, Val) int List, Val; {
    int A;
    while (List != 0) {
        A = Aux[List];
        Aux[List] = Val;
        List = A;
    }
}

int Join(A, B) int A, B;
{
    int T = A;
    if (A == 0) return B;
    while (Aux[A] != 0) A = Aux[A];
    Aux[A] = B;
    return T;
}

int CmplPat(Pattern, CmplPattern) char *Pattern, *CmplPattern;
{
    int I; /* BCPL local */
    Pat = Pattern; Aux = CmplPattern;
    PatP = 0; Patlen = Pat[0]; /** this is a BSTR!!! **/
    Errflag = FALSE;
    for (I = 0; I <= Patlen; I++) Aux[I] = 0;
    Rch();
    Setexits(Exp(0), 0);
    return !Errflag;
}