//
//	File:		dfalgo_set.hh
//	Copyright:	Dominique REVUZ & Vincent LE MAOUT
//	Date:		Fri Jul 18 1997
//	Descrition:	operation ensembliste sur les dfa 
//      liste: unionDfa interDfa 
//      todo : complementDfa soustractionDfa 

#include <map>
#include <utility>   // pair<>
#include <iostream>

typedef void * pvoid;
typedef pair< pvoid , pvoid > pvoid_pair;
typedef map<pvoid_pair, pvoid , less<pvoid_pair> > table_associa_pair; 

template <class DFA, class State1,class State2,class State3>
State3 
exists(DFA &res,State1 q1, State2 q2, State3 dummy, bool erase_table = false)
{ 
  static table_associa_pair *table = NULL;
	
  if (erase_table)
	{
    delete table;
    table = NULL;
    return (dummy);
	}
	
  if (table == NULL) table = new table_associa_pair; 
	
  table_associa_pair &l = *table;
	
  //  return the state (q1,q2) in res if it exists else a new state3 is created 
  if (dummy == res.null_state ) // question 
		return (State3) l[make_pair((pvoid)q1,(pvoid)q2)];
  else // creation 
	{
		pvoid_pair x((pvoid)q1,(pvoid)q2);
    l[x] =(pvoid) dummy;
	}
  return res.null_state;
}


//
// Algorithm    : intersection_dfa_nfa
// Description  : computes intersection of one dfa with a nfa
// Input        : 1 dfa and 2 nfas
// Output       : result is placed in the third argument
// Precondition : none
// Uses         : exists, _intersection_dfa_nfa
//

template <class DFA, class NFA1, class NFA2> 
void 
intersection_dfa_nfa(DFA &dfa, NFA1 &nfa, NFA2 &result)
{
  NFA1::State_set::const_iterator i;
	
  for (i = nfa.initial().begin(); i != nfa.initial().end(); ++i)
    result.initial().push_back(_intersection_dfa_nfa(dfa, dfa.initial(), nfa, *i, result, result.null_state));
}

template <class DFA, class NFA1, class NFA2, class State1, class State2, class State3>
State3
_intersection_dfa_nfa(DFA &dfa, State1 q1, NFA1 &nfa1, State2 q2, NFA2 &result, State3)
{
  State3 q1_q2, but;
  but = q1_q2 = result.null_state;
  if (dfa.final(q1) && nfa1.final(q2))
	{
		q1_q2 = result.new_state();
		exists(result,q1,q2,q1_q2);
		result.final(q1_q2) = true;
	}
  
  DFA::Edges edg1 = dfa.delta2(q1);
  if (!edg1.empty() && !fa2.delta2(q2).empty())
	{
		DFA::Edges::const_iterator      trans_q1;
		DFA::Alphabet                   letter;
		DFA::State                      q1_aim;
		NFA1::State_set                 q2_aim;
		NFA1::State_set::const_iterator q2_i;
		
		// for each outgoing transitions of state q1
		for (trans_q1 = edg1.begin(); trans_q1 != edg1.end(); ++trans_q1)
		{
			letter = (*trans_q1).first;
			q1_aim = dfa.delta1(q1, letter);
			q2_aim = nfa1.delta1(q2, letter);
			
			// does state q2 have a transition with the same letter as state q1 ?
			if (q2_aim != nfa1.null_state)
			{
				for (q2_i = q2_aim.begin(); q2_i != q2_aim.end(); ++q2_i)
					/* if the state (q1_aim, *q2_i) exists or exists by a recursive call then create the edge */
					if (((but = exists(result, q1_aim, *q2_i, result.null_state)) != result.null_state)
						|| ((but = _intersection(fa1, q1_aim, fa2, *q2_i, result, but)) != result.null_state))
					{
						if (q1_q2 == result.null_state) 
						{
							q1_q2 = result.new_state();
							exists(result, q1, q2, q1_q2);  
						}
						result.set_trans(q1_q2, letter, but);
					}
			}
		}
	}
  return (q1_q2);
}


