standard.hxx

00001 // standard.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_STANDARD_HXX
00018 # define VCSN_ALGORITHMS_STANDARD_HXX
00019 
00020 # include <vaucanson/algorithms/standard.hh>
00021 # include <vaucanson/algorithms/internal/has_neighbour.hh>
00022 
00023 # include <vaucanson/algorithms/sum.hh>
00024 # include <vaucanson/algorithms/accessible.hh>
00025 # include <vaucanson/automata/concept/automata_base.hh>
00026 # include <vaucanson/misc/usual_macros.hh>
00027 
00028 # include <set>
00029 
00030 namespace vcsn {
00031 
00032   /*---------.
00033   | standard |
00034   `---------*/
00035   template <class A_, typename Auto_>
00036   void
00037   do_in_standardize(const AutomataBase<A_>& ,
00038                     Auto_&                  a)
00039   {
00040     TIMER_SCOPED("standardize");
00041     AUTOMATON_TYPES(Auto_);
00042 
00043     hstate_t i = a.add_state();
00044     std::set<htransition_t> transition_oi;
00045 
00046     for_all_initial_states(oi, a)
00047     {
00048       series_set_elt_t s = a.get_initial(*oi);
00049       transition_oi.clear();
00050       a.deltac(transition_oi, *oi, delta_kind::transitions());
00051       for_all_const_(std::set<htransition_t>, oil, transition_oi)
00052       {
00053         series_set_elt_t t = s * a.series_of(*oil);
00054         a.add_series_transition(i, a.dst_of(*oil), t);
00055       }
00056     }
00057     a.clear_initial();
00058     a.set_initial(i);
00059     accessible_here(a);
00060   }
00061 
00062   template<typename A, typename T>
00063   void
00064   standardize(Element<A, T>& a)
00065   {
00066     do_in_standardize(a.structure(), a);
00067   }
00068 
00069   /*-----------------.
00070   | standard_union.  |
00071   `-----------------*/
00072 
00073   template <typename A, typename lhs_t, typename rhs_t>
00074   void do_union_of_standard_here(const AutomataBase<A>&,
00075                                  lhs_t& lhs,
00076                                  const rhs_t& rhs)
00077   {
00078     TIMER_SCOPED("union_of_standard");
00079     typedef typename std::set<htransition_t> edelta_ret_t;
00080 
00081     // The resulting initial state is that of lhs.
00082     hstate_t new_i = *lhs.initial().begin();
00083     sum_here(lhs, rhs);
00084 
00085     // Adjust new_i, and handle old_i, the state that was the initial
00086     // state of rhs.
00087     typename lhs_t::initial_support_t initial = lhs.initial();
00088 
00089     // There are two initial states, old_i is the other.
00090     assertion (initial.size() == 2);
00091     typename lhs_t::initial_iterator i = initial.begin();
00092     hstate_t old_i = *i != new_i ? *i : *++i;
00093 
00094     lhs.set_final(new_i,
00095                   lhs.get_final(new_i) + lhs.get_final(old_i));
00096 
00097     // Add output transitions of old_i to new_i.
00098     edelta_ret_t dst;
00099     lhs.deltac(dst, old_i, delta_kind::transitions());
00100     for_all_const_(edelta_ret_t, d, dst)
00101     {
00102       lhs.add_transition(new_i,
00103                          lhs.dst_of(*d),
00104                          lhs.label_of(*d));
00105       lhs.del_transition(*d);
00106     }
00107     lhs.del_state(old_i);
00108   }
00109 
00110   template<typename A, typename T, typename U>
00111   void union_of_standard_here(Element<A, T>& lhs,
00112                               const Element<A, U>& rhs)
00113   {
00114     // assertion(lhs.structure() == rhs.structure())
00115     do_union_of_standard_here(lhs.structure(), lhs, rhs);
00116   }
00117 
00118   template<typename A, typename T, typename U>
00119   Element<A, T>
00120   union_of_standard(const Element<A, T>& lhs,
00121                     const Element<A, U>& rhs)
00122   {
00123     // assertion(lhs.structure() == rhs.structure())
00124     Element<A, T> ret(lhs);
00125     union_of_standard_here(ret, rhs);
00126     return ret;
00127   }
00128 
00129   /*--------------.
00130   | is_standard.  |
00131   `--------------*/
00132   template <typename A, typename auto_t>
00133   bool
00134   do_is_standard(const AutomataBase<A>& ,
00135                  const auto_t& a)
00136   {
00137     TIMER_SCOPED("is_standard");
00138     typedef typename auto_t::series_set_elt_value_t     series_set_elt_value_t;
00139 
00140     // Check there is only one initial state.
00141     if (a.initial().size() != 1)
00142       return false;
00143 
00144     // Check the multiplicity of the initial state.
00145     hstate_t s = *a.initial().begin();
00146     if (a.get_initial(s)
00147         != a.series().identity(SELECT(series_set_elt_value_t)))
00148       return false;
00149 
00150     // Check that there is no input transition on the initial state.
00151     return !has_predecessors(a, s);
00152   }
00153 
00154   template<typename A, typename T>
00155   bool
00156   is_standard(const Element<A, T>& a)
00157   {
00158     return do_is_standard(a.structure(), a);
00159   }
00160 
00161   /*---------------------.
00162   | concat_of_standard.  |
00163   `---------------------*/
00164   template <typename A, typename lhs_t, typename rhs_t>
00165   void do_concat_of_standard_here(const AutomataBase<A>& ,
00166                                   lhs_t& lhs,
00167                                   const rhs_t& rhs)
00168   {
00169     TIMER_SCOPED("concat_of_standard");
00170     AUTOMATON_TYPES(lhs_t);
00171     typedef std::map<hstate_t, hstate_t>        map_t;
00172     typedef std::set<htransition_t>             delta_ret_t;
00173 
00174     /*------------------.
00175     | Concat of states. |
00176     `------------------*/
00177     map_t       map_h;
00178     delta_ret_t dst;
00179     hstate_t    new_state;
00180 
00181     // Add states except the initial one.
00182     for (typename rhs_t::state_iterator s = rhs.states().begin();
00183          s != rhs.states().end();
00184          ++s)
00185       if (!rhs.is_initial(*s))
00186       {
00187         new_state = lhs.add_state();
00188         map_h[*s] = new_state;
00189       }
00190 
00191     // Add transitions.
00192     for (typename rhs_t::state_iterator i = rhs.states().begin();
00193          i != rhs.states().end();
00194          ++i)
00195       if (!rhs.is_initial(*i))
00196       {
00197         dst.clear();
00198         rhs.deltac(dst, *i, delta_kind::transitions());
00199         for_all_const_(delta_ret_t, d, dst)
00200           lhs.add_transition(map_h[*i],
00201                              map_h[rhs.dst_of(*d)],
00202                              rhs.label_of(*d));
00203       }
00204 
00205     // Concat final states of lhs to the initial state of rhs.
00206     hstate_t rhs_i = *rhs.initial().begin();
00207     dst.clear();
00208     rhs.deltac(dst, rhs_i, delta_kind::transitions());
00209     for_all_final_states(f, lhs)
00210     {
00211       typename lhs_t::series_set_elt_t weight = lhs.get_final(*f);
00212       for_all_const_(delta_ret_t, d, dst)
00213         lhs.add_series_transition(*f,
00214                                   map_h[rhs.dst_of(*d)],
00215                                   weight * rhs.label_of(*d));
00216     }
00217 
00218     // Multiply final transitions of lhs by the final multiplicity of the
00219     // initial state of rhs.
00220     typename lhs_t::series_set_elt_t rhs_iw = rhs.get_final(rhs_i);
00221     typename lhs_t::final_support_t support = lhs.final();
00222     for (typename lhs_t::final_iterator next = lhs.final().begin();
00223          next != lhs.final().end();)
00224     {
00225       typename lhs_t::final_iterator f = next;
00226       next++;
00227       lhs.set_final(*f, lhs.get_final(*f) * rhs_iw);
00228     }
00229 
00230     // Set transitions coming from rhs to final if needed.
00231     for_all_const_(map_t, nf, map_h)
00232       if (rhs.is_final(nf->first))
00233         lhs.set_final(nf->second, rhs.get_final(nf->first));
00234   }
00235 
00236   template<typename A, typename T, typename U>
00237   void concat_of_standard_here(Element<A, T>& lhs,
00238                                const Element<A, U>& rhs)
00239   {
00240     // assertion(lhs.structure() == rhs.structure())
00241     do_concat_of_standard_here(lhs.structure(), lhs, rhs);
00242   }
00243 
00244   template<typename A, typename T, typename U>
00245   Element<A, T>
00246   concat_of_standard(const Element<A, T>& lhs,
00247                      const Element<A, U>& rhs)
00248   {
00249     // assertion(lhs.structure() == rhs.structure())
00250     Element<A, T> ret(lhs);
00251     do_concat_of_standard_here(ret.structure(), ret, rhs);
00252     return ret;
00253   }
00254 
00255   /*----------------.
00256   | standard_star.  |
00257   `----------------*/
00258   template <typename A, typename auto_t>
00259   void do_star_of_standard_here(const AutomataBase<A>& ,
00260                                 auto_t& a)
00261   {
00262     TIMER_SCOPED("star_of_standard");
00263     AUTOMATON_TYPES(auto_t);
00264     typedef std::set<htransition_t>             edelta_ret_t;
00265 
00266     edelta_ret_t                        dst;
00267     hstate_t                            new_i = *a.initial().begin();
00268     series_set_elt_t                    out_mult = a.get_final(new_i);
00269 
00270     out_mult.star();
00271     a.deltac(dst, new_i, delta_kind::transitions());
00272     for_all_final_states(f, a)
00273     {
00274       if (*f != new_i)
00275       {
00276         series_set_elt_t f_mult = a.get_final(*f) * out_mult;
00277         a.set_final(*f, f_mult);
00278         for_all_const_(edelta_ret_t, d, dst)
00279           a.add_series_transition(*f, a.dst_of(*d), f_mult * a.label_of(*d));
00280       }
00281     }
00282     a.set_final(new_i, out_mult);
00283   }
00284 
00285   template<typename A, typename T>
00286   void star_of_standard_here(Element<A, T>& a)
00287   {
00288     do_star_of_standard_here(a.structure(), a);
00289   }
00290 
00291   template<typename A, typename T>
00292   Element<A, T>
00293   star_of_standard(const Element<A, T>& a)
00294   {
00295     // assertion(lhs.structure() == rhs.structure())
00296     Element<A, T> ret(a);
00297     do_star_of_standard_here(ret.structure(), ret);
00298     return ret;
00299   }
00300 
00301 } // vcsn
00302 
00303 #endif // ! VCSN_ALGORITHMS_STANDARD_HXX

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