check_nfa.cpp

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

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

#include <astl.h>
#include <nfa_mmap.h>

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

template <typename NFA>
void check_state_creation(NFA &A, typename NFA::state_type q) {
  assert(q != A.null_state);
  typename NFA::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 NFA::edges_type::const_iterator, 
    typename NFA::edges_type::const_iterator> p = e.equal_range('z');
  assert(p.first == p.second);
  assert(e == e);
  typedef typename NFA::edges_type::key_type dummy1;
  typedef typename NFA::edges_type::data_type dummy2;
  typedef typename NFA::edges_type::value_type dummy3;
  typedef typename NFA::edges_type::key_compare dummy4;
  typedef typename NFA::edges_type::value_compare dummy5;
  typedef typename NFA::edges_type::const_reference dummy6;
  typedef typename NFA::edges_type::size_type dummy7;
  typedef typename NFA::edges_type::difference_type dummy8;
  typedef typename NFA::edges_type::const_iterator dummy9;
  typedef typename NFA::edges_type::const_reverse_iterator dummy10;
  typename NFA::edges_type::key_compare kc = e.key_comp();
  assert(kc('b', 'a') == false);
  typename NFA::edges_type::value_compare vc = e.value_comp();
  pair<typename NFA::edges_type::key_type, typename NFA::edges_type::data_type> p1('a', A.null_state);
  typename NFA::edges_type::value_type p2('b', NFA::null_state);
  assert(vc(p2, p1) == false);
}	

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

template <typename NFA>
void check_state_deletion(NFA &A, typename NFA::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 NFA>
void check_transition_deletion(NFA &A, typename NFA::state_type q, 
			       typename NFA::char_type a, 
			       typename NFA::state_type p,
			       unsigned long &T) {
  typename NFA::edges_type::size_type s = A.delta2(q).size();
  typename NFA::state_type qq;
  assert(A.delta1(q, a, &qq) != &qq);
  A.del_trans(q, a);
  assert(A.trans_count() == --T);
  assert(A.delta1(q, a, &qq) == &qq);
  assert(A.delta2(q).size() == --s);
}

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

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

  // state_type creation:
  typename NFA::state_type q = A.new_state();
  check_state_creation(A, q);
  assert(A.state_count() == ++Q);
  A.initial().insert(q);
  assert(A.initial().find(q) != A.initial().end());

  // Transition creation
  typename NFA::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, '