//
// Algorithm    : intersection
// Description  : computes intersection of two dfa
// Input        : 3 dfa
// Output       : result is placed in the third argument
// Precondition : none
// Uses         : exists, _intersection
//

template <class DFA1,class DFA2,class DFA3> 
void 
intersection(DFA1 &fa1, DFA2 &fa2, DFA3 &result)
{
  DFA3::State i = _intersection(fa1, fa1.initial(), fa2, fa2.initial(), result,i);
  if (i != result.null_state) result.initial(i);
  exists(result, fa1.null_state, fa2.null_state, result.null_state, true); // clean mapping table
}


template < class DFA1, class DFA2,class DFA3, class State1, class State2, class State3>
State3 
_intersection(DFA1 &fa1, State1 q1, DFA2 &fa2, State2 q2, DFA3 &result, State3)
{
  State3 q1_q2, but;
  but = q1_q2 = result.null_state;
  if (fa1.final(q1) && fa2.final(q2))
	{
		q1_q2 = result.new_state();
		exists(result, q1, q2, q1_q2);
		result.final(q1_q2) = true;
	}
  
  DFA1::Edges edg1 = fa1.delta2(q1);
  if (!edg1.empty() && !fa2.delta2(q2).empty())
	{
		DFA1::Edges::const_iterator trans_q1;
		DFA1::Alphabet letter;
		DFA1::State q1_aim;
		DFA2::State q2_aim;
		
		// for each outgoing transitions of state q1
		for (trans_q1 = edg1.begin(); trans_q1 != edg1.end(); ++trans_q1)
		{
			letter = (*trans_q1).first;
			q1_aim = fa1.delta1(q1, letter);
			q2_aim = fa2.delta1(q2, letter);
			
			// does state q2 have a transition with the same letter as state q1 ?
			if (q2_aim != fa2.null_state)
			{
				/* if the state (q1_aim, q2_aim) exists or exists by a recursive call then create the edge */
				if (((but = exists(result, q1_aim, q2_aim, result.null_state)) != result.null_state)
					|| ((but = _intersection(fa1, q1_aim, fa2, q2_aim, result, but)) != result.null_state))
				{
					if (q1_q2 == result.null_state) 
					{
						q1_q2 = result.new_state();
						exists(result, q1, q2, q1_q2);  
					}
					result.set_trans(q1_q2, letter, but);
				}
			}
		}
	}
  return (q1_q2);
}


//
// Algorithm    : union
// Description  : computes the union of two dfas
// Input        : three dfas
// Output       : a third dfa which is the union the first two
// Precondition : alphabets must be comparable
//



