00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef VCSN_ALGORITHMS_STANDARD_OF_HXX
00018 # define VCSN_ALGORITHMS_STANDARD_OF_HXX
00019
00020 # include <vaucanson/algorithms/standard_of.hh>
00021
00022 # include <vaucanson/algebra/implementation/series/krat_exp_pattern.hh>
00023 # include <vaucanson/algorithms/standard.hh>
00024
00025 # include <vaucanson/misc/usual_macros.hh>
00026
00027 namespace vcsn {
00028
00029 namespace algebra {
00030
00031
00032
00033
00034 template <class Exp_,
00035 class Auto_,
00036 class Dispatch_>
00037 class Standard_OfVisitor :
00038 public algebra::KRatExpMatcher<
00039 Standard_OfVisitor<Exp_, Auto_, Dispatch_>,
00040 Exp_,
00041 Auto_*,
00042 Dispatch_
00043 >
00044 {
00045 public :
00046 typedef Auto_* automaton_ptr_t;
00047 typedef Auto_ automaton_t;
00048 typedef typename automaton_t::set_t automata_set_t;
00049
00050 typedef typename automaton_t::series_set_t series_set_t;
00051 typedef typename automaton_t::monoid_t monoid_t;
00052 typedef typename automaton_t::semiring_t semiring_t;
00053
00054 typedef typename automaton_t::series_set_elt_t series_set_elt_t;
00055 typedef typename automaton_t::monoid_elt_t monoid_elt_t;
00056 typedef typename automaton_t::semiring_elt_t semiring_elt_t;
00057
00058 typedef typename automaton_t::hstate_t hstate_t;
00059 typedef typename automaton_t::htransition_t htransition_t;
00060
00061 typedef typename Exp_::monoid_elt_value_t monoid_elt_value_t;
00062 typedef typename Exp_::semiring_elt_value_t semiring_elt_value_t;
00063
00064 typedef Standard_OfVisitor<Exp_, Auto_, Dispatch_> this_class;
00065 typedef algebra::KRatExpMatcher<this_class, Exp_, Auto_*, Dispatch_>
00066 parent_class;
00067 typedef typename parent_class::return_type return_type;
00068
00069 public :
00070
00071 Standard_OfVisitor(const series_set_t& series) :
00072 automata_set_(series)
00073 {}
00074
00075 INHERIT_CONSTRUCTORS(this_class, Exp_, Auto_*, Dispatch_);
00076
00077 MATCH__(Product, lhs, rhs)
00078 {
00079 automaton_ptr_t tmp_ = match(rhs);
00080 automaton_ptr_t auto_ = match(lhs);
00081 concat_of_standard_here(*auto_, *tmp_);
00082 delete (tmp_);
00083 return auto_;
00084 }
00085 END
00086
00087 MATCH__(Sum, lhs, rhs)
00088 {
00089 automaton_ptr_t tmp_ = match(rhs);
00090 automaton_ptr_t auto_ = match(lhs);
00091 union_of_standard_here(*auto_, *tmp_);
00092 delete (tmp_);
00093 return auto_;
00094 }
00095 END
00096
00097 MATCH_(Star, node)
00098 {
00099 automaton_ptr_t stared = match(node);
00100 star_of_standard_here(*stared);
00101 return stared;
00102 }
00103 END
00104
00105 MATCH__(LeftWeight, w, node)
00106 {
00107 const semiring_t& semiring = automata_set_.series().semiring();
00108 const semiring_elt_t weight (semiring, w);
00109 automaton_ptr_t auto_ = match(node);
00110
00111 for (typename automaton_t::initial_iterator i = auto_->initial().begin();
00112 i != auto_->initial().end();
00113 ++i)
00114 {
00115 std::list<htransition_t> e;
00116 for (typename automaton_t::delta_iterator j(auto_->value(), *i);
00117 ! j.done();
00118 j.next())
00119 e.push_back(*j);
00120 for (typename std::list<htransition_t>::const_iterator j = e.begin();
00121 j != e.end();
00122 ++j)
00123 {
00124
00125
00126
00127
00128
00129
00130
00131 typedef typename automaton_t::label_t label_t;
00132 typedef Element<series_set_t, label_t> label_elt_t;
00133
00134 label_elt_t label (automata_set_.series(), auto_->label_of(*j));
00135 label = weight * label;
00136
00137 hstate_t dst = auto_->dst_of(*j);
00138 auto_->del_transition(*j);
00139
00140 if (label != zero_as<label_t>::of(automata_set_.series()))
00141 auto_->add_transition(*i, dst, label.value());
00142 }
00143 auto_->set_final(*i, weight * auto_->get_final(*i));
00144 }
00145 return auto_;
00146 }
00147 END
00148
00149 MATCH__(RightWeight, node, w)
00150 {
00151 const semiring_t& semiring = automata_set_.series().semiring();
00152 const semiring_elt_t weight (semiring, w);
00153 automaton_ptr_t auto_ = match(node);
00154
00155 for (typename automaton_t::final_iterator f, next = auto_->final().begin();
00156 next != auto_->final().end();)
00157 {
00158
00159
00160
00161
00162 f = next;
00163 next++;
00164 auto_->set_final(*f, auto_->get_final(*f) * weight);
00165 }
00166 return auto_;
00167 }
00168 END
00169
00170 MATCH_(Constant, m)
00171 {
00172 automaton_ptr_t auto_ = new automaton_t(automata_set_);
00173 hstate_t new_i = auto_->add_state();
00174 hstate_t last = new_i;
00175 hstate_t new_f = new_i;
00176 for (typename monoid_elt_value_t::const_iterator i = m.begin();
00177 i != m.end(); ++i)
00178 {
00179 new_f = auto_->add_state();
00180 auto_->add_letter_transition(last, new_f, *i);
00181 last = new_f;
00182 }
00183 auto_->set_initial(new_i);
00184 auto_->set_final(new_f);
00185 return auto_;
00186 }
00187 END
00188
00189 MATCH(Zero)
00190 {
00191 automaton_ptr_t auto_ = new automaton_t(automata_set_);
00192 hstate_t s = auto_->add_state();
00193 auto_->set_initial(s);
00194 return auto_;
00195 }
00196 END
00197
00198 MATCH(One)
00199 {
00200 automaton_ptr_t auto_ = new automaton_t(automata_set_);
00201 hstate_t new_i = auto_->add_state();
00202 auto_->set_initial(new_i);
00203 auto_->set_final(new_i);
00204 return auto_;
00205 }
00206 END
00207
00208 private:
00209 automata_set_t automata_set_;
00210 };
00211
00212 }
00213
00214 template <typename A,
00215 typename Output,
00216 typename Exp>
00217 void
00218 do_standard_of(const AutomataBase<A>&,
00219 Output& output,
00220 const Exp& kexp)
00221 {
00222 algebra::Standard_OfVisitor<Exp, Output, algebra::DispatchFunction<Exp> >
00223 m(output.structure().series());
00224 Output* res = m.match(kexp);
00225 output = *res;
00226 delete res;
00227 }
00228
00229 template<typename A,
00230 typename T,
00231 typename Exp>
00232 void
00233 standard_of(Element<A, T>& out,
00234 const Exp& kexp)
00235 {
00236 do_standard_of(out.structure(), out, kexp);
00237 }
00238
00239 }
00240
00241 #endif // ! VCSN_ALGORITHMS_STANDARD_OF_HXX