#include <stdio.h>
#include <string.h>
#include <assert.h>

typedef unsigned int Bit;

struct Edge {
    Edge() { _l=0; _d=0; _t=0; _e=0; }
    Bit _l : 5;     // the letter encoded by this edge
    Bit _d : 25;    // indexes to the 1st edge of the node this edge goes to
    Bit _t : 1;     // flag indicating if this edge's node is terminal
    Bit _e : 1;     // flag indicating if this edge is the last of its node
};

class ArrayGraph {
public:
    ArrayGraph( Edge *pEdges, int nEdges, int iStartIndex );
    ~ArrayGraph() { if ( _pEdges ) delete _pEdges; }

    int recognizes( char *pWord ) const;
private:
    int matchChar( char c, int iStart ) const;
    Edge *_pEdges;
    int _iStartIndex;
    int _nEdges;
};

class Node;
typedef Node *NodePtr;

class Node {
public:
    Node();
    ~Node();

    NodePtr addChar( char c, int *pfNewNodeCreated );
    NodePtr matchChar( char c );

    void setTerminal();
    int isTerminal();

    static void dumpDebug();

private:
    friend class Graph;
    static int s_currentID;

    NodePtr _t[26];
    Bit _fTerminal : 1;
    Bit _reserved : 23;
};

int Node::s_currentID = 0;

class NodeSet {
public:
    NodeSet();
    ~NodeSet();
    int add(NodePtr);
    void remove(NodePtr);
    void removeAll();
    int contains(NodePtr) const;
    int size() const { return _nElem; }
    NodePtr elemAt(int index) const;
    void dumpDebug() const;
private:
    class ListNode {
    public:
        ListNode( NodePtr p = 0, ListNode *pLN = 0 ) { _pNode = p; _pNext = pLN; }
        ~ListNode() { _pNode = 0; _pNext = 0; };
        NodePtr _pNode;
        ListNode *_pNext;
    };

    ListNode _Head;
    int _nElem;
};

class Graph {
public:
    Graph();
    ~Graph();

    void addWord( char *pWord);
    int recognizes( char *pWord ) const;

    ArrayGraph *minimize(); // returns a new Graph that is minimized!

private:
    enum { MAX_NUM_SETS = 150000 };
    struct GID {
        GID() { int i; for (i=0;i<26;++i) { _toGrp[i] = -2; } }
        int operator==(const GID& g)
            { int i;
              for (i=0;i<26;++i) {
                if (_toGrp[i] != g._toGrp[i])
                    return 0;
              }
              return 1;
            }
        int isValid() { int i; for (i=0;i<26;++i) { if ( _toGrp[i] == -2 ) return 0; } return 1; }

        int _toGrp[26];
    };

    struct Group {
        GID _id;
        NodeSet _ns;
    };

    NodePtr _pStartNode;
    Group *_pGrps;
};

ArrayGraph::ArrayGraph( Edge *pEdges, int nEdges, int iStartIndex) :
 _pEdges(pEdges), _nEdges(nEdges), _iStartIndex(iStartIndex)
{ 
    assert( pEdges );
    assert( nEdges );
}

int ArrayGraph::matchChar( char c, int iStart ) const {
    c = c - 'A';
    assert( c >= 0 );
    int fLastEdge;
    int curEdge = iStart;
    do {
        fLastEdge = _pEdges[curEdge]._e ? 1 : 0;
        // Need to check for state that points back at itself, and
        // reject any edge for it (this is the terminal state that really
        // has no valid outgoing edges).
        if (_pEdges[curEdge]._l == c && _pEdges[curEdge]._d != iStart) {
            return _pEdges[curEdge]._d; // found an edge for the char, ret
                                       // the 1st edge of the dest. state.
        }
        ++curEdge;
    } while ( !fLastEdge );

    return -1; // no edge found for the char
}

