sub_normalize.hxx

Go to the documentation of this file.
00001 // sub_normalize.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_SUB_NORMALIZE_HXX
00018 # define VCSN_ALGORITHMS_SUB_NORMALIZE_HXX
00019 
00029 namespace vcsn {
00030 
00031   /*------------------.
00032   | is_sub_normalized |
00033   `------------------*/
00034 
00035   template <class M1, class M2, class Auto>
00036   bool do_is_sub_normalized(const algebra::FreeMonoidProduct<M1, M2>&,
00037                             const Auto& a)
00038   {
00039     AUTOMATON_TYPES(Auto);
00040     typedef typename series_set_elt_t::support_t support_t;
00041 
00042     for_each_initial_state(i, a)
00043     {
00044       series_set_elt_t label = a.get_initial(*i);
00045       for (typename support_t::const_iterator it = label.supp().begin();
00046            it != label.supp().end(); ++it)
00047         if ((*it).first.size() > 1 || (*it).second.size() > 1)
00048           return false;
00049     }
00050 
00051     for_each_final_state(f, a)
00052     {
00053       series_set_elt_t label = a.get_initial(*f);
00054       for (typename support_t::const_iterator it = label.supp().begin();
00055            it != label.supp().end(); ++it)
00056         if ((*it).first.size() > 1 || (*it).second.size() > 1)
00057           return false;
00058     }
00059 
00060     for_each_transition(e, a)
00061     {
00062       series_set_elt_t label = a.series_of(*e);
00063       for (typename support_t::const_iterator it = label.supp().begin();
00064            it != label.supp().end(); ++it)
00065         if ((*it).first.size() > 1 || (*it).second.size() > 1)
00066           return false;
00067     }
00068 
00069     return true;
00070   }
00071 
00072 
00073   /*--------------.
00074   | sub_normalize |
00075   `--------------*/
00076 
00077   template <class Auto, class Label>
00078   int do_sub_normalize_transition(Auto& a,
00079                                   hstate_t start, hstate_t stop,
00080                                   const Label& label, bool initial, bool final)
00081   {
00082     AUTOMATON_TYPES(Auto);
00083     hstate_t                    s0;
00084     hstate_t                    s1;
00085     typedef typename monoid_elt_t::first_monoid_elt_t first_monoid_elt_t;
00086     typedef typename monoid_elt_t::second_monoid_elt_t
00087       second_monoid_elt_t;
00088     typedef typename monoid_elt_t::first_monoid_elt_value_t
00089       first_monoid_elt_value_t;
00090     typedef typename monoid_elt_t::second_monoid_elt_value_t
00091       second_monoid_elt_value_t;
00092 
00093     first_monoid_elt_value_t m1_ident =
00094       algebra::identity_as<first_monoid_elt_value_t>
00095       ::of(a.structure().series().monoid().first_monoid()).value();
00096     second_monoid_elt_value_t m2_ident =
00097       algebra::identity_as<second_monoid_elt_value_t>
00098       ::of(a.structure().series().monoid().second_monoid()).value();
00099 
00100     semiring_elt_t s_ident =
00101       algebra::identity_as<semiring_elt_value_t>
00102       ::of(a.structure().series().semiring());
00103 
00104 
00105     monoid_elt_t m1(a.structure().series().monoid(), *label.supp().begin());
00106     first_monoid_elt_value_t w1 = m1.value().first;
00107     second_monoid_elt_value_t w2 = m1.value().second;
00108 
00109     int size1 = w1.size();
00110     int size2 = w2.size();
00111     int cpt1 = 0;
00112     int cpt2 = 0;
00113 
00114     unsigned int size = std::max(w1.size(), w2.size());
00115 
00116     if (size > 1)
00117     {
00118       monoid_elt_t m(a.structure().series().monoid());
00119 
00120       semiring_elt_t s = label.get(m1);
00121       series_set_elt_t in_series(a.structure().series());
00122 
00123       m = std::make_pair(cpt1 < size1 ? w1.substr(cpt1++, 1) : m1_ident,
00124                          cpt2 < size2 ? w2.substr(cpt2++, 1) : m2_ident);
00125 
00126       in_series.assoc(m, s);
00127 
00128       if (initial)
00129       {
00130         s0 = a.add_state();
00131         a.set_initial(s0, in_series);
00132         a.unset_initial(stop);
00133         s1 = s0;
00134       }
00135       else
00136       {
00137         s0 = start;
00138         s1 = a.add_state();
00139         a.add_series_transition(s0, s1, in_series);
00140       }
00141 
00142       for (unsigned int i = 1; i < size - 1; ++i)
00143       {
00144         m = std::make_pair(cpt1 < size1 ? w1.substr(cpt1++, 1) : m1_ident,
00145                            cpt2 < size2 ? w2.substr(cpt2++, 1) : m2_ident);
00146         s0 = s1;
00147         s1 = a.add_state();
00148         series_set_elt_t series(a.structure().series());
00149         series.assoc(m, s_ident);
00150         a.add_series_transition(s0, s1, series);
00151       }
00152 
00153       m = std::make_pair(cpt1 < size1 ? w1.substr(cpt1++, 1) : m1_ident,
00154                          cpt2 < size2 ? w2.substr(cpt2++, 1) : m2_ident);
00155 
00156       series_set_elt_t out_series(a.structure().series());
00157       out_series.assoc(m, s_ident);
00158 
00159       if (final)
00160       {
00161         a.unset_final(start);
00162         a.set_final(s1, out_series);
00163       }
00164       else
00165         a.add_series_transition(s1, stop, out_series);
00166 
00167       return 1;
00168     }
00169 
00170     return 0;
00171   }
00172 
00173 
00174 
00175   template <class M1, class M2, class Auto, class Ret>
00176   void do_sub_normalize(const algebra::FreeMonoidProduct<M1, M2>&,
00177                         const Auto& a,
00178                         Ret& res)
00179   {
00180     AUTOMATON_TYPES(Ret);
00181     typedef std::vector<hstate_t> vector_t;
00182 
00183     auto_copy(res, cut_up(a));
00184 
00185     transitions_t transitions = res.transitions();
00186     vector_t i_states; i_states.reserve(res.initial().size());
00187     vector_t f_states; f_states.reserve(res.final().size());
00188 
00189     for_each_initial_state(f, res)
00190       i_states.push_back(*f);
00191     for_each_final_state(i, res)
00192       f_states.push_back(*i);
00193 
00194     for_each_(vector_t, i, i_states)
00195       do_sub_normalize_transition(res, hstate_t(), *i,
00196                                   res.get_initial(*i), true, false);
00197 
00198     for_each_(vector_t, f, f_states)
00199       do_sub_normalize_transition(res, *f, hstate_t(),
00200                                   res.get_final(*f), false, true);
00201 
00202     for_each_(transitions_t, e, transitions)
00203       if (do_sub_normalize_transition(res, res.src_of(*e), res.dst_of(*e),
00204                                       res.series_of(*e), false, false))
00205         res.del_transition(*e);
00206   }
00207 
00208 
00209   /*---------.
00210   | Wrappers |
00211   `---------*/
00212 
00213   template <class S, class T>
00214   Element<S, T>
00215   sub_normalize(const Element<S, T>& a)
00216   {
00217     Element<S, T> res(a.structure());
00218     do_sub_normalize(a.structure().series().monoid(), a, res);
00219 
00220     return res;
00221   }
00222 
00223 
00224   template <class S, class T>
00225   void
00226   sub_normalize(const Element<S, T>& a, Element<S, T>& res)
00227   {
00228     do_sub_normalize(a.structure().series().monoid(), a, res);
00229   }
00230 
00231   template <class S, class T>
00232   bool is_sub_normalized(const Element<S, T>& a)
00233   {
00234     return do_is_sub_normalized(a.structure().series().monoid(), a);
00235   }
00236 
00237 } // ! vcsn
00238 
00239 #endif // ! VCSN_ALGORITHMS_SUB_NORMALIZE_HXX

Generated on Fri Jul 28 12:18:53 2006 for Vaucanson by  doxygen 1.4.6