cursor.h

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

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

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

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

  bool find(const char_type &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 char_type &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();
  }

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

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

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

template <class StackCursor, class MarkerFunction = always_false>
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::tag_type    tag_type;
  typedef typename StackCursor::state_type  state_type;
  typedef typename StackCursor::char_type   char_type;
  typedef typename StackCursor::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;

  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)
    { }

  // 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.src()) || !c.first_transition()) {
      // cannot forward so backward => pop
      c.backward();
      has_poped = true;
      return false;
    }
    return true;
  }

  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();
  }

  // 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;
  }

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

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

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

  // Not a standard requirement:
  const StackCursor& stack() const {
    return c;
  }
};

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

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

// Use the tag to mark the source state
// Requirements: bool tag_type::visited() behaving like set_marker
template <class DFA>
struct tag_marker : unary_function<typename DFA::state_type, bool>
{
  DFA *dfa;

  tag_marker(DFA &a)
    : dfa(&a)
    { }

  tag_marker()
    { }

  bool operator() (typename DFA::state_type q) {
    return dfa->tag(q).visited();
  }
};

// //
// // Helper functions serve two purposes:
// // 1. Spare 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 either 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 <typename DFA>
inline
cursor<DFA> plainc(const DFA &a, typename DFA::state_type q) {
  return cursor<DFA>(a, q);
}

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

// Build a transition cursor from a FA pointing to state q:
template <typename FA>
inline
transition_cursor<FA> transitionc(const FA &a, typename FA::state_type q) {
  return transition_cursor<FA>(a, q);
}

// Build a transition cursor from a FA with its source state pointing to the initial state:
template <typename FA>
inline
transition_cursor<FA> transitionc(const FA &a) {
  return transition_cursor<FA>(a, a.initial());
}

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

// Build a forward cursor from a DFA with its source state pointing to the initial state:
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);
}

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

// 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> >();
}

// Build a depth-first cursor with the default visited states marker from a forward cursor:
template <typename ForwardCursor>
inline
dfirst_cursor<stack_cursor<ForwardCursor>, set_marker<typename ForwardCursor::state_type> > 
dfirst_markc(const ForwardCursor &x) {
#ifndef _MSC_VER
  return dfirst_markc(x, set_marker<typename ForwardCursor::state_type>());
#else
  return dfirst_markc(x, set_marker<ForwardCursor::state_type>());
#endif
}

template <typename ForwardCursor, typename MarkerFunction>
dfirst_cursor<stack_cursor<ForwardCursor>, set_marker<typename ForwardCursor::state_type> > 
dfirst_markc(const ForwardCursor &x, const MarkerFunction& m) {
  if (!x.sink()) {
    stack_cursor<ForwardCursor> s(x);
    if (s.first_transition()) 
      return dfirst_cursor<stack_cursor<ForwardCursor>, MarkerFunction>(s, m);
  }
  return dfirst_cursor<stack_cursor<ForwardCursor>, MarkerFunction>();
}

#else
// Template servant