#!/usr/bin/env python

'''This code is based on my 1988 C code that does the same thing, simulates
an EFC (Electronic Filing Cabinet).  An EFC is a hardware solution to fast
document searches while allowing for common errors.  Along the way I
found some bugs and converted to object oriented programming.  For more than
you might care to read about it :-), see

    https://udel.edu/~mm/mee/

Mike Markowski
Sep 2026
'''

import os, sys

CM_NO = 16  # Probably a reasonable number of character matchers.
TOK_NO = 10 # Purposely too many token followers per string matcher.

class State:
    '''The EFC is controlled by a Finite State Machine.  This class
    represents a state in the FSM.
    '''

    def __init__(self, num, stActions):
        self.num = num
        self.stActions = stActions
        self.transitions = {} # List of transition:state pairs.

    def __str__(self):
        s = 'state %d: actions %s, transitions:\n' \
            % (self.num, hex(self.stActions))
        for k in self.transitions.keys():
            s += ' %02x -> state %d\n' % (k, self.transitions[k])
        return s

    def actions(self):
        '''Upon arrival in a new state, the actions are performed.  They are
        indicated by the 6-bit pattern in stActions.  From MSB to LSB:

            5: ref - set/unset otheR Error Flag.
            4: ef  - set/unset Error Flag.
            3: i1  - increment token pointer by 1.
            2: i2  - increment token pointer by 2.
            1: ie  - increment error count by 1.
            0: ab  - when set, abort search.
        '''
        return self.stActions

    def addTransitions(self, trigDict):
        '''When creating the FSM, add a dictionary of trigger:newState
        pairs.  The trigger is only looked at, not modified.  A trigger is a
        5-bit pattern where each bit indicates boolean true/false or yes/no:

        4: i   - incoming char matches char matcher i.
        3: i+1 - incoming char matches char matcher i+1.
        2: i-2 - incoming char matches char matcher i-2.
        1: ef  - Error Flag is/isn't set.
        0: ref - OtheR Error Flag is/isn't set.

        The new state associated with a trigger is simply an integer, the
        name of the new state which is also the index into the FSM array of
        states.
        '''
        self.transitions = trigDict

    def nextState(self, trigger):
        '''Once the FSM is built, this subroutine is used to move from state
        to state in the FSM based on the trigger.
        '''
        return self.transitions[trigger]

class Fsm:
    '''The heart of the EFC!  Incoming characters are compared to
    appropriate character matchers as described in the thesis.  Those
    results, together with the two internal error flag states, are used to
    generate a trigger.  In more detail, one FSM is used by all token
    followers.  Once created it is never changed.

    1. Every new token follower enters fsm[2], that is, State 2 in the FSM.
    2. Upon state entry, perform specified actions.
    3. Based on three char matcher outputs and error flags, create 5-bit
       trigger.
    4. Use trigger to transit to new state in FSM.
    5. If abort flag is set or token follower moved beyond last char in
       target string, stop and deactivate token follower.
    6. Go to 2.
    '''

    def __init__(self):
        self.fsm = self.mkFsm()

    def __str__(self):
        s = ''
        for st in self.fsm:
            s += str(st) + '\n'
        return s

    def mkFsm(self):
        fsm = []

        # Create the seven states and actions upon arrival.
        # Action bits are: ref ef i1 i2 ie ab
        # (0x20) ref: set ref
        # (0x10) ef: set ef
        # (0x08) i1: increment token pointer by 1.
        # (0x04) i2: increment token pointer by 2.
        # (0x02) ie: increment error counter by 1.
        # (0x01) ab: abort search.
        fsm.append(State(0, 0x20)) # Set ref.
        fsm.append(State(1, 0x01)) # Set abort.
        fsm.append(State(2, 0x00))
        fsm.append(State(3, 0x16)) # Set ef, i2, ie.
        fsm.append(State(4, 0x06)) # Set i2, ie.
        fsm.append(State(5, 0x08)) # Set i1.
        fsm.append(State(6, 0x0a)) # Set ie, i1.

        # Trigger/destinations for state.
        # Trigger bits are: i i+1 i-2 ref ef
        # (0x10) i:   expected char (token pointer).
        # (0x08) i+1: next expected char.
        # (0x02) i-2: second previous expected char.
        # (0x02) ref: ref setting.
        # (0x01) ef:  ef setting.
        t = {0x00:0, 0x04:0, 0x08:3, 0x0c:3, 0x1c:5}
        fsm[0].addTransitions({0x02:1, 0x06:1, 0x0a:4, 0x0e:4, 0x1e:6})
        fsm[1].addTransitions(t)
        fsm[2].addTransitions(t)
        fsm[3].addTransitions({0x01:0, 0x05:2, 0x0d:2, 0x09:4, 0x1d:5})
        fsm[4].addTransitions(t)
        fsm[5].addTransitions(t)
        fsm[6].addTransitions(t)

        return fsm

    def transit(self, state, trigger):
        if state is None:
            state = self.fsm[2] # The old efc.c activates as st->next->next.
        trigger = 0x1c|trigger if 0x10&trigger else trigger # Mask don't-cares.
        stNum = state.nextState(trigger)
        return self.fsm[stNum]

