//
//	File:	    language.h
//      Version:    ASTL 1.1
//	Copyright:  Vincent LE MAOUT
//	Date:	    Wed Dec 2 1998
//	Descrition: DFA language related algorithms
//                   - language
//                   - is_in
//

#ifndef ASTL_LANGUAGE
#define ASTL_LANGUAGE

#include <vector>


//
// Algorithm    : language
// Version      : ASTL 1.1
// Description  : computes the recognized language of a dfa
// Input        : a dfa, an OutputIterator and a separator character
// Output       : result is written through OutputIterator
// Precondition : OutputIterator::value_type == DFA::Alphabet,
//                separator type == DFA::Alphabet
// Uses         : _language
//

template <class DFA, class OutputIterator>
void 
language(const DFA &A, OutputIterator out, const typename DFA::Alphabet &separator ='\n')
{
#ifdef WIN32
  vector<DFA::Alphabet> w;
#else
  vector<typename DFA::Alphabet> w;
#endif // WIN32

  typename DFA::State i= A.initial() ;
  if (i != A.null_state)
    _language(A, i, w, out,separator);
}

// Main language part:
// DR 08/04/99 des problem je ne comprend pas comment 
// il faut instancier le type typename DFA::Alphabet pour que le conpilateur vc6 
// accepte de compiler 
// j'ai donc cree un type intermediaire char_type 
// pour qu'il ne m'e... plus 

template <class DFA, class OutputIterator,class char_type>//
void 
_language(const DFA &A, typename DFA::State s, 
	  vector<char_type> &w, //
	  OutputIterator out, const char_type &separator)//char_type
{
  if (A.final(s))
  {
    copy(w.begin(), w.end(), out);
    *out = separator;
    ++out;
  }

  typename DFA::Edges edg = A.delta2(s);
  typename DFA::Edges::const_iterator s_trans, edg_end = edg.end();
  for (s_trans = edg.begin(); !(s_trans == edg_end); ++s_trans)
  {
 
    w.push_back((*s_trans).first);
    _language(A, (*s_trans).second, w, out, separator);
    w.pop_back();
  }
}


#endif