template <class DFA1, class DFA2, class DFA3, class State1, class State2, class State3>
State3 
_union(DFA1 &fa1, State1 q1, DFA2 &fa2, State2 q2, DFA3 &result, State3 dummy)
{
	
  State3 q1_q2 = result.null_state;
  State3 but   = result.null_state;
	
  q1_q2 = result.new_state();
  exists(result,q1,q2,q1_q2);   // add q1_q2
  if (q1 == fa1.null_state) 
	{ // (X, q2) 
		if (fa2.final(q2))
			result.final(q1_q2) = true;
		DFA2::Edges edg2 = fa2.delta2(q2);
		DFA2::Edges::const_iterator edg2_end = edg2.end();
		DFA2::Edges::const_iterator trans_q2;
		for (trans_q2 = edg2.begin() ; trans_q2 != edg2_end ; ++trans_q2)
		{
			if (((but=exists(result,fa1.null_state, (*trans_q2).second ,result.null_state))!= result.null_state)
				||  ((but=_union(fa1,fa1.null_state,fa2,(*trans_q2).second , result, dummy))			
				!= result.null_state))
				result.set_trans(q1_q2, (*trans_q2).first,but); 
		}
	}
  else
    if (q2 == fa2.null_state) 
		{ // (q1, X) 
			if (fa1.final(q1))
				result.final(q1_q2) = true;
			DFA1::Edges edg1 = fa1.delta2(q1);
			DFA1::Edges::const_iterator edg1_end = edg1.end();
			DFA1::Edges::const_iterator trans_q1;
			for (trans_q1 = edg1.begin() ; trans_q1 != edg1_end ;++trans_q1 )
			{
				if (((but=exists(result, (*trans_q1).second ,fa2.null_state, result.null_state))!= result.null_state)
					||  ((but=_union(fa1,(*trans_q1).second,fa2,fa2.null_state , result, dummy))			
					!= result.null_state))
					result.set_trans(q1_q2, (*trans_q1).first,but); 
			}
		}
    else 
		{ // (q1, q2)
			if ( fa1.final(q1) || fa2.final(q2) ) 
				result.final(q1_q2) = true;
			
			DFA1::Edges edg1 = fa1.delta2(q1);
			DFA2::Edges edg2 = fa2.delta2(q2);
			DFA1::Edges::const_iterator trans_q1, edg1_end = edg1.end();
			DFA2::Edges::const_iterator trans_q2, edg2_end = edg2.end();
			DFA1::Alphabet letter1, letter2;
			
			for (trans_q1 = edg1.begin(),trans_q2 = edg2.begin(); trans_q1 != edg1_end && trans_q2 != edg2_end; )
			{
				// si l1 == l2 
				letter1 = (*trans_q1).first;
				letter2 = (*trans_q2).first;
				if ( letter1 == letter2)
				{ 
					if  (((but=exists(result,(*trans_q1).second,(*trans_q2).second,result.null_state) )
						!= result.null_state)
						||  (( but=_union(fa1,(*trans_q1).second, fa2,(*trans_q2).second , result, dummy))
						!= result.null_state))
						result.set_trans(q1_q2, letter1, but);
					++trans_q1;
					++trans_q2;
				}
				else		
					if (letter1 < letter2)
					{
						if  (((but=exists(result,(*trans_q1).second, fa2.null_state ,result.null_state) )
							!= result.null_state)
							||  (( but=_union(fa1,(*trans_q1).second, fa2, fa2.null_state , result, dummy))
							!= result.null_state)) 
							result.set_trans(q1_q2, letter1, but);
						++trans_q1;
					}
					else		
					{
						if  (((but=exists(result, fa1.null_state ,(*trans_q2).second,  result.null_state) )
							!= result.null_state)
							||  (( but=_union(fa1, fa1.null_state , fa2, (*trans_q2).second , result, dummy))
							!= result.null_state)) 
							result.set_trans(q1_q2, letter2, but);
						++trans_q2;
					}
			}
			
			if (trans_q1 != edg1_end) {
				for ( ; trans_q1 != edg1_end ;++trans_q1 )
				{
					if (((but=exists(result, (*trans_q1).second ,fa2.null_state, result.null_state))!= result.null_state)
						||  ((but=_union(fa1,(*trans_q1).second,fa2,fa2.null_state , result, dummy))			
						!= result.null_state))
						result.set_trans(q1_q2, (*trans_q1).first,but); 
				}
			}
			else
				for (; trans_q2 != edg2_end; ++trans_q2)
				{
					if (((but=exists(result,fa1.null_state, (*trans_q2).second ,result.null_state))!= result.null_state)
						||  ((but=_union(fa1,fa1.null_state,fa2,(*trans_q2).second , result, dummy))		     
						!= result.null_state))
						result.set_trans(q1_q2, (*trans_q2).first,but); 
				}
		}
		
		return (q1_q2);
}

template < class DFA1, class DFA2, class DFA3 > 
void 
astl_union(DFA1 &fa1, DFA2 &fa2, DFA3 &result)
{
  DFA3::State i = _union(fa1, fa1.initial(), fa2, fa2.initial(), result,i);
	if (i != result.null_state) result.initial(i);
  exists(result, fa1.null_state, fa2.null_state, result.null_state, true);  // clean mapping table
}

