00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef VCSN_ALGORITHMS_EVAL_HXX
00018 # define VCSN_ALGORITHMS_EVAL_HXX
00019
00020 # include <vaucanson/algorithms/eval.hh>
00021 # include <vaucanson/automata/concept/automata_base.hh>
00022 # include <vaucanson/misc/selectors.hh>
00023 # include <vaucanson/misc/usual_macros.hh>
00024 # include <algorithm>
00025 # include <vector>
00026
00027 namespace vcsn {
00028
00029
00030
00031
00032
00033
00034 template <typename auto_t, typename input_t, typename Selt>
00035 struct eval_functor
00036 {
00037 AUTOMATON_TYPES(auto_t);
00038
00039 typedef std::vector<semiring_elt_t> weights;
00040
00041 const auto_t& a;
00042 int max_hstate;
00043
00044 weights v1, v2;
00045
00046 typename weights::const_iterator w;
00047 typename input_t::const_iterator l;
00048
00049 template <typename A>
00050 eval_functor(const AutomataBase<A>&, const auto_t& aut)
00051 : a(aut), max_hstate(a.states().back() + 1),
00052 v1(max_hstate, a.series().semiring().wzero_), v2(max_hstate)
00053 {}
00054
00055 void operator() (htransition_t t)
00056 {
00057 v2[a.dst_of(t)] += *w *
00058 a.series_of(t).get(monoid_elt_t(a.structure().series().monoid(), *l));
00059 }
00060
00061 void execute(const input_t& word, Selt& result)
00062 {
00063 const monoid_elt_t empty = algebra::identity_as<monoid_elt_value_t>::of(a.series().monoid());
00064
00065
00066 for_all_const_initial_states(i, a)
00067 v1[*i] = a.get_initial(*i).get(empty);
00068
00069 const semiring_elt_t zero = a.series().semiring().wzero_;
00070
00071
00072 l = word.begin();
00073 for (typename input_t::const_iterator w_end = word.end();
00074 l != w_end; ++l)
00075 {
00076 std::fill(v2.begin(), v2.end(), zero);
00077 int i = 0;
00078 w = v1.begin();
00079 for (typename weights::const_iterator v1_end = v1.end();
00080 w != v1_end; ++w)
00081 {
00082 if (*w != zero)
00083 a.letter_deltaf(*this, i, *l, delta_kind::transitions());
00084 ++i;
00085 }
00086 std::swap(v1, v2);
00087 }
00088
00089
00090 result = zero;
00091 int i = 0;
00092 for_all_const_ (weights, w, v1)
00093 {
00094 if (*w != zero)
00095 result += *w * a.get_final(i).get(empty);
00096 ++i;
00097 }
00098 }
00099 };
00100
00101
00102
00103
00104
00105 template<typename A, typename AI, typename W>
00106 typename Element<A, AI>::semiring_elt_t
00107 eval(const Element<A, AI>& a, const W& word)
00108 {
00109 TIMER_SCOPED("eval");
00110 typedef Element<A, AI> automaton_t;
00111 AUTOMATON_TYPES(automaton_t);
00112 semiring_elt_t ret(a.structure().series().semiring());
00113
00114
00115 if (!is_empty(a))
00116 {
00117 eval_functor<automaton_t, W, semiring_elt_t> evalf(a.structure(), a);
00118 evalf.execute(word, ret);
00119 }
00120
00121 return ret;
00122 }
00123
00124 }
00125
00126 #endif // ! VCSN_ALGORITHMS_EVAL_HXX