#ifndef ASTL_ASTL_TREE
#define ASTL_ASTL_TREE

#include <iterator>  // iterator_traits<>

//
// Algorithm    : tree_build
// Version      : ASTL 1.1
// Description  : add to a tree-like automaton a list of words 
//                a word is a container<Alphabet>
// Input        : a dfa, a range on a container<container<Alphabet>>
// Output       : result is placed in the first argument and is a tree 
// Precondition : DFA must be a tree or empty
//

template <class DFA, class InputIterator>
void
tree_build(DFA &dfa, InputIterator start, InputIterator finish)
{
  typename DFA::State i = dfa.initial();
  if (i == dfa.null_state)   // no initial state ?
  {
    i = dfa.new_state();
    dfa.initial(i);
  }
  iterator_traits<InputIterator>::value_type *hint = NULL ;
  _tree(dfa, start, finish, hint);
}

template <class DFA, class InputIterator, class Container>
void 
_tree(DFA &dfa, InputIterator start, InputIterator finish, Container*)
{
  typename DFA::State q, t, i;
  typename Container::const_iterator first, last;
  typename DFA::Alphabet a;
  for (i = dfa.initial(); !(start == finish); ++start)  // for each word 
  {
    t = i;    // current state = initial state
    first = (*start).begin();
    last  = (*start).end();
    for (; first != last; ++first)   // for each letter 
    {
      a = *first;
      q = dfa.delta1(t, a);
      if (q == dfa.null_state)   // transition with 'a' does not exist ?
      { 
	q = dfa.new_state();
	dfa.set_trans(t, a, q);
      } 
      t = q; 
    } 
    dfa.final(t) = true;
  } 
} 


//
// Algorithm    : tree_build
// Version      : ASTL 1.1
// Description  : add a single word in a tree-like automaton
// Input        : a dfa, 2 iterators on a container<Alphabet>, 
//                the newly created final state tag
// Output       : result is placed in the first argument 
//                returns the newly created final state
// Precondition : dfa must be a tree or empty
//

#ifdef WIN32
template <class DFA, class InputIterator>
DFA::State 
tree_build(DFA &dfa, InputIterator first, InputIterator last, 
     const typename DFA::Tag &t)
#else
template <class DFA, class InputIterator>
typename DFA::State 
tree_build(DFA &dfa, InputIterator first, InputIterator last, 
     const typename DFA::Tag &t)
#endif // WIN32

{
  typename DFA::State q, i = dfa.initial();
  typename DFA::Alphabet a;

  if (i == dfa.null_state)           // no initial state ?
  {
    i = dfa.new_state();
    dfa.initial(i);
  }

  for (; !( first == last); ++first)    // for each letter in w
  {
    a = *first;
    q = dfa.delta1(i, a);
    if (q == dfa.null_state)   // transition by *first does not exist ?
    {
      q = dfa.new_state();
      dfa.set_trans(i, a, q);
    }
    i = q;
  }

  dfa.final(i) = true;
  dfa.tag(i) = t;
  return (i);
}

#endif  // ASTL_DFALGO_TREE