projection.hxx

00001 // projection.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_PROJECTION_HXX
00018 # define VCSN_ALGORITHMS_PROJECTION_HXX
00019 
00020 # include <vaucanson/algorithms/projection.hh>
00021 
00022 # include <map>
00023 
00024 namespace vcsn {
00025 
00026   template <typename auto_t, typename trans_t>
00027   void
00028   set_states(const trans_t& fmp_trans, auto_t& res,
00029              std::map<hstate_t, hstate_t>& stmap)
00030   {
00031     AUTOMATON_TYPES_(trans_t, trans_);
00032     AUTOMATON_TYPES(auto_t);
00033 
00034     typedef typename trans_series_set_elt_t::support_t  trans_support_t;
00035 
00036     const series_set_t&         series = res.structure().series();
00037     const monoid_t&             monoid = res.structure().series().monoid();
00038 
00039     for_all_states(fmp_s, fmp_trans)
00040     {
00041       hstate_t s = res.add_state();
00042       stmap[*fmp_s] = s;
00043 
00044       if (fmp_trans.is_initial(*fmp_s))
00045       {
00046         trans_series_set_elt_t  in = fmp_trans.get_initial(*fmp_s);
00047         trans_support_t         supp = in.supp();
00048 
00049         semiring_elt_t          in_semi_elt = in.get(*(supp.begin()));
00050         series_set_elt_t        series_elt(series);
00051 
00052         series_elt.assoc(monoid_elt_t(monoid,
00053                                       algebra::identity_as<
00054                                       monoid_elt_value_t>::
00055                                       of(monoid).value()),
00056                          in_semi_elt);
00057         res.set_initial(s, series_elt);
00058       }
00059 
00060       if (fmp_trans.is_final(*fmp_s))
00061       {
00062         trans_series_set_elt_t  out = fmp_trans.get_final(*fmp_s);
00063         trans_support_t         supp = out.supp();
00064 
00065         semiring_elt_t          out_semi_elt = out.get(*(supp.begin()));
00066         series_set_elt_t        series_elt(series);
00067 
00068         series_elt.assoc(monoid_elt_t(monoid,
00069                                       algebra::identity_as<
00070                                       monoid_elt_value_t>::
00071                                       of(monoid).value()),
00072                          out_semi_elt);
00073         res.set_final(s, series_elt);
00074       }
00075     }
00076   }
00077 
00078 
00079   /*---------.
00080   | Identity |
00081   `---------*/
00082 
00083   template <typename S1, typename S2, typename M1, typename M2,
00084             typename auto_t, typename trans_t>
00085   void
00086   do_identity(const AutomataBase<S1>&,
00087               const algebra::FreeMonoidBase<M1>&,
00088               const AutomataBase<S2>&,
00089               const algebra::FreeMonoidProduct<M1,M2>&,
00090               const auto_t& aut, trans_t& res)
00091   {
00092     TIMER_SCOPED("identity");
00093     AUTOMATON_TYPES_(auto_t, aut_);
00094     AUTOMATON_TYPES(trans_t);
00095 
00096     std::map<hstate_t, hstate_t>        stmap;
00097     typedef typename aut_series_set_elt_t::support_t    aut_support_t;
00098 
00099     const series_set_t&         series = res.structure().series();
00100     const monoid_t&             monoid = res.structure().series().monoid();
00101     const aut_monoid_t&         aut_monoid = aut.structure().series().monoid();
00102 
00103     set_states(aut, res, stmap);
00104 
00105     for_all_transitions(aut_e, aut)
00106     {
00107       const aut_series_set_elt_t        aut_series_elt =
00108         aut.series_of(*aut_e);
00109       aut_support_t                     aut_supp = aut_series_elt.supp();
00110       const aut_monoid_elt_t    aut_monoid_elt
00111         (aut_monoid, *(aut_supp.begin()));
00112       const monoid_elt_value_t  word(aut_monoid_elt.value(),
00113                                      aut_monoid_elt.value());
00114 
00115       series_set_elt_t          series_elt(series);
00116 
00117       series_elt.assoc(monoid_elt_t(monoid, word),
00118                        aut_series_elt.get(aut_monoid_elt));
00119 
00120       res.add_series_transition(stmap[aut.src_of(*aut_e)],
00121                                 stmap[aut.dst_of(*aut_e)], series_elt);
00122     }
00123   }
00124 
00125   template <typename S, typename S2, typename T, typename T2>
00126   void
00127   identity(const Element<S,T>& aut, Element<S2, T2>& res)
00128   {
00129     do_identity(aut.structure(), aut.structure().series().monoid(),
00130                 res.structure(), res.structure().series().monoid(), aut, res);
00131   }
00132 
00133   template <typename S, typename S2, typename T, typename T2>
00134   Element<S2, T2>
00135   identity(const Element<S,T>& aut)
00136   {
00137     typedef Element<S, T> auto_t;
00138 
00139     typedef algebra::FreeMonoidProduct<
00140       typename auto_t::series_set_t::monoid_t,
00141       typename auto_t::series_set_t::monoid_t> monoid_t;
00142 
00143     typedef algebra::Series<typename auto_t::series_set_t::semiring_t,
00144       monoid_t>
00145       series_set_t;
00146 
00147     monoid_t            monoid (aut.structure().series().monoid(),
00148                                 aut.structure().series().monoid());
00149 
00150     series_set_t                        series
00151       (aut.structure().series().semiring(), monoid);
00152     Automata<series_set_t>              aut_set(series);
00153     Element< Automata<series_set_t>, T> res(aut_set);
00154 
00155     do_identity(aut.structure(), aut.structure().series().monoid(),
00156                 res.structure(), res.structure().series().monoid(), aut, res);
00157     return res;
00158   }
00159 
00160 }
00161 
00162 #endif // ! VCSN_ALGORITHMS_PROJECTION_HXX

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