7 #include <boost/range/algorithm/find.hpp>
8 #include <boost/range/algorithm/find_if.hpp>
9 #include <boost/range/irange.hpp>
24 template <
typename Context>
25 class mutable_automaton_impl
31 template <
typename Ctx = Context>
35 using kind_t =
typename context_t::kind_t;
45 using label_t =
typename labelset_t::value_t;
47 using weight_t =
typename weightset_t::value_t;
96 , prepost_label_(that.prepost_label_)
98 *
this = std::move(that);
105 ctx_ = std::move(that.ctx_);
106 prepost_label_ = std::move(that.prepost_label_);
107 std::swap(states_, that.states_);
108 std::swap(states_fs_, that.states_fs_);
109 std::swap(transitions_, that.transitions_);
110 std::swap(transitions_fs_, that.transitions_fs_);
128 o <<
"mutable_automaton<";
133 const context_t& context() const { return ctx_; }
134 const weightset_ptr& weightset() const { return ctx_.weightset(); }
135 const labelset_ptr& labelset() const { return ctx_.labelset(); }
138 /*----------------------------------.
139 | Special states and transitions. |
140 `----------------------------------*/
142 // pseudo-initial and final states.
143 // The code below assumes that pre() and post() are the first
144 // two states of the automaton. In other words, all other states
145 // have greater numbers. We also assume that pre()<post().
146 static constexpr state_t pre() { return 0U; }
147 static constexpr state_t post() { return 1U; }
149 static constexpr state_t null_state() { return -1U; }
151 static constexpr transition_t null_transition() { return -1U; }
154 label_t prepost_label() const
156 return prepost_label_;
164 size_t num_all_states() const { return states_.size() - states_fs_.size(); }
165 size_t num_states() const { return num_all_states() - 2; }
166 size_t num_initials() const { return states_[pre()].succ.size(); }
167 size_t num_finals() const { return states_[post()].pred.size(); }
168 size_t num_transitions() const
170 return (transitions_.size()
171 - transitions_fs_.size() - num_initials() - num_finals());
175 /*---------------------.
176 | Queries on states. |
177 `---------------------*/
181 has_state(state_t s) const
183 // Any number outside our container is not a state.
184 // (This includes "null_state()".)
185 if (states_.size() <= s)
189 const stored_state_t& ss = states_[s];
190 // Erased states have 'invalid
' as their first successor.
191 return ss.succ.empty() || ss.succ.front() != null_transition();
197 state_is_strict(state_t s) const
199 assert(has_state(s)); (void) s;
205 is_initial(state_t s) const
207 return has_transition(pre(), s, prepost_label_);
212 is_final(state_t s) const
214 return has_transition(s, post(), prepost_label_);
220 get_initial_weight(state_t s) const
222 transition_t t = get_transition(pre(), s, prepost_label_);
223 if (t == null_transition())
224 return weightset()->zero();
232 get_final_weight(state_t s) const
234 transition_t t = get_transition(s, post(), prepost_label_);
235 if (t == null_transition())
236 return weightset()->zero();
242 /*--------------------------.
243 | Queries on transitions. |
244 `--------------------------*/
247 get_transition(state_t src, state_t dst, label_t l) const
249 assert(has_state(src));
250 assert(has_state(dst));
251 const tr_cont_t& succ = states_[src].succ;
252 const tr_cont_t& pred = states_[dst].pred;
253 const auto& ls = *this->labelset();
254 if (succ.size() <= pred.size())
258 [this,l,ls,dst] (transition_t t)
260 return (dst_of(t) == dst
261 && ls.equal(label_of(t), l));
270 [this,l,ls,src] (transition_t t)
272 return (src_of(t) == src
273 && ls.equal(label_of(t), l));
278 return null_transition();
282 has_transition(state_t src, state_t dst, label_t l) const
284 return get_transition(src, dst, l) != null_transition();
288 has_transition(transition_t t) const
290 // Any number outside our container is not a transition.
291 // (This includes "null_transition()".)
292 if (t >= transitions_.size())
295 // Erased transition have invalid source state.
296 return transitions_[t].src != null_state();
299 state_t src_of(transition_t t) const { return transitions_[t].src; }
300 state_t dst_of(transition_t t) const { return transitions_[t].dst; }
301 label_t label_of(transition_t t) const
303 return transitions_[t].get_label();
306 weight_t weight_of(transition_t t) const
308 return transitions_[t].get_weight();
312 /*---------------------.
313 | Edition of states. |
314 `---------------------*/
319 del_transition_from_src(transition_t t)
321 stored_transition_t& st = transitions_[t];
322 auto& succ = states_[st.src].succ;
323 auto tsucc = boost::range::find(succ, t);
324 assert(tsucc != succ.end());
325 *tsucc = std::move(succ.back());
331 del_transition_from_dst(transition_t t)
333 stored_transition_t& st = transitions_[t];
334 auto& pred = states_[st.dst].pred;
335 auto tpred = boost::range::find(pred, t);
336 assert(tpred != pred.end());
337 *tpred = std::move(pred.back());
342 del_transition_container(tr_cont_t& tc, bool from_succ)
347 del_transition_from_dst(t);
349 del_transition_from_src(t);
350 transitions_[t].src = null_state();
352 transitions_fs_.insert(transitions_fs_.end(), tc.begin(), tc.end());
362 if (states_fs_.empty())
364 res = states_.size();
365 states_.emplace_back();
369 res = states_fs_.back();
370 states_fs_.pop_back();
371 stored_state_t& ss = states_[res];
372 // De-invalidate this state: remove the invalid transition.
379 print_state(state_t s, std::ostream& o) const
383 else if (s == post())
391 print_state_name(state_t s, std::ostream& o,
395 return print_state(s, o);
398 static constexpr bool
399 state_has_name(state_t)
407 assert(has_state(s));
408 assert(s > post()); // Cannot erase pre() and post().
409 stored_state_t& ss = states_[s];
410 del_transition_container(ss.pred, false);
411 del_transition_container(ss.succ, true);
412 ss.succ.emplace_back(null_transition()); // So has_state() can work.
413 states_fs_.emplace_back(s);
417 set_initial(state_t s, weight_t w)
419 set_transition(pre(), s, prepost_label_, w);
423 set_initial(state_t s)
425 set_initial(s, weightset()->one());
429 add_initial(state_t s, weight_t w)
431 return add_transition(pre(), s, prepost_label_, w);
435 unset_initial(state_t s)
437 set_initial(s, weightset()->zero());
441 set_final(state_t s, weight_t w)
443 set_transition(s, post(), prepost_label_, w);
449 set_final(s, weightset()->one());
453 add_final(state_t s, weight_t w)
455 return add_transition(s, post(), prepost_label_, w);
459 unset_final(state_t s)
461 set_final(s, weightset()->zero());
465 /*--------------------------.
466 | Edition of transitions. |
467 `--------------------------*/
470 del_transition(transition_t t)
472 assert(has_transition(t));
473 // Remove transition from source and destination.
474 del_transition_from_src(t);
475 del_transition_from_dst(t);
476 // Actually erase the transition.
477 transitions_[t].src = null_state();
478 transitions_fs_.emplace_back(t);
483 del_transition(state_t src, state_t dst, label_t l)
485 transition_t t = get_transition(src, dst, l);
486 if (t != null_transition())
492 del_transition(state_t s, state_t d)
494 // Make a copy of the transition indexes, as the iterators are
495 // invalidated by del_transition(t).
496 auto ts = outin(s, d);
497 for (auto t: tr_cont_t{std::begin(ts), std::end(ts)})
512 new_transition(state_t src, state_t dst, label_t l, weight_t w)
514 assert(!has_transition(src, dst, l));
515 if (weightset()->is_zero(w))
516 return null_transition();
519 // FIXME: When src == pre() || dst == post(), label must be empty.
521 if (transitions_fs_.empty())
523 t = transitions_.size();
524 transitions_.emplace_back(src, dst, l, w);
528 t = transitions_fs_.back();
529 transitions_fs_.pop_back();
530 stored_transition_t& st = transitions_[t];
536 states_[src].succ.emplace_back(t);
537 states_[dst].pred.emplace_back(t);
554 template <typename A>
556 new_transition_copy(state_t src, state_t dst,
557 const A& aut, typename A::element_type::transition_t t,
558 bool transpose = false)
560 auto l = aut->label_of(t);
561 auto w = aut->weight_of(t);
564 l = aut->labelset()->transpose(l);
565 w = aut->weightset()->transpose(w);
567 return new_transition(src, dst,
568 labelset()->conv(*aut->labelset(), l),
569 weightset()->conv(*aut->weightset(), w));
574 new_transition(state_t src, state_t dst, label_t l)
576 return new_transition(src, dst, l, weightset()->one());
590 set_transition(state_t src, state_t dst, label_t l, weight_t w)
592 // It's illegal to connect
pre() to
post().
596 assert(src !=
post());
598 assert(dst !=
pre());
663 template <
typename A>
666 const A& aut,
typename A::element_type::transition_t t,
669 auto l = aut->label_of(t);
670 auto w = aut->weight_of(t);
673 l = aut->labelset()->transpose(l);
674 w = aut->weightset()->transpose(w);
678 weightset()->conv(*aut->weightset(), w));
684 constexpr
char langle =
'<';
685 constexpr
char rangle =
'>';
687 std::ostringstream o;
708 transitions_[t].set_weight(w);
735 template <
typename Pred>
742 template <
typename Pred>
748 return ((ss.
succ.empty()
758 template <
typename Pred>
796 template <
typename Pred>
798 -> decltype(this->
state_range(0U, states_.size(), pred))
811 template <
typename Pred>
816 template <
typename Pred>
830 template <
typename Pred>
836 boost::irange<transition_t>(0U, transitions_.size()),
894 container_range<const tr_cont_t&>
898 return states_[s].succ;
905 template <
typename Pred>
910 return {states_[s].succ, pred};
918 return all_out(s, not_to_post_p{*
this});
939 return all_out(s, label_equal_p{*
this, l});
944 container_range<const tr_cont_t&>
948 return states_[s].pred;
955 template <
typename Pred>
960 return {states_[s].pred, pred};
968 return all_in(s, not_from_pre_p{*
this});
976 return all_in(s, label_equal_p{*
this, l});
995 return all_out(s, dst_p{*
this, d});
1020 template <
typename Context>
1021 mutable_automaton<Context>
1024 return make_shared_ptr<mutable_automaton<Context>>(
ctx);
bool operator()(transition_t t) const
unsigned transition_t
Lightweight transition handle (or index).
free_store_t states_fs_
Free indexes in states_.
bool operator()(transition_t t) const
transition_t set_weight(transition_t t, weight_t w)
const mutable_automaton_impl & aut_
auto in(state_t s) const -> decltype(this->all_in(s, not_from_pre_p
Indexes of visible transitions arriving to state s.
auto all_states(Pred pred) const -> decltype(this->state_range(0U, states_.size(), pred))
All states including pre()/post() that validate pred.
const mutable_automaton_impl & aut_
typename weightset_t::value_t weight_t
Transition weight.
auto out(state_t s) const -> decltype(this->all_out(s, not_to_post_p
Indexes of visible transitions leaving state s.
typename context_t::kind_t kind_t
transitions_output_t< has_state_p< Pred > > all_transitions(Pred pred) const
All the transition indexes between all states (including pre and post), that validate pred...
typename context_t::weightset_ptr weightset_ptr
labelset_t_of< context_t > labelset_t
state_t dst_of(transition_t t) const
static constexpr state_t null_state()
Invalid state.
auto final_transitions() const -> decltype(this->all_in(post()))
Indexes of transitions from visible final states.
transition_t get_transition(state_t src, state_t dst, label_t l) const
static constexpr state_t pre()
states_output_t< valid_state_p< Pred > > state_range(state_t b, state_t e, Pred pred) const
The range of state numbers in [b .
weightset_mixin< detail::b_impl > b
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
bool operator()(transition_t t) const
unsigned state_t
Lightweight state handle (or index).
static constexpr state_t post()
bool operator()(state_t) const
static constexpr transition_t null_transition()
Invalid transition.
tr_cont_t pred
Incoming transitions.
container_filter_range< boost::integer_range< transition_t >, Pred > transitions_output_t
container_range< const tr_cont_t & > all_out(state_t s) const
Indexes of all transitions leaving state s.
auto outin(state_t s, state_t d) const -> decltype(this->all_out(s, dst_p
Indexes of visible transitions from state s to state d.
weight_t lmul_weight(transition_t t, weight_t w)
std::string format_transition(transition_t t) const
typename labelset_t::value_t label_t
Transition label.
mutable_automaton_impl()=delete
mutable_automaton_impl(const context_t &ctx)
Aut transpose(const transpose_automaton< Aut > &aut)
std::ostream & print_set(std::ostream &o, format fmt={}) const
std::vector< stored_transition_t > tr_store_t
All the automaton's transitions.
Data stored for each state.
bool has_state(state_t s) const
Whether state s belongs to the automaton.
bool operator()(transition_t t) const
const mutable_automaton_impl & aut_
transition_tuple< state_t, label_t, weight_t > stored_transition_t
Data stored per transition.
static dyn::context ctx(const driver &d)
Get the context of the driver.
label_t label_of(transition_t t) const
mutable_automaton< Context > make_mutable_automaton(const Context &ctx)
std::vector< unsigned > free_store_t
A list of unused indexes in the states/transitions tables.
const mutable_automaton_impl & aut_
Provide a variadic mul on top of a binary mul(), and one().
const weightset_ptr & weightset() const
auto operator()(state_t s) -> bool
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
transition_t set_transition(state_t src, state_t dst, label_t l)
Same as above, with unit weight.
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
typename context_t::labelset_ptr labelset_ptr
context_t ctx_
The algebraic type of this automaton.
bool operator()(transition_t t) const
auto out(state_t s, label_t l) const -> decltype(this->all_out(s, label_equal_p
Indexes of all transitions leaving state s on label l.
std::vector< transition_t > tr_cont_t
All the incoming/outgoing transition handles of a state.
transition_t add_transition(state_t src, state_t dst, label_t l, weight_t w)
Add a transition between two states.
transition_t add_transition(state_t src, state_t dst, label_t l)
Same as above, with weight one.
weight_t add_weight(transition_t t, weight_t w)
auto state_range(state_t b, state_t e) const -> decltype(this->state_range(b, e, all_states_p
The range of state numbers in [b .. e].
auto all_states() const -> decltype(this->state_range(0U, states_.size()))
All states including pre()/post().
bool operator()(transition_t t) const
auto all_transitions() const -> decltype(this->all_transitions(all_transitions_p
All the transition indexes between all states (including pre and post).
const mutable_automaton_impl & aut_
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Transition with label and non Boolean weight.
state_t src_of(transition_t t) const
auto initial_transitions() const -> decltype(this->all_out(pre()))
Indexes of transitions to visible initial states.
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::vector< stored_state_t > st_store_t
All the automaton's states.
auto states() const -> decltype(this->state_range(post()+1, states_.size()))
All states excluding pre()/post().
container_range< const tr_cont_t & > all_in(state_t s) const
Indexes of all transitions arriving to state s.
label_t prepost_label_
Label for initial and final transitions.
mutable_automaton_impl & operator=(mutable_automaton_impl &&that)
weightset_t_of< context_t > weightset_t
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.
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. ...
tr_cont_t succ
Outgoing transitions.
auto transitions() const -> decltype(this->all_transitions(not_with_pre_post_p
All the transition indexes between visible states.
mutable_automaton_impl(mutable_automaton_impl &&that)
container_filter_range< boost::integer_range< state_t >, Pred > states_output_t
container_filter_range< const tr_cont_t &, Pred > all_out(state_t s, Pred pred) const
Indexes of transitions leaving state s that validate the predicate.
const mutable_automaton_impl & aut_
const mutable_automaton_impl & aut_
weight_t weight_of(transition_t t) const
weight_t rmul_weight(transition_t t, weight_t w)
free_store_t transitions_fs_
Free indexes in transitions_.
transition_t new_transition(state_t src, state_t dst, label_t l, weight_t w)
Create a transition between two states.
auto in(state_t s, label_t l) const -> decltype(this->all_in(s, label_equal_p
Indexes of visible transitions arriving to state s on label l.
const labelset_ptr & labelset() const
container_filter_range< const tr_cont_t &, Pred > all_in(state_t s, Pred pred) const
Indexes of transitions entering state s that validate the predicate.
void del_transition(transition_t t)
bool operator()(transition_t) const
std::shared_ptr< detail::mutable_automaton_impl< Context >> mutable_automaton
const context_t & context() const
transition_t set_transition(state_t src, state_t dst, label_t l, weight_t w)
Set a transition between two states.