#include <iostream>
#include <map>



// DFA file format:
// state count\n
// initial_state\n
// number of trans for state 1 final(0/1) tag letter state letter state letter state letter state ...\n
// number of trans for state 2 final(0/1) tag letter state letter ...\n
// ... 



template <class DFA>

void

dfa_ascii_write(const DFA &dfa, ostream &out)

{

  if (dfa.state_count() == 0)
    return;

  out << dfa.state_count() << endl;

  vector<DFA::State> mapping;
  typename DFA::const_iterator q, q_end = dfa.end();

  for(q = dfa.begin(); q != q_end; ++q)
    mapping.insert(lower_bound(mapping.begin(), mapping.end(), *q), *q);

  
  if (dfa.initial() == dfa.null_state)
    out << "0" << endl;
  else
    out << (lower_bound(mapping.begin(), mapping.end(), dfa.initial()) -
	    mapping.begin() + 1) << endl;


  for(q = dfa.begin(); q != q_end; ++q)
  {
    typename DFA::Edges e = dfa.delta2(*q);
    typename DFA::Edges::const_iterator trans, trans_end;

    out << e.size() << " ";
		if (dfa.final(*q))
			out << "1 ";
		else
			out << "0 ";
		out << dfa.tag(*q);

    for (trans = e.begin(), trans_end = e.end(); trans != trans_end; ++trans)
    {

      out << " " << (*trans).first << " "                  // letter
					<< (lower_bound(mapping.begin(), mapping.end(), (*trans).second) -

	      mapping.begin() + 1); //aim
    }
    out << endl;
  }  

}



// binary dump of DFA

// DFA::Alphabet and DFA::Tag must have only static allocated members

template <class DFA>

void

dfa_binary_write(const DFA &dfa, ostream &out)

{

  unsigned long tmp = dfa.state_count();

  if (tmp == 0) return;

  out.write(&tmp, sizeof(tmp));           // write state count



  vector<typename DFA::State> mapping;

  typename DFA::const_iterator q, q_end = dfa.end();

  for(q = dfa.begin(); q != q_end; ++q)   // create mapping

    mapping.insert(lower_bound(mapping.begin(), mapping.end(), *q), *q);

  

  typename DFA::State s1, s2;

  typename DFA::Alphabet letter;

  s1 = dfa.initial();

  if (s1 == dfa.null_state)

    tmp = 0;

  else

    tmp = (lower_bound(mapping.begin(), mapping.end(), dfa.initial()) - mapping.begin() + 1);
  out.write(&tmp, sizeof(tmp));           // write initial state


  for(q = dfa.begin(); q != q_end; ++q)  // for each state

  {

    typename DFA::Edges e = dfa.delta2(*q);

    typename DFA::Edges::const_iterator trans, trans_end;

    tmp = e.size();                      // write number of transitions

    out.write(&tmp, sizeof(tmp));

    out.write(&dfa.tag(*q), sizeof(typename DFA::Tag));    // write tag

    for (trans = e.begin(), trans_end = e.end(); trans != trans_end;

	 ++trans)

    {

      letter = (*trans).first;

      out.write(&letter, sizeof(typename DFA::Alphabet)); // write letter

      tmp = lower_bound(mapping.begin(), mapping.end(), (*trans).second) -

	mapping.begin() + 1;

      out.write(&tmp, sizeof(tmp));                       // write aim

    }

  }  

}







// NFA file format:

// state count

// number of initial states initial_state initial_state initial_state

// ...

// number of trans for state 1 tag letter state letter state letter

// state letter state ...

// number of trans for state 2 tag letter state letter state letter

// state letter state ...

// ... 



template <class NFA>

void

nfa_ascii_write(const NFA &nfa, ostream &out)

{

  out << nfa.state_count() << endl;

  if (nfa.state_count() == 0)

    return;



  vector<typename NFA::State> mapping;

  typename NFA::const_iterator q, q_end = nfa.end();

  for(q = nfa.begin(); q != q_end; ++q)

    mapping.insert(lower_bound(mapping.begin(), mapping.end(), *q), *q);

  

  // Initial states

  const typename NFA::State_set &I = nfa.initial();

  typename NFA::State_set::const_iterator i;

  out << I.size();

  for(i = I.begin(); i != I.end(); ++i)

    out << " " << (lower_bound(mapping.begin(), mapping.end(), *i) -

		   mapping.begin() + 1);



  out << endl;

  for(q = nfa.begin(); q != q_end; ++q)

  {

    typename NFA::Edges e = nfa.delta2(*q);

    typename NFA::Edges::const_iterator trans, trans_end;

    out << e.size() << " " << nfa.tag(*q);

    for (trans = e.begin(), trans_end = e.end(); trans != trans_end;

	 ++trans)

      out << " " << (*trans).first << " "  // letter

	  << (lower_bound(mapping.begin(), mapping.end(), (*trans).second) -

	      mapping.begin() + 1); //aim

    out << endl;

  }  

}