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

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