/*
 * 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_CURSORS
#define ASTL_CURSORS

#include <stack>
#include <vector>
#include <functional>
#include <list>
#include <deque>
#include <queue>

#ifndef WIN32
#include <hash_set>
#endif

#include <set>

#ifdef WIN32
using namespace std;
#endif

#ifdef WIN32_OBSOLET_STREAMS
#include <iostream.h>
#else
#include <iostream>
#endif

#include <fa_base.h>

// A few dummy classes allowing dispatching in function templates:
struct cursor_concept 
{
  typedef cursor_concept concept;
};

struct forward_cursor_concept : public cursor_concept 
{
  typedef forward_cursor_concept concept;
};

struct stack_cursor_concept : public forward_cursor_concept 
{
  typedef stack_cursor_concept concept;
};

struct dfirst_cursor_concept 
{
  typedef dfirst_cursor_concept concept;
};

template <class DFA>
class cursor : public cursor_concept
{
public:
  typedef cursor                 self;
  typedef typename DFA::State    State;
  typedef typename DFA::Tag      Tag;
  typedef typename DFA::Alphabet Alphabet;

protected:
  const DFA *dfa;
  State q;

public:
  cursor()
    : dfa(NULL)
  { }

  cursor(const DFA &a)
    : dfa(&a)
  { }

  cursor(const DFA &a, State p)
    : dfa(&a), q(p)
  { }

  State src() const {
    return q;
  }

  self& operator= (State p) {
    q = p;
    return *this;
  }

  self& operator= (const self &x) {
    q = x.q;
    dfa = x.dfa;
    return *this;
  }

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

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

  void to_sink() {
    q = dfa->null_state;
  }

  State sink_state() const {
    return dfa->null_state;
  }

  bool forward(const Alphabet &a) {
    q = dfa->delta1(q, a);
    return !sink();
  }

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

  const Tag& src_tag() const  {
    return dfa->tag(q);
  }

  bool exists(const Alphabet &a) const {      // transition exists ?
    return dfa->delta1(q, a) != dfa->null_state;
  }
};

template <class DFA>
class forward_cursor : public forward_cursor_concept
{
public:
  typedef forward_cursor         self;
  typedef typename DFA::Tag      Tag;
  typedef typename DFA::State    State;
  typedef typename DFA::Alphabet Alphabet;

protected:
  typedef typename DFA::Edges::const_iterator edges_iterator;
  const DFA *dfa;
  State q;
  edges_iterator transition;

public:
  forward_cursor(const DFA &a, State p, const Alphabet &letter) 
    : dfa(&a), q(p), transition(dfa->delta2(p).find(letter)) 
  { }
  
  forward_cursor(const DFA &a, State p, edges_iterator t)
    : dfa(&a), q(p), transition(t)
  { }
  
  forward_cursor(const DFA &a, State p)
    : dfa(&a), q(p)
  { }

  forward_cursor(const DFA &a)
    : dfa(&a)
  { }

  forward_cursor()
  { }

  State src() const {
    return q;
  }

  self& operator= (State p) {
    q = p;
    return *this;
  }

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

  State sink_state() const {
    return dfa->null_state;
  }

  bool forward(const Alphabet &a) {
    q = dfa->delta1(q, a);
    return !sink();
  }

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

  const Tag& src_tag() const  {
    return dfa->tag(q);
  }

  bool exists(const Alphabet &a) const {      // transition exists ?
    return dfa->delta1(q, a) != dfa->null_state;
  }

  self& operator= (const self &x) {
    dfa = x.dfa;
    q = x.q;
    transition = x.transition;
    return *this;
  }

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

  Alphabet letter() const {
    return (*transition).first;
  }

  bool first_transition() {
    return !((transition = dfa->delta2(q).begin()) == dfa->delta2(q).end());
  }
  
  bool next_transition() {
    return !(++transition == dfa->delta2(q).end());
  }

  void forward() {
    q = (*transition).second;
  }

  bool find(const Alphabet &a)  {
    transition = dfa->delta2(q).find(a);
    return !(transition == dfa->delta2(q).end());
  }

  State aim() const {
    return (*transition).second;
  }

  bool aim_final() const {
    return dfa->final((*transition).second);
  }

  const Tag& aim_tag() const {
    return dfa->tag((*transition).second);
  }

  // Not a standard requirement:
#ifdef WIN32
  friend ostream& operator<< (std::ostream &out, const self &x) {
#else
    friend ostream& operator<< (ostream &out, const self &x) {
#endif
      if (x.transition != x.dfa->delta2(x.q).end())
	out << x.q << " '" << (*(x.transition)).first << "' " << (*(x.transition)).second;
      else
	out << x.q << " 'null' 0";
      return out;
    }

    // Not a standard requirement:
    bool operator < (const self &x) const {   
      // STL containers need operator < on
      // their value_type (to define < on themselves)
      return q < x.q || (q == x.q && transition < x.transition);
    }
  };

  // DEPTH-FIRST SEARCH RELATED CURSORS:

  template <class ForwardCursor>
  class stack_cursor : public stack<ForwardCursor, vector<ForwardCursor> >, public stack_cursor_concept
  {
  public:
    typedef stack_cursor                                 self;
    typedef stack<ForwardCursor, vector<ForwardCursor> > super;
    typedef typename ForwardCursor::Tag                  Tag;
    typedef typename ForwardCursor::State                State;
    typedef typename ForwardCursor::Alphabet             Alphabet;

    stack_cursor(const ForwardCursor &x)
      : super() {
      push(x);
    }
  
    stack_cursor()  // Empty stack
      : super()
    { }

    State src() const {
      return top().src();
    }

    State aim() const {
      return top().aim();
    }

    Alphabet letter() const {
      return top().letter();
    }

    bool sink() const {
      return top().sink();
    }

    State sink_state() const {
      return top().sink_state();
    }

    bool find(const Alphabet &a) {
      return top().find(a);
    } 

    bool first_transition() {
      return top().first_transition();
    }

    bool next_transition() {
      return top().next_transition();
    }

    // push:
    void forward() {
      push(top());
      top().forward();
    }

    // push:
    bool forward(const Alphabet &a) {
      if (top().find(a)) {
	push(top());
	top().forward();
	return true;
      }
      return false;
    }
 
    // pop:
    // return false if RESULTING stack is empty
    bool backward() {
      pop();
      return !empty();
    }

    bool aim_final() const {
      return top().aim_final();
    }

    bool src_final() const {
      return top().src_final();
    }

    // Compare entire stacks
    // bool operator == (const self &x) const {
    //	return super::operator==(x);
    // }
		
    const Tag& src_tag() const {
      return top().src_tag();
    }

    const Tag& aim_tag() const {
      return top().aim_tag();
    }
  };
  
  // Depth first cursor base
  template <class StackCursor, class MarkerFunction>
  class dfirst_cursor_base_class : public dfirst_cursor_concept
  {
    //  protected:
  public:
    StackCursor c;
    bool has_poped;
    MarkerFunction visited;

  public:
    typedef dfirst_cursor_base_class       self;
    typedef typename StackCursor::Tag      Tag;
    typedef typename StackCursor::State    State;
    typedef typename StackCursor::Alphabet Alphabet;

    dfirst_cursor_base_class(const StackCursor &x)
      : c(x), has_poped(false), visited()
    {  
      visited(c);   // set c to 'visited'
    }

    dfirst_cursor_base_class()
      : c(), has_poped(false)
    { }

    // Move forward on current transition
    // Position on first_transition() of aim
    // Return true if push, false otherwise
    bool forward() {
      if (has_poped) {
				// move on to the next outgoing transition if any otherwise pop
	if (!c.next_transition()) {
	  // at edges end
	  return !c.backward();
	}
	else {
	  has_poped = false;
	  return true;
	}
      }

      c.forward();
      if (visited(c) || !c.first_transition()) {
				// cannot forward so backward => pop
	c.backward();
	has_poped = true;
	return false;
      }
      return true;
    }

    Alphabet letter() const {
      return c.letter();
    }

    bool aim_final() const {
      return c.aim_final();
    }

    bool src_final() const {
      return c.src_final();
    }
  
    State src() const {
      return c.src();
    }
  
    State aim() const {
      return c.aim();
    }

    // Semantic: a dfirst_cursor represents an algorithm stage
    // hence the operator== behavior : it compares entire stacks (see stack cursor)
    bool operator== (const self &x) const {
      return c == x.c; // && has_poped == x.has_poped;
    }

#ifdef WIN32
    bool operator!= (const self &x) const {
      return !(*this == x);
    }
#endif

    const Tag& src_tag() const {
      return c.src_tag();
    }

    const Tag& aim_tag() const {
      return c.aim_tag();
    }
  };

  // The bogus marker function used when no marks and needed
  // Trick: when asked if a state has already been visited, always return false
  // Marker function for tree like automata
  template <class StackCursor>
  struct always_false : public unary_function<StackCursor, bool>
  {
    bool operator() (const StackCursor &c) const {
      return false;
    }
  };

  // Default marker using a set
  // Requirement: partial order relation on states => operator<(State,State)
  // Check if the source state is in the pool of the visited states
  // if not, add it to the pool and return false else return true
  // the behavior of the operator() is to switch the state flag and to return
  // the flag value BEFORE the switch
  template <class StackCursor, class OperatorLessThan = less<typename StackCursor::State> >
  struct default_marker : unary_function<StackCursor, bool>
  {
    set<typename StackCursor::State, OperatorLessThan> pool;
    bool operator() (const StackCursor &c) {
      return !(pool.insert(c.src()).second);  // insert returns pair<iterator,bool>
    }
  };

#ifndef WIN32
  // Marker function using a hash_set<State> (this is an non standard SGI STL extension)
  // Requirements: 1. State must be equality comparable operator==(State, State)
  //               2. if State is an integral type, none
  //                  otherwise user must provide a hash function from states to unsigned integer
  template <class StackCursor, class HashFunction = identity<typename StackCursor::State> >
  struct hash_marker : unary_function<StackCursor, bool>
  {
    hash_set<typename StackCursor::State, HashFunction> pool;
    bool operator() (const StackCursor &c) {
      return !(pool.insert(c.src()).second);  // insert returns pair<iterator,bool>
    }
  };
#endif

  // Use the tag to mark the source state
  // Requirements: bool Tag::visited() behaving like default_marker
  template <class StackCursor>
  struct tag_marker : unary_function<StackCursor, bool>
  {
    bool operator() (StackCursor &c) {
      return c.src_tag().visited();
    }
  };

  // dfirst_cursor for tree like automata (no state mark)
  template <class StackCursor>
  class dfirst_cursor 
    : public dfirst_cursor_base_class<StackCursor, always_false<StackCursor> >
  {
  public:
    typedef dfirst_cursor self;
    typedef dfirst_cursor_base_class<StackCursor, always_false<StackCursor> > super;

    dfirst_cursor(const StackCursor &c)
      : super(c)
    { }

    dfirst_cursor()
      : super()
    { }
  };

  // During depth-first search, a dfirst_cursor_mark makes only two passes on each transition: one in
  // descending stage and one in ascending stage.
  // By default, the states are marked using a hashed set of states (default_marker)
  // Tags can be used too (tag_marker, more efficient because of constant time access)
  template <class StackCursor, class MarkerFunction = default_marker<StackCursor> >
  class dfirst_cursor_mark 
    : public dfirst_cursor_base_class<StackCursor, MarkerFunction>, public dfirst_cursor_concept
  {
  public:
    typedef dfirst_cursor_mark self;
    typedef dfirst_cursor_base_class<StackCursor, MarkerFunction> super;

    dfirst_cursor_mark(const StackCursor &c)
      : super(c)
    { }

    dfirst_cursor_mark()
      : super()
    { }
  };


  //
  // Helper functions serve two purposes:
  // 1. Save the programmer the complex object types declarations and constructions
  // 2. Manage the construction by default with most common behavior. They must
  //    ensure that the object state is consistent after initializing it.
  //
  // Each of the cursor classes should have at least one helper function
  // taking as arguments its constructor arguments.
  // The functions are named after the cursor type they construct by replacing
  // the suffix '_cursor' with 'c'
  // Examples: the class 'intersection_cursor' has a corresponding helper function 'intersectionc'
  //           the class 'sigma_star_cursor' has a helper function 'sigma_starc'
  //
  // These functions handle the most common default behavior for initialization:
  // examples: - forwardc builds a standard forward_cursor from a DFA pointing by
  //             default to its initial state.
  //           - dfirstc builds a standard depth_first_cursor from wether a DFA, a forward cursor or
  //             a stack cursor. It ensures that the returned depth first cursor is consistent with
  //             the underlying DFA : if the DFA has no initial state or if the initial state has no
  //             transition, it returns an empty depth first cursor, otherwise it returns a depth first
  //             cursor pointing to the first transition of the initial state. If called with a forward
  //             cursor x or a stack cursor y, x.src() or y.src() are considered the initial states.
  //           - intersectionc builds an intersection_cursor adapter from two forward
  //             cursors.
  //

// Build a plain cursor from a DFA pointing to state q:
  template <class DFA>
  cursor<DFA> plainc(const DFA &a, typename DFA::State q) {
    return cursor<DFA>(a, q);
  }

  // Build a plain cursor from a DFA pointing to its initial state:
  template <class DFA>
  cursor<DFA> plainc(const DFA &a) {
    return cursor<DFA>(a, a.initial());
  }

  // Build a forward cursor from a DFA pointing to state q:
  template <class DFA>
  forward_cursor<DFA> forwardc(const DFA &a, typename DFA::State q) {
    return forward_cursor<DFA>(a, q);
  }

  // Build a forward cursor from a DFA with its source state pointing to the initial state:
  template <class DFA>
  forward_cursor<DFA> forwardc(const DFA &a) {
    return forward_cursor<DFA>(a, a.initial());
  }

  // Build a stack cursor from a forward cursor:
  template <class ForwardCursor>
  stack_cursor<ForwardCursor> stackc(const ForwardCursor &x) {
    return stack_cursor<ForwardCursor>(x);
  }

  // We use the old dfirstc helper function because VC++6.0 does 
  // not implement partial template specialization
#ifdef WIN32

  // Build a depth-first cursor from a forward cursor x. If x points to the sink
  // state or has no outgoing transition, an empty dfirst_cursor is returned:
  template <class ForwardCursor>
  dfirst_cursor<stack_cursor<ForwardCursor> >
  dfirstc(const ForwardCursor &x) {
    if (!x.sink()) {
      stack_cursor<ForwardCursor> s(x);
      if (s.first_transition()) return dfirst_cursor<stack_cursor<ForwardCursor> >(s);
    }
    return dfirst_cursor<stack_cursor<ForwardCursor> >();
  }

#else
  // Template servant à typer la valeur de retour de la fonction d'aide dfirstc.
  // Soit T, le type servant à instancier la fonction dfirstc. Le type de retour
  // est récupéré grâce à dfirst_cursor_type<T, T::concept>::model
  // En effet, chaque classe d'automate héritant de DFA_concept, hérite d'un type
  // défini par:
  //
  // struct DFA_concept {
  //   typedef DFA_concept concept;
  // };
  //
  // Chaque type de curseur est typé de la même manière:
  //
  // struct forward_cursor_concept {
  //   typedef forward_cursor_concept concept;
  // };
  //
  // et ainsi de suite pour chaque concept.
  // Le template dfirst_cursor_type exporte lui le type concret (modèle) de curseur de parcours
  // correspondant à chaque concept (DFA, forward_cursor, stack_cursor) grâce aux
  // versions spécialisées.

  // Comportement par défaut (attrape tout):
  template <class Model, class Concept>
  struct dfirst_cursor_type
  {
    // Trick: ce template n'exporte pas de type 'model'. Son instanciation provoquera une erreur
    // lors de l'utilisation qui est de la forme: dfirst_cursor_type<T, U>::model
    // i.e. l'instanciation de ce template signifie qu'aucune de ses spécialisations ne correspond
    // aux paramètres d'instanciation, d'où l'erreur de compilation
  };

  // Spécialisation partielle pour les DFA:
  template <class DFA>
  struct dfirst_cursor_type<DFA, DFA_concept>
  {
    typedef dfirst_cursor<stack_cursor<forward_cursor<DFA> > > model;
  };

  // Spécialisation partielle pour les forward cursors:
  template <class ForwardCursor>
  struct dfirst_cursor_type<ForwardCursor, forward_cursor_concept>
  {
    typedef dfirst_cursor<stack_cursor<ForwardCursor> > model;
  };

  // Spécialisation partielle pour les stack cursors:
  template <class StackCursor>
  struct dfirst_cursor_type<StackCursor, stack_cursor_concept>
  {
    typedef dfirst_cursor<StackCursor> model;
  };

  template <class T>
  typename dfirst_cursor_type<T, typename T::concept>::model
  dfirstc(const T &x) {
    return _dfirstc(x, x);
  }

  // Builds a depth first cursor from a DFA pointing to the first outgoing transition
  // of the initial state if any by constructing the underlying forward and stack cursors
  // If the DFA has no initial state or if it has no outgoing transitions, returns an empty cursor
  template <class DFA>
  dfirst_cursor_type<DFA, DFA_concept>::model
  _dfirstc(const DFA &x, DFA_concept) 
  {
    forward_cursor<DFA> fc(x, x.initial());
    if (!fc.sink() && fc.first_transition()) // has x an initial state ? has it any outgoing transitions ?
      return dfirst_cursor<stack_cursor<forward_cursor<DFA> > >(stackc(fc));
    else
      return dfirst_cursor<stack_cursor<forward_cursor<DFA> > >();
  }

  // Builds a depth first cursor from a forward cursor by constructing the underlying stack cursor:
  template <class ForwardCursor>
  dfirst_cursor_type<ForwardCursor, forward_cursor_concept>::model
  _dfirstc(const ForwardCursor &x, forward_cursor_concept) 
  {
    if (!x.sink()) {
      stack_cursor<ForwardCursor> s(x);
      if (s.first_transition()) return dfirst_cursor<stack_cursor<ForwardCursor> >(s);
    }
    return dfirst_cursor<stack_cursor<ForwardCursor> >();
  }

  // Builds a depth first cursor from a stack cursor:
  template <class StackCursor>
  dfirst_cursor_type<StackCursor, stack_cursor_concept>::model
  _dfirstc(const StackCursor &x, stack_cursor_concept) 
  {
    if (!x.sink()) { 
      StackCursor s(x);
      if (s.first_transition()) return dfirst_cursor<StackCursor>(s);
    }
    return dfirst_cursor<StackCursor>();
  }

#endif

  // Build a depth-first cursor with the default visited states marker from a forward cursor:
  template <class ForwardCursor>
  dfirst_cursor_base_class<stack_cursor<ForwardCursor>, default_marker<stack_cursor<ForwardCursor> > > 
  dfirstmarkc(const ForwardCursor &x) {
    if (!x.sink()) {
      stack_cursor<ForwardCursor> s(x);
      if (s.first_transition()) 
	return dfirst_cursor_base_class<stack_cursor<ForwardCursor>, default_marker<stack_cursor<ForwardCursor> > >(s);
    }
    return dfirst_cursor_base_class<stack_cursor<ForwardCursor>, default_marker<stack_cursor<ForwardCursor> > >();
  }

  // BREADTH-FIRST SEARCH RELATED CURSORS

struct queue_cursor_concept : public forward_cursor_concept
{ };

struct bfirst_cursor_concept : public queue_cursor_concept
{ };

template <class ForwardCursor>
class queue_cursor 
  : public queue<ForwardCursor, deque<ForwardCursor> >, public queue_cursor_concept
{
public:
  typedef queue_cursor                     self;
  typedef queue<ForwardCursor>             super;
  typedef typename ForwardCursor::Tag      Tag;
  typedef typename ForwardCursor::State    State;
  typedef typename ForwardCursor::Alphabet Alphabet;

  queue_cursor(const ForwardCursor &x)
    : super() { 
    push(x);
  }

  queue_cursor()
    : super()
  { }

  State src() const {
    return back().src();
  }

  State aim() const {
    return back().aim();
  }

  bool src_final() const {
    return back().src_final();
  }

  bool aim_final() const {
    return back().aim_final();
  }

  Alphabet letter() const {
    return back().letter();
  }

  bool sink() const {
    return back().sink();
  }

  void to_sink() {
    back().to_sink();
  }

  State sink_state() const {
    return back().sink_state();
  }

  bool find(const Alphabet &a) {
    return back().find(a);
  } 

  bool first_transition() {
    return back().first_transition();
  }

  bool next_transition() {
    push(back());
    return back().next_transition();
  }

  void forward() {
    back().forward();
  }

  bool forward(const Alphabet &a) {
    return back().forward(a);
  }

  bool exists(const Alphabet &a) const {
    return back().exists(a);
  }

  bool dequeue() {
    back() = front();
    pop();
    return !empty();
  }

  const Tag& src_tag() const {
    return back().src_tag();
  }

  const Tag& aim_tag() const {
    return back().aim_tag();
  }
};

template <class QueueCursor, class MarkerFunction>
class bfirst_cursor_base : public bfirst_cursor_concept
{
protected:
  QueueCursor c;
  MarkerFunction visited;

public:
  typedef bfirst_cursor_base             self;
  typedef typename QueueCursor::Tag      Tag;
  typedef typename QueueCursor::State    State;
  typedef typename QueueCursor::Alphabet Alphabet;

  bfirst_cursor_base(const QueueCursor &x)
    : c(x)
  { }

  bfirst_cursor_base()
    : c()
  { }

  bool next_transition() {
    if (!c.next_transition()) {
      while (c.dequeue()) {
	c.forward();
	if (!visited(c) && c.first_transition()) break;
      }
      return false;
    }
    return true;
  }
  
  State src() const {
    return c.src();
  }

  State aim() const {
    return c.aim();
  }

  bool src_final() const {
    return c.src_final();
  }

  bool aim_final() const {
    return c.aim_final();
  }
 
  Alphabet letter() const {
    return c.letter();
  }

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

  const Tag& src_tag() const {
    return c.src_tag();
  }

  const Tag& aim_tag() const {
    return c.aim_tag();
  }
};


template <class QueueCursor, class MarkerFunction = default_marker<QueueCursor> >
class bfirst_cursor_mark 
  : public bfirst_cursor_base<QueueCursor, MarkerFunction>
{
public:
  typedef bfirst_cursor_mark self;
  typedef bfirst_cursor_base<QueueCursor, MarkerFunction> super;

  bfirst_cursor_mark(const QueueCursor &x)
    : super(x)
  { }

  bfirst_cursor_mark()
    : super()
  { }
};

template <class QueueCursor>
class bfirst_cursor 
  : public bfirst_cursor_base<QueueCursor, always_false<QueueCursor> >
{
public:
  typedef bfirst_cursor self;
  typedef bfirst_cursor_base<QueueCursor, always_false<QueueCursor> > super;

  bfirst_cursor(const QueueCursor &x)
    : super(x)
  { }

  bfirst_cursor()
    : super()
  { }
};

// Helper functions:
template <class ForwardCusor>
queue_cursor<ForwardCusor> queuec(const ForwardCusor &x) {
  return queue_cursor<ForwardCusor>(x);
}

template <class ForwardCusor>
bfirst_cursor_mark<queue_cursor<ForwardCusor> >
bfirstmarkc(const ForwardCusor &x) {
  queue_cursor<ForwardCusor> q(x);
  if (q.sink() || !q.first_transition())
    return bfirst_cursor_mark<queue_cursor<ForwardCusor> >();
  else
    return bfirst_cursor_mark<queue_cursor<ForwardCusor> >(q);
}

template <class Model, class Concept>
struct bfirst_cursor_type
{ };

// Spécialisation partielle pour les DFA:
template <class DFA>
struct bfirst_cursor_type<DFA, DFA_concept>
{
  typedef bfirst_cursor<queue_cursor<forward_cursor<DFA> > > model;
};

// Spécialisation partielle pour les forward cursors:
template <class ForwardCursor>
struct bfirst_cursor_type<ForwardCursor, forward_cursor_concept>
{
  typedef bfirst_cursor<queue_cursor<ForwardCursor> > model;
};

// Spécialisation partielle pour les stack cursors:
template <class QueueCursor>
struct bfirst_cursor_type<QueueCursor, queue_cursor_concept>
{
  typedef bfirst_cursor<QueueCursor> model;
};

template <class T>
typename bfirst_cursor_type<T, typename T::concept>::model
bfirstc(const T &x) {
  return _bfirstc(x, x);
}

// Builds a breadth-first cursor from a DFA pointing to the first outgoing transition
// of the initial state if any by constructing the underlying forward and stack cursors
// If the DFA has no initial state or if it has no outgoing transitions, returns an empty cursor
template <class DFA>
bfirst_cursor_type<DFA, DFA_concept>::model
_bfirstc(const DFA &x, DFA_concept) 
{
  forward_cursor<DFA> fc(x, x.initial());
  if (!fc.sink() && fc.first_transition()) // has x an initial state ? has it any outgoing transitions ?
    return bfirst_cursor<queue_cursor<forward_cursor<DFA> > >(queuec(fc));
  else
    return bfirst_cursor<queue_cursor<forward_cursor<DFA> > >();
}

// Builds a breadth-first cursor from a forward cursor by constructing the underlying stack cursor:
template <class ForwardCursor>
bfirst_cursor_type<ForwardCursor, forward_cursor_concept>::model
_bfirstc(const ForwardCursor &x, forward_cursor_concept) 
{
  if (!x.sink()) {
    queue_cursor<ForwardCursor> s(x);
    if (s.first_transition()) return bfirst_cursor<queue_cursor<ForwardCursor> >(s);
  }
  return bfirst_cursor<queue_cursor<ForwardCursor> >();
}

// Builds a breadth-first cursor from a stack cursor:
template <class QueueCursor>
bfirst_cursor_type<QueueCursor, queue_cursor_concept>::model
_bfirstc(const QueueCursor &x, queue_cursor_concept) 
{
  if (!x.sink()) { 
    QueueCursor s(x);
    if (s.first_transition()) return bfirst_cursor<QueueCursor>(s);
  }
  return bfirst_cursor<QueueCursor>();
}

#ifdef ZORGLUB

  // Backward compatibility cursor
  // DO NOT USE !!!
  template <class DFA>
  class D_cursor
  {
  private:
    typedef typename DFA::State State;
    DFA &dfa;
    State current_state;

  public:
    D_cursor(const DFA &a) 
      : dfa((DFA &) a), current_state(a.null_state)
    { }

    void reset() {
      current_state = dfa.initial();
    }

    bool final() const {
      return dfa.final(current_state);
    }

    friend bool operator == (const D_cursor &x, const D_cursor &y) {
      return (x.current_state == y.current_state && &(x.dfa) == &(y.dfa));
    }

    bool operator == (const State &s) const {
      return (current_state == s);
    }

    // cast operator to State
    operator State() const {
      return (current_state);
    }

    // Set the cursor on a specific state
    D_cursor& operator = (State s)
    {
      current_state = s;
      return (*this);
    }

    // Return the current state the cursor is on
    const State& operator * () const {
      return (current_state);
    }

    // Move one transition forward
    // Return true if transition with 'a' exists (if cursor has moved)
    bool forward(const typename DFA::Alphabet &a)  
    {
      State aim = dfa.delta1(current_state, a);
      if (!(aim == dfa.null_state))
	{
	  current_state = aim;
	  return (true);
	}
      else
	return (false);
    }

    // Move n transitions forward
    // Return true if all transitions exist 
    // (if cursor has moved over ALL the transitions)
    template <class InputIterator>
    bool forward(InputIterator first, InputIterator last)
    {
      State s;
      if (first != last)
	{
	  for(s = dfa.delta1(current_state, *first++); 
	      first != last && s != dfa.null_state;
	      s = dfa.delta1(s, *first++));

	  if (s != dfa.null_state) 
	    {
	      current_state = s;
	      return (true);
	    }
	  else
	    return (false);
	}
      return (true);    // ?
    }

    // Return the tag associated to the current state
    typename DFA::Tag& tag() {
      return (dfa.tag(current_state));
    }

    const typename DFA::Tag& tag() const {
      return (dfa.tag(current_state));
    }
  };

#endif  // ZORGLUB

#endif  // ASTL_CURSORS