Vaucanson 1.4
extension.hxx
00001 // extension.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, 2005, 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 #ifndef VCSN_ALGORITHMS_EXTENSION_HXX
00018 # define VCSN_ALGORITHMS_EXTENSION_HXX
00019 
00020 # include <vaucanson/algorithms/extension.hh>
00021 # include <vaucanson/misc/usual_macros.hh>
00022 
00023 namespace vcsn {
00024 
00025   template <typename S, typename K, typename T, typename Auto_t>
00026   typename identity_transducer_helper<S, K, T>::ret
00027   do_extension(const AutomataBase<S>& s,
00028                const Auto_t& a)
00029   {
00030     AUTOMATON_TYPES(Auto_t);
00031     // ret_t is the type of the transducer returned.
00032     typedef typename identity_transducer_helper<S, K, T>::ret    ret_t;
00033 
00034     AUTOMATON_TYPES_(ret_t, t_);
00035     typedef typename ret_t::set_t                set_t;
00036     typedef typename set_t::series_set_t         o_series_set_t;
00037     typedef typename ret_t::series_set_elt_t     output_series_set_elt_t;
00038     typedef typename series_set_elt_t::support_t support_t;
00039 
00040     set_t
00041       ts(o_series_set_t (a.structure().series(),
00042                          a.structure().series().monoid()));
00043     ret_t          t_ret(ts);
00044 
00045     monoid_elt_t   neutre   = a.series().monoid().VCSN_EMPTY_;
00046     monoid_elt_t        t_neutre = t_ret.series().monoid().
00047       identity(SELECT(typename t_monoid_elt_t::value_t));
00048 
00049     std::vector<hstate_t>       conv(a.states().size());
00050 
00051     for_all_const_states (s, a)
00052       conv[t_ret.add_state()] = *s;
00053 
00054     for_all_const_transitions (e, a)
00055     {
00056       series_set_elt_t t = a.series_of(*e);
00057       series_set_elt_t s(t);
00058       output_series_set_elt_t os(t_ret.structure().series());
00059       support_t supp = s.supp();
00060       for_all_const_(support_t, m, supp)
00061       {
00062         series_set_elt_t tmp(a.structure().series());
00063         // try to associate the neutral monoid element with a weight
00064         // to create a series which will be a weight in the series os
00065         tmp.assoc(neutre, s.get(*m));
00066         os.assoc(*m, tmp);
00067       }
00068       htransition_t f = t_ret.add_series_transition(conv[a.src_of(*e)],
00069                                                     conv[a.dst_of(*e)],
00070                                                     os);
00071     }
00072 
00073     initial_iterator i;
00074     for (initial_iterator next = a.initial().begin();
00075          next != a.initial().end();)
00076     {
00077       //We need to store the next iterator before using the current one
00078       //to avoid an invalid iterator after having called set_final.
00079       //Indeed, set_final can delete the iterator if its second parameter
00080       //is the zero of the serie.
00081       i = next;
00082       next++;
00083 
00084       series_set_elt_t a_series = a.get_initial(*i);
00085       t_series_set_elt_t s;
00086       s.set(t_neutre, a_series);
00087       t_ret.set_initial(conv[*i], s);
00088     }
00089 
00090     final_iterator f;
00091     for (final_iterator next = a.final().begin();
00092          next != a.final().end();)
00093     {
00094       //We need to store the next iterator before using the current one
00095       //to avoid an invalid iterator after having called set_final.
00096       //Indeed, set_final can delete the iterator if its second parameter
00097       //is the zero of the serie.
00098       f = next;
00099       next++;
00100       series_set_elt_t a_series = a.get_final(*f);
00101       t_series_set_elt_t s;
00102       s.value_set(t_neutre, a_series);
00103       t_ret.set_final(conv[*f], s);
00104     }
00105 
00106     return t_ret;
00107   }
00108 
00109   template<typename S, typename K, typename T>
00110   typename identity_transducer_helper<S, K, T>::ret
00111   extension(const Element<S, T>& a)
00112   {
00113     BENCH_TASK_SCOPED("extension/1");
00114     return do_extension(a.structure(), a);
00115   }
00116 
00117 
00118   /*----------------.
00119   | Two arguments.  |
00120   `----------------*/
00121 
00122 
00123   template<typename SA, typename ST, typename Auto_t, typename Trans_t>
00124   Trans_t do_extension(const AutomataBase<SA>&,
00125                        const TransducerBase<ST>&,
00126                        const Auto_t& a,
00127                        const Trans_t& t)
00128   {
00129     AUTOMATON_TYPES_(Trans_t, t_);
00130     AUTOMATON_TYPES_(Auto_t, a_);
00131     typedef typename Auto_t::hstate_t hstate_t;
00132     typedef typename Trans_t::series_set_elt_t  t_output_series_set_elt_t;
00133     typedef typename Auto_t::series_set_elt_t::support_t a_support_t;
00134     typedef typename Trans_t::semiring_elt_t    t_weight_t;
00135 
00136     Trans_t                   tt(t.structure());
00137     std::map<hstate_t, hstate_t>   conv;
00138 
00139     a_monoid_elt_t a_neutre =
00140       a.series().monoid().identity(SELECT(typename a_monoid_elt_t::value_t));
00141     t_monoid_elt_t t_neutre =
00142       t.series().monoid().identity(SELECT(typename t_monoid_elt_t::value_t));
00143 
00144     for(a_state_iterator p = a.states().begin(); p != a.states().end(); ++p)
00145       conv[*p] = tt.add_state();
00146 
00147     // convert transitions
00148     for(a_transition_iterator e = a.transitions().begin();
00149         e != a.transitions().end(); ++e)
00150     {
00151       a_series_set_elt_t s_ = a.series_of(*e);
00152       a_series_set_elt_t s(s_);
00153 
00154       t_output_series_set_elt_t os(t.structure().series());
00155 
00156       a_support_t supp = s.supp();
00157       for(typename a_support_t::const_iterator m = supp.begin();
00158           m != supp.end(); ++m)
00159       {
00160         t_weight_t tmp(t.structure().series().semiring());
00161         tmp.assoc(a_neutre, s.get(*m));
00162         os.assoc(a_monoid_elt_t (a.structure().series().monoid(), *m), tmp);
00163       }
00164 
00165       tt.add_series_transition(conv[a.src_of(*e)], conv[a.dst_of(*e)], os);
00166     }
00167 
00168     a_initial_iterator i;
00169     for (a_initial_iterator next = a.initial().begin();
00170          next != a.initial().end();)
00171     {
00172       //We need to store the next iterator before using the current one
00173       //to avoid an invalid iterator after having called set_final.
00174       //Indeed, set_final can delete the iterator if its second parameter
00175       //is the zero of the serie.
00176       i = next;
00177       next++;
00178       a_series_set_elt_t a_series = a.get_initial(*i);
00179       t_series_set_elt_t s (t.structure().series());
00180       s.assoc(t_neutre, a_series);
00181       tt.set_initial(conv[*i], s);
00182     }
00183 
00184     a_final_iterator f;
00185     for (a_final_iterator next = a.final().begin();
00186          next != a.final().end();)
00187     {
00188       //We need to store the next iterator before using the current one
00189       //to avoid an invalid iterator after having called set_final.
00190       //Indeed, set_final can delete the iterator if its second parameter
00191       //is the zero of the serie.
00192       f = next;
00193       next++;
00194       a_series_set_elt_t a_series = a.get_final(*f);
00195       t_series_set_elt_t s (t.structure().series());
00196       s.assoc(t_neutre, a_series);
00197       tt.set_final(conv[*f], s);
00198     }
00199 
00200     return tt;
00201   }
00202 
00203   template<typename SA, typename TA, typename ST, typename TT>
00204   Element<ST, TT>
00205   extension(const Element<SA, TA>& a, const Element<ST, TT>& t)
00206   {
00207     BENCH_TASK_SCOPED("extension/2");
00208     return do_extension(a.structure(), t.structure(), a, t);
00209   }
00210 
00211 }
00212 
00213 #endif // ! VCSN_ALGORITHMS_EXTENSION_HXX