letter_to_letter_composition.hxx

00001 // letter_to_letter_composition.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 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_LETTER_TO_LETTER_COMPOSITION_HXX
00018 # define VCSN_ALGORITHMS_LETTER_TO_LETTER_COMPOSITION_HXX
00019 
00020 # include <vaucanson/automata/concept/transducer_base.hh>
00021 # include <vaucanson/tools/usual_macros.hh>
00022 
00023 # include <set>
00024 # include <map>
00025 
00026 namespace vcsn {
00027 
00028 
00029   template <class Self, class T>
00030   Element<Self, T>
00031   do_letter_to_letter_composition(const TransducerBase<Self>& s,
00032                                   const Element<Self, T>& f,
00033                                   const Element<Self, T>& g)
00034   {
00035     typedef Element<Self, T> transducer_t;
00036     AUTOMATON_TYPES(transducer_t);
00037     typedef std::map<std::pair<hstate_t, hstate_t>, hstate_t> assoc_t;
00038     typedef std::set<htransition_t> delta_ret_t;
00039 
00040     semiring_t output_series(f.series().semiring().semiring(),
00041                              f.series().semiring().monoid());
00042     series_set_t series(output_series, g.series().monoid());
00043     automata_set_t structure(series);
00044     transducer_t output(s);
00045     delta_ret_t f_delta_ret, g_delta_ret;
00046     assoc_t conv;
00047     series_set_elt_t zero =
00048       algebra::zero_as<series_set_elt_value_t>::of(output.series());
00049 
00050     for_each_state(s, f)
00051       for_each_state(t, g)
00052     {
00053       hstate_t ns = output.add_state();
00054       conv[std::make_pair(*s, *t)] = ns;
00055       output.set_initial(ns,
00056                          f.get_initial(*s) * g.get_initial(*t));
00057       output.set_final(ns,
00058                        f.get_final(*s) * g.get_final(*t));
00059 
00060     }
00061 
00062     for_each_state(s, f)
00063       for_each_state(t, g)
00064     {
00065       f_delta_ret.clear();
00066       g_delta_ret.clear();
00067 
00068       f.deltac(f_delta_ret, *s, delta_kind::transitions());
00069       g.deltac(g_delta_ret, *t, delta_kind::transitions());
00070 
00071       for_all_const_(delta_ret_t, lhs_e, f_delta_ret)
00072       {
00073         series_set_elt_t l = f.series_of(*lhs_e);
00074         for_all_const_(delta_ret_t, rhs_e, g_delta_ret)
00075         {
00076           series_set_elt_t l_ = g.series_of(*rhs_e);
00077           series_set_elt_t l__(series);
00078           typedef typename series_set_t::support_t support_t;
00079           for_all_const_(support_t, supp, l.supp())
00080           {
00081             semiring_elt_t ol = l.get(*supp);
00082             typedef typename semiring_elt_t::support_t wsupport_t;
00083             wsupport_t wsupp = ol.supp();
00084             series_set_t ts(series, monoid_elt_t(*supp));
00085             for_all_const_(wsupport_t, ss, wsupp)
00086               l__ += ts * l_.get(*ss);
00087           }
00088           if (l__ != zero)
00089           {
00090             output.add_series_transition(conv[std::make_pair(*s, *t)],
00091                                          conv[std::make_pair(f.dst_of(*lhs_e),
00092                                                              g.dst_of(*rhs_e))
00093                                            ],
00094                                          l__);
00095           }
00096         }
00097       }
00098     }
00099     return output;
00100   }
00101 
00102   template <class S, class T>
00103   Element<S, T>
00104   letter_to_letter_composition(const Element<S, T>& lhs,
00105                                const Element<S, T>& rhs)
00106   {
00107     return do_letter_to_letter_composition(lhs.structure(), lhs, rhs);
00108   }
00109 
00110 } // vcsn
00111 
00112 #endif // ! VCSN_ALGORITHMS_LETTER_TO_LETTER_COMPOSITION_HXX

Generated on Fri Jul 28 12:18:48 2006 for Vaucanson by  doxygen 1.4.6