int ArrayGraph::recognizes( char *pWord ) const {
    assert( pWord );
    int l = strlen( pWord );
    int i;
    int edgeIndex = _iStartIndex;
    for (i=0 ; i<l ; ++i) {
        edgeIndex = matchChar( pWord[i], edgeIndex );
        if (edgeIndex == -1) {
            printf( "\n" );
            return 0; // return of -1 from matchChar means no such edge
        }
    }
    // If we pass the loop, then the char sequence has been
    // recognized; now make sure that the sequence is considered
    // a complete word by the dictionary.
    assert( edgeIndex >= 0 && edgeIndex < _nEdges );
    return ( _pEdges[edgeIndex]._t );
}

NodeSet::NodeSet() : _Head(), _nElem(0)
{
}

NodeSet::~NodeSet()
{
//    printf( "NodeSet dtor\n" );
    ListNode *pDel = _Head._pNext;
    ListNode *pNextDel = pDel ? pDel->_pNext : 0;
    int nDel = 0;

    while ( pDel ) {
        ++nDel;
        delete pDel;
        pDel = pNextDel;
        pNextDel = pDel ? pDel->_pNext : 0;
    }

    assert( nDel == _nElem );
}

int NodeSet::add(NodePtr p)
{
    if ( contains(p) )
        return 0;

    ListNode *pNewLN = new ListNode( p, _Head._pNext );
    assert( pNewLN );

    _Head._pNext = pNewLN;
    ++_nElem;
    return 1;
}

void NodeSet::remove(NodePtr p)
{
    ListNode *pIter = _Head._pNext;
    ListNode *pParent = &(_Head);
    while ( pIter ) {
        if ( pIter->_pNode == p ) {
            pParent->_pNext = pIter->_pNext;
            delete pIter;
            --_nElem;
            return;
        }
        pParent = pParent->_pNext;
        assert( pParent == pIter );
        pIter = pIter->_pNext;
    }
}

void NodeSet::removeAll()
{
    ListNode *pIter = _Head._pNext;
    ListNode *pNext = NULL;
    while ( pIter ) {
        pNext = pIter->_pNext;
        delete pIter;
        pIter = pNext;
    }
    _Head._pNext = 0;
    _nElem = 0;
}

int NodeSet::contains(NodePtr p) const
{
    ListNode *pIter = _Head._pNext;
    while ( pIter ) {
        if ( pIter->_pNode == p ) {
            return 1;
        }
        pIter = pIter->_pNext;
    }
    return 0;
}

NodePtr NodeSet::elemAt(int index) const {
    assert( index < size() );
    ListNode *pIter = _Head._pNext;
    int curIndex = 0;
    while ( pIter && curIndex < index ) {
        pIter = pIter->_pNext;
        ++curIndex;
    }

    assert ( pIter->_pNode );
    return pIter->_pNode;
}

void NodeSet::dumpDebug() const {
    int i;
    int l = size();
    printf( "Class NodeSet @ %x : %d elem : ", this, l );
    NodePtr pIter = 0;
    for (i=0 ; i < l ; ++i) {
        pIter = elemAt(i);
        assert( pIter );
        assert( contains( pIter ) );
        printf( "%x ", pIter );
    }
    printf( "\n" );
}

void Node::dumpDebug() {
    printf( "Class Node debug: %d # outstanding\n", s_currentID );
}

Node::Node() {
    int i;
    for (i=0 ; i < 26 ; ++i) {
        _t[i] = NULL;
    }
    _fTerminal = 0;
    _reserved = 0;
    s_currentID++;
}

Node::~Node() {
    int i;
    for (i=0 ; i < 26 ; ++i) {
        if ( _t[i] ) {
            delete _t[i];
            _t[i] = 0;
        }
    }
    s_currentID--;
}

NodePtr Node::addChar( char c, int *pfNewNodeCreated ) {
    assert( pfNewNodeCreated );
    int l = c - 'A';
    if ( _t[l] ) {
        *pfNewNodeCreated = 0;
        return _t[l];
    }
    else {
        *pfNewNodeCreated = 1;
        _t[l] = new Node();
        assert( _t[l] && "Failed to create node");
        return _t[l];
    }
}

