cursor.h

Go to the documentation of this file.

/*
 * ASTL - the Automaton Standard Template Library.
 * C++ generic components for Finite State Automata handling.
 * Copyright (C) 2000-2006 Vincent Le Maout (vincent.lemaout@chello.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_CURSOR_H
#define ASTL_CURSOR_H

#include <vector>
#include <functional>
#include <list>
#include <deque>
#include <queue>
#include <set>
#include <iostream>
#include <utility>

using namespace std;
#if !defined(__GNUG__) || __GNUG__ >= 3
using namespace rel_ops;
#endif

namespace astl {

template <typename DFA>
class cursor : public cursor_concept
{
public:
  typedef cursor                    self;
  typedef cursor_concept            super;
  typedef typename DFA::state_type  state_type; 
  typedef typename DFA::char_type   char_type;  
  typedef typename DFA::tag_type    tag_type;   
  typedef typename DFA::char_traits char_traits; 
  typedef typename super::concept   concept;

  cursor() 
  { }

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

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

  state_type src() const { return q; } 

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

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

  bool sink() const { return q == DFA::null_state; }

  state_type sink_state() const { return DFA::null_state; }

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

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

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

  bool exists(const char_type &a) const {
    return dfa->delta1(q, a) != DFA::null_state;
  }

protected:
  const DFA *dfa;
  state_type q;
};

template <typename FA>
class transition_cursor : public transition_cursor_concept
{
public:
  typedef transition_cursor         self;
  typedef transition_cursor_concept super;
  typedef typename FA::state_type  state_type; 
  typedef typename FA::char_type   char_type;  
  typedef typename FA::tag_type    tag_type;   
  typedef typename FA::char_traits char_traits; 
  typedef typename super::concept   concept;

  transition_cursor(const FA &a, state_type p)
    : fa(&a), q(p)
  { }

  transition_cursor(const FA &a)
    : fa(&a)
  { }

  transition_cursor()
  { }

  state_type src() const { return q; }

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

  bool sink() const { return q == FA::null_state; }

  state_type sink_state() const { return FA::null_state;  }

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

  const tag_type& src_tag() const { return fa->tag(q);  }

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

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

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

  bool first() {
    return !((transition = fa->delta2(q).begin()) == fa->delta2(q).end());
  }

  bool next() { return !(++transition == fa->delta2(q).end()); }

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

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

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

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

  // Not a standard requirement:
  bool operator<(const self &x) const {
    return q < x.q || (q == x.q && transition < x.transition);
  }

protected:
  const FA *fa;
  state_type q;
  typename FA::edges_type::const_iterator transition;
};

template <typename DFA>
class forward_cursor
  : public transition_cursor<DFA>, public forward_cursor_concept
{
public:
  typedef forward_cursor<DFA>         self;
  typedef transition_cursor<DFA>      super;
  typedef typename DFA::state_type  state_type; 
  typedef typename DFA::char_type   char_type;  
  typedef typename DFA::tag_type    tag_type;   
  typedef typename DFA::char_traits char_traits; 
  typedef forward_cursor_concept      concept;

  forward_cursor(const DFA &a, state_type p)
    : super(a, p)
  { }

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

  forward_cursor()
    : super()
  { }

  self& operator=(state_type p) {
    super::operator=(p);
    return *this;
  }

  bool forward(const char_type &a) {
    q = fa->delta1(q, a);
    return !this->sink();
  }

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

  bool exists(const char_type &a) const {
    return fa->delta1(q, a) != DFA::null_state;
  }

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

protected:
  typedef typename DFA::edges_type::const_iterator edges_iterator;
  using super::q;
  using super::fa;
  using super::transition;
};

template <typename ForwardCursor, typename StackContainer = vector<ForwardCursor> >
class stack_cursor
  : public StackContainer, public stack_cursor_concept
{
  // the interface publicly inherited from stack is not a standard requirement
public:
  typedef stack_cursor                        self;
  typedef StackContainer                      super;
  typedef typename ForwardCursor::state_type  state_type; 
  typedef typename ForwardCursor::char_type   char_type;  
  typedef typename ForwardCursor::tag_type    tag_type;   
  typedef typename ForwardCursor::char_traits char_traits; 
  typedef stack_cursor_concept                concept;

  stack_cursor(const ForwardCursor &x)
    : super() {
    push_back(x);
  }

  stack_cursor()  // Empty stack
    : super()
  { }

  state_type src() const { return super::back().src(); }

  state_type aim() const { return super::back().aim(); }

  char_type letter() const { return super::back().letter(); }

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

  state_type sink_state() const { return super::back().sink_state(); }

  bool exists(const char_type &a) const { return super::back().exists(a); }

  bool find(const char_type &a) { return super::back().find(a); }

  bool first() { return super::back().first(); }

  bool next() { return super::back().next(); }

  void forward() {
    push_back(super::back());
    super::back().forward();
  }

  bool forward(const char_type &a) {
    push_back(super::back());
    return super::back().forward(a);
  }

  bool backward() {
    super::pop_back();
    return !super::empty();
  }

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

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

  tag_type src_tag() const { return super::back().src_tag(); }

  tag_type aim_tag() const { return super::back().aim_tag(); }

  const ForwardCursor& top() const { return super::back(); }
};

struct none
{
  template <class T>
  bool operator()(const T&) const {
    return false;
  }
};

template <typename StackCursor, typename MarkerFunction = none>
class dfirst_cursor : public dfirst_cursor_concept
{
protected:
  StackCursor c;
  bool has_poped;
  MarkerFunction visited;

public:
  typedef dfirst_cursor                     self;
  typedef dfirst_cursor_concept             super;
  typedef typename StackCursor::state_type  state_type; 
  typedef typename StackCursor::char_type   char_type;  
  typedef typename StackCursor::tag_type    tag_type;   
  typedef typename StackCursor::char_traits char_traits; 
  typedef typename super::concept           concept;

  dfirst_cursor(const StackCursor &x,
                const MarkerFunction &f = MarkerFunction())
    : c(x), has_poped(false), visited(f) {
    visited(c.src());   // set c source to 'visited'
  }

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

  bool forward() {
    if (has_poped) { 
      // move on to the next outgoing transition if any otherwise pop
      if (!c.next()) 
        return !c.backward();  // at edges end
      else {
        has_poped = false;
        return true;
      }
    }

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

  void backward() { has_poped = true; } // force pop

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

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

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

  state_type src() const { return c.src(); }

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

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

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

  tag_type src_tag() const { return c.src_tag(); }

  tag_type aim_tag() const { return c.aim_tag(); }

  const StackCursor& stack() const { return c; }
};

template <class state_type, class LessThan = less<state_type> >
struct set_marker : unary_function<state_type, bool>
{
  set<state_type, LessThan> pool;
  set_marker()
  { }
  bool operator() (const state_type &q) {
    return !(pool.insert(q).second);  // insert returns pair<iterator,bool>
  }
};

template <typename DFA>
inline
cursor<DFA> plainc(const DFA &a, typename DFA::state_type q) {
  return cursor<DFA>(a, q);
}

template <typename DFA>
inline
cursor<DFA> plainc(const DFA &a) {
  return cursor<DFA>(a, a.initial());
}

template <typename FA>
inline
transition_cursor<FA> transitionc(const FA &a, typename FA::state_type q) {
  return transition_cursor<FA>(a, q);
}

template <typename FA>
inline
transition_cursor<FA> transitionc(const FA &a) {
  return transition_cursor<FA>(a, a.initial());
}

template <typename DFA>
inline
forward_cursor<DFA> forwardc(const DFA &a, typename DFA::state_type q) {
  return forward_cursor<DFA>(a, q);
}

template <typename DFA>
inline
forward_cursor<DFA> forwardc(const DFA &a) {
  return forward_cursor<DFA>(a, a.initial());
}

template <typename ForwardCursor>
inline
stack_cursor<ForwardCursor> stackc(const ForwardCursor &c) {
  return stack_cursor<ForwardCursor>(c);
}

// default behavior (catch-all):
template <typename Model, typename Concept>
struct dfirst_cursor_type
{
  // Trick: this template does not define a public 'model'
  // type. Instanciation of this template will occur if no
  // specialization exists and will lead to a compiler error
  // which means that Model is not either a FA, DFA, forward_cursor,
  // transition_cursor nor a stack_cursor and therefore cannot be used
  // to instanciate the function template dfirstc
};

template <class FA>
struct dfirst_cursor_type<FA, FA_concept>
{
  typedef dfirst_cursor<stack_cursor<transition_cursor<FA> > > model;
};

template <class DFA>
struct dfirst_cursor_type<DFA, DFA_concept>
{
  typedef dfirst_cursor<stack_cursor<forward_cursor<DFA> > > model;
};

template <class ForwardCursor>
struct dfirst_cursor_type<ForwardCursor, forward_cursor_concept>
{
  typedef dfirst_cursor<stack_cursor<ForwardCursor> > model;
};

template <class TransitionCursor>
struct dfirst_cursor_type<TransitionCursor, transition_cursor_concept>
{
  typedef dfirst_cursor<stack_cursor<TransitionCursor> > model;
};

template <class StackCursor>
struct dfirst_cursor_type<StackCursor, stack_cursor_concept>
{
  typedef dfirst_cursor<StackCursor> model;
};

template <typename T>
inline
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 <typename DFA>
typename 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())
    return dfirst_cursor<stack_cursor<forward_cursor<DFA> > >(stackc(fc));
  else
    return dfirst_cursor<stack_cursor<forward_cursor<DFA> > >();
}

template <typename FA>
typename dfirst_cursor_type<FA, FA_concept>::model
dfirstc_(const FA &x, FA_concept)
{
  transition_cursor<FA> fc(x, x.initial());
  if (!fc.sink() && fc.first())
    return dfirst_cursor<stack_cursor<transition_cursor<FA> > >(stackc(fc));
  else
    return dfirst_cursor<stack_cursor<transition_cursor<FA> > >();
}

// Builds a depth first cursor from a forward cursor by constructing the
// underlying stack cursor:
template <class ForwardCursor>
typename 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())
      return dfirst_cursor<stack_cursor<ForwardCursor> >(s);
  }
  return dfirst_cursor<stack_cursor<ForwardCursor> >();
}

// Builds a depth first cursor from a transition cursor by constructing the
// underlying stack cursor:
template <class TransitionCursor>
typename dfirst_cursor_type<TransitionCursor, transition_cursor_concept>::model
dfirstc_(const TransitionCursor &x, transition_cursor_concept)
{
  if (!x.sink()) {
    stack_cursor<TransitionCursor> s(x);
    if (s.first())
      return dfirst_cursor<stack_cursor<TransitionCursor> >(s);
  }
  return dfirst_cursor<stack_cursor<TransitionCursor> >();
}

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

// Depth first mark cursor helper functions:
template <typename Model, typename Concept, typename MarkerFunction>
struct dfirst_mark_cursor_type
{ };

template <typename DFA, typename MarkerFunction>
struct dfirst_mark_cursor_type<DFA, DFA_concept, MarkerFunction>
{
  typedef dfirst_cursor<stack_cursor<forward_cursor<DFA> >,
                        MarkerFunction> model;
};

template <typename FA, typename MarkerFunction>
struct dfirst_mark_cursor_type<FA, FA_concept, MarkerFunction>
{
  typedef dfirst_cursor<stack_cursor<transition_cursor<FA> >,
                        MarkerFunction> model;
};

template <typename TransitionCursor, typename MarkerFunction>
struct dfirst_mark_cursor_type<TransitionCursor, transition_cursor_concept,
                               MarkerFunction>
{
  typedef dfirst_cursor<stack_cursor<TransitionCursor>, MarkerFunction> model;
};

template <typename ForwardCursor, typename MarkerFunction>
struct dfirst_mark_cursor_type<ForwardCursor, forward_cursor_concept,
                               MarkerFunction>
{
  typedef dfirst_cursor<stack_cursor<ForwardCursor>, MarkerFunction> model;
};

template <typename T>
inline
typename dfirst_mark_cursor_type<T, typename T::concept,
                                 set_marker<typename T::state_type> >::model
dfirst_markc(const T &x)
{
  return dfirst_markc_(x, x, set_marker<typename T::state_type>());
}

template <typename T, typename MarkerFunction>
inline
typename dfirst_mark_cursor_type<T, typename T::concept, MarkerFunction>::model
dfirst_markc(const T &x, const MarkerFunction& m)
{
  return dfirst_markc_(x, x, m);
}

// Build 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 transition, return an empty cursor
template <typename DFA, typename MarkerFunction>
typename dfirst_mark_cursor_type<DFA, DFA_concept, MarkerFunction>::model
dfirst_markc_(const DFA &x, DFA_concept, const MarkerFunction& m)
{
  forward_cursor<DFA> fc(x, x.initial());
  if (!fc.sink() && fc.first())
    return dfirst_cursor<stack_cursor<forward_cursor<DFA> >,
      MarkerFunction>(stackc(fc), m);
  else
    return dfirst_cursor<stack_cursor<forward_cursor<DFA> >,
      MarkerFunction>();
}

template <typename FA, typename MarkerFunction>
typename dfirst_mark_cursor_type<FA, FA_concept, MarkerFunction>::model
dfirst_markc_(const FA &x, FA_concept, const MarkerFunction& m)
{
  transition_cursor<FA> fc(x, x.initial());
  if (!fc.sink() && fc.first())
    return dfirst_cursor<stack_cursor<transition_cursor<FA> >,
      MarkerFunction>(stackc(fc), m);
  else
    return dfirst_cursor<stack_cursor<transition_cursor<FA> >,
      MarkerFunction>();
}

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

// Builds a depth first cursor from a transition cursor by
// constructing the underlying stack cursor:
template <typename TransitionCursor, typename MarkerFunction>
typename dfirst_mark_cursor_type<TransitionCursor, transition_cursor_concept,
                                 MarkerFunction>::model
dfirst_markc_(const TransitionCursor &x, transition_cursor_concept,
              const MarkerFunction& m)
{
  if (!x.sink()) {
    stack_cursor<TransitionCursor> s(x);
    if (s.first())
      return dfirst_cursor<stack_cursor<TransitionCursor>,
        MarkerFunction>(s, m);
  }
  return dfirst_cursor<stack_cursor<TransitionCursor>, MarkerFunction>();
}

template <typename ForwardCursor, typename QueueContainer = deque<ForwardCursor> >
class queue_cursor
  : public QueueContainer, public queue_cursor_concept
{
public:
  typedef queue_cursor                        self;
  typedef QueueContainer                      super;
  typedef typename ForwardCursor::state_type  state_type; 
  typedef typename ForwardCursor::char_type   char_type;  
  typedef typename ForwardCursor::tag_type    tag_type;   
  typedef typename ForwardCursor::char_traits char_traits; 
  queue_cursor(const ForwardCursor &x)
    : super() {
    super::push_back(x);
  }

  queue_cursor()
    : super()
  { }

  state_type src() const { return super::back().src(); }

  state_type aim() const { return super::back().aim(); }

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

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

  char_type letter() const { return super::back().letter();  }

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

  state_type sink_state() const { return super::back().sink_state(); }

  bool find(const char_type &a) { return super::back().find(a); }

  bool first() { return super::back().first(); }

  bool next() { 
    super::push_back(super::back());
    return super::back().next();
  }

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

  bool forward(const char_type &a) { return super::back().forward(a); }

  bool exists(const char_type &a) const { return super::back().exists(a); }

  bool dequeue() {
    super::back() = super::front();
    super::pop_back();
    return !super::empty();
  }

  tag_type src_tag() const { return super::back().src_tag(); }

  tag_type aim_tag() const { return super::back().aim_tag(); }
};


template <typename QueueCursor, typename MarkerFunction = none>
class bfirst_cursor : public bfirst_cursor_concept
{
protected:
  QueueCursor c;
  MarkerFunction visited;

public:
  typedef bfirst_cursor                     self;
  typedef typename QueueCursor::state_type  state_type; 
  typedef typename QueueCursor::char_type   char_type;  
  typedef typename QueueCursor::tag_type    tag_type;   
  typedef typename QueueCursor::char_traits char_traits; 
  typedef bfirst_cursor_concept             concept;

  bfirst_cursor(const QueueCursor &x,
                const MarkerFunction &f = MarkerFunction())
    : c(x), visited(f) {
    visited(c.src());
  }

  bfirst_cursor()
    : c()
  { }

  bool next() {
    if (!c.next()) {
      while (c.dequeue()) {
        c.forward();
        if (!visited(c.src()) && c.first()) break;
      }
      return false;
    }
    return true;
  }

  state_type src() const { return c.src(); }

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

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

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

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

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

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

  tag_type src_tag() const { return c.src_tag(); }

  tag_type aim_tag() const { return c.aim_tag(); }
};

template <class ForwardCursor>
queue_cursor<ForwardCursor> queuec(const ForwardCursor &x) {
  return queue_cursor<ForwardCursor>(x);
}

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

template <class DFA>
struct bfirst_cursor_type<DFA, DFA_concept>
{
  typedef bfirst_cursor<queue_cursor<forward_cursor<DFA> > > model;
};

template <class TransitionCursor>
struct bfirst_cursor_type<TransitionCursor, transition_cursor_concept>
{
  typedef bfirst_cursor<queue_cursor<TransitionCursor> > model;
};

template <class ForwardCursor>
struct bfirst_cursor_type<ForwardCursor, forward_cursor_concept>
{
  typedef bfirst_cursor<queue_cursor<ForwardCursor> > model;
};

template <class QueueCursor>
struct bfirst_cursor_type<QueueCursor, queue_cursor_concept>
{
  typedef bfirst_cursor<QueueCursor> model;
};

template <typename T>
inline
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>
inline
typename 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())
    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 transition cursor by constructing
// the underlying stack cursor:
template <class TransitionCursor>
inline
typename bfirst_cursor_type<TransitionCursor, transition_cursor_concept>::model
_bfirstc(const TransitionCursor &x, transition_cursor_concept)
{
  if (!x.sink()) {
    queue_cursor<TransitionCursor> s(x);
    if (s.first())
      return bfirst_cursor<queue_cursor<TransitionCursor> >(s);
  }
  return bfirst_cursor<queue_cursor<TransitionCursor> >();
}

// Builds a breadth-first cursor from a forward cursor by constructing
// the underlying stack cursor:
template <class ForwardCursor>
inline
typename 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())
      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>
inline
typename bfirst_cursor_type<QueueCursor, queue_cursor_concept>::model
_bfirstc(const QueueCursor &x, queue_cursor_concept)
{
  if (!x.sink()) {
    QueueCursor s(x);
    if (s.first())
      return bfirst_cursor<QueueCursor>(s);
  }
  return bfirst_cursor<QueueCursor>();
}

template <class Model, class Concept, typename MarkerFunction>
struct bfirst_mark_cursor_type
{ };

template <class DFA, typename MarkerFunction>
struct bfirst_mark_cursor_type<DFA, DFA_concept, MarkerFunction>
{
  typedef bfirst_cursor<queue_cursor<forward_cursor<DFA> >,
                        MarkerFunction> model;
};

template <class ForwardCursor, typename MarkerFunction>
struct bfirst_mark_cursor_type<ForwardCursor, forward_cursor_concept,
                               MarkerFunction>
{
  typedef bfirst_cursor<queue_cursor<ForwardCursor>, MarkerFunction > model;
};

template <class QueueCursor, typename MarkerFunction>
struct bfirst_mark_cursor_type<QueueCursor, queue_cursor_concept,
                               MarkerFunction>
{
  typedef bfirst_cursor<QueueCursor, MarkerFunction> model;
};

template <class T>
inline
typename bfirst_mark_cursor_type<T, typename T::concept,
                                 set_marker<typename T::state_type> >::model
bfirst_markc(const T &x) {
  return bfirst_markc_(x, x, set_marker<typename T::state_type>());
}

template <class T, typename MarkerFunction>
inline
typename bfirst_mark_cursor_type<T, typename T::concept,
                                 MarkerFunction>::model
bfirst_markc(const T &x, const MarkerFunction& m) {
  return bfirst_markc_(x, x, m);
}

// Builds a breadth-first mark 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, typename MarkerFunction>
inline
typename bfirst_mark_cursor_type<DFA, DFA_concept, MarkerFunction>::model
bfirst_markc_(const DFA &x, DFA_concept, const MarkerFunction& m)
{
  forward_cursor<DFA> fc(x, x.initial());
  if (!fc.sink() && fc.first())
    return bfirst_cursor<queue_cursor<forward_cursor<DFA> >,
      MarkerFunction >(queuec(fc),m);
  else
    return bfirst_cursor<queue_cursor<forward_cursor<DFA> >,
      MarkerFunction >();
}

// Builds a breadth-first mark cursor from a forward cursor by constructing
// the underlying stack cursor:
template <class ForwardCursor, typename MarkerFunction>
inline
typename bfirst_mark_cursor_type<ForwardCursor, forward_cursor_concept,
                                 MarkerFunction>::model
bfirst_markc_(const ForwardCursor &x, forward_cursor_concept,
              const MarkerFunction& m)
{
  if (!x.sink()) {
    queue_cursor<ForwardCursor> s(x);
    if (s.first())
      return bfirst_cursor<queue_cursor<ForwardCursor>,
        MarkerFunction>(s, m);
  }
  return bfirst_cursor<queue_cursor<ForwardCursor>, MarkerFunction>();
}

// Builds a breadth-first cursor from a stack cursor:
template <class QueueCursor, typename MarkerFunction>
inline
typename bfirst_mark_cursor_type<QueueCursor, queue_cursor_concept,
                                 MarkerFunction>::model
bfirst_markc_(const QueueCursor &x, queue_cursor_concept,
              const MarkerFunction& m)
{
  if (!x.sink()) {
    QueueCursor s(x);
    if (s.first())
      return bfirst_cursor<QueueCursor, MarkerFunction>(s, m);
  }
  return bfirst_cursor<QueueCursor, MarkerFunction>();
}

template <typename Cursor, typename InputIterator>
inline
bool forward(Cursor &c, InputIterator i, InputIterator j) {
  for(; !(i == j) && c.forward(*i); ++i);
  return i == j;
}

} // namespace astl

#endif  // ASTL_CURSOR_H

---