automata_ops.hxx

00001 // automata_ops.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 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_AUTOMATA_CONCEPT_AUTOMATA_OPS_HXX
00018 # define VCSN_AUTOMATA_CONCEPT_AUTOMATA_OPS_HXX
00019 
00020 # include <iterator>
00021 # include <set>
00022 # include <vaucanson/misc/random.hh>
00023 # include <vaucanson/misc/contract.hh>
00024 # include <vaucanson/algebra/concept/series_base.hh>
00025 
00026 namespace vcsn {
00027 
00028 #define AutoType(Type)                          \
00029   typename Element<S, T>::Type
00030 
00031   template <class S, class T>
00032   const typename automaton_traits<T>::tag_t&
00033   op_get_tag(const AutomataBase<S>&, const T& v)
00034   {
00035     return v.tag();
00036   }
00037 
00038   template <class S, class T>
00039   typename automaton_traits<T>::tag_t&
00040   op_get_tag(const AutomataBase<S>&, T& v)
00041   {
00042     return v.tag();
00043   }
00044 
00045   template <class S, class T>
00046   const typename automaton_traits<T>::geometry_t&
00047   op_get_geometry(const AutomataBase<S>&, const T& v)
00048   {
00049     return v.geometry();
00050   }
00051 
00052   template <class S, class T>
00053   typename automaton_traits<T>::geometry_t&
00054   op_get_geometry(const AutomataBase<S>&, T& v)
00055   {
00056     return v.geometry();
00057   }
00058 
00059   template <class S, class T>
00060   bool
00061   op_exists(const AutomataBase<S>& s, const T& v)
00062   {
00063     return v.exists(s);
00064   }
00065 
00066   template <class S, class T>
00067   typename automaton_traits<T>::states_t
00068   op_states(const AutomataBase<S>&, const T& v)
00069   {
00070     return v.states();
00071   }
00072 
00073   template <class S, class T>
00074   typename automaton_traits<T>::transitions_t
00075   op_transitions(const AutomataBase<S>&, const T& v)
00076   {
00077     return v.edges();
00078   }
00079 
00080   template <class S, class T>
00081   typename automaton_traits<T>::initial_support_t
00082   op_initial(const AutomataBase<S>&, const T& v)
00083   {
00084     return v.initial();
00085   }
00086 
00087   template <class S, class T>
00088   typename automaton_traits<T>::final_support_t
00089   op_final(const AutomataBase<S>&, const T& v)
00090   {
00091     return v.final();
00092   }
00093 
00094   template <class S, class T>
00095   void
00096   op_set_initial(const AutomataBase<S>& ss, T& v,
00097                  hstate_t state,
00098                  const AutoType(series_set_elt_t)& s)
00099   {
00100     typedef
00101       typename Element<S, T>::series_set_elt_value_t series_set_elt_value_t;
00102     v.set_initial(state,
00103                   s.value(),
00104                   zero_value(ss.series(),
00105                              SELECT(series_set_elt_value_t)));
00106   }
00107 
00108   template <class S, class T>
00109   typename Element<S, T>::series_set_elt_t
00110   op_get_initial(const AutomataBase<S>& s,
00111                  const T& v,
00112                  hstate_t state)
00113   {
00114     return typename Element<S, T>::series_set_elt_t
00115       (s.series(),
00116        v.get_initial(state,
00117                      zero_value(s.series(),
00118                                 SELECT(AutoType(series_set_elt_value_t)))));
00119   }
00120 
00121   template <class S, class T>
00122   void
00123   op_set_final(const AutomataBase<S>& ss, T& v,
00124                hstate_t state,
00125                const typename Element<S, T>::series_set_elt_t& s)
00126   {
00127     v.set_final(state,
00128                 s.value(),
00129                 zero_value(ss.series(),
00130                            SELECT(AutoType(series_set_elt_value_t))));
00131   }
00132 
00133   template <class S, class T>
00134   typename Element<S, T>::series_set_elt_t
00135   op_get_final(const AutomataBase<S>& s,
00136                const T& v,
00137                hstate_t state)
00138   {
00139     return typename Element<S, T>::series_set_elt_t
00140       (s.series(),
00141        v.get_final(state,
00142                    zero_value(s.series(),
00143                               SELECT(AutoType(series_set_elt_value_t)))));
00144   }
00145 
00146   template <class S, class T>
00147   void
00148   op_clear_initial(const AutomataBase<S>&, T& v)
00149   {
00150     return v.clear_initial();
00151   }
00152 
00153   template <class S, class T>
00154   void
00155   op_clear_final(const AutomataBase<S>&, T& v)
00156   {
00157     return v.clear_final();
00158   }
00159 
00160   template <class S, class T>
00161   hstate_t
00162   op_add_state(const AutomataBase<S>&, T& v)
00163   {
00164     return v.add_state();
00165   }
00166 
00167   template <class S, class T>
00168   hstate_t
00169   op_choose_state(const AutomataBase<S>& s, const T& v)
00170   {
00171     typedef typename automaton_traits<T>::states_t states_t;
00172     typedef typename states_t::iterator state_iterator;
00173     const states_t& st = op_states(s, v);
00174     assertion(st.size() > 0);
00175     int n = misc::random::generate(0, int(st.size() - 1));
00176     state_iterator ss = st.begin();
00177     for (; n > 0; --n)
00178       ++ss;
00179     return *ss;
00180   }
00181 
00182   template <class S, class T>
00183   htransition_t
00184   op_add_transition(const AutomataBase<S>&, T& v,
00185                     hstate_t from,
00186                     hstate_t to,
00187                     const typename Element<S, T>::label_t& label)
00188   {
00189     return v.add_edge(from, to, label);
00190   }
00191 
00192   template<class S, class T>
00193   htransition_t
00194   op_add_weighted_transition(const AutomataBase<S>& s, T& v,
00195                              hstate_t from,
00196                              hstate_t to,
00197                              const typename Element<S, T>::semiring_elt_t& w,
00198                              const typename Element<S, T>::monoid_elt_value_t& m)
00199   {
00200     typename Element<S, T>::series_set_elt_t series (s.series());
00201     series.assoc(m, w.value());
00202     return op_add_series_transition(s, v, from, to, series);
00203   }
00204 
00205   template <class S, class T>
00206   htransition_t
00207   op_add_series_transition(const AutomataBase<S>& s, T& v,
00208                            hstate_t from,
00209                            hstate_t to,
00210                            const typename Element<S, T>::series_set_elt_t& l)
00211   {
00212     return op_add_transition(s, v, from, to, l.value());
00213   }
00214 
00215   template <class S, class T>
00216   htransition_t
00217   op_add_spontaneous(const AutomataBase<S>& s, T& v,
00218                      hstate_t from,
00219                      hstate_t to,
00220                      const typename Element<S, T>::semiring_elt_t& w)
00221   {
00222     AutoType(series_set_elt_t) ss(s.series());
00223     ss.assoc(algebra::identity_as<AutoType(monoid_elt_value_t)>::
00224              of(s.series().monoid()), w);
00225     return op_add_series_transition(s, v, from, to, ss);
00226   }
00227 
00228   template <class S, class T>
00229   htransition_t
00230   op_add_letter_transition(const AutomataBase<S>& s, T& v,
00231                            hstate_t from,
00232                            hstate_t to,
00233                            const typename Element<S, T>::letter_t& l)
00234   {
00235     return op_add_transition(s, v, from, to, l);
00236   }
00237 
00238   template <class S, class T>
00239   void
00240   op_update(const AutomataBase<S>&, T& v,
00241             htransition_t  e,
00242             const AutoType(label_t)& l)
00243   {
00244     // FIXME: test that l != 0.
00245     v.update(e, l);
00246   }
00247 
00248   template <class S, class T>
00249   void
00250   op_del_state(const AutomataBase<S>&, T& v,
00251                hstate_t s)
00252   {
00253     v.del_state(s);
00254   }
00255 
00256   template <class S, class T>
00257   void
00258   op_del_transition(const AutomataBase<S>&, T& v,
00259                     htransition_t e)
00260   {
00261     v.del_edge(e);
00262   }
00263 
00264   template <class S, class T>
00265   bool
00266   op_has_state(const AutomataBase<S>&, const T& v,
00267                hstate_t s)
00268   {
00269     return v.has_state(s);
00270   }
00271 
00272   template <class S, class T>
00273   bool
00274   op_has_transition(const AutomataBase<S>&, const T& v,
00275                     htransition_t e)
00276   {
00277     return v.has_edge(e);
00278   }
00279 
00280   template <class S, class T>
00281   hstate_t
00282   op_src_of(const AutomataBase<S>&, const T& v,
00283             htransition_t e)
00284   {
00285     return v.src_of(e);
00286   }
00287 
00288   template <class S, class T>
00289   hstate_t
00290   op_dst_of(const AutomataBase<S>&, const T& v,
00291             htransition_t e)
00292   {
00293     return v.dst_of(e);
00294   }
00295 
00296   template <class S, class T>
00297   typename Element<S, T>::label_t
00298   op_label_of(const AutomataBase<S>&, const T& v,
00299               htransition_t e)
00300   {
00301     return v.label_of(e);
00302   }
00303 
00304   template <class S, class T>
00305   const typename Element<S, T>::series_set_elt_t
00306   op_series_of(const AutomataBase<S>& s, const T& v,
00307                htransition_t e)
00308   {
00309     return typename Element<S, T>::series_set_elt_t
00310       (s.series(),
00311        v.label_of(e));
00312   }
00313 
00314   template <class S, class T>
00315   typename Element<S, T>::series_set_elt_value_t
00316   op_series_value_of(const AutomataBase<S>& s, const T& v,
00317                      htransition_t e)
00318   {
00319     return op_series_of(s, v, e).value();
00320   }
00321 
00322   template <class S, class T>
00323   typename Element<S, T>::monoid_elt_t
00324   op_word_of(const AutomataBase<S>& s, const T& v,
00325              htransition_t e)
00326   {
00327     return typename Element<S, T>::monoid_elt_t
00328       (s.series().monoid(),
00329        v.label_of(e));
00330   }
00331 
00332   template <class S, class T>
00333   typename Element<S, T>::semiring_elt_t
00334   op_weight_of(const AutomataBase<S>& s, const T& v,
00335                htransition_t e)
00336   {
00337     return op_series_of(s, v, e).get(op_word_of(s, v, e));
00338   }
00339 
00340   template <class S, class T>
00341   typename Element<S, T>::monoid_elt_value_t
00342   op_word_value_of(const AutomataBase<S>& s, const T& v,
00343                    htransition_t e)
00344   {
00345     return op_word_of(s, v, e).value();
00346   }
00347 
00348   template <class S, class T>
00349   typename Element<S, T>::letter_t
00350   op_letter_of(const AutomataBase<S>&, const T& v,
00351                htransition_t e)
00352   {
00353     return v.label_of(e);
00354   }
00355 
00356   template <class S, class T>
00357   bool
00358   op_is_spontaneous(const AutomataBase<S>& s, const T& v,
00359                     htransition_t e)
00360   {
00361     return (op_series_of(s, v, e) ==
00362             algebra::identity_as<AutoType(series_set_elt_value_t)>::of(s.series()));
00363   }
00364 
00365   struct always_true
00366   {
00367       bool operator()(htransition_t) const
00368       {
00369         return true;
00370       }
00371   };
00372 
00373   template <class S, class T, class Letter>
00374   class letter_query
00375   {
00376     public:
00377       letter_query(const S* s, const T* v, const Letter& l) :
00378         s_ (s),
00379         v_ (v),
00380         w_ (s->series().monoid(), l)
00381       {
00382       }
00383 
00384       bool operator()(htransition_t e) const
00385       {
00386         return (op_series_get(s_->series(),
00387                               op_series_of(*s_, *v_, e).value(),
00388                               w_.value())
00389                 != algebra::zero_as<AutoType(semiring_elt_value_t)>
00390                 ::of(s_->series().semiring()));
00391       }
00392 
00393     private:
00394       const S*                  s_;
00395       const T*                  v_;
00396       AutoType(monoid_elt_t)    w_;
00397   };
00398 
00399   template <class S, class T, class Letter>
00400   letter_query<S, T, Letter>
00401   make_letter_query(const S& s, const T& t, const Letter& l)
00402   {
00403     return letter_query<S, T, Letter> (&s, &t, l);
00404   }
00405 
00406   template <class S, class T>
00407   class spontaneous_query
00408   {
00409     public:
00410       spontaneous_query(const S& s, const T& v):
00411         s_(s),
00412         v_(v)
00413       {}
00414 
00415       bool operator()(htransition_t e) const
00416       {
00417         return (op_series_of(s_, v_, e)
00418                 .get(algebra::identity_as<AutoType(monoid_elt_value_t)>::of
00419                      (s_.series().monoid()))
00420                 != algebra::zero_as<AutoType(semiring_elt_value_t)>
00421                 ::of(s_.series().semiring()));
00422       }
00423 
00424     private:
00425       const S& s_;
00426       const T& v_;
00427   };
00428 
00429   template <class S, class T>
00430   spontaneous_query<S, T> make_spontaneous_query(const S& s,
00431                                                  const T& t)
00432   {
00433     return spontaneous_query<S, T>(s.self(), t);
00434   }
00435 
00436     /*---------.
00437     | Deltas.  |
00438     `---------*/
00439 
00440   template <class S, class T,
00441             typename OutputIterator, typename Kind>
00442   void op_delta(const AutomataBase<S>&, const T& v,
00443                 OutputIterator res,
00444                 hstate_t from,
00445                 delta_kind::kind<Kind> k)
00446   {
00447     v.delta(res, from, always_true(), k);
00448   }
00449 
00450   template <class S, class T,
00451             typename OutputIterator, typename L, typename Kind>
00452   void op_delta(const AutomataBase<S>&, const T& v,
00453                 OutputIterator res,
00454                 hstate_t from,
00455                 const L& query,
00456                 delta_kind::kind<Kind> k)
00457   {
00458     v.delta(res, from, query, k);
00459   }
00460 
00461   template <class S, class T,
00462             typename OutputIterator, typename L, typename Kind>
00463   void op_letter_delta(const AutomataBase<S>& s, const T& v,
00464                        OutputIterator res,
00465                        hstate_t from,
00466                        const L& letter,
00467                        delta_kind::kind<Kind> k)
00468   {
00469     v.delta(res, from, make_letter_query(s.self(), v, letter), k);
00470   }
00471 
00472   template <class S, class T,
00473             typename OutputIterator, typename Kind>
00474   void op_spontaneous_delta(const AutomataBase<S>& s,
00475                             const T& v,
00476                             OutputIterator res,
00477                             hstate_t from,
00478                             delta_kind::kind<Kind> k)
00479   {
00480     v.delta (res, from, make_spontaneous_query(s.self(), v), k);
00481   }
00482 
00483     /*----------.
00484     | Deltacs.  |
00485     `----------*/
00486 
00487   template <class S, class T,
00488             typename Container, typename Kind>
00489   void op_deltac(const AutomataBase<S>&, const T& v,
00490                  Container& res, hstate_t from, delta_kind::kind<Kind> k)
00491   {
00492     std::insert_iterator<Container> i(res, res.begin());
00493     v.delta(i, from, always_true(), k);
00494   }
00495 
00496   template <class S, class T,
00497             typename Container, typename L, typename Kind>
00498   void op_deltac(const AutomataBase<S>&,
00499                  const T& v,
00500                  Container& res,
00501                  hstate_t from,
00502                  const L& query,
00503                  delta_kind::kind<Kind> k)
00504   {
00505     std::insert_iterator<Container> i(res, res.begin());
00506     v.delta(i, from, query, k);
00507   }
00508 
00509 
00510   template <class S, class T,
00511             typename Container, typename L, typename Kind>
00512   void op_letter_deltac(const AutomataBase<S>& s,
00513                         const T& v,
00514                         Container& res,
00515                         hstate_t from,
00516                         const L& letter,
00517                         delta_kind::kind<Kind> k)
00518   {
00519     std::insert_iterator<Container> i(res, res.begin());
00520     v.delta(i, from, make_letter_query(s.self(), v, letter), k);
00521   }
00522 
00523   template <class S, class T, class Container, typename Kind>
00524   void op_spontaneous_deltac(const AutomataBase<S>& s,
00525                              const T& v,
00526                              Container& res,
00527                              hstate_t from,
00528                              delta_kind::kind<Kind> k)
00529   {
00530     std::insert_iterator<Container> i(res, res.begin());
00531     v.delta (i, from, make_spontaneous_query(s.self(), v), k);
00532   }
00533 
00534     /*----------.
00535     | Deltafs.  |
00536     `----------*/
00537 
00538   template <class S, class T,
00539             typename Functor, typename Kind>
00540   void op_deltaf(const AutomataBase<S>&, const T& v,
00541                  Functor& fun, hstate_t from, delta_kind::kind<Kind> k)
00542   {
00543     v.deltaf(fun, from, always_true(), k);
00544   }
00545 
00546   template <class S, class T,
00547             typename Functor, typename L, typename Kind>
00548   void op_deltaf(const AutomataBase<S>&,
00549                  const T& v,
00550                  Functor& fun,
00551                  hstate_t from,
00552                  const L& query,
00553                  delta_kind::kind<Kind> k)
00554   {
00555     v.deltaf(fun, from, query, k);
00556   }
00557 
00558 
00559   template <class S, class T,
00560             typename Functor, typename L, typename Kind>
00561   void op_letter_deltaf(const AutomataBase<S>& s,
00562                         const T& v,
00563                         Functor& fun,
00564                         hstate_t from,
00565                         const L& letter,
00566                         delta_kind::kind<Kind> k)
00567   {
00568     v.deltaf(fun, from, make_letter_query(s.self(), v, letter), k);
00569   }
00570 
00571   template <class S, class T, class Functor, typename Kind>
00572   void op_spontaneous_deltaf(const AutomataBase<S>& s,
00573                              const T& v,
00574                              Functor& fun,
00575                              hstate_t from,
00576                              delta_kind::kind<Kind> k)
00577   {
00578     v.deltaf(fun, from, make_spontaneous_query(s.self(), v), k);
00579   }
00580 
00581 
00582     /*-----------------.
00583     | Reverse deltas.  |
00584     `-----------------*/
00585 
00586   template <class S, class T,
00587             typename OutputIterator, typename Kind>
00588   void op_rdelta(const AutomataBase<S>&, const T& v,
00589                  OutputIterator res,
00590                  hstate_t from,
00591                  delta_kind::kind<Kind> k)
00592   {
00593     v.rdelta (res, from, always_true(), k);
00594   }
00595 
00596   template <class S, class T,
00597             typename OutputIterator, typename L, typename Kind>
00598   void op_rdelta(const AutomataBase<S>&, const T& v,
00599                  OutputIterator res,
00600                  hstate_t from,
00601                  const L& query,
00602                  delta_kind::kind<Kind> k)
00603   {
00604     v.rdelta(res, from, query, k);
00605   }
00606 
00607   template <class S, class T,
00608             typename OutputIterator, typename L, typename Kind>
00609   void op_letter_rdelta(const AutomataBase<S>& s, const T& v,
00610                         OutputIterator res,
00611                         hstate_t from,
00612                         const L& letter,
00613                         delta_kind::kind<Kind> k)
00614   {
00615     v.rdelta(res, from, make_letter_query(s.self(), v, letter), k);
00616   }
00617 
00618   template <class S, class T,
00619             typename OutputIterator, typename Kind>
00620   void op_spontaneous_rdelta(const AutomataBase<S>& s, const T& v,
00621                              OutputIterator res,
00622                              hstate_t from,
00623                              delta_kind::kind<Kind> k)
00624   {
00625     v.rdelta(res, from, make_spontaneous_query(s.self(), v), k);
00626   }
00627 
00628     /*------------------.
00629     | Reverse deltacs.  |
00630     `------------------*/
00631 
00632   template <class S, class T,
00633             typename Container, typename Kind>
00634   void op_rdeltac(const AutomataBase<S>&, const T& v,
00635                   Container& res, hstate_t from, delta_kind::kind<Kind> k)
00636   {
00637     std::insert_iterator<Container> i(res, res.begin());
00638     v.rdelta(i, from, always_true(), k);
00639   }
00640 
00641   template <class S, class T,
00642             typename Container, typename L, typename Kind>
00643   void op_rdeltac(const AutomataBase<S>&,
00644                   const T& v,
00645                   Container& res,
00646                   hstate_t from,
00647                   const L& query,
00648                   delta_kind::kind<Kind> k)
00649   {
00650     std::insert_iterator<Container> i(res, res.begin());
00651     v.rdelta(i, from, query, k);
00652   }
00653 
00654 
00655   template <class S, class T,
00656             typename Container, typename L, typename Kind>
00657   void op_letter_rdeltac(const AutomataBase<S>& s,
00658                          const T& v,
00659                          Container& res,
00660                          hstate_t from,
00661                          const L& letter,
00662                          delta_kind::kind<Kind> k)
00663   {
00664     std::insert_iterator<Container> i(res, res.begin());
00665     v.rdelta (i, from, make_letter_query(s.self(), v, letter), k);
00666   }
00667 
00668   template <class S, class T, class  Container, typename Kind>
00669   void op_spontaneous_rdeltac(const AutomataBase<S>& s,
00670                               const T& v,
00671                               Container& res,
00672                               hstate_t from,
00673                               delta_kind::kind<Kind> k)
00674   {
00675     std::insert_iterator<Container> i(res, res.begin());
00676     v.rdelta (i, from, make_spontaneous_query(s.self(), v), k);
00677   }
00678 
00679     /*------------------.
00680     | Reverse Deltafs.  |
00681     `------------------*/
00682 
00683   template <class S, class T,
00684             typename Functor, typename Kind>
00685   void op_rdeltaf(const AutomataBase<S>&, const T& v,
00686                   Functor& fun, hstate_t from, delta_kind::kind<Kind> k)
00687   {
00688     v.rdeltaf(fun, from, always_true(), k);
00689   }
00690 
00691   template <class S, class T,
00692             typename Functor, typename L, typename Kind>
00693   void op_rdeltaf(const AutomataBase<S>&,
00694                   const T& v,
00695                   Functor& fun,
00696                   hstate_t from,
00697                   const L& query,
00698                   delta_kind::kind<Kind> k)
00699   {
00700     v.rdeltaf(fun, from, query, k);
00701   }
00702 
00703 
00704   template <class S, class T,
00705             typename Functor, typename L, typename Kind>
00706   void op_letter_rdeltaf(const AutomataBase<S>& s,
00707                          const T& v,
00708                          Functor& fun,
00709                          hstate_t from,
00710                          const L& letter,
00711                          delta_kind::kind<Kind> k)
00712   {
00713     v.rdeltaf(fun, from, make_letter_query(s.self(), v, letter), k);
00714   }
00715 
00716   template <class S, class T, class Functor, typename Kind>
00717   void op_spontaneous_rdeltaf(const AutomataBase<S>& s,
00718                               const T& v,
00719                               Functor& fun,
00720                               hstate_t from,
00721                               delta_kind::kind<Kind> k)
00722   {
00723     v.rdeltaf(fun, from, make_spontaneous_query(s.self(), v), k);
00724   }
00725 
00726 
00727 } // vcsn
00728 
00729 # undef AutoType
00730 
00731 #endif // ! VCSN_AUTOMATA_CONCEPT_AUTOMATA_OPS_HXX

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