The DFA (deterministic finite-state automata) library is posted here primarily
for use in building the BLAST application programs for biosequence similarity
searching.  See /pub/blast for that software.

dfa.tar.Z is a compressed UNIX tar archive of all of the files splayed beneath
the explode subdirectory.  A single UNIX command pipeline can be used to
unpack the archive:  zcat dfa.tar | tar xf -

The DFA source code requires header files from the stripped-down ncbi library
(see /pub/ncbi) and my personal header files from gish.h (see /pub/gish).

=================================

CAVEAT EMPTOR:  the documentation file, dfa.3, a UNIX-style manual page,
has not been closely examined for consistency with the source code.

The DFA function library distribution includes the following files:

    README
    Makefile - makefile for SunOS and other UNIXes
    dfa.3 - manual page (nroff -man macros) for section 3 of the manual
    dfa.h - generally used header file
    dfa.c - core functions (dfa_new,dfa_begin,dfa_add,dfa_close)

Additional source files:

    accepts.c
    contains.c
    destruct.c
    dump.c
    check.c
    nextstat.c
    errstr.c
    extent.c
    fscanf.c
    perror.c
    pscanf.c
    scanf.c
    size.c
    sscanf.c

    dfatest.c - a small test program (not even close to being comprehensive!)

When compiling, the C preprocessor variable DFA_THENEED4SPEED can be defined
to omit some error checking for a modest improvement in execution speed.

Warren Gish
September 15, 1991

Modification History
4/6/93
Added a few functions to dfa.c, e.g. dfa_addx().

2/18/92
Several changes made, primarily to accommodate the NCBI standard alphabets
for representation of bio-sequences.

o dfa_open() no longer exists for creating a new dfa structure.  It is replaced
by the function dfa_new(), along with a few ancillary functions.  dfa_new()
has only two arguments, the minimum and maximum letter values (both signed
integers) in the working alphabet.

o the library no longer pre-defines any alphabets.  The specification
of an alphabet is left entirely to the developer.

o when dfa_open() was discarded, so were its special-case, obscurely
defined flags.  A saner, more flexible arrangement now exists in the form
of 2 new functions, dfa_ignore() and dfa_halton(), which are called upon
to indicate letters in the input stream that either should be ignored
or should halt a search.  For instance, when searching a plain text
file being read with getchar(), hyphens might be ignored and EOF (-1)
should halt the search.

o elements in the typedef for the DFA structure have been "opened up"
to the developer in the header file dfa.h, so that they can be directly
referenced without the need to interrogate values via calls to functions
in the dfa library.  As a result, several of the dfa functions could be
and have been discarded, e.g. dfa_statesize() and dfa_nstates() are
unnecessary because references of the form dp->statesize and dp->nstates,
where dp is a DFAPtr, can be made instead.  The private header file dfa_priv.h
has been eliminated.

o source code and documentation are each about 33% smaller.

6/10/92
Corrected the name of dfa_restore() (formerly called dfa_restart)
and corrected some but probably not all inconsistencies in the documentation
files dfa.3 and dfa.3ps.

6/15/92
Modified the DFA_Accept structure in preparation for implementing
variable-length pattern identifiers.

7/7/92
Corrected some of the remaining inaccuracies/errors in the dfa.3 manual page.

7/20/92
Changed the "pattern" argument to dfa_contains() and dfa_accepts()
from CharPtr to unsigned char *.  Fixed bug in dfa_contains().

7/26/92
A few changes in preparation for migrating to the Mac and MS-Windows.

