dfa_min.h

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

	  class StateAllocator = allocator<state> >
class DFA_min : public DFA_concept
{
public:
  typedef plain                                      char_traits;
  typedef typename vector<typename StateAllocator::pointer>::size_type state_type;
  typedef char                                       char_type;
  typedef DFA_min                                    self;
  typedef empty_tag                                  tag_type;

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

#ifndef _MSC_VER
  static const state_type null_state = 0;
#else
  static const state_type null_state;
#endif

protected:
  TransitionAllocator t_alloc;
  StateAllocator      s_alloc;
  state_type          i;
  bool                ready;
  unsigned long       _state_count, _trans_count;

  typedef set<state_type, compare_state>   container;
  vector<container*>                       _pool;  // each height has its own set
  vector<typename StateAllocator::pointer> Q;
  compare_state                            cmp_state;
  state_type                               hole;  // first free cell of the state vector
  unsigned long                            wc; // word count

  container& pool(unsigned long h) { 
    for(; _pool.size() < h + 1; _pool.push_back(new container(cmp_state))); 
    return *(_pool[h]);
  }

  void prepare();

  state::bool_reference final(state_type q) {
    return Q[q]->final();
  }

  void initial(state_type q) {
    i = q;
  }

  state_type new_state(const typename StateAllocator::value_type &s = typename StateAllocator::value_type()) {
    ++_state_count;
    while (hole < Q.size())
    if (Q[hole] == NULL) {
      Q[hole] = s_alloc.allocate(1, NULL);
      s_alloc.construct(Q[hole], s);
      return hole++;
    }
    else ++hole;
    Q.push_back(s_alloc.allocate(1, NULL));
    s_alloc.construct(Q.back(), s);
    ++hole;
    return Q.size() - 1;
  }

  void del_state(state_type q) {
    --_state_count;
    _trans_count -= Q[q]->size();
    state::iterator i = Q[q]->begin(), j = Q[q]->end();
    for(; i != j; ++i)
    Q[(*i).aim()]->dec_degree_in();
    s_alloc.destroy(Q[q]);
    s_alloc.deallocate(Q[q], 1);
    Q[q] = NULL;
    hole = min(hole, q);
  }

  void set_trans(state_type q, char_type a, state_type p) {
    ++_trans_count;
    Q[q]->insert(transition(a, p));
    Q[p]->inc_degree_in();
  }

  state_type duplicate_state(state_type q) {
    _trans_count += Q[q]->size();
    state_type p = new_state(*Q[q]);
    state::iterator i = Q[p]->begin(), j = Q[p]->end();
    for(; i != j; ++i)
    Q[(*i).aim()]->inc_degree_in();
    return p;
  }
	
  void del_trans(state_type q, char_type a) {
    --_trans_count;
    Q[Q[q]->delta1(a)]->dec_degree_in();
    Q[q]->erase(transition(a));
  }

  void change_trans(state_type q, char_type a, state_type p) {
    Q[Q[q]->delta1(a)]->dec_degree_in();
    Q[q]->change_trans(transition(a,p));
    Q[p]->inc_degree_in();
  }

public: // TMP
  void height(state_type q, unsigned long h) {
    Q[q]->height(h);
  }

  unsigned long height(state_type q) const {
    return Q[q]->height();
  }

  unsigned long degree_in(state_type q) const {
    return Q[q]->degree_in();
  }

  void degree_in(state_type q, unsigned long d) {
    Q[q]->degree_in(d);
  }

#ifndef _MSC_VER
  template <class InputIterator>
  bool _insert(InputIterator first, InputIterator last);
#else
  bool _insert(const char *, const char *);
#endif
	
public:
  typedef skip_blanks_iterator<state> const_iterator;

  DFA_min()
    : i(0),  ready(false),
      _state_count(0), _trans_count(0), Q(1, (state*) 0), cmp_state(Q), 
      hole(2), wc(0)
  { 
    i = new_state();
  }

  const StateAllocator& state_allocator() const {
    return s_alloc;
  }

  const_iterator begin() const {
    return const_iterator(&Q, initial());
  }

  const_iterator end() const {
    return const_iterator(&Q, Q.size());
  }

  ~DFA_min() {
    freeze();
#ifndef _MSC_VER
    typename vector<typename StateAllocator::pointer>::iterator i = Q.begin(), j = Q.end();
#else
    typename vector<StateAllocator::pointer>::iterator i = Q.begin(), j = Q.end();
#endif
    for(; i != j; ++i)
    if (*i != NULL) {
      s_alloc.destroy(*i);
      s_alloc.deallocate(*i, 1);
    }
  }

  bool final(state_type q) const {
    return Q[q]->final();
  }
	
