/*
 * ASTL - the Automaton Standard Template Library.
 * C++ generic components for Finite State Machine handling.
 * Copyright (C) 2000 Vincent Le Maout (vlemaout@lexiquest.fr).
 * 
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 */


#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<typename DFA1::State, typename DFA2::State> mapping;
      queue<typename DFA1::State> path;
      typename DFA1::State from1, to1;
      typename DFA2::State from2, to2;
      typename 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<typename DFA2::Tag, typename 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:
	  typename 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<typename DFA1::State, typename DFA2::State> mapping;
      queue<typename DFA1::State> path;
      typename DFA1::State from1, to1;
      typename DFA2::State from2, to2;
      typename 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) = dfa1.final(from1);

	  // Iterating on from1 outgoing transitions:
	  typename 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 
  typename 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++;
  typename DFA1::State to1;
  typename DFA2::State to2;
  typename DFA1::Edges edges = dfa1.delta2(from1);
  typename 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<typename DFA1::State, typename DFA2::State> mapping;
      typename DFA2::State x;
      to.initial(_depth_copy(from,from.initial(),to,mapping,x,ta));
    }
}