NodePtr Node::matchChar( char c ) {
    int l = c - 'A';
    return _t[l];
}

void Node::setTerminal() {
    _fTerminal = 1;
}

int Node::isTerminal() {
    return _fTerminal;
}

Graph::Graph() {
    _pStartNode = new Node();
    assert(_pStartNode);
    _pGrps = new Group[ MAX_NUM_SETS ];
    assert(_pGrps);
    _pGrps[0]._ns.add(_pStartNode); // assume start node is nonterminal
}

Graph::~Graph() {
    assert( _pStartNode );
    delete _pStartNode;
    assert(_pGrps);
    delete [] _pGrps;
}

void Graph::addWord( char *pWord) {
    int i;
    int l = strlen( pWord );
    int fNewNodeCreated = 0;
    int fNodeAddedToSet = 0;
    NodePtr pNode = _pStartNode;
    for (i=0 ; i < l ; ++i) {
        pNode = pNode->addChar( pWord[i], &fNewNodeCreated );
        assert(pNode);
        if ( fNewNodeCreated ) {
            fNodeAddedToSet = _pGrps[0]._ns.add(pNode); // all nodes added to grp 0
        }
    }
    pNode->setTerminal();
    if ( fNodeAddedToSet ) {
        _pGrps[0]._ns.remove(pNode); // if it's terminal, remove it from grp 0..
        _pGrps[1]._ns.add(pNode); // ..and put it into grp 1
        fNodeAddedToSet = 0;
    }
    // Grp 0 contains all non-terminal nodes
    // Grp 1 contains all terminal nodes
}

int Graph::recognizes( char *pWord ) const {
    int i;
    int l = strlen( pWord );
    NodePtr pNode = _pStartNode;
    for (i=0 ; i < l ; ++i) {
        pNode = pNode->matchChar( pWord[i] );
        // a null return from matchChar means no
        // such transition exists, thus we fail to match.
        if ( !pNode ) {
            return 0;
        }
    }
    // If we pass the loop, then the char sequence has been
    // recognized; now make sure that the sequence is considered
    // a complete word by the dictionary.
    assert( pNode );
    return ( pNode->isTerminal() );
}

