normalized.hxx

00001 // normalized.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_NORMALIZED_HXX
00018 # define VCSN_ALGORITHMS_NORMALIZED_HXX
00019 
00020 # include <vaucanson/algorithms/normalized.hh>
00021 
00022 # include <vaucanson/automata/concept/automata_base.hh>
00023 # include <vaucanson/tools/usual_macros.hh>
00024 # include <vaucanson/algorithms/sum.hh>
00025 
00026 # include <stack>
00027 
00028 namespace vcsn {
00029 
00030   /*-----------.
00031   | normalized |
00032   `-----------*/
00033   template <class A_, typename Auto_>
00034   void
00035   do_normalize_here(const AutomataBase<A_>&,
00036                     Auto_& a)
00037   {
00038     AUTOMATON_TYPES(Auto_);
00039 
00040     hstate_t h = a.add_state();
00041 
00042     for_each_initial_state(i, a)
00043       a.add_series_transition(h, *i, a.get_initial(*i));
00044 
00045     a.clear_initial();
00046     a.set_initial(h);
00047 
00048     h = a.add_state();
00049 
00050     for_each_final_state(i, a)
00051       a.add_series_transition(*i, h, a.get_final(*i));
00052 
00053     a.clear_final();
00054     a.set_final(h);
00055   }
00056 
00057   template <typename A, typename T>
00058   Element<A, T>
00059   normalize(const Element<A, T>& a)
00060   {
00061     Element<A, T> result(a);
00062     do_normalize_here(result.structure(), result);
00063     return result;
00064   }
00065 
00066   template<typename A, typename T>
00067   void
00068   normalize_here(Element<A, T>& a)
00069   {
00070     do_normalize_here(a.structure(), a);
00071   }
00072 
00073 
00074   /*--------------------.
00075   | union_of_normalized |
00076   `--------------------*/
00077 
00078   template <typename A, typename lhs_t, typename rhs_t>
00079   void do_union_of_normalized_here(const AutomataBase<A>&,
00080                                    lhs_t& lhs,
00081                                    const rhs_t& rhs)
00082   {
00083     AUTOMATON_TYPES(lhs_t);
00084     std::stack<hstate_t> init;
00085     sum_here(lhs, rhs);
00086     hstate_t new_i = lhs.add_state();
00087     hstate_t new_f = lhs.add_state();
00088     monoid_elt_t ident =
00089       lhs.series().monoid().identity(SELECT(monoid_elt_value_t));
00090     for_each_initial_state(i, lhs)
00091     {
00092       lhs.add_spontaneous(new_i, *i, lhs.get_initial(*i).get(ident));
00093       init.push(*i);
00094     }
00095     while (!init.empty())
00096     {
00097       lhs.unset_initial(init.top());
00098       init.pop();
00099     }
00100     for_each_final_state(f, lhs)
00101     {
00102       lhs.add_spontaneous(*f, new_f, lhs.get_final(*f).get(ident));
00103       init.push(*f);
00104     }
00105     while (!init.empty())
00106     {
00107       lhs.unset_final(init.top());
00108       init.pop();
00109     }
00110     lhs.set_final(new_f);
00111     lhs.set_initial(new_i);
00112   }
00113 
00114   template<typename A, typename T, typename U>
00115   void union_of_normalized_here(Element<A, T>& lhs,
00116                                 const Element<A, U>& rhs)
00117   {
00118     // assertion(lhs.structure() == rhs.structure())
00119     do_union_of_normalized_here(lhs.structure(), lhs, rhs);
00120   }
00121 
00122   template<typename A, typename T, typename U>
00123   Element<A, T>
00124   union_of_normalized(const Element<A, T>& lhs,
00125                       const Element<A, U>& rhs)
00126   {
00127     // assertion(lhs.structure() == rhs.structure())
00128     Element<A, T> ret(lhs);
00129     do_union_of_normalized_here(ret.structure(), ret, rhs);
00130     return ret;
00131   }
00132 
00133   /*--------------.
00134   | is_normalized |
00135   `--------------*/
00136   template <typename A, typename auto_t>
00137   bool
00138   do_is_normalized(const AutomataBase<A>&,
00139                    const auto_t& a)
00140   {
00141     if (a.initial().size() != 1)
00142       return false;
00143     if (a.final().size() != 1)
00144       return false;
00145     std::set<hstate_t> delta_ret;
00146     a.rdeltac(delta_ret, *a.initial().begin(), delta_kind::states());
00147     a.deltac(delta_ret, *a.final().begin(), delta_kind::states());
00148     if (delta_ret.size() != 0)
00149       return false;
00150     return true;
00151   }
00152 
00153   template<typename A, typename T>
00154   bool
00155   is_normalized(const Element<A, T>& a)
00156   {
00157     return do_is_normalized(a.structure(), a);
00158   }
00159 
00160   /*--------------------------.
00161   | concatenate_of_normalized |
00162   `--------------------------*/
00163   template <typename A, typename lhs_t, typename rhs_t>
00164   void do_concatenate_of_normalized_here(const AutomataBase<A>&,
00165                                          lhs_t& lhs,
00166                                          const rhs_t& rhs)
00167   {
00168     AUTOMATON_TYPES(rhs_t);
00169     typedef std::map<hstate_t, hstate_t>               map_lhs_rhs_t;
00170     typedef std::set<htransition_t>                            delta_ret_t;
00171 
00172     hstate_t    glue_state = *lhs.final().begin();
00173 
00174     /*-----------------.
00175     | Concat of states |
00176     `-----------------*/
00177     map_lhs_rhs_t       map_h;
00178 
00179     // If rhs initial multiplicity is 1 and so is lhs final multiplicity,
00180     // we can merge the lhs final state and the rhs initial state.
00181     bool merge_lhs_final_and_rhs_initial =
00182       (lhs.get_final(*lhs.final().begin()).value() ==
00183        lhs.series().identity(SELECT(series_set_elt_value_t)) &&
00184        rhs.get_initial(*rhs.initial().begin()).value() ==
00185        rhs.series().identity(SELECT(series_set_elt_value_t)));
00186 
00187     for_each_state(s, rhs)
00188     {
00189       hstate_t new_state;
00190 
00191       if (merge_lhs_final_and_rhs_initial)
00192       {
00193         if (rhs.is_initial(*s))
00194           new_state = glue_state;
00195         else
00196           new_state = lhs.add_state();
00197       }
00198       else
00199         new_state = lhs.add_state();
00200       map_h[*s] = new_state;
00201       lhs.set_final(new_state, rhs.get_final(*s));
00202     }
00203 
00204     /*----------------------.
00205     | Concat of transitions |
00206     `----------------------*/
00207     delta_ret_t aim;
00208     for_each_state(i, rhs)
00209     {
00210       aim.clear();
00211       rhs.deltac(aim, *i, delta_kind::transitions());
00212       for (typename delta_ret_t::const_iterator d = aim.begin();
00213            d != aim.end();
00214            ++d)
00215         lhs.add_transition(map_h[rhs.src_of(*d)],
00216                            map_h[rhs.dst_of(*d)],
00217                            rhs.label_of(*d));
00218     }
00219     // If initial multiplicity of rhs isn't 1, add a spontaneous transition
00220     // between lhs final state and rhs initial state, with lhs final
00221     // multiplicity * rhs initial multiplicity.
00222     if (!merge_lhs_final_and_rhs_initial)
00223     {
00224       monoid_elt_t ident =
00225         rhs.series().monoid().identity(SELECT(monoid_elt_value_t));
00226       lhs.add_spontaneous(*lhs.final().begin(),
00227                           map_h[*rhs.initial().begin()],
00228                           lhs.get_final(*lhs.final().begin()).get(ident) *
00229                           rhs.get_initial(*rhs.initial().begin()).get(ident));
00230       lhs.unset_final(*lhs.final().begin());
00231       lhs.unset_initial(map_h[*rhs.initial().begin()]);
00232     }
00233   }
00234 
00235   template<typename A, typename T, typename U>
00236   void concatenate_of_normalized_here(Element<A, T>& lhs,
00237                                       const Element<A, U>& rhs)
00238   {
00239     // assertion(lhs.structure() == rhs.structure())
00240     do_concatenate_of_normalized_here(lhs.structure(), lhs, rhs);
00241   }
00242 
00243   template<typename A, typename T, typename U>
00244   Element<A, T>
00245   concatenate_of_normalized(const Element<A, T>& lhs,
00246                             const Element<A, U>& rhs)
00247   {
00248     // assertion(lhs.structure() == rhs.structure())
00249     Element<A, T> ret(lhs);
00250     do_concatenate_of_normalized_here(ret.structure(), ret, rhs);
00251     return ret;
00252   }
00253 
00254   /*-------------------.
00255   | star_of_normalized |
00256   `-------------------*/
00257   template <typename A, typename auto_t>
00258   void do_star_of_normalized_here(const AutomataBase<A>&,
00259                                   auto_t& a)
00260   {
00261     AUTOMATON_TYPES(auto_t);
00262     monoid_elt_t ident =
00263       a.series().monoid().identity(SELECT(monoid_elt_value_t));
00264     a.add_spontaneous(*a.final().begin(),
00265                       *a.initial().begin(),
00266                       a.get_initial(*a.initial().begin()).get(ident));
00267     hstate_t old_i = *a.initial().begin();
00268     hstate_t old_f = *a.final().begin();
00269     hstate_t new_i = a.add_state();
00270     hstate_t new_f = a.add_state();
00271     a.add_spontaneous(new_i, old_i, a.get_initial(old_i).get(ident));
00272     a.add_spontaneous(old_f, new_f, a.get_final(old_f).get(ident));
00273     a.add_spontaneous(new_i, new_f);
00274     a.set_final(new_f);
00275     a.unset_final(old_f);
00276     a.set_initial(new_i);
00277     a.unset_initial(old_i);
00278   }
00279 
00280   template<typename A, typename T>
00281   void star_of_normalized_here(Element<A, T>& a)
00282   {
00283     do_star_of_normalized_here(a.structure(), a);
00284   }
00285 
00286   template<typename A, typename T>
00287   Element<A, T>
00288   star_of_normalized(const Element<A, T>& a)
00289   {
00290     // assertion(lhs.structure() == rhs.structure())
00291     Element<A, T> ret(a);
00292     do_star_of_normalized_here(ret.structure(), ret);
00293     return ret;
00294   }
00295 
00296 } // vcsn
00297 
00298 #endif // ! VCSN_ALGORITHMS_NORMALIZED_HXX

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