//
// Algorithm    : difference
// Description  : computes the difference dfa of two dfas
// Input        : three dfas
// Output       : a third dfa which is the result of dfa1 \ dfa2
// Precondition : alphabets must be comparable
//

template < class DFA1, class DFA2, class DFA3 > 
void difference(DFA1 &fa1, DFA2 &fa2, DFA3 &result)
{
	DFA3::State i = _difference(fa1, fa1.initial(), fa2, fa2.initial(), result,i);
	if (i != result.null_state) result.initial(i);
  exists(result, fa1.null_state, fa2.null_state, result.null_state, true);  // clean mapping table
}

template < class DFA1, class DFA2, class DFA3>
DFA3::State _difference (DFA1 &fa1,  DFA1::State q1, DFA2 &fa2, DFA2::State q2, DFA3 &result, DFA3::State)
{
	DFA3::State q1_q2, but;
  but = q1_q2 = result.null_state;
  if (fa1.final(q1))
		if (q2 == fa2.null_state || !fa2.final(q2))
	{
		q1_q2 = result.new_state();
		exists(result, q1, q2, q1_q2);
		result.final(q1_q2) = true;
	}
  
  DFA1::Edges edg1 = fa1.delta2(q1);
  if (!edg1.empty())
	{
		DFA1::Edges::const_iterator trans_q1;
		DFA1::Alphabet letter;
		DFA1::State q1_aim;
		DFA2::State q2_aim;
		
		// for each outgoing transitions of state q1
		for (trans_q1 = edg1.begin(); trans_q1 != edg1.end(); ++trans_q1)
		{
			letter = (*trans_q1).first;
			q1_aim = fa1.delta1(q1, letter);
			if (q2 != fa2.null_state) 
				q2_aim = fa2.delta1(q2, letter);
			else
				q2_aim = fa2.null_state;
			
			/* if the state (q1_aim, q2_aim) exists or exists by a recursive call then create the edge */
			if (((but = exists(result, q1_aim, q2_aim, result.null_state)) != result.null_state)
					|| ((but = _difference(fa1, q1_aim, fa2, q2_aim, result, but)) != result.null_state))
			{
				if (q1_q2 == result.null_state) 
				{
					q1_q2 = result.new_state();
					exists(result, q1, q2, q1_q2);  
				}
				result.set_trans(q1_q2, letter, but);
			}
		}
	}
  return (q1_q2);
}
	

//
// Algorithm    : sym_difference
// Description  : computes the symetrical difference dfa of two dfas (XOR)
// Input        : three dfas
// Output       : a third dfa which is the result of (dfa1 | dfa2) \ (dfa1 & dfa2)
// Precondition : alphabets must be comparable
//

template < class DFA1, class DFA2, class DFA3 > 
void sym_difference(DFA1 &fa1, DFA2 &fa2, DFA3 &result)
{
	DFA3::State i = _sym_difference(fa1, fa1.initial(), fa2, fa2.initial(), result,i);
	if (i != result.null_state) result.initial(i);
  exists(result, fa1.null_state, fa2.null_state, result.null_state, true);  // clean mapping table
}