ArrayGraph *Graph::minimize()
{
    assert( _pStartNode );

    // Grp 0 starts as all non-terminals
    // Grp 1 starts as all terminals
    printf( "Group 0 (nonterminals) has %d elem\n", _pGrps[0]._ns.size());
    printf( "Group 1 (terminals) has %d elem\n", _pGrps[1]._ns.size());

    int lowGrp = 0;     // lower index of Grps to process
    int highGrp = 1;    // high index of Grps to process

    int newGrpLow = highGrp+1;
    int nextNewGrpOffset = 0;

    int curGrp;
    int curGrpSize;
    int curElem;
    int curEdge;

    int destGrp;

    int curNewGrp;

    NodePtr pCurElem = 0;
    NodePtr pCurElemDestNode = 0;

    int fPlacedInNewGroup;

    int nNewStatesCreatedThisPass = 0;
    int newStatesLowThisPass = newGrpLow;

    int nMinimizedStates = highGrp+1; // this represents the # of groups left after minimizing

    // Repartition until nMinimizedStates doesn't change.

    do {
        nMinimizedStates = highGrp+1;
        nNewStatesCreatedThisPass = 0;
        printf( "Starting a pass..\n" );
        // Each repartition step involves repartitioning all groups..
        for (curGrp=lowGrp; curGrp <= highGrp ; ++curGrp) {
//.            printf( "Processing group %d of %d in pass\n", curGrp, highGrp );
            // Get # elem in current group, must be >0.
            curGrpSize = _pGrps[curGrp]._ns.size();
            assert( curGrpSize );
            // ID this group by defining it as the one that will retain
            // the first element.
            for (curEdge=0 ; curEdge < 26 ; ++curEdge) {
                pCurElemDestNode = _pGrps[curGrp]._ns.elemAt(0)->_t[curEdge];
                // If we have a valid dest node for this edge, find what
                // grp the dest node is in..
                if (pCurElemDestNode) {
                    for (destGrp=lowGrp ; destGrp <= highGrp ; ++destGrp) {
                        if (_pGrps[destGrp]._ns.contains(pCurElemDestNode)) {
                            break;
                        }
                    }
                    assert( destGrp <= highGrp ); // dest node must be in some Grp!
                    _pGrps[curGrp]._id._toGrp[curEdge] = destGrp;
                }
                // else this edge goes nowhere (id as -1)
                else {
                    _pGrps[curGrp]._id._toGrp[curEdge] = -1;
                }
            }
            assert( _pGrps[curGrp]._id.isValid() );
    
            // Compute IDs for each element in the group except the first (which
            // has been defined as staying in this group).  If the ID matches
            // the current group, then the element stays.  Otherwise, the
            // element may qualify for a new group: compare the elem ID with
            // the IDs of all newly created groups (new as of this iter).
            // If it matches, it goes into that new group.  Otherwise, it forms
            // its own new group.  New groups start at index newGrpLow+nextNewGrp.
            // and range from newGrpLow to newGrpLow+nextNewGrp-1.
    
            for (curElem=1 ; curElem < curGrpSize ; ++curElem) {
                pCurElem = _pGrps[curGrp]._ns.elemAt(curElem);
                // Compute ID..
                GID elemID;
                for (curEdge=0 ; curEdge < 26 ; ++curEdge) {
                    pCurElemDestNode = pCurElem->_t[curEdge];
                    // find what Grp the dest node is in..
                    if (pCurElemDestNode) {
                        for (destGrp=lowGrp ; destGrp <= highGrp ; ++destGrp) {
                            if (_pGrps[destGrp]._ns.contains(pCurElemDestNode)) {
//.                                printf("Group %d contains dest node %x\n", destGrp, pCurElemDestNode);
                                break;
                            }
                        }
                        if ( destGrp > highGrp) {
                            printf(" pCurElemDestNode=%x\n", pCurElemDestNode );
                        }
                        assert( destGrp <= highGrp ); // dest node must be in some Grp!
                        elemID._toGrp[curEdge] = destGrp;
                    }
                    else {
                        elemID._toGrp[curEdge] = -1;
                    }
                }
                assert( elemID.isValid() );
    
                // Compare with current group..
                if ( elemID == _pGrps[curGrp]._id ) {
//                    printf( " Elem stays in group\n" );
                    continue; // if we match, then we stay.. go to next elem!
                }
    
                // Compare with new groups
                fPlacedInNewGroup = 0;
                for ( curNewGrp=newGrpLow ; curNewGrp < (newGrpLow+nextNewGrpOffset) ; ++curNewGrp) {
                    if ( elemID == _pGrps[curNewGrp]._id ) {
                        // match with a new group! add cur elem to new grp..
                        // we remove it from this group only after the
                        // entire group has been processed!!
                        _pGrps[curNewGrp]._ns.add( pCurElem );
    
                        fPlacedInNewGroup = 1; // we've been placed!
                        break;
                    }
                }
    
                // If we placed this elem in a new group..
                if ( fPlacedInNewGroup ) {
                    continue; // ..then go to next elem!
                }
    
                // If we get here, then we need to create a new group for this
                // element.
    
//.                printf( "New group created\n" );
                curNewGrp = newGrpLow+nextNewGrpOffset;
                assert( curNewGrp < MAX_NUM_SETS );
                ++nextNewGrpOffset;
                ++nNewStatesCreatedThisPass;
    
                _pGrps[curNewGrp]._id = elemID;
                _pGrps[curNewGrp]._ns.add( pCurElem );
            }

            // We've repartitioned this group.  Update new group vars and
            // move to the next group.
    
            newGrpLow += nextNewGrpOffset;
            nextNewGrpOffset = 0;

//.            printf( "Moving to next group\n" );
        }

        // All old groups in the partition have been processed in the pass.
        // During that process, a number of new groups were created.
        // However, elems that were added to those new groups have not
        // yet been removed from the old groups (they needed to be present
        // during the processing of _all_ old groups). 

        // nNewStatesCreatedThisPass tracks how many new states were
        // created this pass, from all the old groups.  New groups/states
        // begin at highGrp+1

        // Now we scan all the new groups created; all elements in those new
        // groups are removed from the old groups.

        // BUGBUG consider implemented operator- on NodeSet for readability.

        assert( lowGrp == 0 );

        for ( curNewGrp=highGrp+1 ; curNewGrp < (highGrp+1+nNewStatesCreatedThisPass) ; ++curNewGrp) {
            NodePtr pElemToRemove;
            int newGrpSize = _pGrps[curNewGrp]._ns.size();
            int curElemToRemove;
            for (curElemToRemove=0 ; curElemToRemove < newGrpSize ; ++curElemToRemove) {
                pElemToRemove = _pGrps[curNewGrp]._ns.elemAt(curElemToRemove);
                assert( pElemToRemove );
                int curOldGrp;
                for ( curOldGrp=lowGrp ; curOldGrp <= highGrp ; ++curOldGrp ) {
                    _pGrps[curOldGrp]._ns.remove( pElemToRemove );
                }
            }
        }


//.        printf( "%d new states created this pass\n", nNewStatesCreatedThisPass );

        highGrp += nNewStatesCreatedThisPass;

        assert( newGrpLow == highGrp+1 );

//.        printf( "Next pass\n" );

    } while ( highGrp != (nMinimizedStates-1) );

    printf( "%d states after minimizing\n", nMinimizedStates );
    assert( highGrp == (nMinimizedStates-1) );

    // Select a representative elem from each of the groups that has been
    // created during minimization, and generate the minimized graph.

    // Start by building an array to hold the representative states.

    NodePtr *ppRepStates = new NodePtr[nMinimizedStates];
    assert( ppRepStates );

    int i;
    int searchGrp;

    for (i=0 ; i < nMinimizedStates ; ++i) {
        ppRepStates[i] = new Node();
        assert( ppRepStates[i] );
    }

    // Link up all the representative states.
    for (curGrp=0 ; curGrp <= highGrp ; ++curGrp) {
        for (curEdge=0 ; curEdge < 26 ; ++curEdge) {
            // Get # elem in current group, must be >0.
            curGrpSize = _pGrps[curGrp]._ns.size();
            assert( curGrpSize );
            for (curElem=0 ; curElem < curGrpSize ; ++curElem) {
                pCurElemDestNode = _pGrps[curGrp]._ns.elemAt(curElem)->_t[curEdge];
                if (pCurElemDestNode) {
                    for (searchGrp=0 ; searchGrp <= highGrp ; ++searchGrp) {
                        if (_pGrps[searchGrp]._ns.contains(pCurElemDestNode)) {
                            // found the group the dest node belongs to..
                            // point this group's representative to the dest group's rep
                            ppRepStates[curGrp]->_t[curEdge] = ppRepStates[searchGrp];
                            break;
                        }
                    }
                    assert( searchGrp <= highGrp && "group not found");
                    break;
                }
            }
        }
    }

    // The start state of the minimized graph is the same as the start
    // state of the original.  Knowing the start state is sufficient,
    // because a path must exist from the start state to every other
    // state.

    // Find the start state
    for (curGrp=0 ; curGrp <= highGrp ; ++curGrp) {
        if ( _pGrps[curGrp]._ns.contains( _pStartNode ) )
            break;
    }
    assert( curGrp <= highGrp );
    printf( "Start state is in Group %d\n", curGrp );
    assert( _pGrps[curGrp]._ns.size() == 1 );

    // Store the index of the start state in ppRepStates
    int iAryStartState = curGrp;

    // Set the terminal flag in the corresponding minimized states
    for (curGrp=0 ; curGrp <= highGrp ; ++curGrp) {
        assert( _pGrps[curGrp]._ns.size() );
        if ( _pGrps[curGrp]._ns.elemAt(0)->_fTerminal ) {
            ppRepStates[curGrp]->_fTerminal = 1;
        }
    }

    // Also find the terminal repr. state that has no edges leaving it.
    // There must be one and only one such state, otherwise there's a bug
    // in the minimization.  We need to know this because in the array
    // representation, nodes are represented as a collected of edges; since
    // this state will have no edges, it will be missed!  We need to know
    // it and fake an edge for it.

    for (curGrp=0 ; curGrp <= highGrp ; ++curGrp) {
        int fEdgeFound;
        fEdgeFound = 0;
        for (curEdge=0 ; curEdge < 26 ; ++curEdge) {
            if (ppRepStates[curGrp]->_t[curEdge]) {
                fEdgeFound = 1;
                break;  // finding any edge is sufficient
            }
        }
        if ( fEdgeFound ) {
            continue;  // some edge was found, try next state
        }
        else {
            break;     // found a state with no edges!
        }
    }
    assert( curGrp <= highGrp ); // such a state MUST exist
    assert( ppRepStates[curGrp]->_fTerminal ); // it MUST be terminal

    // Give that state an edge pointing to itself.  The letter is irrelevant.
    ppRepStates[curGrp]->_t[0] = ppRepStates[curGrp];

    // Now generate the array representation of the minimized graph.
    // To do this, it is useful to be able to quickly enumerate all
    // states in the minimized graph.  ppRepStates is an array of
    // all states in the graph, hence we use it here..

    // Count the num of edges each state has, and accumulate to determine
    // the index of the first edge of each state.
    int *aEdgeIndices = new int[nMinimizedStates];
    assert( aEdgeIndices );

    int nTotalEdges = 0;
    int nEdgesForThisState = 0;
    
    for (i=0 ; i<nMinimizedStates ; ++i) {
        aEdgeIndices[i] = nTotalEdges;
        nEdgesForThisState = 0;
        for (curEdge=0 ; curEdge<26 ; ++curEdge) {
            if (ppRepStates[i]->_t[curEdge]) {
                ++nTotalEdges;
                ++nEdgesForThisState;
            }
        }
        assert( nEdgesForThisState );
        if ( i == iAryStartState ) printf( "Start state has %d edges\n", nEdgesForThisState);

        // while we're here, set the reserved bits for each state to
        // indicate what index it's found at in the ppRepStates array.
        ppRepStates[i]->_reserved = i;
    }

    printf("Minimized graph has total of %d edges\n", nTotalEdges);

    // Allocate array of edges

    Edge *aEdges = new Edge[nTotalEdges];
    assert( aEdges );

    int curEdgeInState;     // index into _t for each state
    curEdge = 0;            // index into aEdges
    int fEdgeAdded;
    for (i=0 ; i<nMinimizedStates ; ++i) {
        fEdgeAdded = 0;
        assert( curEdge == aEdgeIndices[i] );
        for (curEdgeInState=0; curEdgeInState < 26; ++curEdgeInState) {
            if ( ppRepStates[i]->_t[curEdgeInState] ) {
                aEdges[curEdge]._l = curEdgeInState;
                aEdges[curEdge]._d = aEdgeIndices[ppRepStates[i]->_t[curEdgeInState]->_reserved];
                aEdges[curEdge]._t = ppRepStates[i]->_fTerminal;
                aEdges[curEdge]._e = 0; // set the "last edge" flag later
                ++curEdge;  // finished adding an edge to the array
                fEdgeAdded = 1;
            }
        }
        // All edges for this state have been processed.
        // Set "last edge" flag on the last edge we just processed.
        aEdges[curEdge-1]._e = 1;
        assert( fEdgeAdded );
    }

    assert( curEdge == nTotalEdges );

    // Done!  Now persist the array representation of the graph.

    FILE *out = NULL;

    out = fopen( "graph.bin", "w+b" );
    assert( out );

    int nWritten = 0; 

    nWritten = fwrite(&nTotalEdges, sizeof(nTotalEdges), 1, out);
    assert( nWritten == 1 );

    int iStartStateEdgeIndex = aEdgeIndices[iAryStartState];
    nWritten = fwrite(&iStartStateEdgeIndex, sizeof(iStartStateEdgeIndex), 1, out);
    assert( nWritten == 1 );

    nWritten = fwrite(aEdges, sizeof(Edge), nTotalEdges, out);
    assert( nWritten == nTotalEdges );

    fclose( out );

    ArrayGraph *pAryGraph = new ArrayGraph( aEdges, nTotalEdges, iStartStateEdgeIndex );
    assert( pAryGraph );

    delete [] aEdgeIndices;
    delete [] ppRepStates;

    return pAryGraph;
}

