00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef VCSN_AUTOMATA_CONCEPT_KINDS_HXX
00018 # define VCSN_AUTOMATA_CONCEPT_KINDS_HXX
00019
00020 # include <iterator>
00021 # include <algorithm>
00022
00023 # include <vaucanson/misc/contract.hh>
00024 # include <vaucanson/tools/container_ops.hh>
00025 # include <vaucanson/automata/concept/handlers.hh>
00026
00027 namespace vcsn {
00028
00029 template<typename Series,
00030 typename MonoidElt,
00031 typename SemiringElt,
00032 typename L>
00033 ls_delta_letter_query<Series, MonoidElt, SemiringElt, L>::
00034 ls_delta_letter_query(const Series& s, const L& l)
00035 : s_(s),
00036 l_(op_convert(SELECT(typename MonoidElt::set_t),
00037 SELECT(typename MonoidElt::value_t),
00038 l))
00039 {}
00040
00041 template<typename Series,
00042 typename MonoidElt,
00043 typename SemiringElt,
00044 typename L>
00045 template<typename Label>
00046 bool ls_delta_letter_query<Series, MonoidElt, SemiringElt, L>::
00047 operator()(const Label& label) const
00048 {
00049 return (op_series_get(s_.get(), label, l_)
00050 != zero_value(SELECT(typename SemiringElt::set_t),
00051 SELECT(typename SemiringElt::value_t)));
00052 }
00053
00054
00055
00056 template<typename Self, typename Series, typename SeriesT, typename LabelT>
00057 Element<Series, SeriesT>
00058 AutoKind<labels_are_series, Self, Series, SeriesT, LabelT>::
00059 series_of(htransition_t e) const
00060 {
00061 return series_set_elt_t(auto_self().series(),
00062 auto_self().label_of(e));
00063 }
00064
00065 template<typename Self, typename Series, typename SeriesT, typename LabelT>
00066 const SeriesT&
00067 AutoKind<labels_are_series, Self, Series, SeriesT, LabelT>::
00068 series_value_of(htransition_t e) const
00069 {
00070 return auto_self().label_of(e);
00071 }
00072
00073 template<typename Self, typename Series, typename SeriesT, typename LabelT>
00074 bool
00075 AutoKind<labels_are_series, Self, Series, SeriesT, LabelT>::
00076 is_spontaneous(htransition_t e) const
00077 {
00078 const series_set_elt_t& s = auto_self().label_of(e);
00079
00080 return s == algebra::identity_as<SeriesT>::of(s.set());
00081 }
00082
00083 template<typename Self, typename Series, typename SeriesT, typename LabelT>
00084 template<typename L>
00085 L
00086 AutoKind<labels_are_series, Self, Series, SeriesT, LabelT>::
00087 letter_of(SELECTOR(L), htransition_t e) const
00088 {
00089 return *op_begin(auto_self().series().monoid(),
00090 auto_self().label_of(e).begin()->first);
00091 }
00092
00093 template<typename Self, typename Series, typename SeriesT, typename LabelT>
00094 typename Element<Series, SeriesT>::monoid_elt_t
00095 AutoKind<labels_are_series, Self, Series, SeriesT, LabelT>::
00096 word_of(htransition_t e) const
00097 {
00098 const LabelT& l = auto_self().label_of(e);
00099
00100 return monoid_elt_t(auto_self().series().monoid(),
00101 l.begin()->first);
00102 }
00103
00104 template<typename Self, typename Series, typename SeriesT, typename LabelT>
00105 const typename Element<Series, SeriesT>::monoid_elt_t::value_t&
00106 AutoKind<labels_are_series, Self, Series, SeriesT, LabelT>::
00107 word_value_of(htransition_t e) const
00108 {
00109 return auto_self().label_of(e).begin()->first;
00110 }
00111
00112 template<typename Self, typename Series, typename SeriesT, typename LabelT>
00113 template<typename S>
00114 htransition_t
00115 AutoKind<labels_are_series, Self, Series, SeriesT, LabelT>::
00116 add_series_transition(hstate_t from, hstate_t to,
00117 const S& e)
00118 {
00119 return auto_self().add_transition(from, to, e.value());
00120 }
00121
00122 template<typename Self, typename Series, typename SeriesT, typename LabelT>
00123 htransition_t
00124 AutoKind<labels_are_series, Self, Series, SeriesT, LabelT>::
00125 add_spontaneous(hstate_t from, hstate_t to)
00126 {
00127 return auto_self().add_transition(from, to,
00128 identity_value(SELECT(Series),
00129 SELECT(SeriesT)));
00130 }
00131
00132 template<typename Self, typename Series, typename SeriesT, typename LabelT>
00133 template<typename L>
00134 htransition_t
00135 AutoKind<labels_are_series, Self, Series, SeriesT, LabelT>::
00136 add_letter_transition(hstate_t from, hstate_t to,
00137 const L& l)
00138 {
00139 return auto_self().add_transition(from, to,
00140 series_set_elt_t(auto_self().series(),
00141 monoid_elt_t(auto_self().series().monoid(),
00142 l)
00143 ).value()
00144 );
00145 }
00146
00147 #define DELTA_IMPL(Name, Type, Kind_type) \
00148 template<typename Self, typename Series, typename SeriesT, typename LabelT> \
00149 template<typename OutputIterator, typename L> \
00150 void \
00151 AutoKind<labels_are_series, Self, Series, SeriesT, LabelT>:: \
00152 letter_ ## Name (OutputIterator res, hstate_t from, const L& l, Kind_type) const \
00153 { \
00154 return auto_self().value()-> Name ## _ ## Type \
00155 (res, from, \
00156 ls_delta_letter_query<Series, monoid_elt_t, semiring_elt_t, L> \
00157 (auto_self().series(), l)); \
00158 } \
00159 template<typename Self, typename Series, typename SeriesT, typename LabelT> \
00160 template<typename Container, typename L> \
00161 void \
00162 AutoKind<labels_are_series, Self, Series, SeriesT, LabelT>:: \
00163 letter_ ## Name ## c (Container &dst, hstate_t from, const L& l, Kind_type) const \
00164 { \
00165 std::insert_iterator<Container> i(dst, dst.begin()); \
00166 return auto_self().value()-> Name ## _ ## Type \
00167 (i, from, \
00168 ls_delta_letter_query<Series, monoid_elt_t, semiring_elt_t, L> \
00169 (auto_self().series(), l)); \
00170 }
00171
00172 DELTA_IMPL(delta, transitions, delta_kind::transitions);
00173 DELTA_IMPL(rdelta, transitions, delta_kind::transitions);
00174
00175 DELTA_IMPL(delta, states, delta_kind::states);
00176 DELTA_IMPL(rdelta, states, delta_kind::states);
00177 #undef DELTA_IMPL
00178
00179 template<typename Self, typename Series, typename SeriesT, typename LabelT>
00180 Self&
00181 AutoKind<labels_are_series, Self, Series, SeriesT, LabelT>::
00182 auto_self()
00183 { return static_cast<Self&>(*this); }
00184
00185 template<typename Self, typename Series, typename SeriesT, typename LabelT>
00186 const Self&
00187 AutoKind<labels_are_series, Self, Series, SeriesT, LabelT>::
00188 auto_self() const
00189 { return static_cast<const Self&>(*this); }
00190
00191
00192
00193
00194
00195
00196
00197
00198 template<typename Monoid, typename L>
00199 lc_delta_letter_query<Monoid, L>::
00200 lc_delta_letter_query(const Monoid& m, const L& l)
00201 : m_(m), l_(l)
00202 {}
00203
00204 template<typename Monoid, typename L>
00205 template<typename Label>
00206 bool
00207 lc_delta_letter_query<Monoid, L>::
00208 operator()(const Label& label) const
00209 {
00210 typedef typename Element
00211 <Monoid, typename Label::second_type>::const_iterator letter_iterator;
00212
00213 letter_iterator b = op_begin_const(m_.get(), label.second);
00214 letter_iterator e = op_end_const(m_.get(), label.second);
00215
00216 return std::find(b, e, l_) != e;
00217 }
00218
00219
00220
00221
00222
00223 template<typename Self, typename Series, typename SeriesT, typename LabelT>
00224 Element<Series, SeriesT>
00225 AutoKind<labels_are_couples, Self, Series, SeriesT, LabelT>::
00226 series_of(htransition_t e) const
00227 {
00228 const LabelT& label = auto_self().label_of(e);
00229 const Series& s = auto_self().series();
00230
00231 series_set_elt_t se(s, monoid_elt_t(s.monoid(), label.second));
00232 return se *= semiring_elt_t(s.semiring(), label.first);
00233 }
00234
00235 template<typename Self, typename Series, typename SeriesT, typename LabelT>
00236 const SeriesT
00237 AutoKind<labels_are_couples, Self, Series, SeriesT, LabelT>::
00238 series_value_of(htransition_t e) const
00239 {
00240 const LabelT& label = auto_self().label_of(e);
00241 const Series& s = auto_self().series();
00242
00243 series_set_elt_t se(s, monoid_elt_t(s.monoid(), label.second));
00244 return (se *= semiring_elt_t(s.semiring(), label.first)).value();
00245 }
00246
00247 template<typename Self, typename Series, typename SeriesT, typename LabelT>
00248 bool
00249 AutoKind<labels_are_couples, Self, Series, SeriesT, LabelT>::
00250 is_spontaneous(htransition_t e) const
00251 {
00252 const LabelT& label = auto_self().label_of(e);
00253
00254 return label.second == identity_value(SELECT(monoid_t), SELECT(typename monoid_elt_t::value_t));
00255 }
00256
00257 template<typename Self, typename Series, typename SeriesT, typename LabelT>
00258 template<typename L>
00259 L
00260 AutoKind<labels_are_couples, Self, Series, SeriesT, LabelT>::
00261 letter_of(SELECTOR(L), htransition_t e) const
00262 {
00263 return *op_begin(auto_self().series().monoid(),
00264 auto_self().label_of(e).second);
00265 }
00266
00267 template<typename Self, typename Series, typename SeriesT, typename LabelT>
00268 typename Element<Series, SeriesT>::monoid_elt_t
00269 AutoKind<labels_are_couples, Self, Series, SeriesT, LabelT>::
00270 word_of(htransition_t e) const
00271 {
00272 const LabelT& l = auto_self().label_of(e);
00273
00274 return monoid_elt_t(auto_self().series().monoid(),
00275 l.second);
00276 }
00277
00278 template<typename Self, typename Series, typename SeriesT, typename LabelT>
00279 const typename Element<Series, SeriesT>::monoid_elt_t::value_t&
00280 AutoKind<labels_are_couples, Self, Series, SeriesT, LabelT>::
00281 word_value_of(htransition_t e) const
00282 {
00283 return auto_self().label_of(e).second;
00284 }
00285
00286 template<typename Self, typename Series, typename SeriesT, typename LabelT>
00287 template<typename S>
00288 htransition_t
00289 AutoKind<labels_are_couples, Self, Series, SeriesT, LabelT>::
00290 add_series_transition(hstate_t from, hstate_t to,
00291 const S& e)
00292 {
00293 assertion(e.is_finite_app());
00294 htransition_t x;
00295
00296 typedef typename S::value_t supp_t;
00297 for (typename supp_t::const_iterator i = e.supp().begin();
00298 i != e.supp().end();
00299 ++i)
00300 x = auto_self().add_transition(from, to, std::make_pair(i->second, i->first));
00301
00302 return x;
00303 }
00304
00305 template<typename Self, typename Series, typename SeriesT, typename LabelT>
00306 htransition_t
00307 AutoKind<labels_are_couples, Self, Series, SeriesT, LabelT>::
00308 add_spontaneous(hstate_t from, hstate_t to)
00309 {
00310 return auto_self()
00311 .add_transition(from, to,
00312 std::make_pair(identity_value(SELECT(monoid_t),
00313 SELECT(typename monoid_elt_t::value_t)),
00314 identity_value(SELECT(semiring_t),
00315 SELECT(typename semiring_elt_t::value_t)))
00316 );
00317 }
00318
00319
00320 template<typename Self, typename Series, typename SeriesT, typename LabelT>
00321 template<typename L>
00322 htransition_t
00323 AutoKind<labels_are_couples, Self, Series, SeriesT, LabelT>::
00324 add_letter_transition(hstate_t from,
00325 hstate_t to,
00326 const L& l)
00327 {
00328 return auto_self().add_transition
00329 (from,
00330 to,
00331 std::make_pair(identity_value(SELECT(semiring_t),
00332 SELECT(typename semiring_elt_t::value_t)),
00333 monoid_elt_t(auto_self().series().monoid(), l).value()));
00334 }
00335
00336 #define DELTA_IMPL(Name, Type, Kind_type) \
00337 template<typename Self, typename Series, typename SeriesT, typename LabelT> \
00338 template<typename OutputIterator, typename L> \
00339 void \
00340 AutoKind<labels_are_couples, Self, Series, SeriesT, LabelT>:: \
00341 letter_ ## Name (OutputIterator res, hstate_t from, const L& l, Kind_type k) const \
00342 { \
00343 return auto_self().value()-> Name ## _ ## Type \
00344 (res, from, \
00345 lc_delta_letter_query<monoid_t, L>(auto_self().series().monoid(), \
00346 l)); \
00347 } \
00348 template<typename Self, typename Series, typename SeriesT, typename LabelT> \
00349 template<typename Container, typename L> \
00350 void \
00351 AutoKind<labels_are_couples, Self, Series, SeriesT, LabelT>:: \
00352 letter_ ## Name ##c(Container &dst, hstate_t from, const L& l, Kind_type k) const \
00353 { \
00354 std::insert_iterator<Container> i(dst, dst.begin()); \
00355 return auto_self().value()-> Name ## _ ## Type \
00356 (i, from, \
00357 lc_delta_letter_query<monoid_t, L>(auto_self().series().monoid(), \
00358 l)); \
00359 }
00360
00361 DELTA_IMPL(delta, transitions, delta_kind::transitions);
00362 DELTA_IMPL(rdelta, transitions, delta_kind::transitions);
00363
00364 DELTA_IMPL(delta, transitions, delta_kind::states);
00365 DELTA_IMPL(rdelta, transitions, delta_kind::states);
00366 #undef DELTA_IMPL
00367
00368
00369 template<typename Self, typename Series, typename SeriesT, typename LabelT>
00370 Self&
00371 AutoKind<labels_are_couples, Self, Series, SeriesT, LabelT>::
00372 auto_self() { return static_cast<Self&>(*this); }
00373
00374 template<typename Self, typename Series, typename SeriesT, typename LabelT>
00375 const Self&
00376 AutoKind<labels_are_couples, Self, Series, SeriesT, LabelT>::
00377 auto_self() const { return static_cast<const Self&>(*this); }
00378
00379 }
00380
00381
00382
00383 #endif // ! VCSN_AUTOMATA_CONCEPT_KINDS_HXX
