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

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