#include <functional>
#include <map>
#include <queue>

// Object function assignment T = U;
template <class T, class U>
struct assignment : binary_function<T, U, T> 
{
	T& operator () (T &t, const U &u) {
		return (t = u);
	}
	assignment() 
	{ }
};

//
// Algorithm    : copy_breadth 
//  copyright   : DR VL 1999
// Version      : ASTL 1.1 
// Description  : copy a dfa into a second dfa by breadth-first iteration
//               DR  on peut choisr depth-first search plutot ?? 
// Input        : two DFAs, an assignment function object DFA2::Tag = DFA1::Tag (default behavior
//                is DFA2::Tag& operator=(DFA2::Tag&, const DFA1::Tag&) 
// Output       : result is placed in the second argument
// Precondition : DFA1::Alphabet must be castable to DFA2::Alphabet
// Uses         : struct assignment<>
//

template <class DFA1, class DFA2> //, class TagAssignment>  = assignment<DFA2::Tag, DFA1::Tag> >
void astl_copy_breadth(DFA2 &dfa2,const  DFA1 &dfa1) //, TagAssignment ta = assignment<DFA2::Tag, DFA1::Tag>())
{
	if (dfa1.initial() != dfa1.null_state)
	{
		map<DFA1::State, DFA2::State> mapping;
		queue<DFA1::State> path;
		DFA1::State from1, to1;
		DFA2::State from2, to2;
		DFA1::Edges::const_iterator trans_it, trans_end;
		
		path.push(from1 = dfa1.initial());
		from2 = dfa2.new_state();   // creating initial state
		dfa2.initial(from2);
		mapping[from1] = from2;
		assignment<DFA2::Tag, DFA1::Tag> ta;

		do
		{
			from1 = path.front();
			path.pop();
			from2 = mapping[from1];
			ta(dfa2.tag(from2), dfa1.tag(from1));  // setting tags with assignment function object
			dfa2.final(from2) = dfa1.final(from1);

			// Iterating on from1 outgoing transitions:
			DFA1::Edges edges = dfa1.delta2(from1);
			for(trans_it = edges.begin(), trans_end = edges.end(); trans_it != trans_end; ++trans_it) 
			{
				to1 = (*trans_it).second;

				if (mapping.find(to1) != mapping.end())    // already visited ?
					to2 = mapping[to1];
				else
				{
					to2 = dfa2.new_state();// forgoten dfa2 no ? DR
					mapping[to1] = to2;
					path.push(to1);
				}

				dfa2.set_trans(from2, (*trans_it).first, to2);
			}
		} while(!path.empty());
	}
}

template <class DFA1, class DFA2, class TagAssignment>
void astl_copy(DFA2 &dfa2,const DFA1 &dfa1,  TagAssignment ta)
{
	if (dfa1.initial() != dfa1.null_state)
	{
		map<DFA1::State, DFA2::State> mapping;
		queue<DFA1::State> path;
		DFA1::State from1, to1;
		DFA2::State from2, to2;
		DFA1::Edges::const_iterator trans_it, trans_end;
		path.push(dfa1.initial());
		from2 = dfa2.new_state();   // creating initial state
		dfa2.initial(from2);
		mapping[from1] = from2;

		do
		{
			from1 = path.front();
			path.pop();
			from2 = mapping[from1];
			ta(dfa2.tag(from2), dfa1.tag(from1));  // setting tags with assignment function object
			dfa2.final(from2) = dfa.final(from1);

			// Iterating on from1 outgoing transitions:
			DFA1::Edges edges = dfa1.delta2(from1);
			for(trans_it = edges.begin(), trans_end = edges.end(); trans_it != trans_end; ++trans_it) 
			{
				to1 = (*trans_it).second;

				if (mapping.find(to1) != mapping.end())    // already visited ?
					to2 = mapping[to1];
				else
				{
					to2 = dfa2.new_state(); // forgoten dfa2 no ? DR
					mapping[to1] = to2;
					path.push(to1);
				}

				dfa2.set_trans(from2, (*trans_it).first, to2);
			}
		} while(!path.empty());
	}
}

//
// Algorithm    : copy_depth 
//  copyright   : Dominique Revuz 2/04/1999
// Version      : ASTL 1.1 
// Description  : copy a dfa into a second dfa by breadth-first iteration
//               DR  on peut choisr depth-first search plutot ?? 
// Input        : two DFAs, an assignment function object DFA2::Tag = DFA1::Tag (default behavior
//                is DFA2::Tag& operator=(DFA2::Tag&, const DFA1::Tag&) 
// Output       : result is placed in the second argument
// Precondition : DFA1::Alphabet must be castable to DFA2::Alphabet
// Uses         : struct assignment<>
//
// 
// depth-first recursive construction 
template <class DFA1, class State1,class DFA2,class State2, class Container,class TagAssignement >
State2 _depth_copy(const DFA1 &dfa1,State1 from1, DFA2 &dfa2,Container & mapping, State2 dummy, TagAssignement ta)
{
	int n=0;
	// let's copy the state informations 
	DFA2::State from2 = dfa2.new_state() ;
	mapping[from1] =from2 ; // store the copied fact
	dfa2.final(from2) = dfa1.final(from1); 
	ta(dfa2.tag(from2), dfa1.tag(from1)); // setting tags with assignment function object
	n++;
	DFA1::State to1;
	DFA2::State to2;
	DFA1::Edges edges = dfa1.delta2(from1);
	DFA1::Edges::const_iterator trans_it, trans_end;
	for(trans_it = edges.begin(), trans_end = edges.end(); trans_it != trans_end; ++trans_it) 
			{
				to1 = (*trans_it).second;

				if (mapping.find(to1) != mapping.end())    // already visited ?
					to2 = mapping[to1]; 
				else
				{  
					to2 = _depth_copy(dfa1,to1,dfa2,mapping,dummy,ta);
					mapping[to1] = to2;
				}
				// ok create trans 
				dfa2.set_trans(from2, (*trans_it).first, to2);
			}

	return from2;
}

// exported function 
template <class DFA1, class DFA2, class TagAssignment>
void depth_copy(DFA2 &to,const  DFA1 &from, TagAssignment ta )
{
	if (from.initial() != from.null_state)
	{
		map<DFA1::State, DFA2::State> mapping;
		DFA2::State x;
		to.initial(_depth_copy(from,from.initial(),to,mapping,x,ta));
	}
}