int main() {

    printf( "Nodes occupy %d bytes\n", sizeof(Node) );
    printf( "Edges occupy %d bytes\n", sizeof(Edge) );

    FILE *infile = NULL;

    char* aFiles[] = { "2.txt", "3.txt", "4.txt", "5.txt", "6.txt", "7.txt", "8.txt", "9.txt", "10.txt", "11.txt", "12.txt", "13.txt", "14.txt", "15.txt" };

    char ach[20];
    int numWords = 0;
    int l;
    Graph *g = new Graph();
    assert( g );

    Node::dumpDebug();

    int i;
    int wordLen;
    for ( i=0 ; i < sizeof(aFiles)/sizeof(char*) ; ++i ) {
        wordLen = i+2;
        printf( "Processing input file %s\n", aFiles[i] );
        infile = fopen( aFiles[i], "r");
        if ( !infile ) {
            printf( "Failed to open input file\n" );
            break;
        }
        while ( fgets( ach, 20, infile ) ) {
            ach[wordLen] = '\0';
            l = strlen( ach );
            assert ( l == wordLen );
            g->addWord( ach );
            numWords++;
        }
        printf( "%d words total\n", numWords );
        fclose( infile );
    }

    Node::dumpDebug();

    /* now test that all words are recognized */
    numWords = 0;
    for ( i=0 ; i < sizeof(aFiles)/sizeof(char*) ; ++i ) {
        wordLen = i+2;
        printf( "Testing input file %s\n", aFiles[i] );
        infile = fopen( aFiles[i], "r");
        if ( !infile ) {
            printf( "Failed to open input file\n" );
            break;
        }
        while ( fgets( ach, 20, infile ) ) {
            ach[wordLen] = '\0';
            l = strlen( ach );
            assert ( l == wordLen );
            if ( g->recognizes( ach ) )
                numWords++;
        }
        printf( "%d words recognized total\n", numWords );
        fclose( infile );
    }

    printf( "Bad word BBB %d\n", g->recognizes( "BBB" ) );

    // Test minimize
    ArrayGraph *minimalGraph = g->minimize();

    /* now test that all words are recognized */
    numWords = 0;
    for ( i=0 ; i < sizeof(aFiles)/sizeof(char*) ; ++i ) {
        wordLen = i+2;
        printf( "Testing input file %s\n", aFiles[i] );
        infile = fopen( aFiles[i], "r");
        if ( !infile ) {
            printf( "Failed to open input file\n" );
            break;
        }
        while ( fgets( ach, 20, infile ) ) {
            ach[wordLen] = '\0';
            l = strlen( ach );
            assert ( l == wordLen );
            if ( minimalGraph->recognizes( ach ) )
                numWords++;
        }
        printf( "%d words recognized by minimized graph total\n", numWords );
        fclose( infile );
    }

    // cleanup!
    delete g;
    g = 0;

//    delete minimalGraph;
    minimalGraph = 0;

    Node::dumpDebug();

    return 0;

}