template < class DFA1, class DFA2, class DFA3>
DFA3::State _sym_difference (DFA1 &fa1,  DFA1::State q1, DFA2 &fa2, DFA2::State q2, DFA3 &result, DFA3::State dummy)
{
	DFA3::State q1_q2 = result.null_state;
	DFA3::State but   = result.null_state;
	
  q1_q2 = result.new_state();
  exists(result, q1, q2, q1_q2);   // add q1_q2
  if (q1 == fa1.null_state) 
	{ // (X, q2) 
		result.final(q1_q2) = fa2.final(q2);
		DFA2::Edges edg2 = fa2.delta2(q2);
		DFA2::Edges::const_iterator edg2_end = edg2.end();
		DFA2::Edges::const_iterator trans_q2;
		for (trans_q2 = edg2.begin() ; trans_q2 != edg2_end ; ++trans_q2)
		{
			if (((but=exists(result,fa1.null_state, (*trans_q2).second ,result.null_state))!= result.null_state)
				||  ((but=_sym_difference(fa1,fa1.null_state,fa2,(*trans_q2).second , result, dummy))			
				!= result.null_state))
				result.set_trans(q1_q2, (*trans_q2).first,but); 
		}
	}
  else
    if (q2 == fa2.null_state) 
		{ // (q1, X) 
			result.final(q1_q2) = fa1.final(q1);
			DFA1::Edges edg1 = fa1.delta2(q1);
			DFA1::Edges::const_iterator edg1_end = edg1.end();
			DFA1::Edges::const_iterator trans_q1;
			for (trans_q1 = edg1.begin() ; trans_q1 != edg1_end ;++trans_q1 )
			{
				if (((but=exists(result, (*trans_q1).second ,fa2.null_state, result.null_state))!= result.null_state)
					||  ((but=_sym_difference(fa1,(*trans_q1).second,fa2,fa2.null_state , result, dummy))			
					!= result.null_state))
					result.set_trans(q1_q2, (*trans_q1).first,but); 
			}
		}
    else 
		{ // (q1, q2)
			if ( (fa1.final(q1) && !fa2.final(q2)) || (!fa1.final(q1) && fa2.final(q2)) ) 
				result.final(q1_q2) = true;
			
			DFA1::Edges edg1 = fa1.delta2(q1);
			DFA2::Edges edg2 = fa2.delta2(q2);
			DFA1::Edges::const_iterator trans_q1, edg1_end = edg1.end();
			DFA2::Edges::const_iterator trans_q2, edg2_end = edg2.end();
			DFA1::Alphabet letter1, letter2;
			
			for (trans_q1 = edg1.begin(),trans_q2 = edg2.begin(); trans_q1 != edg1_end && trans_q2 != edg2_end; )
			{
				// si l1 == l2 
				letter1 = (*trans_q1).first;
				letter2 = (*trans_q2).first;
				if ( letter1 == letter2)
				{ 
					if  (((but=exists(result,(*trans_q1).second,(*trans_q2).second,result.null_state) )
						!= result.null_state))
						||  (( but=_sym_difference(fa1,(*trans_q1).second, fa2,(*trans_q2).second , result, dummy))
						!= result.null_state))
						result.set_trans(q1_q2, letter1, but);
					++trans_q1;
					++trans_q2;
				}
				else		
					if (letter1 < letter2)
					{
						if  (((but=exists(result,(*trans_q1).second, fa2.null_state ,result.null_state) )
							!= result.null_state)
							||  (( but=_sym_difference(fa1,(*trans_q1).second, fa2, fa2.null_state , result, dummy))
							!= result.null_state)) 
							result.set_trans(q1_q2, letter1, but);
						++trans_q1;
					}
					else		
					{
						if  (((but=exists(result, fa1.null_state ,(*trans_q2).second,  result.null_state) )
							!= result.null_state)
							||  (( but=_sym_difference(fa1, fa1.null_state , fa2, (*trans_q2).second , result, dummy))
							!= result.null_state)) 
							result.set_trans(q1_q2, letter2, but);
						++trans_q2;
					}
			}
			
			if (trans_q1 != edg1_end) {
				for ( ; trans_q1 != edg1_end ;++trans_q1 )
				{
					if (((but=exists(result, (*trans_q1).second ,fa2.null_state, result.null_state))!= result.null_state)
						||  ((but=_sym_difference(fa1,(*trans_q1).second,fa2,fa2.null_state , result, dummy))			
						!= result.null_state))
						result.set_trans(q1_q2, (*trans_q1).first,but); 
				}
			}
			else
				for (; trans_q2 != edg2_end; ++trans_q2)
				{
					if (((but=exists(result,fa1.null_state, (*trans_q2).second ,result.null_state))!= result.null_state)
						||  ((but=_sym_difference(fa1,fa1.null_state,fa2,(*trans_q2).second , result, dummy))		     
						!= result.null_state))
						result.set_trans(q1_q2, (*trans_q2).first,but); 
				}
		}
		
		return (q1_q2);
}