class TokenFollower:
    '''This class is used to do the work to move through the FSM.  It
    performs the character matching, trigger generation, performing state
    actions and remembering current state.

    A big reason for this simulator is to determine how many token followers
    should be built in hardware.  Too few results in poor performance.  Too
    many wastes money and space.
    '''

    def __init__(self, iCell):
        self.reset()
        self.iCell = iCell # Index number of cell.
        self.aNominal = 0 # Activation order of this token follower.

    def abort(self, a=None):
        '''FSM has determined there is no match with incoming characters and
        target.
        '''
        if a is not None:
            self.isAbort = a
        return self.isAbort

    def active(self, act=None):
        '''Getter/setter to set or determine if this token follower is
        active.
        '''
        if act is not None:
            self.isActive = act
        return self.isActive

    def cell(self):
        '''Return character matcher index that the token follower points to.
        This is modified by movement through the FSM.
        '''
        return self.iCell

    def errFlags(self, ef=None, ref=None):
        '''Getter/setter for the two error flags.  These are only get/set
        by transitions and actions in the FSM.
        '''
        if None not in [ef, ref]:
            self.ef = ef   # Deletion/transposition Error Flag.
            self.ref = ref # Insertion/substitution otheR Error Flag.
        return self.ef, self.ref

    def errCnt(self):
        '''Return number of errors counted so far while moving through the
        FSM.
        '''
        return self.errs

    def follow(self, fsm, i, ip1, im2):
        '''Token follows FSM and moves forward one state and perform actions
        upon entry to new state.

        Inputs:
          i (boolean): indicates if char matcher i does/doesn't match.
          ip1 (boolean): indicates if char matcher i+1 does/doesn't match.
          im2 (boolean): indicates if char matcher i-2 does/doesn't match.
        Output:
          None
        '''

        trigger = (i<<4) | (ip1<<3) | (im2<<2) | (self.ref<<1) | self.ef
        self.state = fsm.transit(self.state, trigger) # Move one state in FSM.
        actions = self.state.actions()

        # Act on new state's actions.
        self.ref     = (0x20 & actions) == 0x20 # REF, otheR Error Flag.
        self.ef      = (0x10 & actions) == 0x10 # EF, Error Flag.
        self.isAbort = (0x01 & actions) == 0x01 # Abort search.
        if 0x08 & actions:
            self.iCell += 1
        if 0x04 & actions:
            self.iCell += 2
        if 0x02 & actions:
            self.errs += 1

    def order(self, aNominal=None):
        if aNominal is not None:
            self.aNominal = aNominal
        return self.aNominal

    def reset(self):
        self.isActive = False # Initially in active.
        self.state = None     # Current state EFC FSM.
        self.errs = 0         # Total number of ref and ef occurrences.
        self.iCell = 0        # Cell that token pointer is pointing to.
        self.ref = False      # Deletion/transposition has/hasn't occurred.
        self.ef = False       # Insertion/substitution has/hasn't occurred.
        self.isAbort = False  # Do/don't abort search.

class CharacterMatcher:
    '''Currently just performs simple character match, but can be extended
    to match classes of characters like alpha, numeric, etc., as described
    in Mules' thesis.
    '''

    def __init__(self):
        self.isActive = False

    def active(self, act=None):
        '''Getter/setter to set or determine if this token follower is
        active.
        '''
        if act is not None:
            self.isActive = act
        return self.isActive

    def match(self, c):
#       return self.isActive and (c in self.chList) # For multiple chars.
        return self.isActive and (c == self.chList)

    def target(self, chList=None):
        self.chList = chList # Characters that can be matched.

