Vcsn  2.2
Be Rational
mutable-automaton.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <algorithm>
4 #include <cassert>
5 #include <vector>
6 
7 #include <boost/range/algorithm/find.hpp>
8 #include <boost/range/algorithm/find_if.hpp>
9 #include <boost/range/irange.hpp>
10 
11 #include <vcsn/core/automaton.hh>
12 #include <vcsn/core/fwd.hh>
13 #include <vcsn/core/transition.hh>
14 #include <vcsn/ctx/context.hh>
15 #include <vcsn/ctx/traits.hh>
16 #include <vcsn/misc/crange.hh>
17 #include <vcsn/misc/format.hh>
18 #include <vcsn/misc/index.hh>
19 #include <vcsn/misc/memory.hh>
20 #include <vcsn/misc/symbol.hh>
21 
22 namespace vcsn
23 {
24  namespace detail
25  {
27  template <typename Context>
28  class mutable_automaton_impl
29  {
30  public:
31  using context_t = Context;
35  template <typename Ctx = Context>
39  using kind_t = typename context_t::kind_t;
40 
41  using labelset_ptr = typename context_t::labelset_ptr;
42  using weightset_ptr = typename context_t::weightset_ptr;
43 
45  struct state_tag {};
48  struct transition_tag {};
51  using label_t = typename labelset_t::value_t;
53  using weight_t = typename weightset_t::value_t;
54 
55  protected:
58 
61 
63  using tr_store_t = std::vector<stored_transition_t>;
65  using tr_cont_t = std::vector<transition_t>;
66 
69  {
74  };
75 
77  using st_store_t = std::vector<stored_state_t>;
78 
80  using free_store_t = std::vector<unsigned>;
81 
90 
91  public:
92  mutable_automaton_impl() = delete;
95  : ctx_{ctx}
96  , states_{2}
97  , prepost_label_(ctx.labelset()->special())
98  {}
99 
101  : ctx_(that.ctx_)
102  , prepost_label_(that.prepost_label_)
103  {
104  *this = std::move(that);
105  }
106 
108  {
109  if (this != &that)
110  {
111  ctx_ = std::move(that.ctx_);
112  prepost_label_ = std::move(that.prepost_label_);
113  std::swap(states_, that.states_);
114  std::swap(states_fs_, that.states_fs_);
115  std::swap(transitions_, that.transitions_);
116  std::swap(transitions_fs_, that.transitions_fs_);
117  }
118  return *this;
119  }
120 
121 
122  /*----------------.
123  | Related sets. |
124  `----------------*/
125 
126  static symbol sname()
127  {
128  static auto res
129  = symbol{"mutable_automaton<" + context_t::sname() + '>'};
130  return res;
131  }
132 
133  std::ostream& print_set(std::ostream& o, format fmt = {}) const
134  {
135  o << "mutable_automaton<";
136  context().print_set(o, fmt);
137  return o << '>';
138  }
139 
140  const context_t& context() const { return ctx_; }
141  const weightset_ptr& weightset() const { return ctx_.weightset(); }
142  const labelset_ptr& labelset() const { return ctx_.labelset(); }
143 
144 
145  /*----------------------------------.
146  | Special states and transitions. |
147  `----------------------------------*/
148 
149  // pseudo-initial and final states.
150  // The code below assumes that pre() and post() are the first
151  // two states of the automaton. In other words, all other states
152  // have greater numbers. We also assume that pre()<post().
153  static constexpr state_t pre() { return 0U; }
154  static constexpr state_t post() { return 1U; }
156  static constexpr state_t null_state() { return -1U; }
158  static constexpr transition_t null_transition() { return -1U; }
161  static constexpr transition_t lazy_transition() { return -2U; }
162 
164  label_t prepost_label() const
165  {
166  return prepost_label_;
167  }
168 
169 
170  /*--------------.
171  | Statistics. |
172  `--------------*/
173 
174  size_t num_all_states() const { return states_.size() - states_fs_.size(); }
175  size_t num_states() const { return num_all_states() - 2; }
176  size_t num_initials() const { return states_[pre()].succ.size(); }
177  size_t num_finals() const { return states_[post()].pred.size(); }
178  size_t num_transitions() const
179  {
180  return (transitions_.size()
181  - transitions_fs_.size() - num_initials() - num_finals());
182  }
183 
184 
185  /*---------------------.
186  | Queries on states. |
187  `---------------------*/
188 
190  bool
191  has_state(state_t s) const
192  {
193  // Any number outside our container is not a state.
194  // (This includes "null_state()".)
195  if (states_.size() <= s)
196  return false;
197  else
198  {
199  const stored_state_t& ss = states_[s];
200  // Erased states have 'invalid' as their first successor.
201  return ss.succ.empty() || ss.succ.front() != null_transition();
202  }
203  }
204 
207  bool
208  is_lazy(state_t s) const
209  {
210  auto ts = all_out(s);
211  return !ts.empty() && ts.front() == lazy_transition();
212  }
213 
216  bool
217  is_lazy_in(state_t s) const
218  {
219  auto ts = all_in(s);
220  return !ts.empty() && ts.front() == lazy_transition();
221  }
222 
224  bool
225  is_initial(state_t s) const
226  {
227  return has_transition(pre(), s, prepost_label_);
228  }
229 
231  bool
232  is_final(state_t s) const
233  {
234  return has_transition(s, post(), prepost_label_);
235  }
236 
238  ATTRIBUTE_PURE
239  weight_t
240  get_initial_weight(state_t s) const
241  {
242  transition_t t = get_transition(pre(), s, prepost_label_);
243  if (t == null_transition())
244  return weightset()->zero();
245  else
246  return weight_of(t);
247  }
248 
250  ATTRIBUTE_PURE
251  weight_t
252  get_final_weight(state_t s) const
253  {
254  transition_t t = get_transition(s, post(), prepost_label_);
255  if (t == null_transition())
256  return weightset()->zero();
257  else
258  return weight_of(t);
259  }
260 
261 
262  /*--------------------------.
263  | Queries on transitions. |
264  `--------------------------*/
265 
266  transition_t
267  get_transition(state_t src, state_t dst, label_t l) const
268  {
269  assert(has_state(src));
270  assert(!is_lazy(src));
271  assert(has_state(dst));
272  assert(!is_lazy_in(dst));
273  const tr_cont_t& succ = states_[src].succ;
274  const tr_cont_t& pred = states_[dst].pred;
275  const auto& ls = *this->labelset();
276  if (succ.size() <= pred.size())
277  {
278  auto i =
279  boost::find_if(succ,
280  [this,l,ls,dst] (transition_t t)
281  {
282  return (dst_of(t) == dst
283  && ls.equal(label_of(t), l));
284  });
285  if (i != end(succ))
286  return *i;
287  }
288  else
289  {
290  auto i =
291  boost::find_if(pred,
292  [this,l,ls,src] (transition_t t)
293  {
294  return (src_of(t) == src
295  && ls.equal(label_of(t), l));
296  });
297  if (i != end(pred))
298  return *i;
299  }
300  return null_transition();
301  }
302 
303  bool
304  has_transition(state_t src, state_t dst, label_t l) const
305  {
306  return get_transition(src, dst, l) != null_transition();
307  }
308 
309  bool
310  has_transition(transition_t t) const
311  {
312  // Any number outside our container is not a transition.
313  // (This includes "null_transition()".)
314  if (t >= transitions_.size())
315  return false;
316 
317  // Erased transition have invalid source state.
318  return transitions_[t].src != null_state();
319  }
320 
321  state_t src_of(transition_t t) const { return transitions_[t].src; }
322  state_t dst_of(transition_t t) const { return transitions_[t].dst; }
323  label_t label_of(transition_t t) const
324  {
325  return transitions_[t].get_label();
326  }
327 
328  weight_t weight_of(transition_t t) const
329  {
330  return transitions_[t].get_weight();
331  }
332 
333 
334  /*---------------------.
335  | Edition of states. |
336  `---------------------*/
337 
338  protected:
340  void
341  del_transition_from_src(transition_t t)
342  {
343  stored_transition_t& st = transitions_[t];
344  auto& succ = states_[st.src].succ;
345  auto tsucc = boost::range::find(succ, t);
346  assert(tsucc != succ.end());
347  *tsucc = std::move(succ.back());
348  succ.pop_back();
349  }
350 
352  void
353  del_transition_from_dst(transition_t t)
354  {
355  stored_transition_t& st = transitions_[t];
356  auto& pred = states_[st.dst].pred;
357  auto tpred = boost::range::find(pred, t);
358  assert(tpred != pred.end());
359  *tpred = std::move(pred.back());
360  pred.pop_back();
361  }
362 
363  void
364  del_transition_container(tr_cont_t& tc, bool from_succ)
365  {
366  for (auto t: tc)
367  {
368  if (from_succ)
369  del_transition_from_dst(t);
370  else
371  del_transition_from_src(t);
372  transitions_[t].src = null_state();
373  }
374  transitions_fs_.insert(transitions_fs_.end(), tc.begin(), tc.end());
375  tc.clear();
376  }
377 
378  public:
380  state_t
381  new_state()
382  {
383  state_t res;
384  if (states_fs_.empty())
385  {
386  res = states_.size();
387  states_.emplace_back();
388  }
389  else
390  {
391  res = states_fs_.back();
392  states_fs_.pop_back();
393  stored_state_t& ss = states_[res];
394  // De-invalidate this state: remove the invalid transition.
395  ss.succ.clear();
396  }
397  return res;
398  }
399 
400  std::ostream&
401  print_state(state_t s, std::ostream& o) const
402  {
403  if (s == pre())
404  o << "pre";
405  else if (s == post())
406  o << "post";
407  else
408  o << s - 2;
409  return o;
410  }
411 
412  std::ostream&
413  print_state_name(state_t s, std::ostream& o,
414  format = {},
415  bool = false) const
416  {
417  return print_state(s, o);
418  }
419 
420  static constexpr bool
421  state_has_name(state_t)
422  {
423  return false;
424  }
425 
426  void
427  del_state(state_t s)
428  {
429  assert(has_state(s));
430  assert(s > post()); // Cannot erase pre() and post().
431  stored_state_t& ss = states_[s];
432  del_transition_container(ss.pred, false);
433  del_transition_container(ss.succ, true);
434  ss.succ.emplace_back(null_transition()); // So has_state() can work.
435  states_fs_.emplace_back(s);
436  }
437 
438  void
439  set_initial(state_t s, weight_t w)
440  {
441  set_transition(pre(), s, prepost_label_, w);
442  }
443 
444  void
445  set_initial(state_t s)
446  {
447  set_initial(s, weightset()->one());
448  }
449 
450  void
451  set_lazy(state_t s, bool lazy = true)
452  {
453  assert(has_state(s));
454  stored_state_t& ss = states_[s];
455  assert(ss.succ.empty()
456  || ss.succ.front() == lazy_transition());
457  ss.succ.clear();
458  if (lazy)
459  ss.succ.emplace_back(lazy_transition());
460  }
461 
462  void
463  set_lazy_in(state_t s, bool lazy = true)
464  {
465  assert(has_state(s));
466  stored_state_t& ss = states_[s];
467  assert(ss.pred.empty()
468  || ss.pred.front() == lazy_transition());
469  ss.pred.clear();
470  if (lazy)
471  ss.pred.emplace_back(lazy_transition());
472  }
473 
474  transition_t
475  add_initial(state_t s, weight_t w)
476  {
477  return add_transition(pre(), s, prepost_label_, w);
478  }
479 
480  void
481  unset_initial(state_t s)
482  {
483  set_initial(s, weightset()->zero());
484  }
485 
486  void
487  set_final(state_t s, weight_t w)
488  {
489  set_transition(s, post(), prepost_label_, w);
490  }
491 
492  void
493  set_final(state_t s)
494  {
495  set_final(s, weightset()->one());
496  }
497 
498  transition_t
499  add_final(state_t s, weight_t w)
500  {
501  return add_transition(s, post(), prepost_label_, w);
502  }
503 
504  void
505  unset_final(state_t s)
506  {
507  set_final(s, weightset()->zero());
508  }
509 
510 
511  /*--------------------------.
512  | Edition of transitions. |
513  `--------------------------*/
514 
515  void
516  del_transition(transition_t t)
517  {
518  assert(has_transition(t));
519  // Remove transition from source and destination.
520  del_transition_from_src(t);
521  del_transition_from_dst(t);
522  // Actually erase the transition.
523  transitions_[t].src = null_state();
524  transitions_fs_.emplace_back(t);
525  }
526 
528  void
529  del_transition(state_t src, state_t dst, label_t l)
530  {
531  transition_t t = get_transition(src, dst, l);
532  if (t != null_transition())
533  del_transition(t);
534  }
535 
546  transition_t
547  new_transition(state_t src, state_t dst, label_t l, weight_t w)
548  {
549  assert(!has_transition(src, dst, l));
550  if (weightset()->is_zero(w))
551  return null_transition();
552  else
553  {
554  // FIXME: When src == pre() || dst == post(), label must be empty.
555  transition_t t;
556  if (transitions_fs_.empty())
557  {
558  t = transitions_.size();
559  transitions_.emplace_back(src, dst, l, w);
560  }
561  else
562  {
563  t = transitions_fs_.back();
564  transitions_fs_.pop_back();
565  stored_transition_t& st = transitions_[t];
566  st.src = src;
567  st.dst = dst;
568  st.set_label(l);
569  st.set_weight(w);
570  }
571  states_[src].succ.emplace_back(t);
572  states_[dst].pred.emplace_back(t);
573  return t;
574  }
575  }
576 
589  template <typename A>
590  transition_t
591  new_transition_copy(state_t src, state_t dst,
592  const A& aut, typename A::element_type::transition_t t,
593  bool transpose = false)
594  {
595  auto l = aut->label_of(t);
596  auto w = aut->weight_of(t);
597  if (transpose)
598  {
599  l = aut->labelset()->transpose(l);
600  w = aut->weightset()->transpose(w);
601  }
602  return new_transition(src, dst,
603  labelset()->conv(*aut->labelset(), l),
604  weightset()->conv(*aut->weightset(), w));
605  }
606 
608  transition_t
609  new_transition(state_t src, state_t dst, label_t l)
610  {
611  return new_transition(src, dst, l, weightset()->one());
612  }
613 
624  transition_t
625  set_transition(state_t src, state_t dst, label_t l, weight_t w)
626  {
627  // It's illegal to connect pre() to post().
628  // FIXME: reenable except for labels_are_one.
629  // assert(src != pre() || dst != post());
630  // It's illegal to leave post().
631  assert(src != post());
632  // It's illegal to go to pre().
633  assert(dst != pre());
634 
635  transition_t t = get_transition(src, dst, l);
636  if (t == null_transition())
637  t = new_transition(src, dst, l, w);
638  else if (weightset()->is_zero(w))
639  {
640  del_transition(t);
641  t = null_transition();
642  }
643  else
644  {
645  stored_transition_t& st = transitions_[t];
646  st.set_label(l);
647  st.set_weight(w);
648  }
649  return t;
650  }
651 
655  {
656  return set_transition(src, dst, l, weightset()->one());
657  }
658 
671  {
672  transition_t t = get_transition(src, dst, l);
673  if (t == null_transition())
674  t = new_transition(src, dst, l, w);
675  else
676  {
677  w = weightset()->add(weight_of(t), w);
678  t = set_weight(t, w);
679  }
680  return t;
681  }
682 
686  {
687  return add_transition(src, dst, l, weightset()->one());
688  }
689 
698  template <typename A>
701  const A& aut, typename A::element_type::transition_t t,
702  bool transpose = false)
703  {
704  auto l = aut->label_of(t);
705  auto w = aut->weight_of(t);
706  if (transpose)
707  {
708  l = aut->labelset()->transpose(l);
709  w = aut->weightset()->transpose(w);
710  }
711  return add_transition(src, dst,
712  labelset()->conv(*aut->labelset(), l),
713  weightset()->conv(*aut->weightset(), w));
714  }
715 
717  std::ostream& print(transition_t t, std::ostream& o) const
718  {
719  if (t == null_transition())
720  o << "null_transition";
721  else if (t == lazy_transition())
722  o << "lazy_transition";
723  else
724  {
725  print_state_name(src_of(t), o) << " -- <";
726  weightset()->print(weight_of(t), o) << '>';
727  labelset()->print(label_of(t), o) << " --> ";
728  print_state_name(dst_of(t), o);
729  }
730  return o;
731  }
732 
734  std::ostream& print(std::ostream& o) const
735  {
736  for (auto s: all_states())
737  {
738  o << "State: ";
739  print_state_name(s, o) << '\n';
740  o << " Incoming:\n";
741  for (auto t: all_in(s))
742  {
743  o << " ";
744  print(t, o) << '\n';
745  }
746  o << " Outgoing:\n";
747  for (auto t: all_out(s))
748  {
749  o << " ";
750  print(t, o) << '\n';
751  }
752  }
753  return o;
754  }
755 
758  {
759  if (weightset()->is_zero(w))
760  {
761  del_transition(t);
762  return null_transition();
763  }
764  else
765  transitions_[t].set_weight(w);
766  return t;
767  }
768 
769  weight_t
771  {
772  return weight_of(set_weight(t, weightset()->add(weight_of(t), w)));
773  }
774 
775  weight_t
777  {
778  return weight_of(set_weight(t, weightset()->mul(w, weight_of(t))));
779  }
780 
781  weight_t
783  {
784  return weight_of(set_weight(t, weightset()->mul(weight_of(t), w)));
785  }
786 
787 
788  /*---------------------------------------.
789  | Iteration on states and transitions. |
790  `---------------------------------------*/
791 
792  protected:
795  template <typename Pred>
796  auto state_range(state_t b, state_t e, Pred pred) const
797  {
799  (boost::irange<state_t>(b, e),
800  [this, pred]
801  (state_t s)
802  {
803  const stored_state_t& ss = states_[s];
804  return ((ss.succ.empty()
805  || ss.succ.front() != null_transition())
806  && pred(s));
807  });
808  }
809 
811  auto state_range(state_t b, state_t e) const
812  {
813  return state_range(b, e, [](state_t) { return true; });
814  }
815 
816  public:
819  auto all_states() const
820  {
821  return state_range(0U, states_.size());
822  }
823 
826  template <typename Pred>
827  auto all_states(Pred pred) const
828  {
829  return state_range(0U, states_.size(), pred);
830  }
831 
834  auto states() const
835  {
836  return state_range(post() + 1, states_.size());
837  }
838 
840  auto all_transitions() const
841  {
843  (boost::irange<transition_t>(0U, transitions_.size()),
844  [this](transition_t t)
845  {
846  return src_of(t) != null_state();
847  });
848  }
849 
853  all_out(state_t s) const
854  {
855  assert(has_state(s));
856  return states_[s].succ;
857  }
858 
862  all_in(state_t s) const
863  {
864  assert(has_state(s));
865  return states_[s].pred;
866  }
867  };
868  }
869 
870  template <typename Context>
871  mutable_automaton<Context>
872  make_mutable_automaton(const Context& ctx)
873  {
874  return make_shared_ptr<mutable_automaton<Context>>(ctx);
875  }
876 
877  template <typename Context>
878  auto
879  make_nullable_automaton(const Context& ctx)
880  {
882  }
883 }
const labelset_ptr & labelset() const
weight_t weight_of(transition_t t) const
free_store_t transitions_fs_
Free indexes in transitions_.
auto states() const
All states excluding pre()/post().
container_filter_range< Cont, Pred > make_container_filter_range(const Cont &cont, Pred pred)
Definition: crange.hh:112
transition_t set_transition(state_t src, state_t dst, label_t l)
Same as above, with unit weight.
state_t dst_of(transition_t t) const
std::vector< transition_t > tr_cont_t
All the incoming/outgoing transition handles of a state.
std::vector< stored_state_t > st_store_t
All the automaton's states.
transition_t add_transition(state_t src, state_t dst, label_t l, weight_t w)
Add a transition between two states.
weight_t add_weight(transition_t t, weight_t w)
transition_tuple< state_t, label_t, weight_t > stored_transition_t
Data stored per transition.
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:59
transition_t add_transition(state_t src, state_t dst, label_t l)
Same as above, with weight one.
std::shared_ptr< detail::mutable_automaton_impl< Context >> mutable_automaton
Definition: fwd.hh:25
std::vector< unsigned > free_store_t
A list of unused indexes in the states/transitions tables.
Bidirectional automata.
Definition: fwd.hh:21
typename context_t::weightset_ptr weightset_ptr
Definition: a-star.hh:8
const weightset_ptr & weightset() const
mutable_automaton_impl & operator=(mutable_automaton_impl &&that)
weightset_t_of< context_t > weightset_t
auto state_range(state_t b, state_t e, Pred pred) const
The range of index numbers in [b .
label_t prepost_label_
Label for initial and final transitions.
transition_t set_transition(state_t src, state_t dst, label_t l, weight_t w)
Set a transition between two states.
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:55
Lightweight state handle (or index).
An input/output format for valuesets.
Definition: format.hh:11
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
mutable_automaton_impl(mutable_automaton_impl &&that)
std::ostream & print(transition_t t, std::ostream &o) const
Print a transition, for debugging.
Aut transpose(const transpose_automaton< Aut > &aut)
Definition: transpose.hh:227
weight_t rmul_weight(transition_t t, weight_t w)
labelset_t_of< context_t > labelset_t
weight_t lmul_weight(transition_t t, weight_t w)
typename context_t::labelset_ptr labelset_ptr
index_t_impl< transition_tag > transition_t
transition_t add_transition_copy(state_t src, state_t dst, const A &aut, typename A::element_type::transition_t t, bool transpose=false)
Add a transition between two states, copying the label from the given transition. ...
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
mutable_automaton_impl(const context_t &ctx)
Transition with label and non Boolean weight.
Definition: transition.hh:56
transition_t get_transition(state_t src, state_t dst, label_t l) const
nullableset_context_t< context< LabelSet, WeightSet > > make_nullableset_context(const context< LabelSet, WeightSet > &ctx)
The nullableset context of a context.
Definition: labelset.hh:174
bool has_state(state_t s) const
Whether state s belongs to the automaton.
state_t src_of(transition_t t) const
typename weightset_t::value_t weight_t
Transition weight.
Restrict the interface of a container to begin/end.
Definition: fwd.hh:11
typename context_t::kind_t kind_t
symbol sname()
Definition: name.hh:67
static constexpr transition_t null_transition()
Invalid transition.
auto state_range(state_t b, state_t e) const
The range of state numbers in [b .. e].
auto make_nullable_automaton(const Context &ctx)
const context_t & context() const
static constexpr transition_t lazy_transition()
Invalid transition that shows that the state's outgoing transitions are unknown.
static dyn::context ctx(const driver &d)
Get the context of the driver.
Definition: parse.cc:82
transition_t set_weight(transition_t t, weight_t w)
auto all_states() const
All states including pre()/post().
Lightweight state/transition handle (or index).
Definition: index.hh:9
Lightweight transition handle (or index).
mutable_automaton< Context > make_mutable_automaton(const Context &ctx)
label_t label_of(transition_t t) const
transition_t new_transition(state_t src, state_t dst, label_t l, weight_t w)
Create a transition between two states.
container_range< const tr_cont_t & > all_out(state_t s) const
Indexes of all transitions leaving state s.
std::ostream & print(std::ostream &o) const
Print an automaton, for debugging.
static constexpr state_t null_state()
Invalid state.
container_range< const tr_cont_t & > all_in(state_t s) const
Indexes of all transitions arriving to state s.
std::ostream & print_state_name(state_t s, std::ostream &o, format={}, bool=false) const
context_t ctx_
The algebraic type of this automaton.
auto all_states(Pred pred) const
All states including pre()/post() that validate pred.
mutable_automaton< Ctx > fresh_automaton_t
The (shared pointer) type to use if we have to create an automaton of the same (underlying) type...
std::ostream & print_set(std::ostream &o, format fmt={}) const
free_store_t states_fs_
Free indexes in states_.
typename labelset_t::value_t label_t
Transition label.
auto all_transitions() const
All the transition indexes between all states (including pre and post).
auto conv(const ValueSet &vs, const std::string &str, Args &&...args) -> decltype(vs.conv(std::declval< std::istream & >(), std::forward< Args >(args)...))
Parse str via vs.conv.
Definition: stream.hh:28
std::vector< stored_transition_t > tr_store_t
All the automaton's transitions.