// File: www.cs.colorado.edu/~main/fsa.cxx

#include "fsa.h"
#include <cassert>  // Provides assert function  
#include <iomanip>  // Provides setw manipulator
#include <stack>    // Provides the stack template class
using namespace std;

namespace edu_colorado_main_theory
{
    const finite_state_automaton::state finite_state_automaton::ILLEGAL;
    finite_state_automaton::finite_state_automaton(
        int many_states, int start_state, const bool* is_accept,
        int many_chars, const char* alphabet,
        const int** transition
        )
    {
        int i;          // Index to the alphabet array
        state s;        // A state
        matrix_row row; // One row of the transition matrix

        // Set up the states information:
        many = many_states;
        start = start_state;
        this->is_accept.resize(many);
        for (s = 0; s < many; s++) this->is_accept[s] = is_accept[s];
        
        // Set up the alphabet information:
        encode.assign(255, ILLEGAL);
        for (i=0; i < many_chars; i++)
        {
            chars.insert(alphabet[i]);
            encode[alphabet[i]] = i;
        }
        
        // Set up the transition matrix:
        row.resize(many_chars);
        this->transition.resize(many);
        for (s = 0; s < many; s++)
        {   // Set up the row for state s in the transition matrix
            for (i = 0; i < many_chars; i++)
                row[i] = transition[s][i];
            this->transition[s] = row;
        }
    }

    finite_state_automaton::state finite_state_automaton::transit(state s, string input) const
    {
        size_t i;                 // Index into the string        
        for (i = 0; i < input.length( ); i++)
            s = transit(s, input[i]);
        return s;
    }    

    void finite_state_automaton::remove_unreachable_states( )
    {
        set<state> reachable;              // The set of reachable states     
        stack<state> waiting;              // States waiting to be processed in dfs
        state s;                           // An old state number
        state new_state_number;            // New state number for state s
        vector<state> renumbering;         // renumbering[s]= new state number for s
        vector<matrix_row> old_transition; // The original transition matrix
	vector<bool> old_is_accept;        // The original accepting states
        unsigned int i;                    // Index for chars vector
        set<char>::iterator it;            // Iterator for chars vector
        set<char>::iterator it_end = chars.end( ); // End of the chars vector
	
        // Compute the reachable set of states with a depth-first-search (dfs)
        waiting.push(start);
        do
        {
            s = waiting.top( );
            waiting.pop( );
            if (!reachable.count(s))
            {
                reachable.insert(s);
                for (it = chars.begin( ); it != it_end; it++)
                {
                    waiting.push(transit(s, *it));
                }
            }
        }   while (!waiting.empty( ));

        // Define a renumbering, so that the reachable states are at the front:
        new_state_number = 0;
        renumbering.resize(many);
        for (s = 0; s < many; s++) if (reachable.count(s))
        {
            renumbering[s] = new_state_number++;
        }

        // Recompute the transition matrix using only the renumbered reachable states:
        old_transition = transition;
	old_is_accept = is_accept;
	transition.clear( );
        transition.resize(reachable.size( ));
	is_accept.resize(reachable.size( ));
        for (s = 0; s < many; s++) if (reachable.count(s))
        {
            new_state_number = renumbering[s];
            transition[new_state_number].resize(chars.size( ));
            for (i = 0; i < chars.size( ); i++)
            {
                transition[new_state_number][i] = renumbering[old_transition[s][i]];
            }
	    is_accept[new_state_number] = old_is_accept[s];
        }
        many = reachable.size( );
    }
    
    ostream& operator <<(ostream& outs, const finite_state_automaton& source)
    {
        unsigned int i;    
        finite_state_automaton::state s;
        set<char> alphabet = source.alphabet( );
        set<char>::iterator it;
        const set<char>::iterator it_end = alphabet.end( );
        
        // Label the top of the transition matrix:
        outs << "              |";
        for (it = alphabet.begin(); it != it_end; it++) outs << "   " << *it;
        outs << " <<< Alphabet\nState         |\n--------------|";
        for (i = 0; i < alphabet.size( ); i++) outs << "----";
        outs << endl;
        
        // Each iteration of this loop prints one row of the transition matrix:
        for (s = 0; s < source.many_states( ); s++)
        {
            outs << ((source.accept(s)) ? "Accepting " : "Rejecting ");
            outs << setw(4) << s << '|';
            for (it = alphabet.begin(); it != it_end; it++)
            {
                outs << setw(4) << source.transit(s, *it);
            }
            if (s == source.start_state( )) outs << " <<<Start";
            outs << endl;
        }
        
        return outs;
    }

}



#ifdef INCLUDE_TEST_PROGRAM
// A little test program, using the machine from Figure 2.2.
// The start is state 0; the top two states are 1 and 2;
// state 3 and 5 are unreachable (not in the figure); the others are 4 and 6.
#include <cstdlib>   // Provides EOF
#include <iostream>  // Provides cin and cout
#include "fsa.h"     // Provides the finite_state_automaton class
using namespace edu_colorado_main_theory;
using namespace std;

int main( )
{
    // Set up the fsa.
    const int STATES = 7;
    const int CHARS = 2;
    const bool is_accept[STATES] = {false, true, false, false, true, true, false};
    const char alphabet[CHARS] = {'0', '1'};
    const int matrix[STATES][CHARS] = {{1,4}, {1,2}, {1,2}, {1,4}, {6,4}, {6,4}, {6, 4}};
    const int* transition[STATES];
    for (int i = 0; i < STATES; i++) transition[i] = matrix[i];
    finite_state_automaton f(STATES, 0, is_accept, CHARS, alphabet, transition);

    // Print the fsa, remove unreachable states, and print it again:
    cout << "The original fsa:\n" << f << endl;
    f.remove_unreachable_states( );
    cout << "After removing unreachable states:\n" << f << endl;

    string input;   // Input string from cin

    while (cin && cin.peek( ) != EOF)
    {
        cout << "Please type an input: ";
        getline(cin, input); // Read the next input line
        cout << "Running on \"" << input << "\": "
             << (f.accept(input) ? "accepted" : "rejected")
             << endl;
    }
    return 0;
}
#endif