/*
 * 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
 *
 */


#ifndef ASTL_CURSOR_COPY
#define ASTL_CURSOR_COPY

#include <iostream>
#include <map>
#include <tools/safe.h> // template<> class safe;

#ifdef WIN32
using namespace std;
#endif

// TODO: copie des tags

// Algorithm:   ccopy (cursor copy)
// Description: copy depth-first range [first, last) into a DFA during ascending
//              stage of the depth-first traversal triming uneeded paths
// Input:       two depth-first cursor and a DFA
// Output:      initial copied state
// Remark:      processing of the initial state is an external operation left up
//              to the user. The algorithm simply returns the upper copied
//              transition source state.
// Uses:        DFA::final(), DFA::set_trans(), DFA::new_state(), DFA::null_state

template <class DFirstCursor, class DFA>
typename DFA::State ccopy(DFA &out, DFirstCursor first, DFirstCursor last = DFirstCursor())
{
  typedef map<typename DFirstCursor::State, safe<typename DFA::State> > mapper;
  mapper mapping;
  typename DFirstCursor::State i = first.src();

  while (first != last) {     // while not end of range
    while(first.forward());   // get down as much as possible

    // copy aim state if final:
    safe<typename DFA::State> p;
    if (first.aim_final()) {
      safe<typename DFA::State> &dest = mapping[first.aim()];
      if (dest == out.null_state) {
	dest = out.new_state();
	out.final(dest) = true;
      }
    }

    do { // while moving backward (pop) copy current
      // transition (q, first.letter(), p) 
      // copy source state if needed:
      mapper::const_iterator dest = mapping.find(first.aim());
      if (dest != mapping.end()) p = (*dest).second;
      
      if (p != out.null_state || first.src_final()) {
	safe<typename DFA::State> &q = mapping[first.src()];
	if (q == out.null_state) {
	  q = out.new_state();
	  out.final(q) = first.src_final();
	}
				// copy transition:
	if (p != out.null_state) 
	  out.set_trans(q, first.letter(), p);
	
				// shift (q, first.letter(), p) => (q', first.letter()', q)
	p = q;
      }
    } while (! first.forward());
  }
  return mapping[i];
}

// Algorithm:   clone
// Description: copy depth-first range [first, last) into a DFA in descending
//              stage of the depth-first traversal making thus an exact copy of
//              the compound
// Input:       two depth-first cursor and a DFA
// Output:      initial copied state
// Remark:      processing of the initial state is an external operation left up
//              to the user. The algorithm simply returns the first copied
//              transition source state.
// Uses:        DFA::final(), DFA::set_trans(), DFA::new_state(), DFA::null_state
  
template <class DFirstCursor, class DFA>
typename DFA::State clone(DFA &out, DFirstCursor first, DFirstCursor last = DFirstCursor())
{
  if (first == last) return out.null_state;

#ifdef WIN32
  // Because VC++6.0 has a non standard behavior and refuses 'typename' keyword here:
  typedef DFirstCursor::State cursor_state;
  typedef DFA::State          dfa_state;
#else
  typedef typename DFirstCursor::State cursor_state;
  typedef typename DFA::State          dfa_state;
#endif

  map<cursor_state, safe<dfa_state> > mapping;
  cursor_state i = first.src();

  while (first != last) {     // while not end of range

    // copy source state if needed:
    safe<dfa_state> &source = mapping[first.src()];
    if (source == out.null_state) {
      source = out.new_state();
      out.final(source) = first.src_final();
    }
    dfa_state q = source;

    do {                      // while moving forward
      // copy current transition (q, first.letter(), p)
      // copy aim state if needed:
      safe<dfa_state> &p = mapping[first.aim()];
      if (p == out.null_state) {
	p = out.new_state();
	out.final(p) = first.aim_final();
      }

      // copy transition:
      out.set_trans(q, first.letter(), p);
      // shift (q, first.letter(), p) => (p, first.letter()', p')
      q = p;
    } while (first.forward());

    while (!first.forward());   // pop
  }
  return mapping[i];
}

#endif