class StringMatcher:

    def __init__(self):
        self.enabled = False

        # Instantiate array of token followers.
        self.tf = []
        for cell in range(TOK_NO):
            self.tf.append(TokenFollower(cell))

        # Instantiate array of character matchers.
        self.cm = []
        for i in range(CM_NO):
            self.cm.append(CharacterMatcher())

    def enable(self, en):
        self.enabled = en

    def feed(self, fsm, c, aOrd, errMax, wl=None):
        '''Feed substring matcher a new incoming character.
        '''

        # Activate a new token follower.
        aNom = -1 # Slot index activated this call, or -1 if pool was full.
        for t in range(TOK_NO):
            if not self.tf[t].active():
                tok = self.tf[t]
                tok.reset()
                tok.active(True)
                tok.order(aOrd)
                aOrd += 1 # Order of activation, can be > TOK_NO.
                aNom = t # Tok follower index of activation.
                break
        else:
            print('Ran out of token followers.')

        # Count active token followers for stats gathering.
        nActive = 0
        for t in range(TOK_NO):
            if self.tf[t].active():
                nActive += 1

        # Move each token follower 1 state through FSM.
        match = False
        for iTok in range(TOK_NO):
            tok = self.tf[iTok]
            if self.tf[iTok].active():
                cm = self.cm # Shorter name.
                cur = tok.cell() # Cell pointed to by token follower.
                i = ip1 = im2 = False
                if cur < len(cm) and cm[cur].match(c):
                    i = True
                if cur < len(cm)-1 and cm[cur+1].match(c):
                    ip1 = True
                if cur > 1 and cm[cur-2].match(c):
                    im2 = True
                tok.follow(fsm, i, ip1, im2) # Move 1 state in FSM.

                # Check if match occurred.
                nErr = 0
                tErrs = tok.errCnt()
                if wl is not None: # Mods from studying original system.
                    if ((   tErrs == 1 and wl <= 6)
                        or (tErrs == 2 and wl in [7,8])
                        or (tErrs == 3 and wl in [9,10])
                        or (tErrs >= 4)):
                        tok.abort(True)
                elif tok.errCnt() == 1+errMax: # Original for errMax==3.
                    tok.abort(True)
                elif tok.cell() >= len(cm) or not cm[tok.cell()].active():
                    match = True # Candidate word matched target.
                    nErr = tok.errCnt()
                    break

            if tok.abort(): 
                tok.reset()
                continue
        # Three things tracked for statistical summary:
        #   iTok is index of token follower that matched/aborted.
        #   aOrd is order of activation.
        #   aNom is name of token follower of initial activation.
        return match, nActive, nErr, iTok, aOrd, aNom

    def match(self, c, t):
        val = 0
        cm = self.cm

        ef, ref = self.errFlags()
        i = self.tf[t].cell()

        if cm[i].match(c): # c matches char matcher i.
            val |= 0x10
        if i < len(cm)-1 and cm[i+1].match(c): # c matches char matcher i+1.
            val |= 0x08
        if i > 1 and cm[i-2].match(c): # c matches char matcher i-2.
            val |= 0x04
        if ref:
            val |= 0x02
        if ef:
            val |= 0x01
        return val

    def reset(self):
        for i in range(TOK_NO):
            self.tf[i].reset()

    def target(self, wd=None):
        if wd is not None:
            for c in self.cm:
                c.active(False)
            for i in range(len(wd)):
                c = self.cm[i]
                c.active(True)
                c.target(wd[i])
            self.wd = wd
        return self.wd

class Stats:
    '''This class is instantiated for target words of a particular length.
    '''

    def __init__(self, wds):
        '''As characters stream in, token followers are activated and
        deactivated in an unpredictable way
        '''
        # Words mismatch with cardinal (actual) token follower i.
        self.nNom = [0 for _ in range(TOK_NO)] # Number of mismatches.
        self.pNom = [0 for _ in range(TOK_NO)] # Probability of mismatches.
        # Mismatching words with 0-3 errors.
        self.nErrors = [0 for _ in range(TOK_NO)] # Count of errors.
        self.pErrors = [0 for _ in range(TOK_NO)] # Probability of errors.

        self.mismatches = 0 # Mismatches for this word length.
        self.mostUsed = 0 # Most tokens used in any match.
        self.nToksUsed = [0 for _ in range(TOK_NO)] # Tok followers used for match.
        self.wds = wds # Words in this Kucera-Francis db subset.

    def errors(self, nErr, occTarg=None, occCand=None):
        if occTarg is not None:
            self.nErrors[nErr] += 1
            self.pErrors[nErr] += (occTarg*occCand)/self.wds**2
        return self.nErrors[nErr], self.pErrors[nErr]

    def misMatches(self, occTarg=None, occCand=None):
        if occTarg is not None:
            self.mismatches += (occTarg*occCand)/self.wds**2
        return self.mismatches

    def toksMost(self, used=None):
        if used is not None:
            self.mostUsed = max(self.mostUsed, used)
        return self.mostUsed

    def toksUsed(self, j, occTarg=None, occCand=None):
        '''Histogram of peak simultaneous token-follower usage across
        candidate words, weighted by occTarg*occCand. j is the peak
        count minus 1 (0 -> 1 token used, 1 -> 2 tokens used, etc.),
        matching efc.c's wd_info[wd_len].toks_used[tok_high].
        '''
        if occTarg is not None:
            self.nToksUsed[j] += (occTarg*occCand)/self.wds**2
        return self.nToksUsed[j]

