|
Vaucanson 1.4
|
00001 // automata_base.hh: 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, 2007, 2008 The Vaucanson 00006 // Group. 00007 // 00008 // This program is free software; you can redistribute it and/or 00009 // modify it under the terms of the GNU General Public License 00010 // as published by the Free Software Foundation; either version 2 00011 // of the License, or (at your option) any later version. 00012 // 00013 // The complete GNU General Public Licence Notice can be found as the 00014 // `COPYING' file in the root directory. 00015 // 00016 // The Vaucanson Group consists of people listed in the `AUTHORS' file. 00017 // 00018 #ifndef VCSN_AUTOMATA_CONCEPT_AUTOMATA_BASE_HH 00019 # define VCSN_AUTOMATA_CONCEPT_AUTOMATA_BASE_HH 00020 00021 # include <iterator> 00022 # include <vaucanson/design_pattern/design_pattern.hh> 00023 # include <vaucanson/automata/concept/handlers.hh> 00024 # include <vaucanson/automata/concept/delta_kind.hh> 00025 # include <vaucanson/algebra/concept/series_base.hh> 00026 00027 namespace vcsn { 00028 00032 /*-------------------. 00033 | AutomataBase<Self> | 00034 `-------------------*/ 00036 00040 template <typename Self> 00041 struct AutomataBase 00042 : Structure<Self> 00043 { 00044 public: 00046 typedef typename virtual_types<Self>::series_set_t series_set_t; 00048 typedef typename virtual_types<Self>::kind_t kind_t; 00049 00050 protected: 00052 AutomataBase(); 00053 00055 AutomataBase(const AutomataBase& other); 00056 00057 public: 00059 const series_set_t& series() const; 00060 }; 00061 00062 // FIXME: it must be renamed to automaton_impl_traits 00063 // traits for automaton implementation. 00064 template <typename T> 00065 struct automaton_traits 00066 { 00067 typedef undefined_type label_t; 00068 typedef undefined_type series_set_elt_value_t; 00069 typedef undefined_type word_value_t; 00070 typedef undefined_type semiring_elt_value_t; 00071 typedef undefined_type letter_t; 00072 typedef undefined_type tag_t; 00073 typedef undefined_type states_t; 00074 typedef undefined_type state_iterator; 00075 typedef undefined_type transitions_t; 00076 typedef undefined_type transition_iterator; 00077 typedef undefined_type initial_iterator; 00078 typedef undefined_type initial_t; 00079 typedef undefined_type initial_support_t; 00080 typedef undefined_type final_iterator; 00081 typedef undefined_type final_t; 00082 typedef undefined_type final_support_t; 00083 typedef undefined_type geometry_t; 00084 typedef undefined_type hstate_t; 00085 typedef undefined_type htransition_t; 00086 typedef undefined_type delta_iterator; 00087 typedef undefined_type rdelta_iterator; 00088 }; 00089 00090 # define VCSN_MAKE_AUTOMATON_TRAITS(Type) \ 00091 template <typename Kind, \ 00092 typename WordValue, \ 00093 typename WeightValue, \ 00094 typename SeriesValue, \ 00095 typename Letter, \ 00096 typename Tag, \ 00097 typename GeometryCoords> \ 00098 struct automaton_traits<Type<Kind, WordValue, WeightValue, SeriesValue, \ 00099 Letter, Tag, GeometryCoords> > \ 00100 { \ 00101 typedef Type<Kind, WordValue, WeightValue, SeriesValue, \ 00102 Letter, Tag, GeometryCoords> graph_t; \ 00103 typedef typename graph_t::semiring_elt_value_t semiring_elt_value_t; \ 00104 typedef typename graph_t::monoid_elt_value_t monoid_elt_value_t; \ 00105 typedef typename graph_t::word_value_t word_value_t; \ 00106 typedef typename graph_t::series_set_elt_value_t series_set_elt_value_t; \ 00107 typedef typename graph_t::letter_t letter_t; \ 00108 typedef typename graph_t::tag_t tag_t; \ 00109 typedef typename graph_t::geometry_t geometry_t; \ 00110 typedef typename graph_t::label_t label_t; \ 00111 typedef typename graph_t::states_t states_t; \ 00112 typedef typename states_t::iterator state_iterator; \ 00113 typedef typename graph_t::hstate_t hstate_t; \ 00114 typedef typename graph_t::edges_t transitions_t; \ 00115 typedef typename transitions_t::iterator transition_iterator; \ 00116 typedef typename graph_t::htransition_t htransition_t; \ 00117 typedef typename graph_t::initial_t initial_t; \ 00118 typedef typename graph_t::initial_support_t initial_support_t; \ 00119 typedef typename initial_support_t::iterator initial_iterator; \ 00120 typedef typename graph_t::final_t final_t; \ 00121 typedef typename graph_t::final_support_t final_support_t; \ 00122 typedef typename final_support_t::iterator final_iterator; \ 00123 typedef typename graph_t::delta_iterator delta_iterator; \ 00124 typedef typename graph_t::rdelta_iterator rdelta_iterator; \ 00125 } 00126 00127 // traits for generalized automaton implementation. 00128 template <typename Auto> 00129 struct generalized_traits 00130 { 00131 typedef undefined_type automaton_t; 00132 }; 00133 00134 # define VCSN_MAKE_GENERALIZED_AUTOMATON_TRAITS(Type) \ 00135 template <typename Struct, \ 00136 typename Kind, \ 00137 typename WordValue, \ 00138 typename WeightValue, \ 00139 typename SeriesValue, \ 00140 typename Letter, \ 00141 typename Tag, \ 00142 typename GeometryCoords> \ 00143 struct generalized_traits<Element<Struct, Type<Kind, WordValue, \ 00144 WeightValue, SeriesValue, Letter, \ 00145 Tag, GeometryCoords> > > \ 00146 { \ 00147 typedef Element<Struct, Type<Kind, WordValue, WeightValue, SeriesValue, \ 00148 Letter, Tag, GeometryCoords> > Auto_; \ 00149 typedef typename Auto_::series_set_t series_set_t; \ 00150 typedef typename Auto_::kind_t kind_t; \ 00151 typedef typename series_set_t::monoid_t monoid_t; \ 00152 typedef typename Auto_::series_set_elt_t series_set_elt_t; \ 00153 typedef typename series_set_elt_t::monoid_elt_t monoid_elt_t; \ 00154 typedef typename monoid_elt_t::value_t monoid_elt_value_t; \ 00155 typedef typename series_set_elt_t::semiring_elt_t semiring_elt_t; \ 00156 typedef typename semiring_elt_t::value_t semiring_elt_value_t; \ 00157 typedef typename Auto_::value_t::geometry_t geometry_t; \ 00158 typedef vcsn::Element<vcsn::Automata<series_set_t, Kind>, \ 00159 Type<labels_are_series, \ 00160 monoid_elt_value_t, \ 00161 semiring_elt_value_t, \ 00162 rat::exp<monoid_elt_value_t, semiring_elt_value_t>, \ 00163 typename monoid_t::letter_t, \ 00164 NoTag, \ 00165 typename geometry_t::coords_t> \ 00166 > automaton_t; \ 00167 typedef typename automaton_t::hstate_t hstate_t; \ 00168 typedef typename automaton_t::htransition_t htransition_t; \ 00169 } 00170 00171 // traits to construct an automaton type from a rational expression type, 00172 // with a given structural type. 00173 // (the automaton type must be able to hold the value returned by 00174 // standard_of) 00175 // FIXME: there is no rat exp concept, so we put the code here. (maybe it 00176 // should be put here anyway) 00177 template <typename Struct, typename Ratexp> 00178 struct standard_of_traits 00179 { 00180 typedef undefined_type automaton_t; 00181 }; 00182 00183 # define VCSN_MAKE_STANDARD_OF_TRAITS(Type) \ 00184 template <typename W, \ 00185 typename M, \ 00186 typename Tm, \ 00187 typename Tw> \ 00188 struct standard_of_traits<algebra::Series<W, M>, rat::exp<Tm, Tw> > \ 00189 { \ 00190 typedef typename algebra::Series<W, M> series_set_t; \ 00191 typedef typename algebra::polynom<Tm, Tw> \ 00192 series_set_elt_value_t; \ 00193 typedef typename M::letter_t letter_t; \ 00194 typedef typename Type<labels_are_series, Tm, Tw, \ 00195 series_set_elt_value_t, letter_t, \ 00196 NoTag, std::pair<double, double> > \ 00197 automaton_impl_t; \ 00198 typedef Element<Automata<series_set_t, labels_are_series>, automaton_impl_t> \ 00199 automaton_t; \ 00200 } 00201 00202 // Traits to construct misc projections from a structural type and 00203 // an implementation. 00204 template <typename S, typename T> 00205 struct projection_traits 00206 { 00208 typedef undefined_type first_projection_t; 00209 00211 typedef undefined_type second_projection_t; 00212 }; 00213 00214 // Traits to mute an existing graph implementation into a projection 00215 // implementation with TT. 00216 // FIXME: rename to mute_graph_impl_projection_traits 00217 template <typename T, typename TT> 00218 struct mute_graph_impl_traits 00219 { 00221 typedef undefined_type first_projection_t; 00222 00224 typedef undefined_type second_projection_t; 00225 }; 00226 00227 # define VCSN_MAKE_MUTE_GRAPH_IMPL_TRAITS(Type) \ 00228 template <typename Kind, \ 00229 typename WordValue, \ 00230 typename WeightValue, \ 00231 typename SeriesValue, \ 00232 typename Letter, \ 00233 typename Tag, \ 00234 typename GeometryCoords, \ 00235 typename TT> \ 00236 struct mute_graph_impl_traits<Type<Kind, \ 00237 WordValue, \ 00238 WeightValue, \ 00239 SeriesValue, \ 00240 Letter, \ 00241 Tag, \ 00242 GeometryCoords>, TT> \ 00243 { \ 00244 typedef Type<Kind, WordValue, WeightValue, SeriesValue, \ 00245 Letter, Tag, GeometryCoords> graph_t; \ 00246 typedef typename algebra::letter_traits<Letter>:: \ 00247 first_projection_t first_letter_t; \ 00248 typedef typename algebra::letter_traits<Letter>:: \ 00249 second_projection_t second_letter_t; \ 00250 typedef typename TT::first_projection_t::value_t \ 00251 first_monoid_elt_value_t; \ 00252 typedef typename TT::second_projection_t::value_t \ 00253 second_monoid_elt_value_t; \ 00254 typedef typename algebra::mute_series_impl<SeriesValue, WeightValue, \ 00255 first_monoid_elt_value_t>::ret \ 00256 first_series_impl_t; \ 00257 typedef typename algebra::mute_series_impl<SeriesValue, WeightValue, \ 00258 second_monoid_elt_value_t>::ret \ 00259 second_series_impl_t; \ 00260 typedef Type<Kind, first_monoid_elt_value_t, \ 00261 WeightValue, first_series_impl_t, \ 00262 first_letter_t, Tag, GeometryCoords> first_projection_t; \ 00263 typedef Type<Kind, second_monoid_elt_value_t, \ 00264 WeightValue, second_series_impl_t, \ 00265 second_letter_t, Tag, GeometryCoords> second_projection_t; \ 00266 } 00267 00268 // Traits to mute an existing graph implementation into another 00269 // graph implementation with a different word implementation and letter 00270 // implementation. 00271 template <typename G, typename W, typename L> 00272 struct mute_graph_impl_monoid_traits 00273 { 00275 typedef undefined_type ret; 00276 }; 00277 00278 # define VCSN_MAKE_MUTE_GRAPH_IMPL_MONOID_TRAITS(Type) \ 00279 template <typename Kind, \ 00280 typename WordValue, \ 00281 typename WeightValue, \ 00282 typename SeriesValue, \ 00283 typename Letter, \ 00284 typename Tag, \ 00285 typename GeometryCoords, \ 00286 typename W, \ 00287 typename L> \ 00288 struct mute_graph_impl_monoid_traits<Type<Kind, \ 00289 WordValue, \ 00290 WeightValue, \ 00291 SeriesValue, \ 00292 Letter, \ 00293 Tag, \ 00294 GeometryCoords>, W, L> \ 00295 { \ 00296 typedef Type<Kind, WordValue, WeightValue, SeriesValue, \ 00297 Letter, Tag, GeometryCoords> graph_t; \ 00298 typedef typename algebra::mute_series_impl<SeriesValue, WeightValue, \ 00299 W>::ret \ 00300 series_impl_t; \ 00301 typedef Type<Kind, W, \ 00302 WeightValue, series_impl_t, \ 00303 L, Tag, GeometryCoords> ret; \ 00304 } 00305 00306 /*-----------------------------------. 00307 | virtual_types<AutomataBase<Self> > | 00308 `-----------------------------------*/ 00309 00310 template <class S> 00311 struct virtual_types<AutomataBase<S> > 00312 : virtual_types<Structure<S> > 00313 { }; 00314 00315 /*------------------------------------. 00316 | dynamic_traits<AutomataBase<Self> > | 00317 `------------------------------------*/ 00318 template <class S> 00319 struct dynamic_traits<AutomataBase<S> > 00320 : dynamic_traits<Structure<S> > 00321 { }; 00322 00323 /*-----------------------------------. 00324 | MetaElement<AutomataBase<Self>, T> | 00325 `-----------------------------------*/ 00327 00340 // FIXME: Use some of the TYPEDEF_IMPORT macros. 00341 template <typename Self, typename T> 00342 struct MetaElement<AutomataBase<Self>, T> 00343 : MetaElement<Structure<Self>, T> 00344 { 00346 typedef MetaElement<AutomataBase<Self>, T> self_t; 00347 00349 typedef typename AutomataBase<Self>::series_set_t series_set_t; 00350 00352 typedef typename AutomataBase<Self>::kind_t kind_t; 00353 00355 typedef typename automaton_traits<T>::series_set_elt_value_t 00356 series_set_elt_value_t; 00357 00359 typedef Element<series_set_t, series_set_elt_value_t> series_set_elt_t; 00360 00362 typedef typename series_set_t::monoid_t monoid_t; 00363 00365 typedef typename series_set_elt_t::monoid_elt_t monoid_elt_t; 00366 00368 typedef typename monoid_elt_t::value_t monoid_elt_value_t; 00369 00371 typedef typename monoid_t::letter_t letter_t; 00372 00374 typedef typename series_set_t::semiring_t semiring_t; 00375 00377 typedef typename series_set_elt_t::semiring_elt_t semiring_elt_t; 00378 00380 typedef typename series_set_elt_t::semiring_elt_value_t 00381 semiring_elt_value_t; 00382 00384 typedef typename automaton_traits<T>::tag_t tag_t; 00385 00387 typedef typename automaton_traits<T>::label_t label_t; 00388 00390 typedef typename automaton_traits<T>::states_t states_t; 00391 00393 typedef typename automaton_traits<T>::state_iterator state_iterator; 00394 00396 typedef typename automaton_traits<T>::transitions_t transitions_t; 00397 00399 typedef typename automaton_traits<T>::transition_iterator transition_iterator; 00400 00402 typedef typename automaton_traits<T>::initial_support_t initial_support_t; 00403 00405 typedef typename automaton_traits<T>::initial_iterator initial_iterator; 00406 00408 typedef typename automaton_traits<T>::final_support_t final_support_t; 00409 00411 typedef typename automaton_traits<T>::final_iterator final_iterator; 00412 00414 typedef typename automaton_traits<T>::geometry_t geometry_t; 00415 00417 typedef typename automaton_traits<T>::geometry_t::coords_t geometry_coords_t; 00418 00420 typedef typename automaton_traits<T>::hstate_t hstate_t; 00421 typedef typename automaton_traits<T>::htransition_t htransition_t; 00422 00424 typedef typename automaton_traits<T>::delta_iterator delta_iterator; 00425 typedef typename automaton_traits<T>::rdelta_iterator rdelta_iterator; 00426 00428 const series_set_t& series() const; 00429 00431 tag_t& tag(); 00432 00434 const tag_t& tag() const; 00435 00437 geometry_t& geometry(); 00438 00440 const geometry_t& geometry() const; 00441 00443 bool exists() const; 00444 00447 00449 states_t states() const; 00450 00452 transitions_t transitions() const; 00453 00455 initial_support_t initial() const; 00456 00458 final_support_t final() const; 00459 00461 bool is_initial(const hstate_t& state) const; 00462 bool is_initial(unsigned state) const; 00463 00465 bool is_final(const hstate_t& state) const; 00466 bool is_final(unsigned state) const; 00467 00469 void set_initial(const hstate_t& state); 00470 void set_initial(unsigned state); 00471 00473 void set_initial(const hstate_t& state, const series_set_elt_t& m); 00474 void set_initial(unsigned state, const series_set_elt_t& m); 00475 00477 void set_final(const hstate_t& state); 00478 void set_final(unsigned state); 00479 00481 void set_final(const hstate_t& state, const series_set_elt_t& m); 00482 void set_final(unsigned state, const series_set_elt_t& m); 00483 00485 void unset_initial(const hstate_t& state); 00486 void unset_initial(unsigned state); 00487 00489 void unset_final(const hstate_t& state); 00490 void unset_final(unsigned state); 00491 00493 void clear_initial(); 00494 00496 void clear_final(); 00497 00499 Element<series_set_t, series_set_elt_value_t> 00500 get_initial(const hstate_t& state) const; 00501 Element<series_set_t, series_set_elt_value_t> 00502 get_initial(unsigned state) const; 00503 00505 Element<series_set_t, series_set_elt_value_t> 00506 get_final(const hstate_t& state) const; 00507 Element<series_set_t, series_set_elt_value_t> 00508 get_final(unsigned state) const; 00509 00511 hstate_t add_state(); 00512 00514 hstate_t get_state(unsigned state) const; 00515 00518 hstate_t choose_state() const; 00519 00521 htransition_t add_transition(const hstate_t& src, const hstate_t& dst, 00522 const label_t& label); 00523 htransition_t add_transition(unsigned src, unsigned dst, 00524 const label_t& label); 00525 00528 htransition_t add_weighted_transition(const hstate_t& src, const hstate_t& dst, 00529 const semiring_elt_t& w, 00530 const monoid_elt_value_t& m); 00531 htransition_t add_weighted_transition(unsigned src, unsigned dst, 00532 const semiring_elt_t& w, 00533 const monoid_elt_value_t& m); 00534 00536 00539 htransition_t add_series_transition(const hstate_t& src, const hstate_t& dst, 00540 const series_set_elt_t& e); 00541 htransition_t add_series_transition(unsigned src, unsigned dst, 00542 const series_set_elt_t& e); 00543 00545 htransition_t add_spontaneous(const hstate_t& src, const hstate_t& dst, 00546 const semiring_elt_t& w); 00547 00548 htransition_t add_spontaneous(const hstate_t& src, const hstate_t& dst); 00549 00550 htransition_t add_spontaneous(unsigned src, unsigned dst, 00551 const semiring_elt_t& w); 00552 00553 htransition_t add_spontaneous(unsigned src, unsigned dst); 00554 00556 htransition_t add_letter_transition(const hstate_t& src, const hstate_t& dst, 00557 const letter_t& l); 00558 htransition_t add_letter_transition(unsigned src, unsigned dst, 00559 const letter_t& l); 00560 00563 htransition_t add_letter_transition(const hstate_t& src, const hstate_t& dst, 00564 const std::string& l); 00565 htransition_t add_letter_transition(unsigned src, unsigned dst, 00566 const std::string& l); 00567 00569 void update(const htransition_t& e, const label_t& l); 00570 00572 void del_state(const hstate_t& state); 00573 void del_state(unsigned state); 00574 00576 void del_transition(const htransition_t& e); 00577 00579 bool has_state(const hstate_t& state) const; 00580 bool has_state(unsigned state) const; 00581 00583 bool has_transition(const htransition_t& e) const; 00584 00586 hstate_t src_of(const htransition_t& e) const; 00587 00589 hstate_t dst_of(const htransition_t& e) const; 00590 00592 typename automaton_traits<T>::label_t label_of(const htransition_t& e) const; 00593 00595 series_set_elt_t series_of(const htransition_t& e) const; 00596 00598 series_set_elt_value_t series_value_of(const htransition_t& e) const; 00599 00601 bool is_spontaneous(const htransition_t& e) const; 00602 00604 monoid_elt_t word_of(const htransition_t& e) const; 00605 00607 semiring_elt_t weight_of(const htransition_t& e) const; 00608 00610 monoid_elt_value_t word_value_of(const htransition_t& e) const; 00611 00613 00616 letter_t letter_of(const htransition_t& e) const; 00617 00618 00619 protected: 00620 MetaElement(); 00621 MetaElement(const MetaElement& other); 00622 }; 00623 00626 00627 template <typename S, typename St, typename T> 00628 St& op_rout(const AutomataBase<S>& s, St& st, const T& r); 00629 00630 template <typename Auto_> 00631 typename generalized_traits<Auto_>::automaton_t 00632 generalized(const Auto_& from); 00633 } // vcsn 00634 00635 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB 00636 # include <vaucanson/automata/concept/automata_base.hxx> 00637 # endif // VCSN_USE_INTERFACE_ONLY 00638 00639 #endif // ! VCSN_AUTOMATA_CONCEPT_AUTOMATA_BASE_HH
1.7.4