realtime_to_fmp.hxx

00001 // realtime_to_fmp.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2005 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_ALGORITHMS_REALTIME_TO_FMP_HXX
00018 # define VCSN_ALGORITHMS_REALTIME_TO_FMP_HXX
00019 
00020 # include <vaucanson/algebra/concept/freemonoid_product.hh>
00021 # include <vaucanson/automata/concept/transducer.hh>
00022 # include <vaucanson/automata/concept/automata.hh>
00023 # include <map>
00024 
00025 namespace vcsn
00026 {
00027   template<typename S, typename T,
00028            typename SS, typename TT,
00029            typename Self>
00030   void
00031   do_realtime_to_fmp(const vcsn::TransducerBase<S>&,
00032                      const vcsn::AutomataBase<SS>&,
00033                      const vcsn::algebra::FreeMonoidProductBase<Self>&,
00034                      const vcsn::Element<S, T>& trans,
00035                      vcsn::Element<SS, TT>& res)
00036   {
00037 
00038     //Map source states with result states
00039     std::map<vcsn::hstate_t, vcsn::hstate_t> m;
00040 
00041     //Input transducer type
00042     typedef vcsn::Element<S, T> Trans_t;
00043 
00044     //Output FMP Automaton type
00045     typedef vcsn::Element<SS, TT> FMP_t;
00046 
00047     typename FMP_t::monoid_t fmp(trans.structure().series().monoid(),
00048                                  trans.structure().series().monoid());
00049     typename FMP_t::semiring_t sg;
00050     typename FMP_t::series_set_t ss(sg, fmp);
00051 
00052     typedef vcsn::Element<typename FMP_t::monoid_t::first_monoid_t,
00053       typename FMP_t::monoid_elt_value_t::first_type>
00054       first_monoid_elt_t;
00055     typedef vcsn::Element<typename FMP_t::monoid_t::second_monoid_t,
00056       typename FMP_t::monoid_elt_value_t::second_type>
00057       second_monoid_elt_t;
00058     typedef vcsn::Element<typename Trans_t::series_set_t,
00059       typename Trans_t::series_set_elt_value_t>
00060       mult_elt_t;
00061 
00062 
00063     /*----------------------------.
00064     | Creating the FMP automaton. |
00065     `----------------------------*/
00066 
00067     // Adding states
00068     for (typename Trans_t::state_iterator St = trans.states().begin();
00069          St != trans.states().end();
00070          ++St)
00071       m[*St] = res.add_state();
00072 
00073     typename Trans_t::series_set_elt_t id_series(trans.structure().series());
00074     id_series = vcsn::algebra::
00075       identity_as<typename Trans_t::series_set_elt_value_t>::
00076       of(trans.structure().series());
00077 
00078 
00079     /*------------------------.
00080     | Setting initial states. |
00081     `------------------------*/
00082 
00083     for (typename Trans_t::initial_iterator St = trans.initial().begin();
00084          St != trans.initial().end();
00085          ++St)
00086     {
00087       typename FMP_t::series_set_elt_t s(ss);
00088       typename FMP_t::monoid_elt_t mon(res.structure().series().monoid());
00089       first_monoid_elt_t
00090         first(res.structure().series().monoid().first_monoid());
00091       second_monoid_elt_t
00092         second(res.structure().series().monoid().second_monoid());
00093       typename FMP_t::semiring_elt_t
00094         weight(res.structure().series().semiring());
00095 
00096       mult_elt_t mult = trans.get_initial(*St);
00097       if (mult != id_series)
00098       {
00099         hstate_t tmp = res.add_state();
00100         typename mult_elt_t::support_t mult_supp = mult.supp();
00101         for_all_const_(mult_elt_t::support_t, i, mult_supp)
00102         {
00103           first = *i;
00104 
00105           typename Trans_t::semiring_elt_t
00106             output(trans.structure().series().semiring(), mult.get(*i));
00107           typename Trans_t::semiring_elt_t::support_t
00108             output_supp = output.supp();
00109           for_all_const_(Trans_t::semiring_elt_t::support_t,
00110                          j,
00111                          output_supp)
00112           {
00113             second = *j;
00114             weight = output.get(*j);
00115             mon = typename FMP_t::monoid_elt_value_t(first.value(),
00116                                                      second.value());
00117             s.assoc(mon, weight);
00118           }
00119         }
00120         res.add_series_transition(tmp, m[*St], s);
00121         res.set_initial(tmp);
00122       }
00123       else
00124         res.set_initial(m[*St]);
00125     }
00126 
00127 
00128     /*----------------------.
00129     | Setting final states. |
00130     `----------------------*/
00131 
00132     for (typename Trans_t::final_iterator St = trans.final().begin();
00133          St != trans.final().end();
00134          ++St)
00135     {
00136       typename FMP_t::series_set_elt_t s(ss);
00137       typename FMP_t::monoid_elt_t mon(res.structure().series().monoid());
00138       first_monoid_elt_t
00139         first(res.structure().series().monoid().first_monoid());
00140       second_monoid_elt_t
00141         second(res.structure().series().monoid().second_monoid());
00142       typename FMP_t::semiring_elt_t
00143         weight(res.structure().series().semiring());
00144 
00145       mult_elt_t mult = trans.get_final(*St);
00146       if (mult != id_series)
00147       {
00148         hstate_t tmp = res.add_state();
00149 
00150         typename mult_elt_t::support_t mult_supp = mult.supp();
00151         for_all_const_(mult_elt_t::support_t, i, mult_supp)
00152         {
00153           first = *i;
00154 
00155           typename Trans_t::semiring_elt_t
00156             output(trans.structure().series().semiring(), mult.get(*i));
00157           typename Trans_t::semiring_elt_t::support_t
00158             output_supp = output.supp();
00159           for_all_const_(Trans_t::semiring_elt_t::support_t,
00160                          j,
00161                          output_supp)
00162           {
00163             second = *j;
00164             weight = output.get(*j);
00165             mon = typename FMP_t::monoid_elt_value_t(first.value(),
00166                                                      second.value());
00167             s.assoc(mon, weight);
00168           }
00169         }
00170         res.add_series_transition(m[*St], tmp, s);
00171         res.set_final(tmp);
00172       }
00173       else
00174         res.set_final(m[*St]);
00175     }
00176 
00177 
00178     /*-----------------------.
00179     | Creating transitions.  |
00180     `-----------------------*/
00181 
00182     for (typename Trans_t::transition_iterator Ed = trans.transitions().begin();
00183          Ed != trans.transitions().end();
00184          ++Ed)
00185     {
00186       typename FMP_t::series_set_elt_t s(ss);
00187 
00188       first_monoid_elt_t first(trans.structure().series().monoid());
00189       second_monoid_elt_t
00190         second(trans.structure().series().semiring().monoid());
00191       typename FMP_t::monoid_elt_t
00192         mon(res.structure().series().monoid());
00193 
00194       typename Trans_t::series_set_elt_t
00195         series_elt(trans.structure().series());
00196       series_elt = trans.series_of(*Ed);
00197 
00198       for (typename Trans_t::series_set_elt_t::support_t::const_iterator
00199              i = series_elt.supp().begin();
00200            i != series_elt.supp().end();
00201            ++i)
00202       {
00203         first = *i;
00204 
00205         typename Trans_t::semiring_elt_t
00206           mult(trans.structure().series().semiring());
00207         mult = series_elt.get(first);
00208 
00209         //FIXME
00210         //If we don't use a copy of the support we don't get ALL the
00211         //element of the series when card(mult) > 1.
00212         typename Trans_t::semiring_elt_t::support_t
00213           mult_supp = mult.supp();
00214         for (typename Trans_t::semiring_elt_t::support_t::const_iterator
00215                j = mult_supp.begin();
00216              j != mult_supp.end();
00217              ++j)
00218         {
00219           second = *j;
00220 
00221           mon = typename FMP_t::monoid_elt_value_t(first.value(),
00222                                                    second.value());
00223           s.assoc(mon, trans.output_of(*Ed).get(second));
00224         }
00225       }
00226       res.add_series_transition(m[trans.src_of(*Ed)],
00227                                 m[trans.dst_of(*Ed)],
00228                                 s);
00229     }
00230   }
00231 
00232   template<typename S, typename T,
00233            typename SS, typename TT>
00234   vcsn::Element<SS, TT>&
00235   realtime_to_fmp(const vcsn::Element<S, T>& trans,
00236                   vcsn::Element<SS, TT>& res)
00237   {
00238     do_realtime_to_fmp(trans.structure(), res.structure(),
00239                        res.structure().series().monoid(),
00240                        trans, res);
00241     return res;
00242   }
00243 }
00244 
00245 #endif // ! VCSN_ALGORITHMS_REALTIME_TO_FMP_HXX

Generated on Sat Jul 29 17:13:10 2006 for Vaucanson by  doxygen 1.4.6