kinds.hxx

00001 // kinds.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2001, 2002, 2003, 2004 The Vaucanson Group.
00006 //
00007 // This program is free software; you can redistribute it and/or
00008 // modify it under the terms of the GNU General Public License
00009 // as published by the Free Software Foundation; either version 2
00010 // of the License, or (at your option) any later version.
00011 //
00012 // The complete GNU General Public Licence Notice can be found as the
00013 // `COPYING' file in the root directory.
00014 //
00015 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
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   | Automaton labels are pairs (semiring_elt value, monoidelt value) |
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

Generated on Fri Jul 28 12:18:35 2006 for Vaucanson by  doxygen 1.4.6