cut_up.hxx

Go to the documentation of this file.
00001 // cut_up.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2005, 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_CUT_UP_HXX
00018 # define VCSN_ALGORITHMS_CUT_UP_HXX
00019 
00029 namespace vcsn {
00030 
00031 
00032   /*----------------------------------.
00033   | Check if an automaton is cut up.  |
00034   `----------------------------------*/
00035 
00036   template <class S, class T>
00037   bool is_cut_up(const Element<S, T>& a)
00038   {
00039     TIMER_SCOPED("is_cut_up");
00040     typedef Element<S, T> automaton_t;
00041     AUTOMATON_TYPES(automaton_t);
00042 
00043     for_all_transitions(e, a)
00044       if (! a.series_of(*e).is_finite_app() ||
00045           a.series_of(*e).supp().size() > 1)
00046         return false;
00047 
00048     return true;
00049   }
00050 
00051 
00052   /*------------------------------------------------.
00053   | Specialization for label with rational series.  |
00054   `------------------------------------------------*/
00055 
00056   template <class S, class T, class TT, class Auto, class Ret>
00057   void do_cut_up(const AutomataBase<S>&,
00058                  const rat::exp<T, TT>&,
00059                  const Auto& a,
00060                  Ret& res)
00061   {
00062     AUTOMATON_TYPES(Ret);
00063     typedef typename generalized_traits<Ret>::automaton_t gen_automaton_t;
00064 
00065     auto_copy(res, a);
00066 
00067     std::map<hstate_t, hstate_t> statemap;
00068 
00069     transitions_t               transitions = res.transitions();
00070 
00071     for_all_(transitions_t, e, transitions)
00072     {
00073       if (! res.series_of(*e).is_finite_app() ||
00074           res.series_of(*e).supp().size() > 1)
00075       {
00076         gen_automaton_t tmp(res.structure());
00077         standard_of(tmp, res.series_of(*e).value());
00078 
00079         for_all_states(s, tmp)
00080           statemap[*s] = res.add_state();
00081 
00082         for_all_initial_states(i, tmp)
00083           res.add_series_transition(res.src_of(*e),
00084                                     statemap[*i],
00085                                     tmp.get_initial(*i));
00086 
00087         for_all_transitions(ed, tmp)
00088           res.add_transition(statemap[tmp.src_of(*ed)],
00089                              statemap[tmp.dst_of(*ed)],
00090                              tmp.label_of(*ed));
00091 
00092         for_all_final_states(f, tmp)
00093           res.add_series_transition(statemap[*f], res.dst_of(*e),
00094                                     tmp.get_final(*f));
00095 
00096         res.del_transition(*e);
00097       }
00098     }
00099   }
00100 
00101 
00102   /*--------------------------------------------------.
00103   | Specialization for label with polynomial series.  |
00104   `--------------------------------------------------*/
00105 
00106   template <class S, class T, class TT, class Auto, class Ret>
00107   void do_cut_up(const S&,
00108                  const algebra::polynom<T, TT>&,
00109                  const Auto& a,
00110                  Ret& res)
00111   {
00112     AUTOMATON_TYPES(Ret);
00113     typedef typename Ret::series_set_elt_t::support_t support_t;
00114     int size;
00115 
00116     auto_copy(res, a);
00117 
00118     transitions_t transitions = res.transitions();
00119 
00120     for_all_(transitions_t, e, transitions)
00121     {
00122       series_set_elt_t label(res.structure().series());
00123       label = res.series_of(*e);
00124 
00125       if ((size = label.supp().size()) > 1)
00126       {
00127         typename support_t::const_iterator m = label.supp().begin();
00128         for (int i = 0; i < size; ++i, ++m)
00129         {
00130           series_set_elt_t series(res.structure().series());
00131           series.assoc(*m, label.get(*m));
00132           res.add_series_transition(res.src_of(*e),
00133                                     res.dst_of(*e),
00134                                     series);
00135         }
00136 
00137         res.del_transition(*e);
00138       }
00139     }
00140   }
00141 
00142 
00143   /*---------.
00144   | Wrappers |
00145   `---------*/
00146 
00147   template <class S, class T>
00148   void
00149   cut_up(const Element<S, T>& a, Element<S, T>& res)
00150   {
00151     TIMER_SCOPED("cut_up");
00152     typedef typename Element<S, T>::series_set_elt_t::value_t series_impl_t;
00153     do_cut_up(a.structure(), SELECT(series_impl_t), a, res);
00154   }
00155 
00156 
00157   template <class S, class T>
00158   Element<S, T>
00159   cut_up(const Element<S, T>& a)
00160   {
00161     Element<S, T> res(a.structure());
00162     cut_up(a, res);
00163     return res;
00164   }
00165 
00166 
00167   template <class S, class T>
00168   void
00169   cut_up_here(Element<S, T>& a)
00170   {
00171     a = cut_up(a);
00172   }
00173 
00174 
00175 } // ! vcsn
00176 
00177 
00178 #endif // ! VCSN_ALGORITHMS_CUT_UP_HXX

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