Vaucanson: bmig_graph_letters_spec.hh Source File

00001 // bmig_graph_letters_spec.hh: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2007, 2008 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 
00018 #ifndef VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_LETTERS_SPEC_HH_
00019 # define VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_LETTERS_SPEC_HH_
00020 
00021 # include <set>
00022 # include <vaucanson/automata/implementation/bmig_graph_impl.hh>
00023 
00024 namespace vcsn
00025 {
00026   namespace bmig
00027   {
00028 
00029     // class Graph.
00030     template <typename WordValue,
00031     typename SeriesValue, typename Letter, typename Tag, typename GeometryCoords>
00032     class Graph<labels_are_letters, WordValue, bool, SeriesValue, Letter,
00033                 Tag, GeometryCoords>
00034     {
00035       public:
00036         /*
00037         ** Type definitions
00038         */
00039 
00040         // self definition.
00041         typedef Graph<labels_are_letters, WordValue, bool,
00042                 SeriesValue, Letter, Tag, GeometryCoords>
00043                                                         self_t;
00044 
00045         typedef bool                                    semiring_elt_value_t;
00046         typedef WordValue                               monoid_elt_value_t;
00047         typedef WordValue                               word_value_t;
00048         typedef SeriesValue                             series_set_elt_value_t;
00049         typedef Letter                                  letter_t;
00050         typedef Tag                                     tag_t;
00051 
00052         typedef typename LabelOf<labels_are_letters, WordValue, bool,
00053                 SeriesValue, Letter>::ret               label_t;
00054 
00055         typedef boost::shared_ptr<std::size_t>          state_t;
00056         // State descriptor.
00057         //
00058         typedef handler<state_h, state_t>               hstate_t;
00059 
00060         typedef EdgeValue<state_t, label_t>             edge_data_t;
00061 
00062         typedef GraphContainer<state_t, label_t, edge_data_t>   graph_data_t;
00063 
00064         // Transition descriptor.
00065         //
00066         // We store a pointer to an EdgeValue to avoid a new index on transitions and
00067         // get the data more quickly. Actually this is the adresse of an element
00068         // inserted in the multi_index.
00069         // We are allowed to do so since Boost::multi_index guaranties that the data
00070         // inserted will not be reallocated.
00071         //
00072         // We may need to try storing an iterator instead of a pointer. We haven't tried yet
00073         // since its size is higher than a simple pointer.
00074         typedef typename graph_data_t::iterator         edges_iterator;
00075         typedef handler<transition_h, edges_iterator>   htransition_t;
00076         typedef htransition_t                           hedge_t;
00077 
00078         typedef VGraphContainer<edges_iterator, graph_data_t, htransition_t> edges_t;
00079         typedef std::vector<state_t>                      states_data_t;
00080         typedef misc::Support<states_data_t>              states_t;
00081 
00082         typedef std::set<state_t>                        initial_t;
00083         typedef std::set<state_t>                        final_t;
00084 
00085         typedef misc::Support<initial_t>                  initial_support_t;
00086         typedef misc::Support<final_t>                    final_support_t;
00087 
00088         typedef GeometryCoords                            geometry_coords_t;
00089 
00090         typedef geometry<hstate_t, htransition_t, GeometryCoords>
00091                                                           geometry_t;
00092 
00093         //Definition of various iterator types for the graph structure.
00094         typedef typename graph_data_t::iterator           iterator;
00095         typedef typename graph_data_t::const_iterator     const_iterator;
00096         typedef iterator                                  transition_iterator;
00097 
00098         typedef typename index_iterator<graph_data_t, src>::type
00099                                                           src_iterator;
00100         typedef src_iterator                              src_const_iterator;
00101         typedef typename index_iterator<graph_data_t, dst>::type
00102                                                           dst_iterator;
00103         typedef dst_iterator                              dst_const_iterator;
00104         typedef typename index_iterator<graph_data_t, pred>::type
00105                                                           pred_iterator;
00106         typedef pred_iterator                             pred_const_iterator;
00107         typedef typename index_iterator<graph_data_t, succ>::type
00108                                                           succ_iterator;
00109         typedef succ_iterator                             succ_const_iterator;
00110         typedef std::pair<src_iterator, src_iterator>     src_range;
00111         typedef std::pair<dst_iterator, dst_iterator>     dst_range;
00112         typedef std::pair<pred_iterator, pred_iterator>   pred_range;
00113         typedef std::pair<succ_iterator, succ_iterator>   succ_range;
00114 
00115         Graph ();
00116         Graph (unsigned int reserve_number_of_state,
00117                unsigned int reserve_number_edge);
00118         Graph (const self_t&);
00119         ~Graph ();
00120 
00121         self_t& operator= (const self_t&);
00122 
00123         // FIXME: add const rettype& versions?
00124 
00125         states_t          states () const;
00126         edges_t           edges () const;
00127         initial_support_t initial () const;
00128         final_support_t   final () const;
00129 
00130         // state manipulations
00131         bool              has_state (const hstate_t& h) const;
00132         hstate_t          add_state ();
00133         hstate_t          get_state (unsigned h) const;
00134         void              del_state (const hstate_t& h);
00135 
00136         void              set_initial(const hstate_t& s,
00137                                       const series_set_elt_value_t& v,
00138                                       const series_set_elt_value_t& z);
00139         const series_set_elt_value_t&
00140                           get_initial(const hstate_t&,
00141                                       const series_set_elt_value_t&) const;
00142         bool              is_initial(const hstate_t& s,
00143                                      const series_set_elt_value_t&) const;
00144         void              clear_initial();
00145 
00146         void              set_final(const hstate_t&,
00147                                     const series_set_elt_value_t&,
00148                                     const series_set_elt_value_t&);
00149         const series_set_elt_value_t&
00150                           get_final(const hstate_t&,
00151                                     const series_set_elt_value_t&) const;
00152         bool              is_final(const hstate_t& s,
00153                                    const series_set_elt_value_t&) const;
00154         void              clear_final();
00155 
00156 
00157         // edge manipulations
00158         bool              has_edge (const hedge_t& h) const;
00159         hedge_t           add_edge (const hstate_t& from,
00160                                     const hstate_t& to,
00161                                     const label_t& l);
00162         void              del_edge (const hedge_t& h);
00163 
00164         hstate_t          src_of (const hedge_t& h) const;
00165         hstate_t          dst_of (const hedge_t& h) const;
00166 
00167         const label_t&    label_of (const hedge_t& h) const;
00168         void              update(const hedge_t& h, const label_t& l);
00169 
00170         // check the consistency of an automata
00171         template <class S>
00172         bool              exists (const AutomataBase<S>& s) const;
00173 
00174         self_t&           clone () const; // TODO
00175 
00176         tag_t&            tag ();
00177         const tag_t&      tag () const;
00178         geometry_t&       geometry ();
00179         const geometry_t& geometry () const;
00180 
00181 
00183 # define DECLARE_DELTA_FUNCTION(FunName, DeltaKind)                     \
00184         template <typename OutputIterator, typename Query>              \
00185         void FunName (OutputIterator res, const hstate_t& from,         \
00186                       const Query& q, ::vcsn::delta_kind::DeltaKind) const
00187         DECLARE_DELTA_FUNCTION (delta, states);
00188         DECLARE_DELTA_FUNCTION (delta, transitions);
00189         DECLARE_DELTA_FUNCTION (rdelta, states);
00190         DECLARE_DELTA_FUNCTION (rdelta, transitions);
00191 # undef DECLARE_DELTA_FUNCTION
00192 
00193 # define DECLARE_DELTAF_BOOL_FUNCTION(FunName, DeltaKind, IsBool)       \
00194         template <typename Functor, typename Query>                     \
00195         void FunName (Functor& f, const hstate_t& from, const Query& q, \
00196                       ::vcsn::delta_kind::DeltaKind, misc::IsBool ## _t) const
00197         DECLARE_DELTAF_BOOL_FUNCTION (deltaf, states, true);
00198         DECLARE_DELTAF_BOOL_FUNCTION (deltaf, states, false);
00199         DECLARE_DELTAF_BOOL_FUNCTION (deltaf, transitions, true);
00200         DECLARE_DELTAF_BOOL_FUNCTION (deltaf, transitions, false);
00201         DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, states, true);
00202         DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, states, false);
00203         DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, transitions, true);
00204         DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, transitions, false);
00205 # undef DECLARE_DELTAF_BOOL_FUNCTION
00206 # define DECLARE_DELTAF_BOOL_FUNCTION(FunName, DeltaKind, IsBool)       \
00207         template <typename Functor, typename S, typename T>             \
00208         void FunName (Functor& f, const hstate_t& from,                 \
00209                       const letter_query<S, T, label_t>& q,             \
00210                       ::vcsn::delta_kind::DeltaKind, misc::IsBool ## _t) const
00211         DECLARE_DELTAF_BOOL_FUNCTION (deltaf, states, true);
00212         DECLARE_DELTAF_BOOL_FUNCTION (deltaf, states, false);
00213         DECLARE_DELTAF_BOOL_FUNCTION (deltaf, transitions, true);
00214         DECLARE_DELTAF_BOOL_FUNCTION (deltaf, transitions, false);
00215         DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, states, true);
00216         DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, states, false);
00217         DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, transitions, true);
00218         DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, transitions, false);
00219 # undef DECLARE_DELTAF_BOOL_FUNCTION
00220 # define DECLARE_DELTAF_BOOL_FUNCTION(FunName, DeltaKind, IsBool)       \
00221         template <typename Functor, typename S, typename T>             \
00222         void FunName (Functor& f, const hstate_t& from,                 \
00223                       const spontaneous_query<S, T>& q,                 \
00224                       ::vcsn::delta_kind::DeltaKind, misc::IsBool ## _t) const
00225         DECLARE_DELTAF_BOOL_FUNCTION (deltaf, states, true);
00226         DECLARE_DELTAF_BOOL_FUNCTION (deltaf, states, false);
00227         DECLARE_DELTAF_BOOL_FUNCTION (deltaf, transitions, true);
00228         DECLARE_DELTAF_BOOL_FUNCTION (deltaf, transitions, false);
00229         DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, states, true);
00230         DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, states, false);
00231         DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, transitions, true);
00232         DECLARE_DELTAF_BOOL_FUNCTION (rdeltaf, transitions, false);
00233 # undef DECLARE_DELTAF_BOOL_FUNCTION
00234 
00235 # define DECLARE_DELTAF_FUNCTION(FunName)                               \
00236         template <typename Functor, typename Query, typename DeltaKind> \
00237         void FunName (Functor& f, const hstate_t& from,                 \
00238                       const Query& q, ::vcsn::delta_kind::kind<DeltaKind>) const
00239         DECLARE_DELTAF_FUNCTION (deltaf);
00240         DECLARE_DELTAF_FUNCTION (rdeltaf);
00241 # undef DECLARE_DELTAF_FUNCTION
00242 
00243 
00244       private:
00245         typename graph_data_t::const_iterator
00246                           find_edge(const state_t&,
00247                                     const state_t&,
00248                                     const label_t&) const;
00249 
00250         geometry_t        geometry_;
00251         graph_data_t      graph_;
00252         tag_t             tag_;
00253         final_t           final_;
00254         initial_t         initial_;
00255 
00256         //NEW ATTRIBUTES
00257         boost::dynamic_bitset<>  initial_bitset_;
00258         boost::dynamic_bitset<>  final_bitset_;
00259         unsigned          number_of_epsilon_;
00260 
00261         // number_of_state_ == 0 => there is no state.
00262         unsigned          number_of_state_;
00263         states_data_t     states_;
00264 
00265     }; // End of class Graph
00266 
00267 
00268 # define BMIGRAPH_TPARAM                                    \
00269     template <class S, class WordValue, class SeriesValue,  \
00270               class Letter, class Tag, class GeometryCoords>
00271 
00272 # define BMIGRAPH_LETTERS                                          \
00273     Graph<labels_are_letters, WordValue, bool, SeriesValue,        \
00274           Letter, Tag, GeometryCoords>
00275 
00276     BMIGRAPH_TPARAM
00277     ADAPT_WORD_OF_TO_LETTERS_LABEL(BMIGRAPH_LETTERS);
00278 
00279     BMIGRAPH_TPARAM
00280     ADAPT_SERIE_OF_TO_LETTERS_LABEL(BMIGRAPH_LETTERS);
00281 
00282     BMIGRAPH_TPARAM
00283     ADAPT_ADD_SERIE_TRANSITION_TO_LETTERS_LABEL(BMIGRAPH_LETTERS);
00284 
00285 # define BMIGRAPH                                                 \
00286     Graph<labels_are_letters, WordValue, bool, SerieValue,        \
00287           Letter, Tag, GeometryCoords>
00288 
00289     template <class WordValue, class SerieValue,
00290               class Letter, class Tag, class GeometryCoords, class I>
00291     Tag& op_tag(const AutomataBase<I>&, BMIGRAPH&);
00292 
00293     template <class WordValue, class SerieValue,
00294               class Letter, class Tag, class GeometryCoords, class I>
00295     const Tag& op_tag(const AutomataBase<I>&, BMIGRAPH&);
00296 
00297     template <class WordValue, class SerieValue,
00298               class Letter, class Tag, class GeometryCoords, class I>
00299     typename BMIGRAPH::geometry_t&
00300     op_geometry(const AutomataBase<I>&, BMIGRAPH&);
00301 
00302     template <class WordValue, class SerieValue,
00303               class Letter, class Tag, class GeometryCoords, class I>
00304     const typename BMIGRAPH::geometry_t&
00305     op_geometry(const AutomataBase<I>&, const BMIGRAPH&);
00306 
00307 # undef BMIGRAPH
00308 # undef BMIGRAPH_TPARAM
00309 
00310   } // End of namespace bmig
00311 
00312   // This implementation can be used as an implementation of automaton.
00313   template <typename WordValue,
00314             typename SeriesValue,
00315             typename Letter,
00316             typename Tag,
00317             typename GeometryCoords>
00318   struct automaton_traits<bmig::Graph<labels_are_letters, WordValue, bool, SeriesValue,
00319                           Letter, Tag, GeometryCoords> >
00320   {
00321     typedef bmig::Graph<labels_are_letters, WordValue, bool, SeriesValue,
00322                  Letter, Tag, GeometryCoords>           graph_t;
00323     typedef typename graph_t::semiring_elt_value_t      semiring_elt_value_t;
00324     typedef typename graph_t::monoid_elt_value_t        monoid_elt_value_t;
00325     typedef typename graph_t::word_value_t              word_value_t;
00326     typedef typename graph_t::series_set_elt_value_t    series_set_elt_value_t;
00327     typedef typename graph_t::letter_t                  letter_t;
00328     typedef typename graph_t::tag_t                     tag_t;
00329     typedef typename graph_t::geometry_t                geometry_t;
00330     typedef typename graph_t::label_t                   label_t;
00331     typedef typename graph_t::states_t                  states_t;
00332     typedef typename states_t::iterator                 state_iterator;
00333     typedef typename graph_t::hstate_t                  hstate_t;
00334     typedef typename graph_t::edges_t                   transitions_t;
00335     typedef typename transitions_t::iterator            transition_iterator;
00336     typedef typename graph_t::htransition_t             htransition_t;
00337     typedef typename graph_t::initial_t                 initial_t;
00338     typedef typename graph_t::initial_support_t         initial_support_t;
00339     typedef typename initial_support_t::iterator        initial_iterator;
00340     typedef typename graph_t::final_t                   final_t;
00341     typedef typename graph_t::final_support_t           final_support_t;
00342     typedef typename final_support_t::iterator          final_iterator;
00343   };
00344 
00345  } // End of namespace vcsn
00346 
00347 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
00348 #  include <vaucanson/automata/implementation/bmig_graph_letters_spec.hxx>
00349 # endif // !VCSN_USE_INTERFACE_ONLY || VCSN_USE_LIB
00350 
00351 #endif // !VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_LETTERS_SPEC_HH_ //
00352