Vaucanson  1.4.1
bmig_graph_letters_spec.hh
1 // bmig_graph_letters_spec.hh: this file is part of the Vaucanson project.
2 //
3 // Vaucanson, a generic library for finite state machines.
4 //
5 // Copyright (C) 2007, 2008 The Vaucanson Group.
6 //
7 // This program is free software; you can redistribute it and/or
8 // modify it under the terms of the GNU General Public License
9 // as published by the Free Software Foundation; either version 2
10 // of the License, or (at your option) any later version.
11 //
12 // The complete GNU General Public Licence Notice can be found as the
13 // `COPYING' file in the root directory.
14 //
15 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
16 //
17 
18 #ifndef VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_LETTERS_SPEC_HH_
19 # define VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_LETTERS_SPEC_HH_
20 
21 # include <set>
22 # include <vaucanson/automata/implementation/bmig_graph_impl.hh>
23 
24 namespace vcsn
25 {
26  namespace bmig
27  {
28 
29  // class Graph.
30  template <typename WordValue,
31  typename SeriesValue, typename Letter, typename Tag, typename GeometryCoords>
32  class Graph<labels_are_letters, WordValue, bool, SeriesValue, Letter,
33  Tag, GeometryCoords>
34  {
35  public:
36  /*
37  ** Type definitions
38  */
39 
40  // self definition.
41  typedef Graph<labels_are_letters, WordValue, bool,
42  SeriesValue, Letter, Tag, GeometryCoords>
43  self_t;
44 
45  typedef bool semiring_elt_value_t;
46  typedef WordValue monoid_elt_value_t;
47  typedef WordValue word_value_t;
48  typedef SeriesValue series_set_elt_value_t;
49  typedef Letter letter_t;
50  typedef Tag tag_t;
51 
52  typedef typename LabelOf<labels_are_letters, WordValue, bool,
53  SeriesValue, Letter>::ret label_t;
54 
55  typedef boost::shared_ptr<std::size_t> state_t;
56  // State descriptor.
57  //
58  typedef handler<state_h, state_t> hstate_t;
59 
60  typedef EdgeValue<state_t, label_t> edge_data_t;
61 
62  typedef GraphContainer<state_t, label_t, edge_data_t> graph_data_t;
63 
64  // Transition descriptor.
65  //
66  // We store a pointer to an EdgeValue to avoid a new index on transitions and
67  // get the data more quickly. Actually this is the adresse of an element
68  // inserted in the multi_index.
69  // We are allowed to do so since Boost::multi_index guaranties that the data
70  // inserted will not be reallocated.
71  //
72  // We may need to try storing an iterator instead of a pointer. We haven't tried yet
73  // since its size is higher than a simple pointer.
74  typedef typename graph_data_t::iterator edges_iterator;
75  typedef handler<transition_h, edges_iterator> htransition_t;
76  typedef htransition_t hedge_t;
77 
78  typedef VGraphContainer<edges_iterator, graph_data_t, htransition_t> edges_t;
79  typedef std::vector<state_t> states_data_t;
80  typedef misc::Support<states_data_t> states_t;
81 
82  typedef std::set<state_t> initial_t;
83  typedef std::set<state_t> final_t;
84 
85  typedef misc::Support<initial_t> initial_support_t;
86  typedef misc::Support<final_t> final_support_t;
87 
88  typedef GeometryCoords geometry_coords_t;
89 
90  typedef vcsn::geometry<hstate_t, htransition_t, GeometryCoords>
91  geometry_t;
92 
93  //Definition of various iterator types for the graph structure.
94  typedef typename graph_data_t::iterator iterator;
95  typedef typename graph_data_t::const_iterator const_iterator;
96  typedef iterator transition_iterator;
97 
98  typedef typename index_iterator<graph_data_t, src>::type
99  src_iterator;
100  typedef src_iterator src_const_iterator;
101  typedef typename index_iterator<graph_data_t, dst>::type
102  dst_iterator;
103  typedef dst_iterator dst_const_iterator;
104  typedef typename index_iterator<graph_data_t, pred>::type
105  pred_iterator;
106  typedef pred_iterator pred_const_iterator;
107  typedef typename index_iterator<graph_data_t, succ>::type
108  succ_iterator;
109  typedef succ_iterator succ_const_iterator;
110  typedef std::pair<src_iterator, src_iterator> src_range;
111  typedef std::pair<dst_iterator, dst_iterator> dst_range;
112  typedef std::pair<pred_iterator, pred_iterator> pred_range;
113  typedef std::pair<succ_iterator, succ_iterator> succ_range;
114 
115  Graph ();
116  Graph (unsigned int reserve_number_of_state,
117  unsigned int reserve_number_edge);
118  Graph (const self_t&);
119  ~Graph ();
120 
121  self_t& operator= (const self_t&);
122 
123  // FIXME: add const rettype& versions?
124 
125  states_t states () const;
126  edges_t edges () const;
127  initial_support_t initial () const;
128  final_support_t final () const;
129 
130  // state manipulations
131  bool has_state (const hstate_t& h) const;
132  hstate_t add_state ();
133  hstate_t get_state (unsigned h) const;
134  void del_state (const hstate_t& h);
135 
136  void set_initial(const hstate_t& s,
137  const series_set_elt_value_t& v,
138  const series_set_elt_value_t& z);
139  const series_set_elt_value_t&
140  get_initial(const hstate_t&,
141  const series_set_elt_value_t&) const;
142  bool is_initial(const hstate_t& s,
143  const series_set_elt_value_t&) const;
144  void clear_initial();
145 
146  void set_final(const hstate_t&,
147  const series_set_elt_value_t&,
148  const series_set_elt_value_t&);
149  const series_set_elt_value_t&
150  get_final(const hstate_t&,
151  const series_set_elt_value_t&) const;
152  bool is_final(const hstate_t& s,
153  const series_set_elt_value_t&) const;
154  void clear_final();
155 
156 
157  // edge manipulations
158  bool has_edge (const hedge_t& h) const;
159  hedge_t add_edge (const hstate_t& from,
160  const hstate_t& to,
161  const label_t& l);
162  void del_edge (const hedge_t& h);
163 
164  hstate_t src_of (const hedge_t& h) const;
165  hstate_t dst_of (const hedge_t& h) const;
166 
167  const label_t& label_of (const hedge_t& h) const;
168  void update(const hedge_t& h, const label_t& l);
169 
170  // check the consistency of an automata
171  template <class S>
172  bool exists (const AutomataBase<S>& s) const;
173 
174  self_t& clone () const; // TODO
175 
176  tag_t& tag ();
177  const tag_t& tag () const;
178  geometry_t& geometry ();
179  const geometry_t& geometry () const;
180 
181 
183 # define DECLARE_DELTA_FUNCTION(FunName, DeltaKind) \
184  template <typename OutputIterator, typename Query> \
185  void FunName (OutputIterator res, const hstate_t& from, \
186  const Query& q, ::vcsn::delta_kind::DeltaKind) const
187  DECLARE_DELTA_FUNCTION (delta, states);
188  DECLARE_DELTA_FUNCTION (delta, transitions);
189  DECLARE_DELTA_FUNCTION (rdelta, states);
190  DECLARE_DELTA_FUNCTION (rdelta, transitions);
191 # undef DECLARE_DELTA_FUNCTION
192 
193 
194  private:
195  typename graph_data_t::const_iterator
196  find_edge(const state_t&,
197  const state_t&,
198  const label_t&) const;
199 
200  geometry_t geometry_;
201  graph_data_t graph_;
202  tag_t tag_;
203  final_t final_;
204  initial_t initial_;
205 
206  //NEW ATTRIBUTES
207  boost::dynamic_bitset<> initial_bitset_;
208  boost::dynamic_bitset<> final_bitset_;
209  unsigned number_of_epsilon_;
210 
211  // number_of_state_ == 0 => there is no state.
212  unsigned number_of_state_;
213  states_data_t states_;
214 
215  }; // End of class Graph
216 
217 
218 # define BMIGRAPH_TPARAM \
219  template <class S, class WordValue, class SeriesValue, \
220  class Letter, class Tag, class GeometryCoords>
221 
222 # define BMIGRAPH_LETTERS \
223  Graph<labels_are_letters, WordValue, bool, SeriesValue, \
224  Letter, Tag, GeometryCoords>
225 
226  BMIGRAPH_TPARAM
227  ADAPT_WORD_OF_TO_LETTERS_LABEL(BMIGRAPH_LETTERS);
228 
229  BMIGRAPH_TPARAM
230  ADAPT_SERIE_OF_TO_LETTERS_LABEL(BMIGRAPH_LETTERS);
231 
232  BMIGRAPH_TPARAM
233  ADAPT_ADD_SERIE_TRANSITION_TO_LETTERS_LABEL(BMIGRAPH_LETTERS);
234 
235 # define BMIGRAPH \
236  Graph<labels_are_letters, WordValue, bool, SerieValue, \
237  Letter, Tag, GeometryCoords>
238 
239  template <class WordValue, class SerieValue,
240  class Letter, class Tag, class GeometryCoords, class I>
241  Tag& op_tag(const AutomataBase<I>&, BMIGRAPH&);
242 
243  template <class WordValue, class SerieValue,
244  class Letter, class Tag, class GeometryCoords, class I>
245  const Tag& op_tag(const AutomataBase<I>&, BMIGRAPH&);
246 
247  template <class WordValue, class SerieValue,
248  class Letter, class Tag, class GeometryCoords, class I>
249  typename BMIGRAPH::geometry_t&
250  op_geometry(const AutomataBase<I>&, BMIGRAPH&);
251 
252  template <class WordValue, class SerieValue,
253  class Letter, class Tag, class GeometryCoords, class I>
254  const typename BMIGRAPH::geometry_t&
255  op_geometry(const AutomataBase<I>&, const BMIGRAPH&);
256 
257 # undef BMIGRAPH
258 # undef BMIGRAPH_TPARAM
259 
260  } // End of namespace bmig
261 
262  // This implementation can be used as an implementation of automaton.
263  template <typename WordValue,
264  typename SeriesValue,
265  typename Letter,
266  typename Tag,
267  typename GeometryCoords>
268  struct automaton_traits<bmig::Graph<labels_are_letters, WordValue, bool, SeriesValue,
269  Letter, Tag, GeometryCoords> >
270  {
271  typedef bmig::Graph<labels_are_letters, WordValue, bool, SeriesValue,
272  Letter, Tag, GeometryCoords> graph_t;
273  typedef typename graph_t::semiring_elt_value_t semiring_elt_value_t;
274  typedef typename graph_t::monoid_elt_value_t monoid_elt_value_t;
275  typedef typename graph_t::word_value_t word_value_t;
276  typedef typename graph_t::series_set_elt_value_t series_set_elt_value_t;
277  typedef typename graph_t::letter_t letter_t;
278  typedef typename graph_t::tag_t tag_t;
279  typedef typename graph_t::geometry_t geometry_t;
280  typedef typename graph_t::label_t label_t;
281  typedef typename graph_t::states_t states_t;
282  typedef typename states_t::iterator state_iterator;
283  typedef typename graph_t::hstate_t hstate_t;
284  typedef typename graph_t::edges_t transitions_t;
285  typedef typename transitions_t::iterator transition_iterator;
286  typedef typename graph_t::htransition_t htransition_t;
287  typedef typename graph_t::initial_t initial_t;
288  typedef typename graph_t::initial_support_t initial_support_t;
289  typedef typename initial_support_t::iterator initial_iterator;
290  typedef typename graph_t::final_t final_t;
291  typedef typename graph_t::final_support_t final_support_t;
292  typedef typename final_support_t::iterator final_iterator;
293  };
294 
295  } // End of namespace vcsn
296 
297 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
298 # include <vaucanson/automata/implementation/bmig_graph_letters_spec.hxx>
299 # endif // !VCSN_USE_INTERFACE_ONLY || VCSN_USE_LIB
300 
301 #endif // !VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_LETTERS_SPEC_HH_ //
302 
Generated on Sat Jul 14 2012 18:46:39 for Vaucanson by   doxygen 1.8.1.1