realtime_composition.hxx

00001 // realtime_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, 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_REALTIME_COMPOSITION_HXX
00018 # define VCSN_ALGORITHMS_REALTIME_COMPOSITION_HXX
00019 
00020 # include <vaucanson/algorithms/realtime_composition.hh>
00021 
00022 # include <vaucanson/automata/concept/transducer.hh>
00023 
00024 # include <queue>
00025 
00026 namespace vcsn {
00027 
00028   /* Composition for realtime transducers. */
00029   template< typename S,
00030             typename Trans_t>
00031   void
00032   do_realtime_composition(const TransducerBase<S>&,
00033                           const Trans_t& lhs,
00034                           const Trans_t& rhs,
00035                           Trans_t& ret)
00036   {
00037     AUTOMATON_TYPES(Trans_t);
00038 
00039     using namespace std;
00040 
00041     typedef series_set_elt_t exp_t;
00042     typedef typename series_set_elt_t::semiring_elt_t  output_exp_t;
00043     typedef set<std::pair<hstate_t, output_exp_t> >    state_exp_pair_set_t;
00044     typedef pair<hstate_t, hstate_t>                   state_pair_t;
00045     typedef map<state_pair_t, hstate_t>                state_pair_map_t;
00046     typedef queue<state_pair_t>                        state_pair_queue_t;
00047     typedef set<htransition_t>                         set_of_transitions_t;
00048 
00049     typedef typename Trans_t::value_t                     T;
00050     typedef typename output_projection_helper<S, T>::ret  Auto_t;
00051     typedef typename Auto_t::set_t::series_set_t          Auto_series_set_t;
00052     typedef typename Auto_t::set_t                        o_automata_set_t;
00053 
00054     o_automata_set_t auto_structure
00055       (Auto_series_set_t (lhs.structure().series().semiring()));
00056 
00057     AUTOMATON_TYPES_(Auto_t, a_);
00058 
00059     state_exp_pair_set_t     sep_set;
00060     state_pair_map_t         sp_map;
00061 
00062     state_pair_queue_t       sp_queue;
00063 
00064     exp_t         null_exp = lhs.series().zero_;
00065     monoid_elt_t  empty    = lhs.series().monoid().empty_;
00066 
00067     for_all_initial_states(p, lhs)
00068     {
00069       exp_t exp = lhs.get_initial(*p);
00070       partial_evaluation(exp, rhs, sep_set);
00071 
00072       for_all_const_(state_exp_pair_set_t, mypair, sep_set)
00073       {
00074 
00075         hstate_t new_state = ret.add_state(); // add_state
00076 
00077         state_pair_t sp;
00078         sp.first  = *p;
00079         sp.second = (*mypair).first;
00080 
00081         sp_queue.push(sp);
00082         sp_map[sp] = new_state;
00083         exp_t s(exp.structure());
00084         s.assoc(empty, (*mypair).second);
00085         ret.set_initial(new_state, s);
00086       }
00087 
00088     }
00089     while(!sp_queue.empty())
00090     {
00091       state_pair_t sp = sp_queue.front();
00092       sp_queue.pop();
00093       hstate_t p = sp.first;
00094       hstate_t q = sp.second;
00095 
00096       if (lhs.is_final(p))
00097       {
00098         exp_t exp = lhs.get_final(p);
00099 
00100         Auto_t a(auto_structure);
00101         standard_of(a, exp.get(empty).value());
00102 
00103         output_exp_t exp1 (a.series());
00104         partial_2(a, rhs, q, exp1);
00105 
00106         output_exp_t null_series =
00107           a.series().zero(SELECT(typename a_series_set_elt_t::value_t));
00108 
00109         if (exp1 != null_series)
00110         {
00111           exp_t s (lhs.series());
00112           s.assoc(empty, exp1);
00113           ret.set_final(sp_map[sp], s);
00114         }
00115       }
00116 
00117       set_of_transitions_t transitions;
00118       lhs.deltac(transitions, p, delta_kind::transitions());
00119 
00120       for_all_const_(set_of_transitions_t, e, transitions)
00121       {
00122         hstate_t p_ = lhs.dst_of(*e);
00123         exp_t exp = lhs.series_of(*e);
00124 
00125         assertion(exp.supp().size() == 1);
00126         monoid_elt_t word (exp.structure().monoid(), *exp.supp());
00127         // This supp would have one word
00128 
00129         Auto_t a(auto_structure);
00130         standard_of(a, exp.get(word).value());
00131         state_exp_pair_set_t sep_set1;
00132         partial_3(a, rhs, q, sep_set1);
00133 
00134         for_all_const_(state_exp_pair_set_t, mypair, sep_set1)
00135         {
00136           state_pair_t sp1;
00137           sp1.first = p_;
00138           sp1.second = (*mypair).first;
00139           if (sp_map.find(sp1) == sp_map.end())
00140           {
00141             hstate_t new_state = ret.add_state();
00142             sp_map[sp1] = new_state;
00143             sp_queue.push(sp1);
00144           }
00145 
00146           exp_t s (lhs.structure().series());
00147           s.assoc(word, (*mypair).second);
00148           ret.add_series_transition( sp_map[sp], sp_map[sp1], s);
00149         }
00150       }
00151     }
00152 
00153   }
00154 
00155   template< typename S, typename T>
00156   void
00157   realtime_composition(const Element<S, T>& lhs,
00158                        const Element<S, T>& rhs,
00159                        Element<S, T>& ret)
00160   {
00161     typedef Element<S, T> auto_t;
00162     AUTOMATON_TYPES(auto_t);
00163     for_all_states (s, ret)
00164     {
00165       ret.del_state (*s);
00166     }
00167     do_realtime_composition(lhs.structure(), lhs, rhs, ret);
00168   }
00169 
00170 
00171   template< typename S, typename T>
00172   Element<S, T>
00173   realtime_composition(const Element<S, T>& lhs,
00174                        const Element<S, T>& rhs)
00175   {
00176     Element<S, T> ret (lhs.structure());
00177     do_realtime_composition(lhs.structure(), lhs, rhs, ret);
00178     return ret;
00179   }
00180 }
00181 
00182 #endif // ! VCSN_ALGORITHMS_REALTIME_COMPOSITION_HXX

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