00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018 #ifndef VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_IMPL_HH_
00019 # define VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_IMPL_HH_
00020 # include <boost/dynamic_bitset.hpp>
00021 # include <boost/shared_ptr.hpp>
00022
00023 # include <vaucanson/algebra/implementation/series/rat/exp.hh>
00024 # include <vaucanson/automata/implementation/bmig/vgraph_container.hh>
00025 # include <vaucanson/automata/implementation/bmig/bmig_handlers.hh>
00026 # include <vaucanson/automata/implementation/bmig/iterator.hh>
00027 # include <vaucanson/automata/concept/automata_base.hh>
00028 # include <vaucanson/automata/concept/automata.hh>
00029 # include <vaucanson/automata/concept/automata_kind.hh>
00030 # include <vaucanson/automata/implementation/bmig/bmig_support.hh>
00031 # include <vaucanson/automata/concept/transducer_base.hh>
00032 # include <vaucanson/automata/concept/smart_label.hh>
00033 # include <vaucanson/automata/implementation/kind_adapter.hh>
00034 # include <vaucanson/automata/implementation/geometry.hh>
00035 # include <vaucanson/automata/concept/tags.hh>
00036 # include <vaucanson/misc/hash.hh>
00037 # include <vaucanson/automata/implementation/bmig/initial_value.hh>
00038 # include <vaucanson/automata/implementation/bmig/graphcontainer.hh>
00039 # include <vaucanson/automata/implementation/bmig/edge_value.hh>
00040 # include <vaucanson/automata/implementation/bmig/bmig_functors.hh>
00041 # include <vaucanson/automata/implementation/bmig/initial_container.hh>
00042
00043 namespace vcsn
00044 {
00045 namespace bmig
00046 {
00047
00048
00049 template <typename Kind, typename WordValue, typename WeightValue,
00050 typename SeriesValue, typename Letter, typename Tag, typename GeometryCoords>
00051 class Graph
00052 {
00053 public:
00054
00055
00056
00057
00058
00059 typedef Graph<Kind, WordValue, WeightValue,
00060 SeriesValue, Letter, Tag, GeometryCoords>
00061 self_t;
00062
00063 typedef WeightValue semiring_elt_value_t;
00064 typedef WordValue monoid_elt_value_t;
00065 typedef WordValue word_value_t;
00066 typedef SeriesValue series_set_elt_value_t;
00067 typedef Letter letter_t;
00068 typedef Tag tag_t;
00069
00070 typedef typename LabelOf<Kind, WordValue, WeightValue,
00071 SeriesValue, Letter>::ret label_t;
00072
00073
00074 typedef label_t
00075 hlabel_t;
00076
00077 typedef boost::shared_ptr<std::size_t> state_t;
00078
00079
00080 typedef handler<state_h, state_t> hstate_t;
00081
00082 typedef EdgeValue<state_t, label_t> edge_data_t;
00083
00084
00085 typedef GraphContainer<state_t, label_t, edge_data_t> graph_data_t;
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098 typedef typename graph_data_t::iterator
00099 edges_iterator;
00100 typedef handler<transition_h, edges_iterator> htransition_t;
00101 typedef htransition_t hedge_t;
00102
00103
00104 typedef VGraphContainer<edges_iterator, graph_data_t, htransition_t> edges_t;
00105 typedef std::vector<state_t> states_data_t;
00106 typedef misc::Support<states_data_t> states_t;
00107
00108
00109
00110 typedef InitialValue<state_t, series_set_elt_value_t>
00111 initial_value_t;
00112 typedef initial_value_t final_value_t;
00113 typedef InitialContainer<initial_value_t, state_t>
00114 initial_container_t;
00115
00116 typedef typename initial_container_t::Type initial_t;
00117 typedef initial_t final_t;
00118
00119 typedef misc::Support<initial_container_t> initial_support_t;
00120 typedef misc::Support<initial_container_t> final_support_t;
00121
00122 typedef GeometryCoords geometry_coords_t;
00123
00124 typedef geometry<hstate_t, htransition_t, GeometryCoords>
00125 geometry_t;
00126
00127
00128 typedef typename graph_data_t::iterator iterator;
00129 typedef typename graph_data_t::const_iterator const_iterator;
00130 typedef iterator transition_iterator;
00131
00132 typedef typename index_iterator<graph_data_t, src>::type
00133 src_iterator;
00134 typedef src_iterator src_const_iterator;
00135 typedef typename index_iterator<graph_data_t, dst>::type
00136 dst_iterator;
00137 typedef dst_iterator dst_const_iterator;
00138 typedef std::pair<src_iterator, src_iterator> src_range;
00139 typedef std::pair<dst_iterator, dst_iterator> dst_range;
00140
00141
00142
00143
00144
00145
00146 typedef typename index_iterator<graph_data_t, succ>::type
00147 succ_iterator;
00148 typedef succ_iterator succ_const_iterator;
00149 typedef std::pair<succ_iterator, succ_iterator> succ_range;
00150
00151 typedef ::vcsn::bmig::DeltaConstIterator<self_t, hstate_t, src_iterator>
00152 delta_state_iterator;
00153 typedef ::vcsn::bmig::DeltaConstIterator<self_t, htransition_t, src_iterator>
00154 delta_transition_iterator;
00155 typedef ::vcsn::bmig::DeltaConstIterator<self_t, hstate_t, dst_iterator>
00156 rdelta_state_iterator;
00157 typedef ::vcsn::bmig::DeltaConstIterator<self_t, htransition_t, dst_iterator>
00158 rdelta_transition_iterator;
00159
00160 Graph ();
00161 Graph (unsigned int reserve_number_of_state,
00162 unsigned int reserve_number_edge);
00163 Graph (const self_t&);
00164 ~Graph ();
00165
00166 self_t& operator= (const self_t&);
00167
00168
00169
00170 states_t states () const;
00171 edges_t edges () const;
00172 initial_support_t initial () const;
00173 final_support_t final () const;
00174
00175
00176 bool has_state (const hstate_t& h) const;
00177 hstate_t add_state ();
00178 hstate_t get_state (unsigned h) const;
00179 void del_state (const hstate_t& h);
00180
00181 void set_initial(const hstate_t& s,
00182 const series_set_elt_value_t& v,
00183 const series_set_elt_value_t& z);
00184 const series_set_elt_value_t&
00185 get_initial(const hstate_t&,
00186 const series_set_elt_value_t&) const;
00187 bool is_initial(const hstate_t& s,
00188 const series_set_elt_value_t&) const;
00189 void clear_initial();
00190
00191 void set_final(const hstate_t&,
00192 const series_set_elt_value_t&,
00193 const series_set_elt_value_t&);
00194 const series_set_elt_value_t&
00195 get_final(const hstate_t&,
00196 const series_set_elt_value_t&) const;
00197 bool is_final(const hstate_t& s,
00198 const series_set_elt_value_t&) const;
00199 void clear_final();
00200
00201
00202
00203 bool has_edge (const hedge_t& h) const;
00204 hedge_t add_edge (const hstate_t& from,
00205 const hstate_t& to,
00206 const label_t& l);
00207 void del_edge (const hedge_t& h);
00208
00209 hstate_t src_of (const hedge_t& h) const;
00210 hstate_t dst_of (const hedge_t& h) const;
00211
00212 const label_t& label_of (const hedge_t& h) const;
00213 void update(const hedge_t& h, const label_t& l);
00214
00215
00216 template <class S>
00217 bool exists (const AutomataBase<S>& s) const;
00218
00219 self_t& clone () const;
00220
00221 tag_t& tag ();
00222 const tag_t& tag () const;
00223 geometry_t& geometry ();
00224 const geometry_t& geometry () const;
00225
00226
00227
00228
00229
00230 template <typename I>
00231 htransition_t get_htransition(const I& i) const;
00232
00233
00234
00235
00236
00237 # define DECLARE_DELTA_FUNCTION(FunName, DeltaKind) \
00238 template <typename OutputIterator, typename Query> \
00239 void FunName (OutputIterator res, const hstate_t& from, \
00240 const Query& q, ::vcsn::delta_kind::DeltaKind) const
00241 DECLARE_DELTA_FUNCTION (delta, states);
00242 DECLARE_DELTA_FUNCTION (delta, transitions);
00243 DECLARE_DELTA_FUNCTION (rdelta, states);
00244 DECLARE_DELTA_FUNCTION (rdelta, transitions);
00245 # undef DECLARE_DELTA_FUNCTION
00246
00247 # define DECLARE_DELTAF_BOOL_FUNCTION(FunName, DeltaKind, IsBool) \
00248 template <typename Functor, typename Query> \
00249 void FunName (Functor& f, const hstate_t& from, const Query& q, \
00250 ::vcsn::delta_kind::DeltaKind, misc::IsBool ## _t) const
00251 DECLARE_DELTAF_BOOL_FUNCTION (deltaf, states, true);
00252 DECLARE_DELTAF_BOOL_FUNCTION (deltaf, states, false);
00253 DECLARE_DELTAF_BOOL_FUNCTION (deltaf, transitions, true);
00254 DECLARE_DELTAF_BOOL_FUNCTION (deltaf, transitions, false);
00255 DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, states, true);
00256 DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, states, false);
00257 DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, transitions, true);
00258 DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, transitions, false);
00259 # undef DECLARE_DELTAF_BOOL_FUNCTION
00260
00261 # define DECLARE_DELTAF_FUNCTION(FunName) \
00262 template <typename Functor, typename Query, typename DeltaKind> \
00263 void FunName (Functor& f, const hstate_t& from, \
00264 const Query& q, ::vcsn::delta_kind::kind<DeltaKind>) const
00265 DECLARE_DELTAF_FUNCTION (deltaf);
00266 DECLARE_DELTAF_FUNCTION (rdeltaf);
00267 # undef DECLARE_DELTAF_FUNCTION
00268
00269
00270
00271 # define DECLARE_DELTAI_FUNCTION(DeltaKind) \
00272 std::pair<DeltaKind##_iterator, DeltaKind##_iterator> \
00273 deltai(const hstate_t& s, DeltaKind##_iterator) const
00274 DECLARE_DELTAI_FUNCTION(src);
00275 DECLARE_DELTAI_FUNCTION(dst);
00276 # undef DECLARE_DELTAI_FUNCTION
00277
00278 private:
00279 typename graph_data_t::const_iterator
00280 find_edge(const state_t&,
00281 const state_t&,
00282 const hlabel_t&) const;
00283
00284 geometry_t geometry_;
00285 graph_data_t graph_;
00286 tag_t tag_;
00287 final_t final_;
00288 initial_t initial_;
00289
00290
00291 boost::dynamic_bitset<> initial_bitset_;
00292 boost::dynamic_bitset<> final_bitset_;
00293 unsigned number_of_epsilon_;
00294
00295
00296 unsigned number_of_state_;
00297 states_data_t states_;
00298
00299 SmartLabelContainer<label_t>
00300 label_container_;
00301
00302 };
00303
00304
00305
00306 # define BMIGRAPH_TPARAM \
00307 template <class S, class WordValue, class WeightValue, class SeriesValue, \
00308 class Letter, class Tag, class GeometryCoords>
00309
00310 # define BMIGRAPH_SERIES \
00311 Graph<labels_are_series, WordValue, WeightValue, SeriesValue, \
00312 Letter, Tag, GeometryCoords>
00313
00314 BMIGRAPH_TPARAM
00315 ADAPT_ADD_LETTER_TRANSITION_TO_SERIES_LABEL(BMIGRAPH_SERIES);
00316
00317 BMIGRAPH_TPARAM
00318 ADAPT_LETTER_OF_TO_SERIES_LABEL(BMIGRAPH_SERIES);
00319
00320 BMIGRAPH_TPARAM
00321 ADAPT_WORD_OF_TO_SERIES_LABEL(BMIGRAPH_SERIES);
00322
00323 # undef BMIGRAPH_SERIES
00324 # define BMIGRAPH_LETTERS \
00325 Graph<labels_are_letters, WordValue, WeightValue, SeriesValue,\
00326 Letter, Tag, GeometryCoords>
00327
00328 BMIGRAPH_TPARAM
00329 ADAPT_WORD_OF_TO_LETTERS_LABEL(BMIGRAPH_LETTERS);
00330
00331 BMIGRAPH_TPARAM
00332 ADAPT_SERIE_OF_TO_LETTERS_LABEL(BMIGRAPH_LETTERS);
00333
00334 BMIGRAPH_TPARAM
00335 ADAPT_ADD_SERIE_TRANSITION_TO_LETTERS_LABEL(BMIGRAPH_LETTERS);
00336
00337 # undef BMIGRAPH_LETTERS
00338
00339 # define BMIGRAPH \
00340 Graph<Kind, WordValue, WeightValue, SerieValue, \
00341 Letter, Tag, GeometryCoords>
00342
00343 template <class Kind, class WordValue, class WeightValue, class SerieValue,
00344 class Letter, class Tag, class GeometryCoords, class I>
00345 Tag& op_tag(const AutomataBase<I>&, BMIGRAPH&);
00346
00347 template <class Kind, class WordValue, class WeightValue, class SerieValue,
00348 class Letter, class Tag, class GeometryCoords, class I>
00349 const Tag& op_tag(const AutomataBase<I>&, BMIGRAPH&);
00350
00351 template <class Kind, class WordValue, class WeightValue, class SerieValue,
00352 class Letter, class Tag, class GeometryCoords, class I>
00353 typename BMIGRAPH::geometry_t&
00354 op_geometry(const AutomataBase<I>&, BMIGRAPH&);
00355
00356 template <class Kind, class WordValue, class WeightValue, class SerieValue,
00357 class Letter, class Tag, class GeometryCoords, class I>
00358 const typename BMIGRAPH::geometry_t&
00359 op_geometry(const AutomataBase<I>&, const BMIGRAPH&);
00360
00361 # undef BMIGRAPH
00362 # undef BMIGRAPH_TPARAM
00363
00364 }
00365
00366
00367 VCSN_MAKE_AUTOMATON_TRAITS(bmig::Graph);
00368 VCSN_MAKE_GENERALIZED_AUTOMATON_TRAITS(bmig::Graph);
00369
00370
00371 template <class Kind,
00372 class WordValue,
00373 class WeightValue,
00374 class SeriesValue,
00375 class Letter,
00376 class Tag,
00377 class GeometryCoords>
00378 struct transducer_traits<bmig::Graph<Kind,
00379 WordValue,
00380 WeightValue,
00381 SeriesValue,
00382 Letter,
00383 Tag,
00384 GeometryCoords> >
00385 {
00386 typedef WordValue input_monoid_elt_value_t;
00387 typedef typename algebra::series_traits<WeightValue>::monoid_elt_value_t
00388 output_monoid_elt_value_t;
00389 typedef typename algebra::series_traits<WeightValue>::semiring_elt_value_t
00390 output_semiring_elt_value_t;
00391 };
00392
00393
00394 template <class Kind,
00395 class WordValue,
00396 class WeightValue,
00397 class SeriesValue,
00398 class Letter,
00399 class Tag,
00400 class GeometryCoords>
00401 struct projection_traits<bmig::Graph<Kind,
00402 WordValue,
00403 WeightValue,
00404 SeriesValue,
00405 Letter,
00406 Tag,
00407 GeometryCoords> >
00408 {
00409 typedef bmig::Graph<Kind, WordValue, WeightValue, SeriesValue,
00410 Letter, Tag, GeometryCoords>
00411 self_t;
00412 typedef typename transducer_traits<self_t>::output_semiring_elt_value_t
00413 semiring_elt_value_t;
00414 typedef typename transducer_traits<self_t>::input_monoid_elt_value_t
00415 monoid_elt_value_t;
00416 typedef typename algebra::mute_series_impl<SeriesValue,
00417 semiring_elt_value_t,
00418 monoid_elt_value_t>::ret
00419 series_set_elt_value_t;
00420
00421 typedef
00422 bmig::Graph<Kind,
00423 monoid_elt_value_t,
00424 semiring_elt_value_t,
00425 series_set_elt_value_t,
00426 Letter,
00427 Tag,
00428 GeometryCoords>
00429 ret;
00430 };
00431
00432
00433 template <class Kind,
00434 class WordValue,
00435 class WeightValue,
00436 class SeriesValue,
00437 class Letter,
00438 class Tag,
00439 class GeometryCoords>
00440 struct fmp_projection_traits<bmig::Graph<Kind,
00441 WordValue,
00442 WeightValue,
00443 SeriesValue,
00444 Letter,
00445 Tag,
00446 GeometryCoords> >
00447 {
00448 typedef bmig::Graph<Kind, WordValue, WeightValue, SeriesValue,
00449 Letter, Tag, GeometryCoords>
00450 self_t;
00451
00452 typedef typename automaton_traits<self_t>::semiring_elt_value_t
00453 semiring_elt_value_t;
00454
00455 typedef typename WordValue::first_type monoid_elt_value_t;
00456 typedef typename monoid_elt_value_t::value_type letter_t;
00457
00458 typedef typename algebra::mute_series_impl<SeriesValue,
00459 semiring_elt_value_t,
00460 monoid_elt_value_t>::ret
00461 series_set_elt_value_t;
00462
00463 typedef
00464 bmig::Graph<Kind,
00465 monoid_elt_value_t,
00466 semiring_elt_value_t,
00467 series_set_elt_value_t,
00468 letter_t,
00469 Tag,
00470 GeometryCoords>
00471 ret;
00472 };
00473
00474 template <class Kind,
00475 class WordValue,
00476 class WeightValue,
00477 class SeriesValue,
00478 class Letter,
00479 class Tag,
00480 class GeometryCoords>
00481 struct output_projection_traits<bmig::Graph<Kind,
00482 WordValue,
00483 WeightValue,
00484 SeriesValue,
00485 Letter,
00486 Tag,
00487 GeometryCoords> >
00488 {
00489 typedef bmig::Graph<Kind, WordValue, WeightValue, SeriesValue,
00490 Letter, Tag, GeometryCoords>
00491 self_t;
00492
00493 typedef typename automaton_traits<self_t>::semiring_elt_value_t
00494 series_set_elt_value_t;
00495
00496 typedef typename
00497 algebra::series_traits<series_set_elt_value_t>::monoid_elt_value_t
00498 monoid_elt_value_t;
00499
00500 typedef typename
00501 algebra::series_traits<series_set_elt_value_t>::semiring_elt_value_t
00502 semiring_elt_value_t;
00503
00504 typedef
00505 bmig::Graph<Kind,
00506 monoid_elt_value_t,
00507 semiring_elt_value_t,
00508 series_set_elt_value_t,
00509 Letter,
00510 Tag,
00511 GeometryCoords>
00512 ret;
00513 };
00514
00515
00516 template <class Kind,
00517 class WordValue,
00518 class WeightValue,
00519 class SeriesValue,
00520 class Letter,
00521 class Tag,
00522 class GeometryCoords>
00523 struct fmp_output_projection_traits<bmig::Graph<Kind,
00524 WordValue,
00525 WeightValue,
00526 SeriesValue,
00527 Letter,
00528 Tag,
00529 GeometryCoords> >
00530 {
00531 typedef bmig::Graph<Kind, WordValue, WeightValue, SeriesValue,
00532 Letter, Tag, GeometryCoords>
00533 self_t;
00534
00535 typedef typename WordValue::second_type monoid_elt_value_t;
00536 typedef typename monoid_elt_value_t::value_type letter_t;
00537
00538 typedef typename automaton_traits<self_t>::semiring_elt_value_t
00539 semiring_elt_value_t;
00540
00541 typedef typename algebra::mute_series_impl<SeriesValue,
00542 semiring_elt_value_t,
00543 monoid_elt_value_t>::ret series_set_elt_value_t;
00544
00545 typedef
00546 bmig::Graph<Kind,
00547 monoid_elt_value_t,
00548 semiring_elt_value_t,
00549 series_set_elt_value_t,
00550 letter_t,
00551 Tag,
00552 GeometryCoords>
00553 ret;
00554 };
00555
00556
00557 template <class Kind,
00558 class WordValue,
00559 class WeightValue,
00560 class SeriesValue,
00561 class Letter,
00562 class Tag,
00563 class GeometryCoords>
00564 struct extension_traits<bmig::Graph<Kind,
00565 WordValue,
00566 WeightValue,
00567 SeriesValue,
00568 Letter,
00569 Tag,
00570 GeometryCoords> >
00571 {
00572 typedef bmig::Graph<Kind, WordValue, WeightValue,
00573 SeriesValue, Letter, Tag, GeometryCoords>
00574 self_t;
00575 typedef typename automaton_traits<self_t>::monoid_elt_value_t
00576 monoid_elt_value_t;
00577 typedef typename algebra::mute_series_impl<SeriesValue,
00578 SeriesValue,
00579 monoid_elt_value_t>::ret
00580 series_set_elt_value_t;
00581
00582 typedef
00583 bmig::Graph<Kind,
00584 monoid_elt_value_t,
00585 SeriesValue,
00586 series_set_elt_value_t,
00587 Letter,
00588 Tag,
00589 GeometryCoords>
00590 ret;
00591 };
00592 }
00593
00594 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
00595 # include <vaucanson/automata/implementation/bmig_graph_impl.hxx>
00596 # endif // !VCSN_USE_INTERFACE_ONLY || VCSN_USE_LIB
00597
00598
00599
00600
00601 #endif // !VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_IMPL_HH_ //
00602