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