###########################################################################

def cli(argv):
    prog = os.path.basename(argv[0])
    argv = argv[1:]
    arg = None
    i = 0
    errMax = 3 # Custom error thresholds not in use by default.
    retro = False
    while i < len(argv):
        arg = argv[i]
        if arg[0] != '-':
            break
        elif arg == '-1988': # Python data type of incoming IQ.
            retro = True
        elif arg == '-e': # Max errors allowed.
            i += 1
            if argv[i] == 'm': # Modified, variable error thresholds.
                errMax = -1
            else:
                errMax = int(argv[i])
                if errMax <= 0:
                    usage(prog)
            mod = True
        else:
            usage(prog)
        i += 1
    if arg == None:
        usage(prog)
    fname = arg
    return retro, errMax, fname

def kfdbRead(kfDb, mike1988):
    db = []
    tot = 0
    f = open(kfDb, 'r') # Kucera-Francis words.
    while True:
        wd, occur = wdGet(f, mike1988)
        if wd is None:
            break # Done!
        db.append([wd, int(occur)])
        tot += db[-1][1]
    f.close()
    return db, tot

def efc(kfDb, mike1988, errMax=3):

    fsm = Fsm()
    db, wds = kfdbRead(kfDb, mike1988)
    wl = None # Used when errMax==-1 to use word len based error thresholds.

    # Prepare to gather statistics, one set per word length.
    stats = []
    for _ in range(16):
        stats.append(Stats(wds))

    # Global stats for final summary.
    matchingTok = [0 for _ in range(5*TOK_NO + 1)]
    nomTok = [0 for _ in range(TOK_NO + 1)]
    sm = StringMatcher() # The one and only string matcher in this sim.

    for iTarg in range(len(db)): # Loop through target words.
        target, occTarg = db[iTarg]
        sm.target(target) # New target word.
        tlen = len(target) - 1

        for iCand in range(len(db)): # Loop through candidate words.
            cand, occCand = db[iCand]
            if cand is None:
                break # Done!
            isSelf = (iCand == iTarg)
            if isSelf and not mike1988:
                # Avoid my 1988 bug!  Info on matches should never be kept.
                # My old code partially did.  Please don't take my degree
                # away. :-D
                continue
            if errMax == -1:
                wl = len(target)

            # Feed word, char by char, to substring matcher.
            most = 0
            tokHigh = -1 # Most followers activated for this word.
            ord0 = 0 # Token follower activation order for this word.
            for ch in cand: # Use each character.
                match,nActive,nErr,iTok,ord1,aNom = sm.feed(
                    fsm, ch, ord0, errMax, wl)
                ord0 = ord1 # Age counter from feed().
                most = max(most, nActive) # Most token followers active.
                tokHigh = max(tokHigh, aNom)
                if match:
                    break

            stats[tlen].toksMost(most)
            if tokHigh >= 0:
                stats[tlen].toksUsed(tokHigh, occTarg, occCand)
            if match: # target & candidate words match!
                if not isSelf:
                    stats[tlen].misMatches(occTarg, occCand)
                stats[tlen].errors(nErr, occTarg, occCand)
                if mike1988 or not isSelf:
                    matchOrder = sm.tf[iTok].order() + 1
                    wds = stats[tlen].wds
                    matchingTok[matchOrder] += (occTarg*occCand)/wds**2
                    nomTok[iTok+1] += occTarg/stats[tlen].wds
            sm.reset()
    results(stats, matchingTok, nomTok)
    plotFiles(stats, kfDb)

