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

Generated on Sat Jul 29 17:12:58 2006 for Vaucanson by  doxygen 1.4.6