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

Generated on Sun Jul 29 19:35:27 2007 for Vaucanson by  doxygen 1.5.2