// Worksheet 2-2 (Revised)
//
// Work: Implement the minimize member function using the algorithm from
// Chapter 2 of the text.  You may work in groups of two or three students,
// but make sure you each do enough work that you can answer questions
// about your work on future quizzes.
//
// Submit your work by e-mail to main@colorado.edu
//
//
// Due date:__________________________________________________________
//
//
// File: www.cs.colorado.edu/~main/theory/source/fsa.h
// Class Provided: edu_colorado_main_thoery::finite_state_automaton
//
// CONSTRUCTORS and DESTRUCTOR
//   finite_state_automaton(
//     int many_states,
//     state start_state,
//     bool is_accept[ ],
//     int many_chars,
//     char alphabet[ ],
//     int transition[ ][ ]
//   );
//     Precondition: 0 < start_state < many
//     and the size of is_accept == many
//     and the size of transition is many by k, where k is the size of alphabet.
//     Postcondition: An fsa has been created with the specified information.
//
// CONST MEMBER FUNCTIONS
//   bool accept(state s) const;
//     Precondition: 0 <= s < many_states.
//     Postcondition: The return value is true iff s is an accepting state.
//   bool accept(string input) const;
//     Precondition: Every character of input is in the alphabet of this fsa.
//     Postcondition: Returns true iff this automaton accepts s.
//   set<char> alphabet const;
//     Postcondition: The return value is the alphabet for this fsa.
//   int many_states( ) const;
//     Postcondition: The return value is the number of states in this fsa,
//     including unreachable states.
//   state start_state( ) const;
//     Postcondition: The return value is the start state of this fsa.
//   state transit(state s, char c) const;
//     Precondition: 0 <= s < many_states, and c is in the alphabet of this fsa.
//     Postcondition: The return value is the state that this fsa transits to
//     from state s upon reading character c.
//   state transit(state s, string input) const;
//     Precondition: 0 <= s < many_states, and every character of input is in the
//     alphabet of this fsa.
//
// MODIFICATION MEMBER FUNCTIONS
//   void minimize( );
//     Postcondition: The number of states in this fsa has been minimized.
//     The other states might have been renumbered, so that the state numbers
//     are still consecutive from 0 to the new value of many_states-1.
//   void remove_unreachables_states( );
//     Postcondition: Any states that cannot be reached from the start state
//     have been removed.  The other states might have been renumbered, so
//     that the state numbers are still consecutive from 0 to the new value
//     of many_states-1.

#ifndef EDU_COLORADO_MAIN_THEORY_FSA_H
#define EDU_COLORADO_MAIN_THEORY_FSA_H
#include <iostream> // Provides std::ostream class
#include <set>      // Provides std::set template class
#include <string>   // Provides std::string class
#include <vector>   // Provides std::vector template class

namespace edu_colorado_main_theory
{
    class finite_state_automaton
    {
    public:
        // TYPEDEFS
        typedef int state;

        // CONSTRUCTOR
        finite_state_automaton(
          int many_states,
          state start_state,
          const bool* is_accept,
          int many_chars,
          const char* alphabet,
          const int** transition
        );

        // CONST MEMBER FUNCTIONS
        bool accept(state s) const { return is_accept[s]; }
        bool accept(std::string input) const { return is_accept[transit(start, input)]; }
        std::set<char> alphabet( ) const { return chars; }
        int many_states( ) const { return many; }
        state start_state( ) const { return start; }
        state transit(state s, char c) const { return transition[s][encode[c]]; }
        state transit(state s, std::string input) const;

        // MODIFICATION MEMBER FUNCTIONS
        void minimize( );
        void remove_unreachable_states( );

    private:
        int many;                    // Number of states in the fsa
        state start;                 // The start state
        std::vector<bool> is_accept; // is_accept[s] = is s accepting?
        std::set<char> chars;        // The alphabet of characters

        // The transition matrix:  For any c in the alphabet, encode[c] is the
        // column number that we are using for c in the transition matrix.
        // If c is not in the alphabet, then encode[c] is the const ILLEGAL.
        // For any character c and state s, transition
        // transition[s][encode[c]] is the state that the fsa goes to when it
        // is in state s and reads character c.
        static const state ILLEGAL = -1;
        std::vector<int> encode;
        typedef std::vector<state> matrix_row; 
        std::vector<matrix_row> transition;
    };

    // NON-MEMBER FUNCTIONS:
    std::ostream& operator<<(std::ostream& outs, const finite_state_automaton& source);
}

#endif