astl_tree.h

一个类似STL的自动机的源代码库

/*
 * ASTL - the Automaton Standard Template Library.
 * C++ generic components for Finite State Automata handling.
 * Copyright (C) 2000-2003 Vincent Le Maout ([e-mail]).
 * 
 * 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_ASTL_TREE_H
#define ASTL_ASTL_TREE_H

#include <iterator>  // iterator_traits<>
#include <astl.h>

ASTL_BEGIN_NAMESPACE

// Algorithm    : tree_build
// 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_type i = dfa.initial();
  if (i == dfa.null_state)   // no initial state ?
  {
    i = dfa.new_state();
    dfa.initial(i);
  }
  typename std::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_type q, t, i;
  typename Container::const_iterator first, last;
  typename DFA::char_type 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
// Description  : add a single word in a tree-like automaton
// Input        : a dfa, 2 iterators on a container<char_type>, 
//                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 _MSC_VER
template <class DFA, class InputIterator>
DFA::state_type 
tree_build(DFA &dfa, InputIterator first, InputIterator last, 
     const typename DFA::tag_type &t)
#else
template <class DFA, class InputIterator>
typename DFA::state_type 
tree_build(DFA &dfa, InputIterator first, InputIterator last, 
     const typename DFA::tag_type &t)
#endif // _MSC_VER

{
  typename DFA::state_type q, i = dfa.initial();
  typename DFA::char_type 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);
}

// new school signature:
template <typename DFA, typename InputIterator>
inline
typename DFA::state_type
add_word(DFA &a, InputIterator first, InputIterator last,
	 const typename DFA::tag_type &t = typename DFA::tag_type())
{
  return tree_build(a, first, last, t);
}

template <typename DFA2, typename InputIterator2>
inline
void add_words(DFA2 &a, InputIterator2 start, InputIterator2 finish)
{
  tree_build(a, start, finish);
}

ASTL_END_NAMESPACE

#endif  // ASTL_ASTL_TREE_H