/*
 * ASTL - the Automaton Standard Template Library.
 * C++ generic components for Finite State Machine handling.
 * Copyright (C) 2000 Vincent Le Maout (vlemaout@lexiquest.fr).
 * 
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 */


#ifndef ASTL_LANGUAGE_ALGORITHMS
#define ASTL_LANGUAGE_ALGORITHMS

#include <iterator>
#include <algorithm>
#include <vector>
#include <cursor.h>
#include <string>
#include <iostream>

// Name:                  language
// Category:              Algorithms
// Component Type:        Function
// Prototype:             See below
// Description:           Output the recognized language of a DFA
// Return value:          none
// Definition:            language.h
// Requirements on types: There must exist a conversion from char to OutputIterator::value_type 
// Preconditions:         [first, last) is a valid range. If DFA is cyclic, DepthFirstCursor must use a state marker
// Complexity:            linear
// Example:               language.cpp
// Notes:
// See also:

template <class DepthFirstCursor>
void language_stream(ostream &out,                    // where to write
	      DepthFirstCursor first,                      // start position
	      DepthFirstCursor last = DepthFirstCursor())  // stop condition
{
  vector<typename DepthFirstCursor::Alphabet> word;
  for(word.reserve(16); first != last; ) {
    word.push_back(first.letter());
    if (first.aim_final()) {
      for(vector<typename DepthFirstCursor::Alphabet>::const_iterator i =
	    word.begin(); i != word.end(); ++i)
	out << *i;
      out << endl;
    }
    while (!first.forward())  word.pop_back();
  }
}

template <class OutputIterator, class DepthFirstCursor>
void language(OutputIterator out,                    // where to write
	      DepthFirstCursor first,                      // start position
	      DepthFirstCursor last = DepthFirstCursor())  // stop condition
{
  vector<typename DepthFirstCursor::Alphabet> word;
  for(word.reserve(16); first != last; ) {
    word.push_back(first.letter());
    if (first.aim_final()) {
      copy(word.begin(), word.end(), out);
      *out = '\n';
      ++out;
    }
    while (!first.forward())  word.pop_back();
  }
}



/*
template <class DepthFirstCursor>
void language(ostream &out,                    // where to write
	      DepthFirstCursor first,                      // start position
	      DepthFirstCursor last = DepthFirstCursor())  // stop condition
{
  string word;
  for(word.reserve(32); first != last; ) {
    word += (char) first.letter();
    if (first.aim_final())
			out << word << endl;
    while (!first.forward())  word.erase(word.size() - 1, 1);
  }
}
*/
// Name:                  is_in
// Category:              Algorithms
// Component Type:        Function
// Prototype:             See below
// Description:           test if a word is in the recognized language of a DFA
// Return value:          true if the word has been recognized
// Definition:            language.h
// Requirements on types: first and last are models of input iterator. c is a model of cursor.
// Preconditions:         [first, last) is a valid range. c must point to a valid state.
// Complexity:            linear
// Example:               
// Notes:
// See also:

template <class InputIterator, class Cursor>
bool is_in(InputIterator first, InputIterator last, Cursor c)
{
	if (c.sink()) return false;
  while (first != last && c.forward(*first)) ++first;
  return first == last && c.src_final();
}

// Name:                 language_iterator
// Category:             Iterators
// Component Type:       Type
// Description:          An iterator whose value type is string. During traversal, the underlying
//                       cursor retrieves the recognized words of the DFA (depth-first search) and 
//                       stores the current one
//                       in a string of chars available through the dereferencement operator *
//                       (this is in fact an incremental version of the language algorithm above).
// Example:              
// Definition:           language.h
// Template parameters:  ForwardCursor = the type of the cursor to be used to access the DFA
// Model of:             Input iterator
// Type requirements:    
// Public base classes:  iterator<input_iterator_tag, string>
// Members:              
// New members:          
// Notes:                
// Bugs and limitations: The iterator outputs strings of ASCII chars. A more sophisticated alphabet
//                       will requires some extensions.
// See also:             algorithm language.

#ifdef WIN32
template <class ForwardCursor>
class language_iterator : public iterator<input_iterator_tag, string> 
#else
template <class ForwardCursor>
class language_iterator : public input_iterator<string, int>
#endif
{
protected:
	string current;
	dfirst_cursor<stack_cursor<ForwardCursor> > first, last;

public:
	typedef language_iterator self;

	language_iterator()      // end of range
		: first(), last()
	{ }

	language_iterator(const ForwardCursor &x)    // beginning of range
		: first(dfirstc(x)), last()
	{ 
		if (first != last) {
			current += (char) first.letter();
			if (!first.aim_final()) ++*this;
		}
	}

	const string& operator* () const {
		return current;
	}

	bool operator== (const self &x) const {
		return first == x.first;
	}

	bool operator!= (const self &x) const {
		return first != x.first;
	}
	
	self& operator++ () {
		while (1) 
			if (!first.forward())                      // ascending stage
				current.erase(current.size() - 1, 1);    // pop
			else
			  if (first == last) return *this;
			  else {
					current += (char) first.letter();        // descending stage, push and test
					if (first.aim_final()) return *this;
			  }
		return *this;
	}
};
		
#endif // ASTL_LANGUAGE_ALGORITHMS