// This file tests pre/postconditions and invariants of DFA class.
// Input: a dictionary file (one word per line)
// Output: should be the same language modulo the words ordering

#include <cassert>
#include <dfa_matrix.h>
#include <dfa_map.h>
#include <dfa_bin.h>
#include <dfa_mtf.h>
#include <dfa_tr.h>
// #include "dfa_hash.h"
#include <astl_tree.h>

#include <astl.h>
#include <vector>
#include <iterator>
#include <language.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <cursor.h>

typedef DFA_matrix<plain> DFA;
// typedef DFA_map<plain> DFA;
// typedef DFA_bin<plain> DFA;
// typedef DFA_mtf<plain> DFA;
// typedef DFA_tr<plain> DFA;
// typedef DFA_hash<plain> DFA;

DFA A;
unsigned long Q = 0, T = 0;

void check_state_creation(DFA::State q) {
	assert(q != A.null_state);
	DFA::Edges 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);
}	

void check_transition_creation(DFA::State q, DFA::Sigma::char_type a, DFA::State p) {
	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);
	DFA::Edges e = A.delta2(q);
	DFA::Edges::size_type s = e.size();
	assert(e.size() > 0);
	assert(e.empty() == false);
	pair<const DFA::Alphabet, DFA::State> tmp_pair(a, p);
	assert(*(e.find(a)) == tmp_pair);
	assert(e.count(a) == 1);
	for(DFA::Edges::const_iterator i = e.begin(); i != e.end(); ++i, --s);
	assert(s == 0);
}

void check_state_deletion(DFA::State q) {
	T -= A.delta2(q).size();
	A.del_state(q);
	assert(A.state_count() == --Q);
	assert(A.trans_count() == T);
}

void check_transition_deletion(DFA::State q, DFA::Alphabet a, DFA::State p) {
	DFA::Edges::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);
}

int main()
{
	cerr << "Taille de l'alphabet == " << DFA::Sigma::size << endl;
	// Check the DFA initial state:
	assert(A.state_count() == 0);
	assert(A.trans_count() == 0);
	assert(A.initial() == A.null_state);

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

	// Transition creation
	DFA::State p = A.new_state();
	check_state_creation(p);
	assert(A.state_count() == ++Q);
	check_transition_creation(q, 'a', p);
	check_transition_creation(q, 'é', p);
	check_transition_creation(p, 'a', p);
	check_transition_creation(p, 'é', p);
	assert(A.delta2(q) == A.delta2(p));
	
	// State deletion and initial state constistency:
	check_state_deletion(q);
	assert(A.initial() == A.null_state);   // the initial state q has been removed

	// Multiple state creation:
	DFA::State t[25];
	DFA::State *ptr = A.new_state(10, t);
	assert(ptr == (t + 10));
	for_each(t, t + 10, check_state_creation);
	Q += 10;
	assert(A.state_count() == Q);
	ptr = A.new_state(15, ptr);
	assert(ptr == (t + 25));
	for_each(t + 10, ptr, check_state_creation);
	Q += 15;
	assert(A.state_count() == Q);	

	// Transition deletion:
	check_transition_deletion(p, 'a', p);
	check_transition_deletion(p, 'é', p);

	// Transition redefinition:
	q = A.new_state();
	check_state_creation(q);
	assert(A.state_count() == ++Q);
	check_transition_creation(p, '$', p);
	check_transition_creation(p, 't', q);
	check_transition_creation(p, '0', q);
	A.change_trans(p, '0', p);
	DFA::Edges::size_type s = A.delta2(p).size();
	assert(A.delta1(p, '0') == p);
	assert(A.trans_count() == T);
	assert(A.delta2(p).size() == s);
	
	// State duplication:
	check_transition_creation(p, ',', t[0]);
	check_transition_creation(p, 'u', t[0]);
	check_transition_creation(p, 'ç', t[1]);
	check_transition_creation(p, 'o', t[2]);
	DFA::State h = A.duplicate_state(p);
	assert(h != A.null_state);
	assert(A.state_count() == ++Q);
	T += A.delta2(p).size();
	assert(A.trans_count() == T);
	assert(A.delta2(h) == A.delta2(p));
	assert(A.delta2(h).size() == A.delta2(p).size());
	assert(A.delta2(h).empty() == A.delta2(p).empty());
	assert(equal(A.delta2(h).begin(), A.delta2(h).end(), A.delta2(p).begin()));
	assert(A.final(h) == A.final(p));

	// State copy:
	check_transition_creation(t[1], 'ù', t[4]);
	check_transition_creation(t[1], '?', t[5]);
	T += A.delta2(p).size() - A.delta2(t[1]).size();
	A.final(p) = true;
	assert(A.final(p) == true);
	A.copy_state(p, t[1]);
	assert(A.state_count() == Q);
	assert(A.trans_count() == T);
	assert(A.delta2(t[1]) == A.delta2(p));
	assert(A.delta2(t[1]).size() == A.delta2(p).size());
	assert(A.delta2(t[1]).empty() == A.delta2(p).empty());
	assert(equal(A.delta2(t[1]).begin(), A.delta2(t[1]).end(), A.delta2(p).begin()));
	assert(A.final(t[1]) == A.final(p));

 	// Final:
	A.final(t[9]) = A.final(p);
	assert(A.final(t[9]) == true);
	assert(A.final(t[9]) == A.final(p));
	A.final(p) = false;
	assert(A.final(p) == false);
	assert(A.final(t[9]) != A.final(p));

	// Delta1 and Delta2 consistency:
	vector<pair<DFA::Sigma::Alphabet, DFA::State> >::const_iterator i;
	vector<pair<DFA::Sigma::Alphabet, DFA::State> > v;
	copy(A.delta2(p).begin(), A.delta2(p).end(), back_inserter(v));
	for(i = v.begin(); i != v.end(); ++i)
		assert((*i).second == A.delta1(p, (*i).first));
	
	// Tree construction
	(&A)->~DFA();
	new (&A) DFA();
	string word;
	while (!cin.eof()) {
		getline(cin, word);
		if (!word.empty()) tree_build(A, word.begin(), word.end(), empty_tag());
	}
	language(ostream_iterator<char>(cout), dfirstc(forwardc(A)));
}