Vaucanson  1.4.1
bmig_graph_letters_spec.hxx
1 // boost_graph.hxx: 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_HXX_
19 # define VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_LETTERS_SPEC_HXX_
20 
21 # include <vaucanson/automata/implementation/bmig_graph_letters_spec.hh>
22 
23 namespace vcsn
24 {
25  namespace bmig
26  {
27 
28  /*--------------------.
29  | Convenient macros. |
30  `--------------------*/
31 
32  # define BMIGRAPH_TPARAM \
33  template <class WordValue, \
34  class SeriesValue, class Letter, class Tag, class GeometryCoords>
35 
36  # define BMIGRAPH \
37  Graph<labels_are_letters, WordValue, bool, SeriesValue, Letter, Tag, GeometryCoords>
38 
39  /*-------------------------.
40  | Graph's implementation. |
41  `-------------------------*/
42 
43  /*---------------.
44  | Constructors. |
45  `---------------*/
46 
47  BMIGRAPH_TPARAM
48  inline
49  BMIGRAPH::Graph ()
50  : initial_bitset_(0),
51  final_bitset_(0),
52  number_of_epsilon_(0),
53  number_of_state_(0)
54  {
55  }
56 
66  BMIGRAPH_TPARAM
67  BMIGRAPH::Graph (unsigned initial_number_of_states,
68  unsigned)
69  : initial_bitset_(initial_number_of_states),
70  final_bitset_(initial_number_of_states),
71  number_of_epsilon_(0),
72  number_of_state_(initial_number_of_states),
73  states_(initial_number_of_states)
74  {
75  for (unsigned i = 0; i < initial_number_of_states; ++i)
76  {
77  boost::shared_ptr<unsigned> p(new unsigned(i));
78  states_[i] = p;
79  }
80  }
81 
82  BMIGRAPH_TPARAM
83  BMIGRAPH::Graph (const self_t& g)
84  {
85  tag_ = g.tag_;
86  initial_bitset_ = g.initial_bitset_;
87  final_bitset_ = g.final_bitset_;
88  number_of_epsilon_ = g.number_of_epsilon_;
89  number_of_state_ = g.number_of_state_;
90 
91  initial_.clear();
92  final_.clear();
93  graph_.clear();
94  typename geometry_t::transitions_geometry_map_t& map_transitions = geometry_.transitions();
95  map_transitions.clear();
96 
97  states_.resize(g.number_of_state_);
98  for (unsigned i = 0; i < g.number_of_state_; ++i)
99  {
100  boost::shared_ptr<unsigned> p(new unsigned(i));
101  states_[i] = p;
102  }
103  for (typename graph_data_t::const_iterator i = g.graph_.begin();
104  i != g.graph_.end();
105  ++i)
106  graph_.insert(edge_data_t(states_[*i->from_],
107  states_[*i->to_],
108  i->label_));
109  for (initial_t::iterator it = g.initial_.begin(); it != g.initial_.end(); ++it)
110  initial_.insert(states_[**it]);
111  for (final_t::iterator it = g.final_.begin(); it != g.final_.end(); ++it)
112  final_.insert(states_[**it]);
113 
114  # define VCSN_COPY_GEOMETRY(Type) \
115  { \
116  typename geometry_t::Type##_geometry_map_t& map_##Type = geometry_.Type(); \
117  map_##Type.clear(); \
118  for (typename geometry_t::Type##_geometry_map_t::const_iterator i = g.geometry_.Type().begin(); \
119  i != g.geometry_.Type().end(); \
120  ++i) \
121  map_##Type[i->first] = i->second; \
122  }
123  VCSN_COPY_GEOMETRY(states)
124  VCSN_COPY_GEOMETRY(initials)
125  VCSN_COPY_GEOMETRY(finals)
126  # undef VCSN_COPY_GEOMETRY
127  {
128  for (typename geometry_t::transitions_geometry_map_t::const_iterator i = g.geometry_.transitions().begin();
129  i != g.geometry_.transitions().end();
130  ++i)
131  {
132  typename graph_data_t::const_iterator tmp = find_edge(states_[*i->first.value()->from_],
133  states_[*i->first.value()->to_],
134  i->first.value()->label_);
135  if (tmp != graph_.end())
136  map_transitions[htransition_t(tmp)] = i->second;
137  }
138  }
139  }
140 
141  /*--------------.
142  | Destructors. |
143  `--------------*/
144 
145  BMIGRAPH_TPARAM
146  inline
147  BMIGRAPH::~Graph ()
148  {
149  }
150 
151  BMIGRAPH_TPARAM
152  typename BMIGRAPH::self_t&
153  BMIGRAPH::operator= (const self_t& g)
154  {
155  if (this == &g)
156  return *this;
157  tag_ = g.tag_;
158  initial_bitset_ = g.initial_bitset_;
159  final_bitset_ = g.final_bitset_;
160  number_of_epsilon_ = g.number_of_epsilon_;
161  number_of_state_ = g.number_of_state_;
162 
163  initial_.clear();
164  final_.clear();
165  graph_.clear();
166  typename geometry_t::transitions_geometry_map_t& map_transitions = geometry_.transitions();
167  map_transitions.clear();
168 
169  states_.resize(g.number_of_state_);
170  for (unsigned i = 0; i < g.number_of_state_; ++i)
171  {
172  boost::shared_ptr<unsigned> p(new unsigned(i));
173  states_[i] = p;
174  }
175  for (typename graph_data_t::const_iterator i = g.graph_.begin();
176  i != g.graph_.end();
177  ++i)
178  graph_.insert(edge_data_t(states_[*i->from_],
179  states_[*i->to_],
180  i->label_));
181  for (initial_t::iterator it = g.initial_.begin(); it != g.initial_.end(); ++it)
182  initial_.insert(states_[**it]);
183  for (final_t::iterator it = g.final_.begin(); it != g.final_.end(); ++it)
184  final_.insert(states_[**it]);
185 
186  # define VCSN_COPY_GEOMETRY(Type) \
187  { \
188  typename geometry_t::Type##_geometry_map_t& map_##Type = geometry_.Type(); \
189  map_##Type.clear(); \
190  for (typename geometry_t::Type##_geometry_map_t::const_iterator i = g.geometry_.Type().begin(); \
191  i != g.geometry_.Type().end(); \
192  ++i) \
193  map_##Type[i->first] = i->second; \
194  }
195  VCSN_COPY_GEOMETRY(states)
196  VCSN_COPY_GEOMETRY(initials)
197  VCSN_COPY_GEOMETRY(finals)
198  # undef VCSN_COPY_GEOMETRY
199  for (typename geometry_t::transitions_geometry_map_t::const_iterator i = g.geometry_.transitions().begin();
200  i != g.geometry_.transitions().end();
201  ++i)
202  {
203  typename graph_data_t::const_iterator tmp = find_edge(states_[*i->first.value()->from_],
204  states_[*i->first.value()->to_],
205  i->first.value()->label_);
206  if (tmp != graph_.end())
207  map_transitions[htransition_t(tmp)] = i->second;
208  }
209  return *this;
210  }
211 
212  /*------------------.
213  | Basic accessors. |
214  `------------------*/
215 
216  BMIGRAPH_TPARAM
217  typename BMIGRAPH::states_t
218  BMIGRAPH::states() const
219  {
220  return misc::Support<states_data_t>(states_);
221  }
222 
223  BMIGRAPH_TPARAM
224  typename BMIGRAPH::edges_t
225  BMIGRAPH::edges() const
226  {
227  return edges_t(graph_);
228  }
229 
230  BMIGRAPH_TPARAM
231  typename BMIGRAPH::initial_support_t
232  BMIGRAPH::initial () const
233  {
234  return initial_support_t(initial_);
235  }
236 
237  BMIGRAPH_TPARAM
238  typename BMIGRAPH::final_support_t
239  BMIGRAPH::final () const
240  {
241  return final_support_t(final_);
242  }
243 
244 
245  /*----------------------.
246  | State manipulations. |
247  `----------------------*/
248 
249  BMIGRAPH_TPARAM
250  bool
251  BMIGRAPH::has_state (const hstate_t& s) const
252  {
253  return s < states_.size();
254  }
255 
256  BMIGRAPH_TPARAM
257  typename BMIGRAPH::hstate_t
258  BMIGRAPH::add_state ()
259  {
260  initial_bitset_.append(false);
261  final_bitset_.append(false);
262  boost::shared_ptr<unsigned> p(new unsigned(number_of_state_++));
263  state_t h(p);
264  states_.push_back(h);
265  return hstate_t(h);
266  }
267 
268  BMIGRAPH_TPARAM
269  typename BMIGRAPH::hstate_t
270  BMIGRAPH::get_state (unsigned s) const
271  {
272  precondition(s < states_.size());
273  return hstate_t(states_[s]);
274  }
275 
276  BMIGRAPH_TPARAM
277  void
278  BMIGRAPH::del_state (const hstate_t& s)
279  {
280  precondition (has_state(s));
281 
282  // One removes the state h
283  graph_.get<src>().erase(s.value());
284  graph_.get<dst>().erase(s.value());
285 
286  if (number_of_state_ > 1 && s != (number_of_state_ - 1))
287  {
288  state_t lastone = states_.back();
289  states_[s] = lastone;
290  # define VCSN_UPDATE(Set) \
291  if (Set##bitset_[*lastone]) \
292  { \
293  if (Set##bitset_[s]) \
294  Set.erase(s.value()); \
295  else \
296  Set##bitset_[s] = true; \
297  } \
298  else \
299  { \
300  if (Set##bitset_[s]) \
301  { \
302  Set##bitset_[s] = false; \
303  Set.erase(s.value()); \
304  } \
305  }
306 
307  //Updating initial/final states information
308  VCSN_UPDATE(initial_)
309  VCSN_UPDATE(final_)
310  # undef VCSN_UPDATE
311  *lastone = *s.value();
312  }
313  else
314  {
315  initial_.erase(s.value());
316  final_.erase(s.value());
317  }
318 
319  --number_of_state_;
320  states_.pop_back();
321  postcondition(states_.size() == number_of_state_);
322  initial_bitset_.resize(number_of_state_);
323  final_bitset_.resize(number_of_state_);
324 
325  //Useless postcondition since the states are renumbered
326  //postcondition(!has_state(h));
327  }
328 
329  BMIGRAPH_TPARAM
330  void
331  BMIGRAPH::set_initial (const hstate_t& s,
332  const series_set_elt_value_t& v,
333  const series_set_elt_value_t& z)
334  {
335  precondition(has_state(s));
336  if (z == v)
337  {
338  initial_.erase (s.value());
339  initial_bitset_[s] = false;
340  }
341  else
342  {
343  initial_.insert (s.value());
344  initial_bitset_[s] = true;
345  }
346  }
347 
348  BMIGRAPH_TPARAM
349  const typename BMIGRAPH::series_set_elt_value_t&
350  BMIGRAPH::get_initial(const hstate_t& s, const series_set_elt_value_t &) const
351  {
352  precondition(has_state(s));
353  return initial_bitset_[s];
354  }
355 
356  BMIGRAPH_TPARAM
357  bool
358  BMIGRAPH::is_initial(const hstate_t& s, const series_set_elt_value_t&) const
359  {
360  precondition(has_state(s));
361  return initial_bitset_[s];
362  }
363 
364  BMIGRAPH_TPARAM
365  void
366  BMIGRAPH::clear_initial()
367  {
368  initial_.clear();
369  initial_bitset_.reset();
370  }
371 
372  BMIGRAPH_TPARAM
373  void
374  BMIGRAPH::set_final(const hstate_t& s,
375  const series_set_elt_value_t& v,
376  const series_set_elt_value_t& z)
377  {
378  precondition(has_state(s));
379  if (z == v)
380  {
381  final_.erase (s.value());
382  final_bitset_[s] = false;
383  }
384  else
385  {
386  final_.insert (s.value());
387  final_bitset_[s] = true;
388  }
389  }
390 
391  BMIGRAPH_TPARAM
392  const typename BMIGRAPH::series_set_elt_value_t&
393  BMIGRAPH::get_final(const hstate_t& s, const series_set_elt_value_t &) const
394  {
395  precondition(has_state(s));
396  return final_bitset_[s];
397  }
398 
399  BMIGRAPH_TPARAM
400  bool
401  BMIGRAPH::is_final(const hstate_t& s, const series_set_elt_value_t&) const
402  {
403  precondition(has_state(s));
404  return final_bitset_[s];
405  }
406 
407  BMIGRAPH_TPARAM
408  void
409  BMIGRAPH::clear_final()
410  {
411  final_.clear();
412  final_bitset_.reset();
413  }
414 
415  /*---------------------.
416  | Edge manipulations. |
417  `---------------------*/
418 
419  BMIGRAPH_TPARAM
420  bool
421  BMIGRAPH::has_edge (const hedge_t& h) const
422  {
423  succ_range r = graph_.equal_range(boost::make_tuple(*h.value()->from_,
424  h.value()->label_));
425  succ_iterator it;
426  state_t to = h.value()->to_;
427  for (it = r.first; it != r.second && it->to_ != to; ++it)
428  /*Nothing*/;
429 
430  return it != r.second;
431  }
432 
433  BMIGRAPH_TPARAM
434  typename BMIGRAPH::hedge_t
435  BMIGRAPH::add_edge (const hstate_t& from, const hstate_t& to, const label_t& l)
436  {
437  return hedge_t (graph_.insert (edge_data_t (from.value(), to.value(), l)).first);
438  }
439 
440  BMIGRAPH_TPARAM
441  void
442  BMIGRAPH::del_edge (const hedge_t& h)
443  {
444  precondition (has_edge(h));
445  graph_.erase(h.value());
446 
447  // h points to an invalid edgeValue since it is already destroyed.
448  // We can't check this postcondition anymore!
449  //postcondition(!has_edge(h));
450  }
451 
452  BMIGRAPH_TPARAM
453  typename BMIGRAPH::hstate_t
454  BMIGRAPH::src_of (const hedge_t& h) const
455  {
456  return hstate_t(h.value()->from_);
457  }
458 
459  BMIGRAPH_TPARAM
460  typename BMIGRAPH::hstate_t
461  BMIGRAPH::dst_of (const hedge_t& h) const
462  {
463  return hstate_t(h.value()->to_);
464  }
465 
466  BMIGRAPH_TPARAM
467  const typename BMIGRAPH::label_t&
468  BMIGRAPH::label_of (const hedge_t& h) const
469  {
470  return h.value()->label_;
471  }
472 
473  BMIGRAPH_TPARAM
474  void
475  BMIGRAPH::update(const hedge_t& h, const label_t& l)
476  {
477  graph_.modify(h.value(), update_hlabel<label_t>(l));
478  }
479 
480  BMIGRAPH_TPARAM
481  template <class S>
482  bool
483  BMIGRAPH::exists (const AutomataBase<S>& s) const
484  {
485  typename WordValue::iterator it;
486  typename label_t::const_iterator r;
487  label_t l;
488  WordValue w;
489 
490  for (typename graph_data_t::iterator i = graph_.begin(); i != graph_.end(); ++i)
491  {
492  // Make sure that source and destination of edge are part of the
493  // automaton.
494  if (!has_state(dst_of(hedge_t(i))) ||
495  !has_state(src_of(hedge_t(i))))
496  return false;
497 
498  // Make sure that every letter of the edge is in the alphabet.
499  l = label_of(hedge_t(i));
500  for (r = l.begin(); r != l.end(); ++r)
501  {
502  w = r->first;
503  for (it = w.begin(); it != w.end(); ++it)
504  if (!s.series().monoid().alphabet().contains(*it))
505  return false;
506  }
507  }
508  return true;
509  }
510 
511  BMIGRAPH_TPARAM
512  inline
513  typename BMIGRAPH::tag_t&
514  BMIGRAPH::tag ()
515  {
516  return tag_;
517  }
518 
519  BMIGRAPH_TPARAM
520  inline
521  const typename BMIGRAPH::tag_t&
522  BMIGRAPH::tag () const
523  {
524  return tag_;
525  }
526 
527  BMIGRAPH_TPARAM
528  inline
529  typename BMIGRAPH::geometry_t&
530  BMIGRAPH::geometry ()
531  {
532  return geometry_;
533  }
534 
535  BMIGRAPH_TPARAM
536  inline
537  const typename BMIGRAPH::geometry_t&
538  BMIGRAPH::geometry () const
539  {
540  return geometry_;
541  }
542 
543  template <class WordValue, class SeriesValue,
544  class Letter, class Tag, class GeometryCoords, class I>
545  Tag&
546  op_tag(const AutomataBase<I>&, BMIGRAPH &g)
547  {
548  return g.tag();
549  }
550 
551  template <class WordValue, class SeriesValue,
552  class Letter, class Tag, class GeometryCoords, class I>
553  const Tag&
554  op_tag(const AutomataBase<I>&, BMIGRAPH &g)
555  {
556  return g.tag();
557  }
558 
559  template <class WordValue, class SeriesValue,
560  class Letter, class Tag, class GeometryCoords, class I>
561  typename BMIGRAPH::geometry_t&
562  op_geometry(const AutomataBase<I>&, BMIGRAPH &g)
563  {
564  return g.geometry();
565  }
566 
567  template <class WordValue, class SeriesValue,
568  class Letter, class Tag, class GeometryCoords, class I>
569  const typename BMIGRAPH::geometry_t&
570  op_geometry(const AutomataBase<I>&, const BMIGRAPH &g)
571  {
572  return g.geometry();
573  }
574 
575  BMIGRAPH_TPARAM
576  typename BMIGRAPH::graph_data_t::const_iterator
577  BMIGRAPH::find_edge(const state_t& from, const state_t& to,
578  const label_t& label) const
579  {
580  succ_range r = graph_.equal_range(::boost::make_tuple(from, label));
581  for (succ_iterator i = r.first; i != r.second; ++i)
582  if (i->to_ == to)
583  return i;
584  return graph_.end();
585  }
586 
587  /*------------------.
588  | Delta functions. |
589  `------------------*/
590  # define DEFINE_DELTA_FUNCTION(FunName, DeltaKind, Target, GetElt) \
591  BMIGRAPH_TPARAM \
592  template <typename OutputIterator, typename Query> \
593  void \
594  BMIGRAPH::FunName(OutputIterator res, \
595  const typename BMIGRAPH::hstate_t& s, \
596  const Query& query, \
597  ::vcsn::delta_kind::DeltaKind) const \
598  { \
599  assertion(has_state(s)); \
600  Target##_range r = graph_.get<Target>().equal_range(s.value()); \
601  for (Target##_iterator e = r.first; e != r.second; ++e) \
602  if (query(hedge_t(graph_.project<0>(e)))) \
603  *res++ = GetElt; \
604  }
605 
606  DEFINE_DELTA_FUNCTION (delta, transitions, src, hedge_t(graph_.project<0>(e)));
607  DEFINE_DELTA_FUNCTION (delta, states, src, hstate_t(e->to_));
608  DEFINE_DELTA_FUNCTION (rdelta, transitions, dst, hedge_t(graph_.project<0>(e)));
609  DEFINE_DELTA_FUNCTION (rdelta, states, dst, hstate_t(e->from_));
610 
611  # undef DEFINE_DELTA_FUNCTION
612 
613 
614  // End of syntactic sugar
615 # undef BMIGRAPH_TPARAM
616 # undef BMIGRAPH
617  } // End of namespace boost
618 } // End of namespace vcsn
619 
620 #endif // !VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_IMPL_HXX_ //
Generated on Sat Jul 14 2012 18:46:39 for Vaucanson by   doxygen 1.8.1.1