def plotFiles(s, fname, matchingTok=None, nomTok=None):
    base = os.path.basename(fname)
    dot = base.rfind('.')
    if dot > 0:
        base = base[:dot]

    f = open(base+'-mm.dat', 'w')
    for i in range(3, 16):
        print('%d %.6e' % (1+i, s[i].misMatches()), file=f)
    f.close()

    pTot = [0 for _ in range(16)]
    for i in range(3, 16):
        # Calculate tmpTotToks for wd len i.
        pTot[i] = 0
        for j in range(4):
            _,pErr = s[i].errors(j)
            pTot[i] += pErr

    for j in range(1,4):
        dname = base + '-err%d.dat' % j
        f = open(dname, 'w')
        for i in range(3, 16):
            _,pErr = s[i].errors(j)
            if pTot[i] == 0:
                print('%d 0' % (1+i), file=f)
            else:
                print('%d %.6e' % (1+i, pErr/pTot[i]), file=f)
        f.close()

def results(s, matchingTok=None, nomTok=None):

    # Mismatches per word length.
    toksSubtot = [0 for _ in range(TOK_NO)]
    tokErrs = [0 for _ in range(4)]
    mmTot = wdTot = toksTot = allErrs = avgTot = 0
    for i in range(3, 16):
        print('\n%d letter target string:\n' % (1+i))
        mm = s[i].misMatches()
        if mm > 0:
            print('  %1.8f mismatches.\n' % mm)
            mmTot += mm

        # Tokens used per word length.
        tmpWdTot = avgWd = 0
        for j in range(TOK_NO):
            pUsed = s[i].toksUsed(j)
            if pUsed == 0: # No words of len i peaked at j+1 tok followers.
                continue
            avgWd  += pUsed*(j+1) # Fraction of matches using j+1 tok followers.
            avgTot += pUsed*(j+1)
            toksSubtot[j] += pUsed
            toksTot       += pUsed
            tmpWdTot      += pUsed
            wdTot         += pUsed

        for j in range(TOK_NO):
            pUsed = s[i].toksUsed(j)
            if pUsed == 0:
                continue
            print('  %1.8f used %2d tokens.' % (pUsed/tmpWdTot, j+1))

        tmpTotToks = 0
        cntTot = 0
        for j in range(4):
            nErr, pErr = s[i].errors(j)
            if nErr == 0:
                continue
            tmpTotToks += pErr
            tokErrs[j] += pErr
            allErrs    += pErr
            cntTot     += nErr

        print()
        for j in range(4):
            nErr, pErr = s[i].errors(j)
            if nErr == 0:
                continue
            print('  %1.8f prob of matching tokens had %d errors.'
                % (pErr/tmpTotToks, j))
        if avgWd > 0:
            print(' Average: %1.8f tokens per %d-letter word.'
                % (avgWd/tmpWdTot, i+1))

    # Overall summary across all word lengths.
    print('\n%1.8f total mismatches.\n' % mmTot)
    for j in range(TOK_NO):
        if toksTot > 0:
            print('%1.8f used %d tokens.' % (toksSubtot[j]/toksTot, j+1))
    if wdTot > 0:
        print('\nAverage: %1.8f tokens per word.' % (avgTot/wdTot))
    mstTok = 0
    for j in range(TOK_NO):
        if toksSubtot[j] > 0:
            mstTok = j
    print('Most:    %d tokens.\n' % (mstTok+1))

    for j in range(4):
        if allErrs > 0:
            print('%1.8f had %d errors.' % (tokErrs[j]/allErrs, j))

    if matchingTok is not None and nomTok is not None:
        matchTokTot = 0
        for n in matchingTok:
            matchTokTot += n
        nomTokTot = 0
        for n in nomTok:
            nomTokTot += n
        print()
        for j in range(1, len(matchingTok)):
            if matchingTok[j] and matchTokTot > 0:
                print('%1.8f words were matched with activated token %d'
                    % (matchingTok[j]/matchTokTot, j))
        print()
        for j in range(1, TOK_NO+1):
            if nomTok[j] and nomTokTot > 0:
                print('%1.8f words were matched with the real token %d'
                    % (nomTok[j]/nomTokTot, j))

def usage(prog):
    print('Usage: %s -1988 -m errs words' % prog)
    print('  -1988: generate results using my original (buggy!) code')
    print('  -m v: variable error thresholds from 1988 studies.')
    print('  -m #: flat error study using max errors of #.')
    sys.exit(1)

def wdGet(f, mike1988):
    line = f.readline()
    if line == '':
        return None, None
    word, freq = line.split()
    if mike1988:
        word = word[:CM_NO-1] # Bug in my 1988 thesis. :-o
    else:
        word = word[:CM_NO]
    freq = int(freq)
    return word, freq

def main(argv):
    mike1988, errMax, kfDb = cli(argv)
    efc(kfDb, mike1988, errMax)

if __name__ == '__main__':
    main(sys.argv)