Vaucanson: fmp_to_rw.hxx Source File

00001 // fmp_to_rw.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2005, 2006, 2008 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_FMP_TO_RW_HXX
00018 # define VCSN_ALGORITHMS_FMP_TO_RW_HXX
00019 
00020 # include <vaucanson/automata/concept/automata.hh>
00021 # include <vaucanson/automata/concept/transducer.hh>
00022 # include <vaucanson/algebra/concept/freemonoid_product.hh>
00023 
00024 # include <map>
00025 
00026 namespace vcsn
00027 {
00028 
00029   template<typename S, typename T,
00030            typename SS, typename TT,
00031            typename Self>
00032   void
00033   do_fmp_to_rw(const vcsn::AutomataBase<S>&,
00034                const vcsn::TransducerBase<SS>&,
00035                const vcsn::algebra::FreeMonoidProductBase<Self>&,
00036                const vcsn::Element<S, T>& fmp,
00037                vcsn::Element<SS, TT>& res)
00038   {
00039     typedef typename T::hstate_t hstate_t;
00040     // Map source automaton's states with result's states
00041     std::map<hstate_t, hstate_t> m;
00042 
00043     // Input FMP type
00044     typedef vcsn::Element<S, T> FMP_t;
00045 
00046     // Output transducer type
00047     typedef vcsn::Element<SS, TT> Trans_t;
00048 
00049     /*-------------------------.
00050     | Creating the transducer. |
00051     `-------------------------*/
00052 
00053     // Adding states
00054     for (typename FMP_t::state_iterator St = fmp.states().begin();
00055          St != fmp.states().end();
00056          ++St)
00057       m[*St] = res.add_state();
00058 
00059 
00060     /*-------------------------.
00061     | Setting initial states.  |
00062     `-------------------------*/
00063 
00064     for (typename FMP_t::initial_iterator St, next = fmp.initial().begin();
00065          next != fmp.initial().end();)
00066     {
00067       //We need to store the next iterator before using the current one
00068       //to avoid an invalid iterator after having called set_final.
00069       //Indeed, set_final can delete the iterator if its second parameter
00070       //is the zero of the serie.
00071       St = next;
00072       next++;
00073       //Series to be created
00074       typename Trans_t::series_set_elt_t s(res.structure().series());
00075 
00076       typename FMP_t::series_set_elt_t s_elt = fmp.get_initial(*St);
00077       for_all_const_(FMP_t::series_set_elt_t::support_t, i, s_elt.supp())
00078       {
00079         typename Trans_t::semiring_elt_value_t::monoid_elt_value_t
00080           output_monoid_value;
00081         typename Trans_t::semiring_elt_t::semiring_elt_t weight;
00082 
00083         typename Trans_t::monoid_elt_value_t
00084           input_monoid_value = (*i).first;
00085         typename Trans_t::monoid_elt_t
00086           input_monoid(res.structure().series().monoid(),
00087                        input_monoid_value);
00088 
00089         typename Trans_t::semiring_elt_t::monoid_elt_t
00090           output_monoid(res.structure().series().semiring().monoid(),
00091                         (*i).second);
00092         weight = s_elt.get(*i);
00093 
00094         //Creating the element multiplicity
00095         typename Trans_t::semiring_elt_t
00096           out_mult(res.structure().series().semiring());
00097         out_mult.assoc(output_monoid, weight);
00098 
00099         //Associating it to the input monoid
00100         s.assoc(input_monoid, out_mult);
00101       }
00102       res.set_initial(m[*St], s);
00103     }
00104 
00105 
00106     /*------------------------.
00107     | Setting final states.   |
00108     `------------------------*/
00109 
00110     for (typename FMP_t::final_iterator St, next = fmp.final().begin();
00111          next != fmp.final().end();)
00112     {
00113       //We need to store the next iterator before using the current one
00114       //to avoid an invalid iterator after having called set_final.
00115       //Indeed, set_final can delete the iterator if its second parameter
00116       //is the zero of the serie.
00117       St = next;
00118       next++;
00119       //Series to be created
00120       typename Trans_t::series_set_elt_t s(res.structure().series());
00121 
00122       typename FMP_t::series_set_elt_t s_elt = fmp.get_final(*St);
00123       for_all_const_(FMP_t::series_set_elt_t::support_t, i, s_elt.supp())
00124       {
00125         typename Trans_t::semiring_elt_value_t::monoid_elt_value_t
00126           output_monoid_value;
00127         typename Trans_t::semiring_elt_t::semiring_elt_t weight;
00128 
00129         typename Trans_t::monoid_elt_value_t input_monoid_value =
00130           (*i).first;
00131         typename Trans_t::monoid_elt_t
00132           input_monoid(res.structure().series().monoid(),
00133                        input_monoid_value);
00134         typename Trans_t::semiring_elt_t::monoid_elt_t
00135           output_monoid(res.structure().series().semiring().monoid(),
00136                         (*i).second);
00137         weight = s_elt.get(*i);
00138 
00139         //Creating the element multiplicity
00140         typename Trans_t::semiring_elt_t
00141           out_mult(res.structure().series().semiring());
00142         out_mult.assoc(output_monoid, weight);
00143 
00144         //Associating it to the input monoid
00145         s.assoc(input_monoid, out_mult);
00146       }
00147       res.set_final(m[*St], s);
00148     }
00149 
00150 
00151     /*-----------------------.
00152     | Creating transitions.  |
00153     `-----------------------*/
00154 
00155     for (typename FMP_t::transition_iterator Ed = fmp.transitions().begin();
00156          Ed != fmp.transitions().end();
00157          ++Ed)
00158     {
00159       // FIXME
00160       // No Special Treatment is done for 0 weighted
00161       typename Trans_t::series_set_elt_t
00162         transition_value(res.structure().series());
00163 
00164       typename Trans_t::monoid_elt_value_t input_monoid_value;
00165       typename Trans_t::semiring_elt_value_t::monoid_elt_value_t
00166         output_monoid_value;
00167 
00168       typename FMP_t::series_set_elt_t series_fmp(fmp.structure().series());
00169       typename Trans_t::semiring_elt_t
00170         out_mult(res.structure().series().semiring());
00171       series_fmp = fmp.series_of(*Ed);
00172 
00173       for_all_const_(FMP_t::series_set_elt_t::support_t,
00174                      i,
00175                      series_fmp.supp())
00176       {
00177         input_monoid_value = (*i).first;
00178         output_monoid_value = (*i).second;
00179 
00180         //Creating the transition's semiring value
00181         typename Trans_t::semiring_elt_t::semiring_elt_t
00182           transition_weight(res.structure().series().semiring().semiring(),
00183                             series_fmp.get(*i));
00184         typename Trans_t::semiring_elt_t
00185           out_mult(res.structure().series().semiring());
00186         out_mult.assoc(typename Trans_t::semiring_elt_t::monoid_elt_t
00187                        (res.structure().series().semiring().monoid(),
00188                         output_monoid_value),
00189                        transition_weight);
00190 
00191         //Creating the transition's monoid value
00192         typename Trans_t::monoid_elt_t
00193           input(res.structure().series().monoid(),
00194                 input_monoid_value);
00195         transition_value.assoc(input, out_mult);
00196         res.add_series_transition(m[fmp.src_of(*Ed)],
00197                                   m[fmp.dst_of(*Ed)],
00198                                   transition_value);
00199       }
00200     }
00201   }
00202 
00203   template<typename S, typename T,
00204            typename SS, typename TT>
00205   vcsn::Element<SS, TT>&
00206   fmp_to_rw(const vcsn::Element<S, T>& fmp,
00207             vcsn::Element<SS, TT>& res)
00208   {
00209     BENCH_TASK_SCOPED("fmp_to_rw");
00210     do_fmp_to_rw(fmp.structure(), res.structure(),
00211                  fmp.structure().series().monoid(),
00212                  fmp, res);
00213     return res;
00214   }
00215 }
00216 #endif // ! VCSN_ALGORITHMS_FMP_TO_RW_HXX