Vaucanson 1.4
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, 2008 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 <typename A, typename AI>
00037   bool is_cut_up(const Element<A, AI>& a)
00038   {
00039     BENCH_TASK_SCOPED("is_cut_up");
00040     typedef Element<A, AI> automaton_t;
00041     AUTOMATON_TYPES(automaton_t);
00042 
00043     for_all_const_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 <typename S, typename T, typename TT, typename Auto, typename 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, ret_);
00063     typedef typename generalized_traits<Ret>::automaton_t gen_automaton_t;
00064     AUTOMATON_TYPES(gen_automaton_t);
00065 
00066     auto_copy(res, a);
00067 
00068     std::map<hstate_t, ret_hstate_t> statemap;
00069 
00070     ret_transitions_t           transitions = res.transitions();
00071 
00072     for_all_(ret_transitions_t, e, transitions)
00073     {
00074       if (! res.series_of(*e).is_finite_app() ||
00075           res.series_of(*e).supp().size() > 1)
00076       {
00077         gen_automaton_t tmp(res.structure());
00078         standard_of(tmp, res.series_of(*e).value());
00079 
00080         for_all_states(s, tmp)
00081           statemap[*s] = res.add_state();
00082 
00083         for_all_initial_states(i, tmp)
00084           res.add_series_transition(res.src_of(*e),
00085                                     statemap[*i],
00086                                     tmp.get_initial(*i));
00087 
00088         for_all_transitions(ed, tmp)
00089           res.add_transition(statemap[tmp.src_of(*ed)],
00090                              statemap[tmp.dst_of(*ed)],
00091                              tmp.label_of(*ed));
00092 
00093         for_all_final_states(f, tmp)
00094           res.add_series_transition(statemap[*f], res.dst_of(*e),
00095                                     tmp.get_final(*f));
00096 
00097         res.del_transition(*e);
00098       }
00099     }
00100   }
00101 
00102 
00103   /*--------------------------------------------------.
00104   | Specialization for label with polynomial series.  |
00105   `--------------------------------------------------*/
00106 
00107   template <typename S, typename T, typename TT, typename Auto, typename Ret>
00108   void do_cut_up(const S&,
00109                  const algebra::polynom<T, TT>&,
00110                  const Auto& a,
00111                  Ret& res)
00112   {
00113     AUTOMATON_TYPES(Ret);
00114     typedef typename Ret::series_set_elt_t::support_t support_t;
00115     int size;
00116 
00117     auto_copy(res, a);
00118 
00119     transitions_t transitions = res.transitions();
00120 
00121     for_all_(transitions_t, e, transitions)
00122     {
00123       series_set_elt_t label(res.structure().series());
00124       label = res.series_of(*e);
00125 
00126       if ((size = label.supp().size()) > 1)
00127       {
00128         typename support_t::const_iterator m = label.supp().begin();
00129         for (int i = 0; i < size; ++i, ++m)
00130         {
00131           series_set_elt_t series(res.structure().series());
00132           series.assoc(*m, label.get(*m));
00133           res.add_series_transition(res.src_of(*e),
00134                                     res.dst_of(*e),
00135                                     series);
00136         }
00137 
00138         res.del_transition(*e);
00139       }
00140     }
00141   }
00142 
00143 
00144   /*---------.
00145   | Wrappers |
00146   `---------*/
00147 
00148   template <typename A, typename AI>
00149   void
00150   cut_up(const Element<A, AI>& a, Element<A, AI>& res)
00151   {
00152     BENCH_TASK_SCOPED("cut_up");
00153     typedef typename Element<A, AI>::series_set_elt_t::value_t series_impl_t;
00154     do_cut_up(a.structure(), SELECT(series_impl_t), a, res);
00155   }
00156 
00157 
00158   template <typename A, typename AI>
00159   Element<A, AI>
00160   cut_up(const Element<A, AI>& a)
00161   {
00162     Element<A, AI> res(a.structure());
00163     cut_up(a, res);
00164     return res;
00165   }
00166 
00167 
00168   template <typename A, typename AI>
00169   void
00170   cut_up_here(Element<A, AI>& a)
00171   {
00172     a = cut_up(a);
00173   }
00174 
00175 
00176 } // ! vcsn
00177 
00178 
00179 #endif // ! VCSN_ALGORITHMS_CUT_UP_HXX