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 vcsn::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 
00194       private:
00195         typename graph_data_t::const_iterator
00196                           find_edge(const state_t&,
00197                                     const state_t&,
00198                                     const label_t&) const;
00199 
00200         geometry_t        geometry_;
00201         graph_data_t      graph_;
00202         tag_t             tag_;
00203         final_t           final_;
00204         initial_t         initial_;
00205 
00206         //NEW ATTRIBUTES
00207         boost::dynamic_bitset<>  initial_bitset_;
00208         boost::dynamic_bitset<>  final_bitset_;
00209         unsigned          number_of_epsilon_;
00210 
00211         // number_of_state_ == 0 => there is no state.
00212         unsigned          number_of_state_;
00213         states_data_t     states_;
00214 
00215     }; // End of class Graph
00216 
00217 
00218 # define BMIGRAPH_TPARAM                                    \
00219     template <class S, class WordValue, class SeriesValue,  \
00220               class Letter, class Tag, class GeometryCoords>
00221 
00222 # define BMIGRAPH_LETTERS                                          \
00223     Graph<labels_are_letters, WordValue, bool, SeriesValue,        \
00224           Letter, Tag, GeometryCoords>
00225 
00226     BMIGRAPH_TPARAM
00227     ADAPT_WORD_OF_TO_LETTERS_LABEL(BMIGRAPH_LETTERS);
00228 
00229     BMIGRAPH_TPARAM
00230     ADAPT_SERIE_OF_TO_LETTERS_LABEL(BMIGRAPH_LETTERS);
00231 
00232     BMIGRAPH_TPARAM
00233     ADAPT_ADD_SERIE_TRANSITION_TO_LETTERS_LABEL(BMIGRAPH_LETTERS);
00234 
00235 # define BMIGRAPH                                                 \
00236     Graph<labels_are_letters, WordValue, bool, SerieValue,        \
00237           Letter, Tag, GeometryCoords>
00238 
00239     template <class WordValue, class SerieValue,
00240               class Letter, class Tag, class GeometryCoords, class I>
00241     Tag& op_tag(const AutomataBase<I>&, BMIGRAPH&);
00242 
00243     template <class WordValue, class SerieValue,
00244               class Letter, class Tag, class GeometryCoords, class I>
00245     const Tag& op_tag(const AutomataBase<I>&, BMIGRAPH&);
00246 
00247     template <class WordValue, class SerieValue,
00248               class Letter, class Tag, class GeometryCoords, class I>
00249     typename BMIGRAPH::geometry_t&
00250     op_geometry(const AutomataBase<I>&, BMIGRAPH&);
00251 
00252     template <class WordValue, class SerieValue,
00253               class Letter, class Tag, class GeometryCoords, class I>
00254     const typename BMIGRAPH::geometry_t&
00255     op_geometry(const AutomataBase<I>&, const BMIGRAPH&);
00256 
00257 # undef BMIGRAPH
00258 # undef BMIGRAPH_TPARAM
00259 
00260   } // End of namespace bmig
00261 
00262   // This implementation can be used as an implementation of automaton.
00263   template <typename WordValue,
00264             typename SeriesValue,
00265             typename Letter,
00266             typename Tag,
00267             typename GeometryCoords>
00268   struct automaton_traits<bmig::Graph<labels_are_letters, WordValue, bool, SeriesValue,
00269                           Letter, Tag, GeometryCoords> >
00270   {
00271     typedef bmig::Graph<labels_are_letters, WordValue, bool, SeriesValue,
00272                  Letter, Tag, GeometryCoords>           graph_t;
00273     typedef typename graph_t::semiring_elt_value_t      semiring_elt_value_t;
00274     typedef typename graph_t::monoid_elt_value_t        monoid_elt_value_t;
00275     typedef typename graph_t::word_value_t              word_value_t;
00276     typedef typename graph_t::series_set_elt_value_t    series_set_elt_value_t;
00277     typedef typename graph_t::letter_t                  letter_t;
00278     typedef typename graph_t::tag_t                     tag_t;
00279     typedef typename graph_t::geometry_t                geometry_t;
00280     typedef typename graph_t::label_t                   label_t;
00281     typedef typename graph_t::states_t                  states_t;
00282     typedef typename states_t::iterator                 state_iterator;
00283     typedef typename graph_t::hstate_t                  hstate_t;
00284     typedef typename graph_t::edges_t                   transitions_t;
00285     typedef typename transitions_t::iterator            transition_iterator;
00286     typedef typename graph_t::htransition_t             htransition_t;
00287     typedef typename graph_t::initial_t                 initial_t;
00288     typedef typename graph_t::initial_support_t         initial_support_t;
00289     typedef typename initial_support_t::iterator        initial_iterator;
00290     typedef typename graph_t::final_t                   final_t;
00291     typedef typename graph_t::final_support_t           final_support_t;
00292     typedef typename final_support_t::iterator          final_iterator;
00293   };
00294 
00295  } // End of namespace vcsn
00296 
00297 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
00298 #  include <vaucanson/automata/implementation/bmig_graph_letters_spec.hxx>
00299 # endif // !VCSN_USE_INTERFACE_ONLY || VCSN_USE_LIB
00300 
00301 #endif // !VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_LETTERS_SPEC_HH_ //
00302