|
Vaucanson 1.4
|
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
1.7.4