  void freeze() {  // get rid of the unnecessary data
    for(typename vector<container*>::iterator i = _pool.begin(); i != _pool.end(); ++i)
    delete *i;
    _pool.clear();
    ready = false;
  }

#ifndef _MSC_VER
  template <class InputIterator>
  bool insert(InputIterator first, InputIterator last) {
#else
  bool insert(const char *first, const char *last) {
#endif
    if (_insert(first, last)) {
      ++wc;
      return true;
    }
    return false;
  }
	
  bool insert(const char *s) {
    return insert(s, s + strlen(s));
  }

  bool insert(const string &s) {
    return insert(s.begin(), s.end());
  }
	
  state_type initial() const {
    return i;
  }

  state_type delta1(state_type q, char_type a) const {
    return Q[q]->delta1(a);
  }

  class edges_type
  {
  protected:
    state *q;

  public:
    typedef int                               difference_type;
    typedef char_type                         key_type;
    typedef state_type                        data_type;
    typedef pair<const char_type, state_type> value_type;

    edges_type(state *p)
      : q(p)
    { }

    edges_type()
    {}

    bool empty() const {
      return q->size() == 0;
    }

    unsigned int size() const {
      return q->size();
    }

#if (__GNUG__ && __GNUG__ < 3)
    class const_iterator : public bidirectional_iterator<pair<char_type, state_type>, ptrdiff_t >
#else
    class const_iterator : public iterator<bidirectional_iterator_tag, pair<char_type, state_type> >
#endif
    {
    protected:
      state::const_iterator i;

    public:
      typedef const_iterator self;

      const_iterator()
      { }
      const_iterator(state::const_iterator j)
	: i(j)
      { }
      pair<char_type, state_type> operator* () const {
	return make_pair((*i).letter(), (*i).aim());
      }
      self& operator++ () {
	++i;
	return *this;
      }
      self operator++ (int) {
	self tmp = *this;
	++*this;
	return tmp;
      }
      bool operator== (const self &x) const {
	return i == x.i;
      }
      self& operator--() {
	--i;
	return *this;
      }
      self operator-- (int) {
	self tmp = *this;
	--*this;
	return tmp;
      }
    };
		
    const_iterator begin() const {
      return const_iterator(q->begin());
    }

    const_iterator end() const {
      return const_iterator(q->end());
    }

    const_iterator find(char_type a) const {
      return const_iterator(q->find(a));
    }
  };

  // Backward compatibility:
  typedef edges_type Edges;

  edges_type delta2(state_type q) const {
    return edges_type(Q[q]);
  }

  unsigned long state_count() const {
    return _state_count;
  }

  unsigned long trans_count() const {
    return _trans_count;
  }

  unsigned long size() const {
    return wc;
  }
};

#ifndef _MSC_VER
template <typename T, typename U>
const typename DFA_min<T, U>::state_type DFA_min<T, U>::null_state;
#else
template <class T, class U>
const typename DFA_min<T, U>::state_type DFA_min<T, U>::null_state = 0;
#endif

template <class T, class U>
void DFA_min<T, U>::prepare() {
  const_iterator first = begin(), last = end();
  for(; first != last; ++first)
    pool(height(*first)).insert(*first);
  ready = true;
}

#ifndef _MSC_VER
template <class TAllocator, class SAllocator> 
template <class InputIterator>
bool DFA_min<TAllocator, SAllocator>::_insert(InputIterator first, InputIterator last)
#else
template <class TAllocator, class SAllocator> 
bool DFA_min<TAllocator, SAllocator>::_insert(const char *first, const char *last)
#endif
{
  if (is_in(first, last, plainc(*this))) return false;  // word exists ?
  if (!ready) prepare();  // build the structure if necessary
  stack_cursor<forward_cursor<self> > c(forwardc(*this));
  bool duplicating;

  for(duplicating = false; first != last; ++first) {
    if (!duplicating)
      pool(height(c.src())).erase(c.src());

    if (!c.find(*first)) {
      set_trans(c.src(), *first, new_state());
      duplicating = true;
    }
    else 
      if (Q[c.aim()]->degree_in() > 1) {
	change_trans(c.src(), *first, duplicate_state(c.aim())); 
	duplicating = true;
      }
    c.forward(*first);
  }
  if (!duplicating) 
    pool(height(c.src())).erase(c.src());

  final(c.src()) = true;
  unsigned long h = height(c.src());

  for(; c.backward(); ) {
    // try to insert the current state in its height pool
    // if an equivalent state is found its ID is returned, otherwise it is inserted
#ifndef _MSC_VER
    pair<typename container::iterator, bool> i = pool(height(c.aim())).insert(c.aim());
#else
    pair<container::iterator, bool> i = pool(height(c.aim())).insert(c.aim());
#endif
    if (i.second == false) {  // found an equivalent state ?
      state_type tmp = c.aim(); 
      change_trans(c.src(), c.letter(), *i.first); // redirect the transition towards equivalent state
      del_state(tmp);
    }
    h = max(height(c.src()), h+1); // Precondition: states are initialized with height == 0
    height(c.src(), h);
  }
  pool(height(initial())).insert(initial());
  return true;
}

ASTL_END_NAMESPACE

#endif // ASTL_CLASS_DFA_MIN