image.hxx

00001 // projections_fmp.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2006 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 
00018 #ifndef         VCSN_ALGORITHMS_IMAGE_HXX
00019 # define        VCSN_ALGORITHMS_IMAGE_HXX
00020 
00021 # include <vaucanson/algorithms/image.hh>
00022 # include <vaucanson/algorithms/projection.hh>
00023 
00024 namespace vcsn
00025 {
00026   template <typename auto_t, typename trans_t>
00027   static void
00028   do_fmp_image(const trans_t& fmp_trans, auto_t& res)
00029   {
00030     TIMER_SCOPED("image");
00031     AUTOMATON_TYPES_(trans_t, trans_);
00032     AUTOMATON_TYPES(auto_t);
00033 
00034     typedef typename trans_series_set_elt_t::support_t  trans_support_t;
00035     std::map<hstate_t, hstate_t>        stmap;
00036 
00037     const series_set_t&         series = res.structure().series();
00038     const monoid_t&             monoid = res.structure().series().monoid();
00039     const trans_monoid_t&       trans_monoid =
00040       fmp_trans.structure().series().monoid();
00041 
00042     set_states(fmp_trans, res, stmap);
00043 
00044     for_all_transitions(fmp_e, fmp_trans)
00045     {
00046       const trans_series_set_elt_t      trans_series_elt =
00047         fmp_trans.series_of(*fmp_e);
00048       trans_support_t                   trans_supp = trans_series_elt.supp();
00049       const trans_monoid_elt_t  trans_monoid_elt
00050         (trans_monoid, *(trans_supp.begin()));
00051 
00052       const monoid_elt_value_t  word(trans_monoid_elt.value().second);
00053 
00054       series_set_elt_t          series_elt(series);
00055 
00056       series_elt.assoc(monoid_elt_t(monoid, word),
00057                        trans_series_elt.get(trans_monoid_elt));
00058 
00059       res.add_series_transition(stmap[fmp_trans.src_of(*fmp_e)],
00060                                 stmap[fmp_trans.dst_of(*fmp_e)], series_elt);
00061     }
00062   }
00063 
00064 
00065 
00066   template<typename Trans_t, typename Auto_t>
00067   static void
00068   do_rw_image(const Trans_t& t,
00069               Auto_t& ret)
00070   {
00071     TIMER_SCOPED("image (transducer to automaton)");
00072     AUTOMATON_TYPES(Trans_t);
00073 
00074     std::map<hstate_t, hstate_t> m;
00075 
00076     for_all_states(p, t)
00077       m[*p] = ret.add_state();
00078 
00079     monoid_elt_t empty =
00080       algebra::identity_as<monoid_elt_value_t>::of(t.series().monoid());
00081     typename Trans_t::series_set_elt_t id_series(t.structure().series());
00082     id_series = vcsn::algebra::
00083       identity_as<typename Trans_t::series_set_elt_value_t>::
00084       of(t.structure().series());
00085 
00086     for_all_initial_states(p, t)
00087     {
00088       if (t.get_initial(*p) != id_series)
00089       {
00090         hstate_t tmp = ret.add_state();
00091         ret.set_initial(tmp);
00092         ret.add_series_transition(tmp, m[*p], t.get_initial(*p).get(empty));
00093       }
00094       else
00095         ret.set_initial(m[*p], t.get_initial(*p).get(empty));
00096     }
00097 
00098     for_all_final_states(p, t)
00099     {
00100       if (t.get_final(*p) != id_series)
00101       {
00102         hstate_t tmp = ret.add_state();
00103         ret.set_final(tmp);
00104         ret.add_series_transition(m[*p], tmp, t.get_final(*p).get(empty));
00105       }
00106       else
00107         ret.set_final(m[*p], t.get_final(*p).get(empty));
00108     }
00109 
00110     for_all_transitions(e, t)
00111     {
00112       ret.add_series_transition(m[t.src_of(*e)],
00113                                 m[t.dst_of(*e)],
00114                                 t.output_of(*e));
00115     }
00116   }
00117 
00118 
00119   template <typename S, typename T, typename Auto_t>
00120   static
00121   typename output_projection_helper<S, T>::ret
00122   do_rw_image(const Element<S, T>& t,
00123               Auto_t& ret,
00124               std::map<hstate_t, hstate_t>& m_)
00125   {
00126     TIMER_SCOPED("image (transducer to automaton)");
00127     typedef Element<S, T>  Trans_t;
00128     AUTOMATON_TYPES(Trans_t);
00129 
00130     monoid_elt_t empty = t.series().monoid().vcsn_empty;
00131     std::map<hstate_t, hstate_t> m;
00132 
00133     for_all_states(p, t)
00134     {
00135       m[*p] = ret.add_state();
00136       m_[m[*p]] = *p;
00137     }
00138 
00139     for_all_initial_states(p, t)
00140       ret.set_initial(m[*p], t.get_initial(*p).get(empty));
00141 
00142     for_all_final_states(p, t)
00143       ret.set_final(m[*p], t.get_final(*p).get(empty));
00144 
00145     for_all_transitions(e, t)
00146       ret.add_series_transition(m[t.src_of(*e)], m[t.dst_of(*e)],
00147                                 t.output_of(*e));
00148 
00149     return ret;
00150   }
00151 
00152 
00153 
00154   /*-------------.
00155   | DISPATCHERS. |
00156   `-------------*/
00157 
00158   // Dispatchers for RW transducers.
00159   template <typename S, typename S2,
00160             typename T, typename T2,
00161             typename ST, typename M1>
00162   static void
00163   image_dispatch(const Element<S,T>& src,
00164                  const TransducerBase<ST>&,
00165                  const algebra::FreeMonoidBase<M1>&,
00166                  Element<S2, T2>& dst)
00167   {
00168     do_rw_image(src, dst);
00169   }
00170 
00171   template <typename S, typename S2,
00172             typename T, typename T2,
00173             typename ST, typename M1>
00174   static void
00175   image_dispatch(const Element<S,T>& src,
00176                  const TransducerBase<ST>&,
00177                  const algebra::FreeMonoidBase<M1>&,
00178                  Element<S2, T2>& dst,
00179                  std::map<hstate_t, hstate_t>& m)
00180   {
00181     do_rw_image(src, dst, m);
00182   }
00183 
00184 # define MAKE_RET_AUTOMATON()                                                   \
00185     typedef Element<S, T>  Trans_t;                                             \
00186   AUTOMATON_TYPES(Trans_t);                                                     \
00187   typedef typename output_projection_helper<S, T>::ret   Auto_t;                \
00188   typedef typename Auto_t::set_t                         Auto_set_t;            \
00189   typedef typename Auto_set_t::series_set_t              Auto_series_set_t;     \
00190   Auto_set_t     auto_set                                                       \
00191       (Auto_series_set_t(src.structure().series().semiring()));                 \
00192     Auto_t       dst(auto_set)
00193 
00194   // Dispatch and build returned object for RW transducers. A map between states
00195   // of the resulting automaton and the tranducer is filled.
00196   template <typename S, typename T, typename ST>
00197   static
00198   typename output_projection_helper<S, T>::ret
00199   image_dispatch2(const Element<S,T>& src,
00200                   const TransducerBase<ST>&,
00201                   std::map<hstate_t, hstate_t>& m)
00202   {
00203     MAKE_RET_AUTOMATON();
00204 
00205     image_dispatch(src, src.structure(),
00206                    src.structure().series().monoid(), dst, m);
00207     return dst;
00208   }
00209 
00210   // Dispatch and build returned object for RW transducers
00211   template <typename S, typename T, typename ST>
00212   static
00213   typename output_projection_helper<S, T>::ret
00214   image_dispatch2(const Element<S,T>& src,
00215                   const TransducerBase<ST>&)
00216   {
00217     MAKE_RET_AUTOMATON();
00218 
00219     image_dispatch(src, src.structure(),
00220                    src.structure().series().monoid(), dst);
00221     return dst;
00222   }
00223 
00224 # undef MAKE_RET_AUTOMATON
00225 
00226   // Dispatcher for transducers
00227   template <typename S, typename S2,
00228             typename T, typename T2,
00229             typename ST, typename M1>
00230   static void
00231   image_dispatch(const Element<S,T>& src,
00232                  const AutomataBase<ST>&,
00233                  const algebra::FreeMonoidProductBase<M1>&,
00234                  Element<S2, T2>& dst)
00235   {
00236     do_fmp_image(src, dst);
00237   }
00238 
00239 
00240 
00241   /*---------------.
00242   | IMAGE FACADES. |
00243   `---------------*/
00244 
00245   template <typename S, typename S2, typename T, typename T2>
00246   void
00247   image(const Element<S,T>& src, Element<S2, T2>& dst)
00248   {
00249     image_dispatch(src, src.structure(),
00250                    src.structure().series().monoid(),
00251                    dst);
00252   }
00253 
00254   template <typename S, typename T>
00255   typename output_projection_helper<S, T>::ret
00256   image(const Element<S, T>& src)
00257   {
00258     return image_dispatch2(src, src.structure());
00259   }
00260 
00261   template <typename S, typename T>
00262   typename output_projection_helper<S, T>::ret
00263   image(const Element<S, T>& src,
00264         std::map<hstate_t, hstate_t>& m)
00265   {
00266     return image_dispatch2(src, src.structure(), m);
00267   }
00268 
00269 } // End of namespace vcsn.
00270 
00271 #endif      /* !VCSN_ALGORITHMS_IMAGE_HXX */

Generated on Sun Jul 29 19:35:19 2007 for Vaucanson by  doxygen 1.5.2