/*
 * 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_CLASS_LAZY_CURSOR
#define ASTL_CLASS_LAZY_CURSOR

#include <map>
#include <safe.h>
#include <cursor.h>
#include <dfa_matrix.h>

// Defines:
// 1. lazy_cursor (cursor adapter)

// A lazy cursor builds an automaton incrementally

// Instanciation parameters:
// 1. Cursor: the type of the cursor to be adapted
// 2. DFA: a ASTL DFA type
//
// Requirements:
// 1. The DFA Tag must be of type Cursor::State
//
// Constructors:
// 1. A cursor to be adapted, a DFA

#ifndef TEMPLATE_TEMPLATE_IMPLEMENTATION
template <class Cursor, class DFA>
class lazy_cursor : public cursor_concept
{
protected:
  typedef map<typename Cursor::State, safe<typename DFA::State> > mapper;
  Cursor c;
  DFA    *dfa;
  mapper mapping;
  safe<typename DFA::State> q;

public:
  typedef typename DFA::State       State;
	typedef typename Cursor::State    Tag;
  typedef typename Cursor::Alphabet Alphabet;

  lazy_cursor(const Cursor &x, DFA &a)
    : c(x), dfa(&a), q(a.initial())
  { 
    if (q == dfa->null_state && !x.sink()) {
      q = dfa->new_state();
      dfa->tag(q) = c.src();
      mapping[c.src()] = q;
			dfa->final(q) = c.src_final();
			dfa->initial(q);
    }
  }

  State src() const {
    return q;
  }

	bool src_final() const {
		return dfa->final(q);
	}

  bool sink() const {
    return q == dfa->null_state;
  }

  bool forward(const Alphabet &a) {
    State tmp = dfa->delta1(q, a);
    if (tmp == dfa->null_state) {    // transition is not in the cache ?
      c = dfa->tag(q);
      if (c.forward(a)) {    // any transition labelled with 'a' ?
				safe<State> &tmp2 = mapping[c.src()];
				if (tmp2 == dfa->null_state) {   // not already been there ?
					tmp2 = dfa->new_state();
					dfa->final(tmp2) = c.src_final();
					dfa->tag(tmp2) = c.src();
					mapping[c.src()] = tmp2;
				}
				tmp = tmp2;
				dfa->set_trans(q, a, tmp);
      }
      else 
				return false;
    }
    q = tmp;
    return true;
  }
};

// helper function
template <class Cursor, class DFA>
lazy_cursor<Cursor, DFA> lazyc(const Cursor &x, DFA &a) {
	return lazy_cursor<Cursor, DFA>(x, a);
}

#else
// Ideal solution using template template: the user does not have to instanciate 
// the DFA by himself, he only has to pass a template as argument of the cursor
// template (the DFA must be instanciated with Tag == Cursor::State)

template <class Cursor, class Sigma, template <class Sigma, class Tag> class DFA = DFA_matrix>
class lazy_cursor : public cursor_concept
{
public:
	typedef DFA<Sigma, typename Cursor::State> DFA_type;

protected:
	typedef map<typename Cursor::State, safe<typename DFA_type::State> > mapper;
  Cursor   c;
  DFA_type *dfa_;
  mapper   mapping;
  safe<typename DFA_type::State> q;

public:
  typedef typename DFA_type::State       State;
	typedef typename Cursor::State    Tag;
  typedef typename Cursor::Alphabet Alphabet;

  lazy_cursor(const Cursor &x, DFA_type &a)
    : c(x), dfa_(&a), q(a.initial())
  { 
    if (q == dfa_->null_state && !x.sink()) {
      q = dfa_->new_state();
      dfa_->tag(q) = c.src();
      mapping[c.src()] = q;
			dfa_->final(q) = c.src_final();
			dfa_->initial(q);
    }
  }

	DFA_type& dfa() {
		return *dfa_;
	}

	const DFA_type& dfa() const {
		return *dfa_;
	}

  State src() const {
    return q;
  }

	bool src_final() const {
		return dfa_->final(q);
	}

  bool sink() const {
    return q == dfa_->null_state;
  }

  bool forward(const Alphabet &a) {
    State tmp = dfa_->delta1(q, a);
    if (tmp == dfa_->null_state) {    // transition is not in the cache ?
      c = dfa_->tag(q);
      if (c.forward(a)) {    // any transition labelled with 'a' ?
				safe<State> &tmp2 = mapping[c.src()];
				if (tmp2 == dfa_->null_state) {   // not already been there ?
					tmp2 = dfa_->new_state();
					dfa_->final(tmp2) = c.src_final();
					dfa_->tag(tmp2) = c.src();
					mapping[c.src()] = tmp2;
				}
				tmp = tmp2;
				dfa_->set_trans(q, a, tmp);
      }
      else 
				return false;
    }
    q = tmp;
    return true;
  }
};

#endif // TEMPLATE_TEMPLATE_IMPLEMENTATION
     
#endif // ASTL_CLASS_LAZY_CURSOR