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 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 ST, typename SA,
00027            typename Trans_t, typename Auto_t>
00028   void
00029   do_output_projection(const TransducerBase<ST>&,
00030                        const AutomataBase<SA>&,
00031                        const Trans_t& t,
00032                        Auto_t& ret)
00033   {
00034     AUTOMATON_TYPES(Trans_t);
00035 
00036     std::map<hstate_t, hstate_t> m;
00037 
00038     for_all_states(p, t)
00039       m[*p] = ret.add_state();
00040 
00041     monoid_elt_t empty =
00042       algebra::identity_as<monoid_elt_value_t>::of(t.series().monoid());
00043     typename Trans_t::series_set_elt_t id_series(t.structure().series());
00044     id_series = vcsn::algebra::
00045       identity_as<typename Trans_t::series_set_elt_value_t>::
00046       of(t.structure().series());
00047 
00048     for_all_initial_states(p, t)
00049     {
00050       if (t.get_initial(*p) != id_series)
00051       {
00052         hstate_t tmp = ret.add_state();
00053         ret.set_initial(tmp);
00054         ret.add_series_transition(tmp, m[*p], t.get_initial(*p).get(empty));
00055       }
00056       else
00057         ret.set_initial(m[*p], t.get_initial(*p).get(empty));
00058     }
00059 
00060     for_all_final_states(p, t)
00061     {
00062       if (t.get_final(*p) != id_series)
00063       {
00064         hstate_t tmp = ret.add_state();
00065         ret.set_final(tmp);
00066         ret.add_series_transition(m[*p], tmp, t.get_final(*p).get(empty));
00067       }
00068       else
00069         ret.set_final(m[*p], t.get_final(*p).get(empty));
00070     }
00071 
00072     for_all_transitions(e, t)
00073     {
00074       ret.add_series_transition(m[t.src_of(*e)],
00075                                 m[t.dst_of(*e)],
00076                                 t.output_of(*e));
00077     }
00078   }
00079 
00080   template <class ST, class TT,
00081             class SA, class TA>
00082   void
00083   output_projection(const Element<ST, TT>& t,
00084                     Element<SA, TA>& a)
00085   {
00086     return do_output_projection(t.structure(), a.structure(), t, a);
00087   }
00088 
00090 
00091   template <typename S, typename T>
00092   typename output_projection_helper<S, T>::ret
00093   do_output_projection(const TransducerBase<S>&,
00094                        const Element<S, T>& t,
00095                        std::map<hstate_t, hstate_t>& m_)
00096   {
00097     using namespace std;
00098     typedef Element<S, T>  Trans_t;
00099     AUTOMATON_TYPES(Trans_t);
00100 
00101     typedef typename output_projection_helper<S, T>::ret    Auto_t;
00102     typedef typename Auto_t::set_t                   Auto_set_t;
00103     typedef typename Auto_set_t::series_set_t            Auto_series_set_t;
00104 
00105     Auto_set_t   auto_set(Auto_series_set_t(t.structure().series().semiring()));
00106     Auto_t       ret(auto_set);
00107 
00108     monoid_elt_t empty = t.series().monoid().empty_;
00109     std::map<hstate_t, hstate_t> m;
00110 
00111     for_all_states(p, t)
00112     {
00113       m[*p] = ret.add_state();
00114       m_[m[*p]] = *p;
00115     }
00116 
00117     for_all_initial_states(p, t)
00118       ret.set_initial(m[*p], t.get_initial(*p).get(empty));
00119 
00120     for_all_final_states(p, t)
00121       ret.set_final(m[*p], t.get_final(*p).get(empty));
00122 
00123     for_all_transitions(e, t)
00124       ret.add_series_transition(m[t.src_of(*e)], m[t.dst_of(*e)], t.output_of(*e));
00125 
00126     return ret;
00127   }
00128 
00129   template <typename S, typename T>
00130   typename output_projection_helper<S,T>::ret
00131   output_projection(const Element<S, T>& t,
00132                     std::map<hstate_t, hstate_t>& m)
00133   {
00134     return do_output_projection(t.structure(), t, m);
00135   }
00136 
00137   template <typename S, typename T>
00138   typename output_projection_helper<S,T>::ret
00139   output_projection(const Element<S, T>& t)
00140   {
00141     std::map<hstate_t, hstate_t> m;
00142     return do_output_projection(t.structure(), t, m);
00143   }
00144 
00146 
00147   template <typename S, typename T>
00148   typename input_projection_helper<S, T>::ret
00149   do_input_projection(const TransducerBase<S>&,
00150                       const Element<S, T>& t)
00151   {
00152     using namespace std;
00153     typedef Element<S, T> Trans_t;
00154     AUTOMATON_TYPES(Trans_t);
00155 
00156     typedef typename input_projection_helper<S, T>::ret Auto_t;
00157     typedef typename Auto_t::set_t                      Auto_set_t;
00158     typedef typename Auto_set_t::series_set_t           Auto_series_set_t;
00159 
00160     Auto_set_t   auto_set(Auto_series_set_t(t.structure().series().semiring()));
00161     Auto_t       ret(auto_set);
00162 
00163     monoid_elt_t empty = t.series().monoid().empty_;
00164     std::map<hstate_t, hstate_t> m;
00165 
00166     for_all_states(p, t)
00167     {
00168       m[*p] = ret.add_state();
00169     }
00170 
00171     for_all_initial_states(p, t)
00172       ret.set_initial(m[*p]);
00173 
00174     for_all_final_states(p, t)
00175       ret.set_final(m[*p]);
00176 
00177     for_all_transitions(e, t)
00178     {
00179       ret.add_series_transition(m[t.src_of(*e)],
00180                                 m[t.dst_of(*e)],
00181                                 t.input_of(*e));
00182     }
00183 
00184     return ret;
00185   }
00186 
00187   template <typename S, typename T>
00188   typename input_projection_helper<S, T>::ret
00189   input_projection(const Element<S, T>& t)
00190   {
00191     return do_input_projection(t.structure(), t);
00192   }
00193 
00194 }
00195 
00196 #endif // ! VCSN_ALGORITHMS_PROJECTION_HXX

Generated on Sat Jul 29 17:13:10 2006 for Vaucanson by  doxygen 1.4.6