invert.hxx

00001 // invert.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_INVERT_HXX_
00019 # define VCSN_ALGORITHMS_INVERT_HXX_
00020 
00021 # include <map>
00022 
00023 # include <vaucanson/automata/concept/automata_base.hh>
00024 # include <vaucanson/automata/concept/transducer.hh>
00025 # include <vaucanson/algebra/concept/freemonoid_product.hh>
00026 # include <vaucanson/algebra/implementation/series/series.hh>
00027 
00028 # include <vaucanson/misc/usual_macros.hh>
00029 
00030 # include <vaucanson/algorithms/standard_of.hh>
00031 # include <vaucanson/algorithms/realtime.hh>
00032 
00033 namespace vcsn
00034 {
00035 
00036   /*------------------------------------.
00037   | Specialization for RW transducers.  |
00038   `------------------------------------*/
00039 
00040   template<typename S, typename T>
00041   Element<S, T>&
00042   do_invert_rw(Element<S, T>& t,
00043                Element<S, T>& u)
00044   {
00045     typedef Element<S, T> Trans_t;
00046     typedef typename output_projection_helper<S, T>::ret Auto_t;
00047     AUTOMATON_TYPES(Trans_t);
00048 
00049     normalize_here(t);
00050 
00051     std::map<hstate_t, hstate_t> map_t_u;
00052     for_all_states (p, t)
00053       map_t_u[*p] = u.add_state ();
00054 
00055     initial_iterator i_it;
00056     for (initial_iterator next = t.initial().begin(), next_end = t.initial().end();
00057          next != next_end;)
00058     {
00059       //We need to store the next iterator before using the current one
00060       //to avoid an invalid iterator after having called set_final.
00061       //Indeed, set_final can delete the iterator if its second parameter
00062       //is the zero of the serie.
00063       i_it = next;
00064       next++;
00065       u.set_initial (map_t_u[*i_it]);
00066     }
00067 
00068     final_iterator f_it;
00069     for (final_iterator next = t.final().begin(), next_end = t.final().end();
00070          next != next_end;)
00071     {
00072       //We need to store the next iterator before using the current one
00073       //to avoid an invalid iterator after having called set_final.
00074       //Indeed, set_final can delete the iterator if its second parameter
00075       //is the zero of the serie.
00076       f_it = next;
00077       next++;
00078       u.set_final (map_t_u[*f_it]);
00079     }
00080 
00081     for_all_transitions (e, t)
00082     {
00083       semiring_elt_t exp = t.output_of(*e);
00084 
00085       typename Auto_t::set_t auto_structure
00086         (typename Auto_t::set_t::series_set_t
00087          (t.structure().series().semiring()));
00088       Auto_t auto_tmp(auto_structure);
00089 
00090       // As the output of each transition is not supposed to be
00091       // realtime we build the standard automaton corresponding to
00092       // this expression
00093       standard_of(auto_tmp, exp.value());
00094 
00095       std::map<hstate_t, hstate_t> map_auto_u;
00096 
00097       for_all_states (p, auto_tmp)
00098         if (auto_tmp.is_initial (*p))
00099           map_auto_u[*p] = map_t_u[t.src_of(*e)];
00100         else
00101           map_auto_u[*p] = u.add_state();
00102 
00103       typename semiring_elt_t::semiring_elt_t
00104         o_sm_zero (u.structure().series().semiring().semiring());
00105       monoid_elt_t monoid_identity = u.series().monoid().vcsn_empty;
00106 
00107       monoid_elt_t a (u.structure().series().monoid());
00108       semiring_elt_t sm (u.structure().series().semiring());
00109       series_set_elt_t s (u.structure().series());
00110 
00111       for (typename Auto_t::transition_iterator f =
00112              auto_tmp.transitions().begin();
00113            f != auto_tmp.transitions().end();
00114            ++f)
00115       {
00116         a = auto_tmp.word_of (*f);
00117 
00118         s.assoc (a, algebra::identity_as<semiring_elt_value_t>
00119                  ::of(u.series().semiring()));
00120 
00121         u.add_series_transition (map_auto_u[auto_tmp.src_of(*f)],
00122                                  map_auto_u[auto_tmp.dst_of(*f)],
00123                                  s);
00124       }
00125 
00126       a = t.input_of (*e);
00127       for (typename Auto_t::final_iterator q = auto_tmp.final().begin();
00128            q != auto_tmp.final().end();
00129            ++q)
00130       {
00131         typedef typename semiring_elt_t::semiring_elt_t output_sm_t;
00132         typedef typename output_sm_t::value_t output_sm_value_t;
00133 
00134         sm.assoc (a, algebra::identity_as<output_sm_value_t>
00135                   ::of(u.series().semiring().semiring()));
00136         s.assoc(monoid_identity, sm);
00137         u.add_series_transition(map_auto_u[*q],
00138                                 map_t_u[t.dst_of(*e)],
00139                                 s);
00140       }
00141     }
00142 
00143     realtime_here(u);
00144 
00145     return u;
00146   }
00147 
00148 
00149   /*----------------------------------.
00150   | Specialization for  transducers.  |
00151   `----------------------------------*/
00152 
00153 
00154   // Invert `label' and store the result in `res'.
00155   template<typename S, typename T,
00156            typename SS, typename TT>
00157   static void invert_label(const Element<S, T>& label,
00158                            Element<SS, TT>& res)
00159   {
00160     typedef Element<S, T> series_set_elt_t;
00161     typedef typename series_set_elt_t::monoid_elt_t::value_t
00162       res_monoid_elt_value_t;
00163 
00164     // Invert each pair
00165     for_all_const_(series_set_elt_t::support_t, w, label.supp())
00166       // (u,v) -> (v,u)
00167       res.assoc(res_monoid_elt_value_t((*w).second, (*w).first),
00168                 label.get(*w));
00169   }
00170 
00171 
00172   template<typename S, typename T,
00173            typename SS, typename TT>
00174   Element<SS, TT>&
00175   do_invert_tdc(const Element<S, T>& t,
00176                 Element<SS, TT>& u)
00177   {
00178     typedef Element<S, T> Trans_t;
00179     typedef Element<SS, TT> res_t;
00180     AUTOMATON_TYPES(Trans_t);
00181     AUTOMATON_TYPES_(res_t, res_);
00182 
00183     std::map<hstate_t, hstate_t> map_t_u;
00184     for_all_states (p, t)
00185       map_t_u[*p] = u.add_state ();
00186 
00187     // Proceed initial and final states
00188     for_all_initial_states (p, t)
00189       {
00190         res_series_set_elt_t s (u.structure().series());
00191         invert_label(t.get_initial(*p), s);
00192         u.set_initial (map_t_u[*p], s);
00193       }
00194 
00195     for_all_final_states (p, t)
00196       {
00197         res_series_set_elt_t s (u.structure().series());
00198         invert_label(t.get_final(*p), s);
00199         u.set_final (map_t_u[*p], s);
00200       }
00201 
00202 
00203     for_all_transitions (e, t)
00204       {
00205         res_series_set_elt_t s (u.structure().series());
00206         res_monoid_elt_t a (u.structure().series().monoid());
00207 
00208         // Get the label of the current transition
00209         series_set_elt_t label(t.structure().series());
00210         label = t.series_of(*e);
00211 
00212         invert_label(label, s);
00213 
00214         u.add_series_transition(map_t_u[t.src_of(*e)],
00215                                 map_t_u[t.dst_of(*e)],
00216                                 s);
00217       }
00218 
00219     return u;
00220   }
00221 
00222 
00223 
00224   /*---------------------------.
00225   | Dispatch for  tranducers.  |
00226   `---------------------------*/
00227 
00228   template<typename S, typename T,
00229            typename M1, typename M2>
00230   Element<S, T>&
00231   do_invert_fmp(const algebra::FreeMonoidProduct<M1, M2>&,
00232                 const Element<S, T>& t)
00233   {
00234     // Declaration of the inverted transducer
00235     typedef Element<S, T> trans_t;
00236     AUTOMATON_TYPES(trans_t);
00237 
00238     typedef algebra::FreeMonoidProduct<
00239       typename trans_t::series_set_t::monoid_t::second_monoid_t,
00240       typename trans_t::series_set_t::monoid_t::first_monoid_t>
00241       res_monoid_t;
00242 
00243     typedef algebra::Series<typename trans_t::series_set_t::semiring_t,
00244       res_monoid_t>
00245       res_series_set_t;
00246 
00247     res_monoid_t monoid(t.structure().series().monoid().second_monoid(),
00248                         t.structure().series().monoid().first_monoid());
00249 
00250 
00251     res_series_set_t series(t.structure().series().semiring(), monoid);
00252 
00253     Automata<series_set_t> trans_set(series);
00254 
00255     typedef Element< Automata<series_set_t>, T> res_trans_t;
00256     res_trans_t* res = new res_trans_t(trans_set);
00257 
00258     return do_invert_tdc(t, *res);
00259   }
00260 
00261 
00262   template<typename S, typename T,
00263            typename SS, typename TT,
00264            typename M1, typename M2>
00265   Element<SS, TT>&
00266   do_invert_fmp(const algebra::FreeMonoidProduct<M1, M2>&,
00267                 const Element<S, T>& t,
00268                 Element<SS, TT>& res)
00269   {
00270     return do_invert_tdc(t, res);
00271   }
00272 
00273 
00274   template<typename S, typename T>
00275   Element<S, T>&
00276   do_invert(const AutomataBase<S>&,
00277             const Element<S, T>& t)
00278   {
00279     return do_invert_fmp(t.structure().series().monoid(), t);
00280   }
00281 
00282   template<typename S, typename T>
00283   Element<S, T>&
00284   do_invert(const AutomataBase<S>&,
00285             const Element<S, T>& t,
00286             Element<S, T>& res)
00287   {
00288     return do_invert_fmp(t.structure().series().monoid(), t, res);
00289 
00290   }
00291 
00292   /*-----------------------------.
00293   | Dispatch for RW tranducers.  |
00294   `-----------------------------*/
00295 
00296   template<typename S, typename T>
00297   Element<S, T>&
00298   do_invert(const TransducerBase<S>&,
00299             const Element<S, T>& t)
00300   {
00301     // Building the structure of the inverted transducer
00302     typedef Element<S, T> Trans_t;
00303     AUTOMATON_TYPES(Trans_t);
00304 
00305     monoid_t o_mon_structure
00306       (t.structure().series().monoid());
00307     typename semiring_t::semiring_t sm_sm_structure
00308       (t.structure().series().semiring().semiring());
00309     typename semiring_t::monoid_t i_mon_structure
00310       (t.structure().series().semiring().monoid());
00311 
00312     semiring_t sm_structure (sm_sm_structure, o_mon_structure);
00313     series_set_t ss_structure(sm_structure, i_mon_structure);
00314 
00315     automata_set_t auto_structure(ss_structure);
00316 
00317     Trans_t* res = new Trans_t(auto_structure);
00318     Trans_t src(t);
00319 
00320     do_invert_rw(src, *res);
00321     return *res;
00322   }
00323 
00324 
00325   template<typename S, typename T>
00326   Element<S, T>&
00327   do_invert(const TransducerBase<S>&,
00328             const Element<S, T>& t,
00329             Element<S, T>& res)
00330   {
00331     Element<S, T> src(t);
00332     return do_invert_rw(src, res);
00333   }
00334 
00335 
00336 
00337 
00338   /*----------.
00339   | Facades.  |
00340   `----------*/
00341 
00342   template<typename S, typename T>
00343   Element<S, T>&
00344   invert(const Element<S, T>& t)
00345   {
00346     TIMER_SCOPED("invert");
00347     return do_invert(t.structure(), t);
00348   }
00349 
00350   template<typename S, typename T>
00351   void
00352   invert(const Element<S, T>& t,
00353          Element<S, T>& res)
00354   {
00355     TIMER_SCOPED("invert");
00356     do_invert(t.structure(), t, res);
00357   }
00358 }
00359 
00360 #endif // !VCSN_ALGORITHMS_INVERT_HXX_

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