cursor.h

一个类似STL的自动机的源代码库

/*
 * ASTL - the Automaton Standard Template Library.
 * C++ generic components for Finite State Automata handling.
 * Copyright (C) 2000-2003 Vincent Le Maout ([e-mail]).
 * 
 * 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 <stack>
#include <vector>
#include <functional>
#include <list>
#include <deque>
#include <queue>
#include <set>
#include <iostream>
#include <utility>

#ifdef __GNUG__
#if (__GNUG__ < 3)
#include <hash_set>
#else
#include <ext/hash_set>
using namespace __gnu_cxx;
#endif
#endif

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

#include <concept.h>

ASTL_BEGIN_NAMESPACE

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

  // Backward compatibility typedefs:
  typedef state_type  State;
  typedef tag_type    Tag;
  typedef char_type   Alphabet;
  typedef char_traits Sigma;

protected:
  const DFA *dfa;
  state_type q;

public:
  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;
  }
};

template <typename Cursor, typename InputIterator>
inline
bool forward(Cursor &c, InputIterator first, InputIterator last)
{
  if (c.sink()) return false;
  for(;  first != last && c.forward(*first); ++first);
  return first == last;
}

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

  // Backward compatibility typedefs:
  typedef state_type  State;
  typedef tag_type    Tag;
  typedef char_type   Alphabet;
  typedef char_traits Sigma;

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

public:
  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);
  }

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

  bool first_transition() {
    return !((transition = fa->delta2(q).begin()) == fa->delta2(q).end());
  }
  
  bool next_transition() {
    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 {   
    // STL containers need operator < on
    // their value_type (to define < on themselves)
    return q < x.q || (q == x.q && transition < x.transition);
  }
};

template <typename DFA>
class forward_cursor : public transition_cursor<DFA>, public forward_cursor_concept
{
protected:
  typedef typename DFA::edges_type::const_iterator edges_iterator;

public:
  typedef forward_cursor<DFA>         self;
  typedef transition_cursor<DFA>      super;
  typedef typename super::Tag         tag_type;
  typedef typename super::State       state_type;
  typedef typename super::Alphabet    char_type;
  typedef typename super::char_traits char_traits;
  typedef forward_cursor_concept      concept;

  // Backward compatibility typedefs:
  typedef state_type  State;
  typedef tag_type    Tag;
  typedef char_type   Alphabet;
  typedef char_traits Sigma;

  forward_cursor(const DFA &a, state_type p, const char_type &letter) 
    : super(a, p), super::transition(fa->delta2(p).find(letter)) 
    { }
  
  forward_cursor(const DFA &a, state_type p, edges_iterator t)
    : super(a, p), super::transition(t)
    { }
  
  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 !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());
  }
};

// DEPTH-FIRST SEARCH RELATED CURSORS:

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

  // Backward compatibility typedefs:
  typedef state_type  State;
  typedef tag_type    Tag;
  typedef char_type   Alphabet;
  typedef char_traits Sigma;

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

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

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