check_dfa.cpp

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

// This file tests pre/postconditions and invariants of DFA class.

#include <astl.h>
#include <dfa.h>

#include <cassert>
#include <vector>
#include <iterator>
#include <string>
#include <iostream>
#include <algorithm>
#include <utility>

template <typename DFA>
void check_state_creation(DFA &A, typename DFA::state_type q) {
  assert(q != A.null_state);
  typename DFA::edges_type e = A.delta2(q);
  assert(e.empty() == true);  // there should be no transitions at creation
  assert(e.size() == 0);
  assert(e.find('a') == e.end());
  assert(e.begin() == e.end());
  assert(e.count(' ') == 0);
  assert(e.lower_bound('z') == e.begin());
  assert(e.upper_bound('z') == e.end());
  pair<typename DFA::edges_type::const_iterator, 
    typename DFA::edges_type::const_iterator> p = e.equal_range('z');
  assert(p.first == p.second);
  assert(e == e);
  assert(A.final(q) == false);
  typedef typename DFA::edges_type::key_type dummy1;
  typedef typename DFA::edges_type::data_type dummy2;
  typedef typename DFA::edges_type::value_type dummy3;
  typedef typename DFA::edges_type::key_compare dummy4;
  typedef typename DFA::edges_type::value_compare dummy5;
  typedef typename DFA::edges_type::const_reference dummy6;
  typedef typename DFA::edges_type::size_type dummy7;
  typedef typename DFA::edges_type::difference_type dummy8;
  typedef typename DFA::edges_type::const_iterator dummy9;
  typedef typename DFA::edges_type::const_reverse_iterator dummy10;
  typename DFA::edges_type::key_compare kc = e.key_comp();
  assert(kc('b', 'a') == false);
  typename DFA::edges_type::value_compare vc = e.value_comp();
  pair<typename DFA::edges_type::key_type, typename DFA::edges_type::data_type> p1('a', A.null_state);
  typename DFA::edges_type::value_type p2('b', DFA::null_state);
  assert(vc(p2, p1) == false);
}	

template <typename DFA>
void check_transition_creation(DFA &A, typename DFA::state_type q, 
			       typename DFA::char_traits::char_type a, 
			       typename DFA::state_type p,
			       unsigned long &T) {
  assert(A.delta1(q, a) == A.null_state);
  A.set_trans(q, a, p);
  assert(A.trans_count() == ++T);
  assert(A.delta1(q, a) == p);
  typename DFA::edges_type e = A.delta2(q);
  typedef typename DFA::edges_type edges_t;
  typename edges_t::size_type s = e.size();
  assert(e.size() > 0);
  assert(e.empty() == false);
  pair<typename DFA::char_type, typename DFA::state_type> tmp_pair(a, p);
  assert(*(e.find(a)) == tmp_pair);
  assert(e.count(a) == 1);
  for(typename DFA::edges_type::const_iterator i = e.begin(); i != e.end(); ++i, --s);
  assert(s == 0);
  assert(e == e);
}

template <typename DFA>
void check_state_deletion(DFA &A, typename DFA::state_type q, 
			  unsigned long &Q, unsigned long &T) {
  T -= A.delta2(q).size();
  A.del_state(q);
  assert(A.state_count() == --Q);
  assert(A.trans_count() == T);
}

template <typename DFA>
void check_transition_deletion(DFA &A, typename DFA::state_type q, 
			       typename DFA::char_type a, 
			       typename DFA::state_type p,
			       unsigned long &T) {
  typename DFA::edges_type::size_type s = A.delta2(q).size();
  assert(A.delta1(q, a) == p);
  A.del_trans(q, a);
  assert(A.trans_count() == --T);
  assert(A.delta1(q, a) == A.null_state);
  assert(A.delta2(q).size() == --s);
}

template <typename DFA>
void check_tags(DFA &A)
{
  typename DFA::state_type s = A.new_state();
  const typename DFA::tag_type& t = A.tag(s);
  typename DFA::tag_type& tt = A.tag(s);
  typename DFA::tag_type ttt = A.tag(s);
  const DFA& r = A;
  ttt = r.tag(s);
  assert((t == tt) && (t == ttt) && (tt == ttt));
}

template <typename DFA>
void check(DFA &A)
{
  unsigned long Q = 0, T = 0;

  // Check the DFA initial state:
  assert(A.state_count() == 0);
  assert(A.trans_count() == 0);
  assert(A.initial() == A.null_state);

  // state_type creation:
  typename DFA::state_type q = A.new_state();
  check_state_creation(A, q);
  assert(A.state_count() == ++Q);
  A.initial(q);
  assert(A.initial() == q);

  // Transition creation
  typename DFA::state_type p = A.new_state();
  check_state_creation(A, p);
  assert(A.state_count() == ++Q);
  check_transition_creation(A, q, 'a', p, T);
  check_transition_creation(A, q, '