Awali
Another Weighted Automata library
mutable_automaton.hh
Go to the documentation of this file.
1 // This file is part of Awali.
2 // Copyright 2016-2021 Sylvain Lombardy, Victor Marsault, Jacques Sakarovitch
3 //
4 // Awali is a free software: you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License as published by
6 // the Free Software Foundation, either version 3 of the License, or
7 // (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with this program. If not, see <http://www.gnu.org/licenses/>.
16 
17 #ifndef AWALI_CORE_MUTABLE_AUTOMATON_HH
18 # define AWALI_CORE_MUTABLE_AUTOMATON_HH
19 
20 # include <algorithm>
21 # include <cassert>
22 # include <vector>
23 # include <sstream>
24 # include <string>
25 
26 //#include <awali/sttc/core/crange.hh>
27 #include <awali/common/types.hh>
30 #include <awali/sttc/ctx/traits.hh>
35 
36 namespace awali {
37  namespace sttc {
38 
39  namespace internal {
40  template <typename Context>
41  class mutable_automaton_impl;
42  }
43  template <typename Context>
45  = std::shared_ptr<internal::mutable_automaton_impl<Context>>;
46 
47  namespace internal
48  {
49  template <typename Context>
51  {
52  public:
53  using context_t = Context;
59  using kind_t = typename context_t::kind_t;
60 
61  using labelset_ptr = typename context_t::labelset_ptr;
62  using weightset_ptr = typename context_t::weightset_ptr;
63 
65  using label_t = typename labelset_t::value_t;
67  using weight_t = typename weightset_t::value_t;
69  using history_t = std::shared_ptr<history_base>;
70  using names_t = std::shared_ptr<string_history>;
71 
74 
77 
79  using tr_cont_t = std::vector<transition_t>;
80 
83  {
86  };
88  using st_store_t = std::vector<stored_state_t>;
90  using tr_store_t = std::vector<stored_transition_t>;
92  using free_store_t = std::vector<state_t>;
93  private:
94 
95  st_store_t states_;
97  free_store_t states_fs_;
98  tr_store_t transitions_;
100  free_store_t transitions_fs_;
102  label_t prepost_label_;
104  history_t history_;
105  // State names
106  names_t names_;
107  public:
111  : ctx_{ctx}
112  , states_{2}
113  , prepost_label_(ctx.labelset()->special())
114  , history_(std::make_shared<no_history>())
115  , names_(std::make_shared<string_history>())
116  {}
117 
119  : ctx_(that.ctx_)
120  , prepost_label_(that.prepost_label_) {
121  *this = std::move(that);
122  }
123 
125  if (this != &that) {
126  ctx_ = std::move(that.ctx_);
127  prepost_label_ = std::move(that.prepost_label_);
128  std::swap(states_, that.states_);
129  std::swap(states_fs_, that.states_fs_);
130  std::swap(transitions_, that.transitions_);
131  std::swap(transitions_fs_, that.transitions_fs_);
132  history_ = that.history_;
133  names_ = that.names_;
134  }
135  return *this;
136  }
137 
138  // Related sets
140 
141  static std::string sname() {
142  return "mutable_automaton<" + context_t::sname() + ">";
143  }
144 
145  std::string vname(bool full = true) const {
146  return "mutable_automaton<" + context().vname(full) + ">";
147  }
148 
149  const context_t& context() const { return ctx_; }
150  const weightset_ptr& weightset() const { return ctx_.weightset(); }
151  const labelset_ptr& labelset() const { return ctx_.labelset(); }
152 
153  // Special states and transitions
155 
156  // pseudo-initial and final states.
157  // The code below assumes that pre() and post() are the first
158  // two states of the automaton. In other words, all other states
159  // have greater numbers. We also assume that pre()<post().
160  static constexpr state_t pre() { return 0U; }
161  static constexpr state_t post() { return 1U; }
162  // Invalid transition or state.
163  static constexpr state_t null_state() { return -1U; }
164  static constexpr transition_t null_transition() { return -1U; }
165 
167  return prepost_label_;
168  }
169 
170  // Statistics
172 
173  size_t num_all_states() const { return states_.size() - states_fs_.size(); }
174  size_t num_states() const { return num_all_states() - 2; }
175  size_t num_initials() const { return states_[pre()].succ.size(); }
176  size_t num_finals() const { return states_[post()].pred.size(); }
177  size_t num_transitions() const {
178  return (transitions_.size()
179  - transitions_fs_.size() - num_initials() - num_finals());
180  }
181 
182  // Queries on states
184 
185  bool
186  has_state(state_t s) const {
187  // Any number outside our container is not a state.
188  // (This includes "null_state()".)
189  if (s >= states_.size())
190  return false;
191  const stored_state_t& ss = states_[s];
192 
193  // Erased states have 'invalid' as their first successor.
194  return ss.succ.empty() || ss.succ.front() != null_transition();
195  }
196 
197  state_t max_state() const {
198  state_t s=states_.size();
199  for(; !has_state(s); --s)
200  ;
201  return s;
202  }
203 
204  bool
205  is_initial(state_t s) const {
206  return has_transition(pre(), s, prepost_label_);
207  }
208 
209  bool
210  is_final(state_t s) const {
211  return has_transition(s, post(), prepost_label_);
212  }
213 
214  ATTRIBUTE_PURE
215  weight_t
217  transition_t t = get_transition(pre(), s, prepost_label_);
218  if (t == null_transition())
219  return weightset()->zero();
220  else
221  return weight_of(t);
222  }
223 
224  ATTRIBUTE_PURE
225  weight_t
227  transition_t t = get_transition(s, post(), prepost_label_);
228  if (t == null_transition())
229  return weightset()->zero();
230  else
231  return weight_of(t);
232  }
233 
234  // Queries on transitions
236 
238  get_transition(state_t src, state_t dst, label_t l) const {
239  assert(has_state(src));
240  assert(has_state(dst));
241  const tr_cont_t& succ = states_[src].succ;
242  const tr_cont_t& pred = states_[dst].pred;
243  const auto& ls = *this->labelset();
244  if (succ.size() <= pred.size()) {
245  auto i =
246  std::find_if(begin(succ), end(succ),
247  [this,l,ls,dst] (transition_t t) -> bool {
248  const stored_transition_t& st = transitions_[t];
249  return (st.dst == dst
250  && ls.equals(st.get_label(), l));
251  });
252  if (i != end(succ))
253  return *i;
254  }
255  else {
256  auto i =
257  std::find_if(begin(pred), end(pred),
258  [this,l,ls,src] (transition_t t) -> bool {
259  const stored_transition_t& st = transitions_[t];
260  return (st.src == src
261  && ls.equals(st.get_label(), l));
262  });
263  if (i != end(pred))
264  return *i;
265  }
266  return null_transition();
267  }
268 
269  bool
270  has_transition(state_t src, state_t dst, label_t l) const {
271  return get_transition(src, dst, l) != null_transition();
272  }
273 
274  bool
276  // Any number outside our container is not a transition.
277  // (This includes "null_transition()".)
278  if (t >= transitions_.size())
279  return false;
280 
281  // Erased transition have invalid source state.
282  return transitions_[t].src != null_state();
283  }
284 
285  state_t src_of(transition_t t) const { return transitions_[t].src; }
286  state_t dst_of(transition_t t) const { return transitions_[t].dst; }
288  return transitions_[t].get_label();
289  }
290 
292  return transitions_[t].get_weight();
293  }
294 
295  // Edition of states
297 
298  protected:
300  void
302  stored_transition_t& st = transitions_[t];
303  auto& succ = states_[st.src].succ;
304  auto tsucc = std::find(succ.begin(), succ.end(), t);
305  assert(tsucc != succ.end());
306  *tsucc = std::move(succ.back());
307  succ.pop_back();
308  }
309 
311  void
313  stored_transition_t& st = transitions_[t];
314  auto& pred = states_[st.dst].pred;
315  auto tpred = std::find(pred.begin(), pred.end(), t);
316  assert(tpred != pred.end());
317  *tpred = std::move(pred.back());
318  pred.pop_back();
319  }
320 
321  void
322  del_transition_container(tr_cont_t& tc, bool from_succ) {
323  for (auto t: tc) {
324  if (from_succ)
326  else
328  transitions_[t].src = null_state();
329  }
330  transitions_fs_.insert(transitions_fs_.end(), tc.begin(), tc.end());
331  tc.clear();
332  }
333 
334  public:
335  state_t
337  state_t s;
338  if (states_fs_.empty()) {
339  s = states_.size();
340  states_.resize(s + 1);
341  }
342  else {
343  s = states_fs_.back();
344  states_fs_.pop_back();
345  }
346  stored_state_t& ss = states_[s];
347  // De-invalidate this state: remove the invalid transition.
348  ss.succ.clear();
349  return s;
350  }
351 
352  history_t history() const {
353  return history_;
354  }
355 
357  history_ = h;
358  }
359 
360  void strip_history() {
361  history_ = std::make_shared<no_history>();
362  }
363 
364  void strip_names() {
365  history_ = std::make_shared<string_history>();
366  }
367 
368  std::ostream& print_state(state_t s, std::ostream& o) const {
369  if(names_->has_history(s))
370  return names_->print_state_name(s, o, "text");
371  if(s == pre())
372  return o << "_";
373  if(s == post())
374  return o << "_";
375  return o << '$' << (s-2);
376  }
377 
378  std::ostream& print_state_name(state_t s, std::ostream& o,
379  const std::string& fmt = "text") const {
380  return print_state(s, o);
381  }
382 
383  std::string get_state_name(state_t s) const {
384  if(names_->has_history(s))
385  return names_->get_state_name(s);
386  std::ostringstream o;
387  print_state(s, o);
388  return o.str();
389  }
390 
391  std::ostream& print_state_history(state_t s, std::ostream& o,
392  const std::string& fmt = "text") const {
393  if(history_->has_history(s))
394  return history_->print_state_name(s, o, fmt);
395  return print_state_name(s, o, fmt);
396  }
397 
398  bool has_history(state_t s) const {
399  return history_->has_history(s);
400  }
401 
403  for(auto s : states())
404  if(history_->has_history(s)) {
405  std::ostringstream o;
406  print_state_history(s, o);
407  set_state_name(s,o.str());
408  }
409  }
410 
411  bool has_explicit_name(state_t s) const {
412  return names_->has_history(s);
413  }
414 
415  void set_state_name(state_t s, const std::string& n) {
416  names_->add_state(s, n);
417  }
418 
419  state_t get_state_by_name(const std::string& name) const {
420  for(auto i : states()) {
421  std::ostringstream os;
422  print_state_name(i,os);
423  if(os.str()==name)
424  return i;
425  }
426  return null_state();
427  }
428 
429  bool set_name(const std::string& n) {
430  if(n.length()>0 && n[0]=='$')
431  return false;
432  names_->set_name(n);
433  return true;
434  }
435 
436  void set_desc(const std::string& d) {
437  names_->set_desc(d);
438  }
439 
440  const std::string& get_name() const {
441  return names_->get_name();
442  }
443 
444  const std::string& get_desc() const {
445  return names_->get_desc();
446  }
447 
448 
449  void del_state(state_t s) {
450  assert(has_state(s));
451  assert(s > post()); // Cannot erase pre() and post().
452  stored_state_t& ss = states_[s];
453  del_transition_container(ss.pred, false);
454  del_transition_container(ss.succ, true);
455  history_->remove_history(s);
456  names_->remove_history(s);
457  ss.succ.emplace_back(null_transition()); // So has_state() can work.
458  states_fs_.emplace_back(s);
459  }
460 
462  set_transition(pre(), s, prepost_label_, w);
463  }
464 
466  set_initial(s, weightset()->one());
467  }
468 
470  return add_transition(pre(), s, prepost_label_, w);
471  }
472 
474  set_initial(s, weightset()->zero());
475  }
476 
478  set_transition(s, post(), prepost_label_, w);
479  }
480 
481  void set_final(state_t s) {
482  set_final(s, weightset()->one());
483  }
484 
486  return add_transition(s, post(), prepost_label_, w);
487  }
488 
490  set_final(s, weightset()->zero());
491  }
492 
493  // Edition of transitions
495 
496  void
498  {
499  assert(has_transition(t));
500  // Remove transition from source and destination.
503  // Actually erase the transition.
504  transitions_[t].src = null_state();
505  transitions_fs_.emplace_back(t);
506  }
507 
511  {
512  transition_t t = get_transition(src, dst, l);
513  if (t != null_transition())
514  del_transition(t);
515  return t;
516  }
517 
519  void
521  {
522  // Make a copy of the transition indexes, as the iterators are
523  // invalidated by del_transition(t).
524  auto ts = outin(s, d);
525  for (auto t: tr_cont_t{ts.begin(), ts.end()})
526  del_transition(t);
527  }
528 
541  {
542  assert(!has_transition(src, dst, l));
543  if (weightset()->is_zero(w))
544  return null_transition();
545  else
546  {
547  transition_t t;
548  if (transitions_fs_.empty())
549  {
550  t = transitions_.size();
551  transitions_.resize(t + 1);
552  }
553  else
554  {
555  t = transitions_fs_.back();
556  transitions_fs_.pop_back();
557  }
558  stored_transition_t& st = transitions_[t];
559  st.src = src;
560  st.dst = dst;
561  // FIXME: When src == pre() || dst == post(), label must be empty.
562  st.set_label(l);
563  st.set_weight(w);
564  states_[src].succ.emplace_back(t);
565  states_[dst].pred.emplace_back(t);
566  return t;
567  }
568  }
569 
583  template <typename A>
586  const A& aut, transition_t t,
587  bool transpose = false)
588  {
589  auto l = aut->label_of(t);
590  auto w = aut->weight_of(t);
591  if (transpose)
592  {
593  l = aut->labelset()->transpose(l);
594  w = aut->weightset()->transpose(w);
595  }
596  return new_transition(src, dst,
597  labelset()->conv(*aut->labelset(), l),
598  weightset()->conv(*aut->weightset(), w));
599  }
600 
604  {
605  return new_transition(src, dst, l, weightset()->one());
606  }
607 
620  {
621  // It's illegal to connect pre() to post().
622  // FIXME: reenable except for labels_are_one.
623  // assert(src != pre() || dst != post());
624  // It's illegal to leave post().
625  assert(src != post());
626  // It's illegal to go to pre().
627  assert(dst != pre());
628  transition_t t = get_transition(src, dst, l);
629  if (t == null_transition())
630  t = new_transition(src, dst, l, w);
631  else if (weightset()->is_zero(w))
632  {
633  del_transition(t);
634  t = null_transition();
635  }
636  else
637  {
638  stored_transition_t& st = transitions_[t];
639  st.set_label(l);
640  st.set_weight(w);
641  }
642  return t;
643  }
644 
648  {
649  return set_transition(src, dst, l, weightset()->one());
650  }
651 
652  template <typename A>
655  const A& aut, transition_t t,
656  bool transpose = false)
657  {
658  auto l = aut->label_of(t);
659  auto w = aut->weight_of(t);
660  if (transpose)
661  {
662  l = aut->labelset()->transpose(l);
663  w = aut->weightset()->transpose(w);
664  }
665  return set_transition(src, dst,
666  labelset()->conv(*aut->labelset(), l),
667  weightset()->conv(*aut->weightset(), w));
668  }
669 
680  weight_t
682  {
683  transition_t t = get_transition(src, dst, l);
684  if (t == null_transition())
685  new_transition(src, dst, l, w);
686  else
687  {
688  w = weightset()->add(weight_of(t), w);
689  set_weight(t, w);
690  }
691  return w;
692  }
693 
695  weight_t
697  {
698  return add_transition(src, dst, l, weightset()->one());
699  }
700 
712  template <typename A>
713  weight_t
715  const A& aut, transition_t t,
716  bool transpose = false)
717  {
718  auto l = aut->label_of(t);
719  auto w = aut->weight_of(t);
720  if (transpose)
721  {
722  l = aut->labelset()->transpose(l);
723  w = aut->weightset()->transpose(w);
724  }
725  return add_transition(src, dst,
726  labelset()->conv(*aut->labelset(), l),
727  weightset()->conv(*aut->weightset(), w));
728  }
729 
730  weight_t
732  {
733  if (weightset()->is_zero(w))
734  del_transition(t);
735  else
736  transitions_[t].set_weight(w);
737  return w;
738  }
739 
740  weight_t
742  {
743  return set_weight(t, weightset()->add(weight_of(t), w));
744  }
745 
746  weight_t
748  {
749  return set_weight(t, weightset()->mul(w, weight_of(t)));
750  }
751 
752  weight_t
754  {
755  return set_weight(t, weightset()->mul(weight_of(t), w));
756  }
757 
758  // Iteration on states and transitions
760 
762 
766  states() const {
767  return states_output_t(states_, [this] (const stored_state_t& ss) -> bool
768  {
769  return (ss.succ.empty()
770  || ss.succ.front() != this->null_transition());
771  }, 2);
772  }
776  all_states() const {
777  return states_output_t(states_, [this] (const stored_state_t& ss) -> bool
778  {
779  return (ss.succ.empty()
780  || ss.succ.front() != this->null_transition());
781  });
782  }
783 
785 
788  transitions() const
789  {
790  return transitions_output_t (transitions_, [this] (const stored_transition_t& tr) -> bool
791  {
792  state_t src = tr.src;
793  if (src == this->null_state() || src == this->pre())
794  return false;
795  return tr.dst != this->post();
796  });
797  }
798 
802  {
803  return transitions_output_t(transitions_, [this] (const stored_transition_t& tr) -> bool
804  {
805  return tr.src != this->null_state();
806  });
807  }
808 
810 
814  {
815  return out(pre());
816  }
817 
821  {
822  return in(post());
823  }
824 
828  out(state_t s) const
829  {
830  assert(has_state(s));
831  return transitions_s_output_t(states_[s].succ, [this] (const transition_t& i) -> bool
832  {
833  return this->transitions_[i].dst != this->post();
834  });
835  }
836 
839  const tr_cont_t&
840  all_out(state_t s) const
841  {
842  assert(has_state(s));
843  return states_[s].succ;
844  }
845 
846  tr_cont_t&
848  {
849  assert(has_state(s));
850  return states_[s].succ;
851  }
852 
856  out(state_t s, const label_t& l) const
857  {
858  assert(has_state(s));
859  return transitions_s_output_t(states_[s].succ, [this,l] (const transition_t& i) -> bool
860  {
861  return this->labelset()->equals(this->transitions_[i].get_label(), l);
862  });
863  }
864 
868  in(state_t s) const
869  {
870  assert(has_state(s));
871  return transitions_s_output_t(states_[s].pred, [this] (const transition_t& i) -> bool
872  { return this->transitions_[i].src != this->pre(); });
873  }
874 
877  const tr_cont_t&
878  all_in(state_t s) const
879  {
880  assert(has_state(s));
881  return states_[s].pred;
882  }
883 
887  in(state_t s, const label_t& l) const
888  {
889  assert(has_state(s));
890  return transitions_s_output_t(states_[s].pred, [this,l] (const transition_t& i) -> bool
891  {
892  return this->labelset()->equals(this->transitions_[i].get_label(), l);
893  });
894  }
895 
899  outin(state_t s, state_t d) const
900  {
901  assert(has_state(s));
902  assert(has_state(d));
903  return transitions_s_output_t(states_[s].succ, [this,d] (const transition_t& i) -> bool
904  { return this->transitions_[i].dst == d; });
905  }
906  };
907  }
908 
909  template <typename Context>
910  mutable_automaton<Context>
911  make_mutable_automaton(const Context& ctx)
912  {
913  return make_shared_ptr<mutable_automaton<Context>>(ctx);
914  }
915  }
916 }//end of ns awali::stc
917 
918 #endif // !AWALI_CORE_MUTABLE_AUTOMATON_HH
Definition: mutable_automaton.hh:51
cont_filter< tr_cont_t > transitions_s_output_t
Definition: mutable_automaton.hh:809
std::vector< stored_state_t > st_store_t
All the automaton's states.
Definition: mutable_automaton.hh:88
std::string get_state_name(state_t s) const
Definition: mutable_automaton.hh:383
void set_desc(const std::string &d)
Definition: mutable_automaton.hh:436
indice_filter< tr_store_t > transitions_output_t
Definition: mutable_automaton.hh:784
transitions_s_output_t final_transitions() const
Indexes of transitions from visible final states.
Definition: mutable_automaton.hh:820
std::shared_ptr< string_history > names_t
Definition: mutable_automaton.hh:70
void set_initial(state_t s, weight_t w)
Definition: mutable_automaton.hh:461
bool is_final(state_t s) const
Definition: mutable_automaton.hh:210
transitions_s_output_t out(state_t s) const
Indexes of visible transitions leaving state s.
Definition: mutable_automaton.hh:828
const tr_cont_t & all_out(state_t s) const
Indexes of all transitions leaving state s.
Definition: mutable_automaton.hh:840
bool has_history(state_t s) const
Definition: mutable_automaton.hh:398
state_t src_of(transition_t t) const
Definition: mutable_automaton.hh:285
std::ostream & print_state_name(state_t s, std::ostream &o, const std::string &fmt="text") const
Definition: mutable_automaton.hh:378
void unset_initial(state_t s)
Definition: mutable_automaton.hh:473
weight_t add_transition(state_t src, state_t dst, label_t l, weight_t w)
Add a transition between two states.
Definition: mutable_automaton.hh:681
states_output_t states() const
All states excluding pre()/post().
Definition: mutable_automaton.hh:766
indice_filter< st_store_t > states_output_t
Definition: mutable_automaton.hh:761
states_output_t all_states() const
All states including pre()/post().
Definition: mutable_automaton.hh:776
transitions_output_t all_transitions() const
All the transition indexes between all states (including pre and post).
Definition: mutable_automaton.hh:801
std::vector< transition_t > tr_cont_t
All the incoming/outgoing transition handles of a state.
Definition: mutable_automaton.hh:79
weight_t weight_of(transition_t t) const
Definition: mutable_automaton.hh:291
bool has_explicit_name(state_t s) const
Definition: mutable_automaton.hh:411
std::ostream & print_state(state_t s, std::ostream &o) const
Definition: mutable_automaton.hh:368
context_t ctx_
The algebraic type of this automaton.
Definition: mutable_automaton.hh:73
void set_final(state_t s)
Definition: mutable_automaton.hh:481
void set_final(state_t s, weight_t w)
Definition: mutable_automaton.hh:477
static constexpr state_t null_state()
Definition: mutable_automaton.hh:163
state_t get_state_by_name(const std::string &name) const
Definition: mutable_automaton.hh:419
ATTRIBUTE_PURE weight_t get_initial_weight(state_t s) const
Definition: mutable_automaton.hh:216
transitions_s_output_t initial_transitions() const
Indexes of transitions to visible initial states.
Definition: mutable_automaton.hh:813
size_t num_transitions() const
Definition: mutable_automaton.hh:177
void del_transition_container(tr_cont_t &tc, bool from_succ)
Definition: mutable_automaton.hh:322
void del_transition(state_t s, state_t d)
Remove all the transitions between s and d.
Definition: mutable_automaton.hh:520
void del_state(state_t s)
Definition: mutable_automaton.hh:449
state_t dst_of(transition_t t) const
Definition: mutable_automaton.hh:286
mutable_automaton_impl(mutable_automaton_impl &&that)
Definition: mutable_automaton.hh:118
transition_t set_transition(state_t src, state_t dst, label_t l)
Same as above, with unit weight.
Definition: mutable_automaton.hh:647
ATTRIBUTE_PURE weight_t get_final_weight(state_t s) const
Definition: mutable_automaton.hh:226
void strip_history()
Definition: mutable_automaton.hh:360
const context_t & context() const
Definition: mutable_automaton.hh:149
static std::string sname()
Definition: mutable_automaton.hh:141
const labelset_ptr & labelset() const
Definition: mutable_automaton.hh:151
typename context_t::kind_t kind_t
Definition: mutable_automaton.hh:59
bool has_transition(transition_t t) const
Definition: mutable_automaton.hh:275
mutable_automaton_impl(const context_t &ctx)
Definition: mutable_automaton.hh:110
state_t max_state() const
Definition: mutable_automaton.hh:197
const std::string & get_name() const
Definition: mutable_automaton.hh:440
weight_t lmul_weight(transition_t t, weight_t w)
Definition: mutable_automaton.hh:747
static constexpr transition_t null_transition()
Definition: mutable_automaton.hh:164
transition_t new_transition(state_t src, state_t dst, label_t l)
Same as above, with weight one.
Definition: mutable_automaton.hh:603
transition_t get_transition(state_t src, state_t dst, label_t l) const
Definition: mutable_automaton.hh:238
transitions_s_output_t outin(state_t s, state_t d) const
Indexes of visible transitions from state s to state d.
Definition: mutable_automaton.hh:899
size_t num_all_states() const
Definition: mutable_automaton.hh:173
weight_t rmul_weight(transition_t t, weight_t w)
Definition: mutable_automaton.hh:753
transition_t del_transition(state_t src, state_t dst, label_t l)
Remove the transition (src, l, dst).
Definition: mutable_automaton.hh:510
weight_t add_final(state_t s, weight_t w)
Definition: mutable_automaton.hh:485
bool set_name(const std::string &n)
Definition: mutable_automaton.hh:429
std::vector< state_t > free_store_t
A list of unused indexes in the states/transitions tables.
Definition: mutable_automaton.hh:92
labelset_t_of< context_t > labelset_t
Definition: mutable_automaton.hh:57
label_t label_of(transition_t t) const
Definition: mutable_automaton.hh:287
weight_t add_transition_copy(state_t src, state_t dst, const A &aut, transition_t t, bool transpose=false)
Add a transition between two states, copying the label from the given transition.
Definition: mutable_automaton.hh:714
typename context_t::labelset_ptr labelset_ptr
Definition: mutable_automaton.hh:61
Context context_t
Definition: mutable_automaton.hh:53
void strip_names()
Definition: mutable_automaton.hh:364
transitions_s_output_t in(state_t s) const
Indexes of visible transitions arriving to state s.
Definition: mutable_automaton.hh:868
std::vector< stored_transition_t > tr_store_t
All the automaton's transitions.
Definition: mutable_automaton.hh:90
typename weightset_t::value_t weight_t
Transition weight.
Definition: mutable_automaton.hh:67
mutable_automaton< context_t > automaton_nocv_t
The (shared pointer) type to use it we have to create an automaton of the same (underlying) type.
Definition: mutable_automaton.hh:56
typename labelset_t::value_t label_t
Transition label.
Definition: mutable_automaton.hh:65
size_t num_initials() const
Definition: mutable_automaton.hh:175
mutable_automaton_impl(const mutable_automaton_impl &)=delete
bool is_initial(state_t s) const
Definition: mutable_automaton.hh:205
void set_state_name(state_t s, const std::string &n)
Definition: mutable_automaton.hh:415
history_t history() const
Definition: mutable_automaton.hh:352
weightset_t_of< context_t > weightset_t
Definition: mutable_automaton.hh:58
void set_state_names_from_history()
Definition: mutable_automaton.hh:402
transitions_output_t transitions() const
All the transition indexes between visible states.
Definition: mutable_automaton.hh:788
const std::string & get_desc() const
Definition: mutable_automaton.hh:444
bool has_transition(state_t src, state_t dst, label_t l) const
Definition: mutable_automaton.hh:270
transition_t new_transition_copy(state_t src, state_t dst, const A &aut, transition_t t, bool transpose=false)
Copy the label of a transition between two states, creating a new transition.
Definition: mutable_automaton.hh:585
size_t num_finals() const
Definition: mutable_automaton.hh:176
void set_history(history_t h)
Definition: mutable_automaton.hh:356
static constexpr state_t pre()
Definition: mutable_automaton.hh:160
tr_cont_t succ
Definition: mutable_automaton.hh:84
state_t add_state()
Definition: mutable_automaton.hh:336
const weightset_ptr & weightset() const
Definition: mutable_automaton.hh:150
void del_transition(transition_t t)
Definition: mutable_automaton.hh:497
std::shared_ptr< history_base > history_t
History.
Definition: mutable_automaton.hh:69
bool has_state(state_t s) const
Definition: mutable_automaton.hh:186
void del_transition_from_dst(transition_t t)
Remove t from the ingoing transition of the destination state.
Definition: mutable_automaton.hh:312
transitions_s_output_t out(state_t s, const label_t &l) const
Indexes of all transitions leaving state s on label l.
Definition: mutable_automaton.hh:856
label_t prepost_label() const
Definition: mutable_automaton.hh:166
weight_t add_initial(state_t s, weight_t w)
Definition: mutable_automaton.hh:469
size_t num_states() const
Definition: mutable_automaton.hh:174
transition_t set_transition(state_t src, state_t dst, label_t l, weight_t w)
Set a transition between two states.
Definition: mutable_automaton.hh:619
const tr_cont_t & all_in(state_t s) const
Indexes of all transitions arriving to state s.
Definition: mutable_automaton.hh:878
void unset_final(state_t s)
Definition: mutable_automaton.hh:489
weight_t add_weight(transition_t t, weight_t w)
Definition: mutable_automaton.hh:741
void set_initial(state_t s)
Definition: mutable_automaton.hh:465
transition_t new_transition(state_t src, state_t dst, label_t l, weight_t w)
Create a transition between two states.
Definition: mutable_automaton.hh:540
mutable_automaton_impl & operator=(mutable_automaton_impl &&that)
Definition: mutable_automaton.hh:124
transitions_s_output_t in(state_t s, const label_t &l) const
Indexes of visible transitions arriving to state s on label l.
Definition: mutable_automaton.hh:887
static constexpr state_t post()
Definition: mutable_automaton.hh:161
tr_cont_t pred
Definition: mutable_automaton.hh:85
std::string vname(bool full=true) const
Definition: mutable_automaton.hh:145
std::ostream & print_state_history(state_t s, std::ostream &o, const std::string &fmt="text") const
Definition: mutable_automaton.hh:391
weight_t add_transition(state_t src, state_t dst, label_t l)
Same as above, with weight one.
Definition: mutable_automaton.hh:696
weight_t set_weight(transition_t t, weight_t w)
Definition: mutable_automaton.hh:731
tr_cont_t & all_out_(state_t s)
Definition: mutable_automaton.hh:847
typename context_t::weightset_ptr weightset_ptr
Definition: mutable_automaton.hh:62
transition_t set_transition_copy(state_t src, state_t dst, const A &aut, transition_t t, bool transpose=false)
Definition: mutable_automaton.hh:654
void del_transition_from_src(transition_t t)
Remove t from the outgoing transitions of the source state.
Definition: mutable_automaton.hh:301
Data stored for each state.
Definition: mutable_automaton.hh:83
The semiring of Natural numbers.
Definition: n.hh:34
specialisation of history_base
Definition: no_history.hh:28
Definition: string_history.hh:29
ATTRIBUTE_PURE auto find(const std::vector< T, Alloc > &s, const T &e) -> typename std::vector< T, Alloc >::const_iterator
Convenience wrapper around std::find.
Definition: vector.hh:81
typename internal::labelset_t_of_impl< internal::base_t< ValueSet > >::type labelset_t_of
Helper to retrieve the type of the labelset of a value set.
Definition: traits.hh:76
AutOut transpose(Aut &aut, bool keep_history=true)
Definition: transpose.hh:79
mutable_automaton< Context > make_mutable_automaton(const Context &ctx)
Definition: mutable_automaton.hh:911
std::shared_ptr< internal::mutable_automaton_impl< Context > > mutable_automaton
Definition: mutable_automaton.hh:45
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:45
typename internal::weightset_t_of_impl< internal::base_t< ValueSet > >::type weightset_t_of
Helper to retrieve the type of the weightset of a value set.
Definition: traits.hh:86
static const std::string full
Completely version of Awali as a std::string.
Definition: version.hh:40
Main namespace of Awali.
Definition: ato.hh:22
unsigned state_t
Definition: types.hh:21
unsigned transition_t
Definition: types.hh:22
Definition: cont_filter.hh:145
Definition: cont_filter.hh:69
label_t get_label() const
Definition: transition.hh:39
void set_label(label_t &l)
Definition: transition.hh:40
Definition: transition.hh:65
void set_weight(weight_t &k)
Definition: transition.hh:68