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 vcsn::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 VCSN_MAKE_MUTE_GRAPH_IMPL_TRAITS(bmig::Graph);
00370 VCSN_MAKE_MUTE_GRAPH_IMPL_MONOID_TRAITS(bmig::Graph);
00371
00372
00373 template <class Kind,
00374 class WordValue,
00375 class WeightValue,
00376 class SeriesValue,
00377 class Letter,
00378 class Tag,
00379 class GeometryCoords>
00380 struct transducer_traits<bmig::Graph<Kind,
00381 WordValue,
00382 WeightValue,
00383 SeriesValue,
00384 Letter,
00385 Tag,
00386 GeometryCoords> >
00387 {
00388 typedef WordValue input_monoid_elt_value_t;
00389 typedef typename algebra::series_traits<WeightValue>::monoid_elt_value_t
00390 output_monoid_elt_value_t;
00391 typedef typename algebra::series_traits<WeightValue>::semiring_elt_value_t
00392 output_semiring_elt_value_t;
00393 };
00394
00395
00396 template <class Kind,
00397 class WordValue,
00398 class WeightValue,
00399 class SeriesValue,
00400 class Letter,
00401 class Tag,
00402 class GeometryCoords>
00403 struct input_projection_traits<bmig::Graph<Kind,
00404 WordValue,
00405 WeightValue,
00406 SeriesValue,
00407 Letter,
00408 Tag,
00409 GeometryCoords> >
00410 {
00411 typedef bmig::Graph<Kind, WordValue, WeightValue, SeriesValue,
00412 Letter, Tag, GeometryCoords>
00413 self_t;
00414 typedef typename transducer_traits<self_t>::output_semiring_elt_value_t
00415 semiring_elt_value_t;
00416 typedef typename transducer_traits<self_t>::input_monoid_elt_value_t
00417 monoid_elt_value_t;
00418 typedef typename algebra::mute_series_impl<SeriesValue,
00419 semiring_elt_value_t,
00420 monoid_elt_value_t>::ret
00421 series_set_elt_value_t;
00422
00423 typedef
00424 bmig::Graph<Kind,
00425 monoid_elt_value_t,
00426 semiring_elt_value_t,
00427 series_set_elt_value_t,
00428 Letter,
00429 Tag,
00430 GeometryCoords>
00431 ret;
00432 };
00433
00434
00435 template <class Kind,
00436 class WordValue,
00437 class WeightValue,
00438 class SeriesValue,
00439 class Letter,
00440 class Tag,
00441 class GeometryCoords>
00442 struct fmp_input_projection_traits<bmig::Graph<Kind,
00443 WordValue,
00444 WeightValue,
00445 SeriesValue,
00446 Letter,
00447 Tag,
00448 GeometryCoords> >
00449 {
00450 typedef bmig::Graph<Kind, WordValue, WeightValue, SeriesValue,
00451 Letter, Tag, GeometryCoords>
00452 self_t;
00453
00454 typedef typename automaton_traits<self_t>::semiring_elt_value_t
00455 semiring_elt_value_t;
00456
00457 typedef typename WordValue::first_type monoid_elt_value_t;
00458 typedef typename monoid_elt_value_t::value_type letter_t;
00459
00460 typedef typename algebra::mute_series_impl<SeriesValue,
00461 semiring_elt_value_t,
00462 monoid_elt_value_t>::ret
00463 series_set_elt_value_t;
00464
00465 typedef
00466 bmig::Graph<Kind,
00467 monoid_elt_value_t,
00468 semiring_elt_value_t,
00469 series_set_elt_value_t,
00470 letter_t,
00471 Tag,
00472 GeometryCoords>
00473 ret;
00474 };
00475
00476 template <class Kind,
00477 class WordValue,
00478 class WeightValue,
00479 class SeriesValue,
00480 class Letter,
00481 class Tag,
00482 class GeometryCoords>
00483 struct output_projection_traits<bmig::Graph<Kind,
00484 WordValue,
00485 WeightValue,
00486 SeriesValue,
00487 Letter,
00488 Tag,
00489 GeometryCoords> >
00490 {
00491 typedef bmig::Graph<Kind, WordValue, WeightValue, SeriesValue,
00492 Letter, Tag, GeometryCoords>
00493 self_t;
00494
00495 typedef typename automaton_traits<self_t>::semiring_elt_value_t
00496 series_set_elt_value_t;
00497
00498 typedef typename
00499 algebra::series_traits<series_set_elt_value_t>::monoid_elt_value_t
00500 monoid_elt_value_t;
00501
00502 typedef typename
00503 algebra::series_traits<series_set_elt_value_t>::semiring_elt_value_t
00504 semiring_elt_value_t;
00505
00506 typedef
00507 bmig::Graph<Kind,
00508 monoid_elt_value_t,
00509 semiring_elt_value_t,
00510 series_set_elt_value_t,
00511 Letter,
00512 Tag,
00513 GeometryCoords>
00514 ret;
00515 };
00516
00517
00518 template <class Kind,
00519 class WordValue,
00520 class WeightValue,
00521 class SeriesValue,
00522 class Letter,
00523 class Tag,
00524 class GeometryCoords>
00525 struct fmp_output_projection_traits<bmig::Graph<Kind,
00526 WordValue,
00527 WeightValue,
00528 SeriesValue,
00529 Letter,
00530 Tag,
00531 GeometryCoords> >
00532 {
00533 typedef bmig::Graph<Kind, WordValue, WeightValue, SeriesValue,
00534 Letter, Tag, GeometryCoords>
00535 self_t;
00536
00537 typedef typename WordValue::second_type monoid_elt_value_t;
00538 typedef typename monoid_elt_value_t::value_type letter_t;
00539
00540 typedef typename automaton_traits<self_t>::semiring_elt_value_t
00541 semiring_elt_value_t;
00542
00543 typedef typename algebra::mute_series_impl<SeriesValue,
00544 semiring_elt_value_t,
00545 monoid_elt_value_t>::ret series_set_elt_value_t;
00546
00547 typedef
00548 bmig::Graph<Kind,
00549 monoid_elt_value_t,
00550 semiring_elt_value_t,
00551 series_set_elt_value_t,
00552 letter_t,
00553 Tag,
00554 GeometryCoords>
00555 ret;
00556 };
00557
00558
00559 template <class Kind,
00560 class WordValue,
00561 class WeightValue,
00562 class SeriesValue,
00563 class Letter,
00564 class Tag,
00565 class GeometryCoords>
00566 struct extension_traits<bmig::Graph<Kind,
00567 WordValue,
00568 WeightValue,
00569 SeriesValue,
00570 Letter,
00571 Tag,
00572 GeometryCoords> >
00573 {
00574 typedef bmig::Graph<Kind, WordValue, WeightValue,
00575 SeriesValue, Letter, Tag, GeometryCoords>
00576 self_t;
00577 typedef typename automaton_traits<self_t>::monoid_elt_value_t
00578 monoid_elt_value_t;
00579 typedef typename algebra::mute_series_impl<SeriesValue,
00580 SeriesValue,
00581 monoid_elt_value_t>::ret
00582 series_set_elt_value_t;
00583
00584 typedef
00585 bmig::Graph<Kind,
00586 monoid_elt_value_t,
00587 SeriesValue,
00588 series_set_elt_value_t,
00589 Letter,
00590 Tag,
00591 GeometryCoords>
00592 ret;
00593 };
00594 }
00595
00596 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
00597 # include <vaucanson/automata/implementation/bmig_graph_impl.hxx>
00598 # endif // !VCSN_USE_INTERFACE_ONLY || VCSN_USE_LIB
00599
00600
00601
00602
00603 #endif // !VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_IMPL_HH_ //
00604