![]() |
Vcsn
2.3a
Be Rational
|
Bidirectional automata. More...
#include <fwd.hh>
Classes | |
struct | state_tag |
Lightweight state handle (or index). More... | |
struct | stored_state_t |
Data stored for each state. More... | |
struct | transition_tag |
Lightweight transition handle (or index). More... | |
Public Types | |
using | context_t = Context |
using | self_t = mutable_automaton_impl |
template<typename Ctx = Context> | |
using | fresh_automaton_t = mutable_automaton< Ctx > |
The (shared pointer) type to use if we have to create an automaton of the same (underlying) type. More... | |
using | labelset_t = labelset_t_of< context_t > |
using | weightset_t = weightset_t_of< context_t > |
using | kind_t = typename context_t::kind_t |
using | labelset_ptr = typename context_t::labelset_ptr |
using | weightset_ptr = typename context_t::weightset_ptr |
using | state_t = index_t_impl< state_tag > |
using | transition_t = index_t_impl< transition_tag > |
using | label_t = typename labelset_t::value_t |
Transition label. More... | |
using | weight_t = typename weightset_t::value_t |
Transition weight. More... | |
Public Member Functions | |
mutable_automaton_impl ()=delete | |
mutable_automaton_impl (const mutable_automaton_impl &)=delete | |
mutable_automaton_impl (const context_t &ctx) | |
mutable_automaton_impl (mutable_automaton_impl &&that) | |
mutable_automaton_impl & | operator= (mutable_automaton_impl &&that) |
std::ostream & | print_set (std::ostream &o=std::cout, format fmt={}) const |
const context_t & | context () const |
const weightset_ptr & | weightset () const |
const labelset_ptr & | labelset () const |
label_t | prepost_label () const |
Label for preinitial and postfinal transitions. More... | |
size_t | num_all_states () const |
size_t | num_states () const |
size_t | num_initials () const |
size_t | num_finals () const |
size_t | num_transitions () const |
bool | has_state (state_t s) const |
Whether state s belongs to the automaton. More... | |
bool | is_lazy (state_t s) const |
Whether a given state's outgoing transitions have been computed. More... | |
bool | is_lazy_in (state_t s) const |
Whether a given state's incoming transitions have been computed. More... | |
bool | is_initial (state_t s) const |
Whether s is initial. More... | |
bool | is_final (state_t s) const |
Whether s is final. More... | |
ATTRIBUTE_PURE weight_t | get_initial_weight (state_t s) const |
Initial weight of s. More... | |
ATTRIBUTE_PURE weight_t | get_final_weight (state_t s) const |
Final weight of s. More... | |
transition_t | get_transition (state_t src, state_t dst, label_t l) const |
bool | has_transition (state_t src, state_t dst, label_t l) const |
bool | has_transition (transition_t t) const |
state_t | src_of (transition_t t) const |
state_t | dst_of (transition_t t) const |
label_t | label_of (transition_t t) const |
weight_t | weight_of (transition_t t) const |
state_t | new_state () |
Create a new state and return its id. More... | |
std::ostream & | print_state (state_t s, std::ostream &o=std::cout) const |
std::ostream & | print_state_name (state_t s, std::ostream &o=std::cout, format={}, bool=false) const |
void | del_state (state_t s) |
void | set_initial (state_t s, weight_t w) |
void | set_initial (state_t s) |
void | set_lazy (state_t s, bool lazy=true) |
void | set_lazy_in (state_t s, bool lazy=true) |
transition_t | add_initial (state_t s, weight_t w) |
void | unset_initial (state_t s) |
void | set_final (state_t s, weight_t w) |
void | set_final (state_t s) |
transition_t | add_final (state_t s, weight_t w) |
void | unset_final (state_t s) |
void | del_transition (transition_t t) |
void | del_transition (state_t src, state_t dst, label_t l) |
Remove the transition (src, l, dst). More... | |
transition_t | new_transition (state_t src, state_t dst, label_t l, weight_t w) |
Create a transition between two states. More... | |
template<Automaton A> | |
transition_t | new_transition_copy (state_t src, state_t dst, const A &aut, transition_t_of< A > t, bool transpose=false) |
Copy the label of a transition between two states, creating a new transition. More... | |
transition_t | new_transition (state_t src, state_t dst, label_t l) |
Same as above, with weight one. More... | |
transition_t | set_transition (state_t src, state_t dst, label_t l, weight_t w) |
Set a transition between two states. More... | |
transition_t | set_transition (state_t src, state_t dst, label_t l) |
Same as above, with unit weight. More... | |
transition_t | add_transition (state_t src, state_t dst, label_t l, weight_t w) |
Add a transition between two states. More... | |
transition_t | add_transition (state_t src, state_t dst, label_t l) |
Same as above, with weight one. More... | |
template<Automaton A> | |
transition_t | add_transition_copy (state_t src, state_t dst, const A &aut, transition_t_of< A > t, bool transpose=false) |
Add a transition between two states, copying the label from the given transition. More... | |
std::ostream & | print (transition_t t, std::ostream &o=std::cout, format fmt={}) const |
Print a transition, for debugging. More... | |
std::ostream & | print (std::ostream &o=std::cout) const |
Print an automaton, for debugging. More... | |
transition_t | set_weight (transition_t t, weight_t w) |
weight_t | add_weight (transition_t t, weight_t w) |
weight_t | lweight (transition_t t, weight_t w) |
weight_t | rweight (transition_t t, weight_t w) |
auto | all_states () const |
All states including pre()/post(). More... | |
template<typename Pred > | |
auto | all_states (Pred pred) const |
All states including pre()/post() that validate pred. More... | |
auto | states () const |
All states excluding pre()/post(). More... | |
auto | all_transitions () const |
All the transition indexes between all states (including pre and post). More... | |
container_range< const tr_cont_t & > | all_out (state_t s) const |
Indexes of all transitions leaving state s. More... | |
container_range< const tr_cont_t & > | all_in (state_t s) const |
Indexes of all transitions arriving to state s. More... | |
Static Public Member Functions | |
static symbol | sname () |
static constexpr state_t | pre () |
static constexpr state_t | post () |
static constexpr state_t | null_state () |
Invalid state. More... | |
static constexpr transition_t | null_transition () |
Invalid transition. More... | |
static constexpr transition_t | lazy_transition () |
Invalid transition that shows that the state's outgoing transitions are unknown. More... | |
static constexpr bool | state_has_name (state_t) |
Protected Types | |
using | stored_transition_t = transition_tuple< state_t, label_t, weight_t > |
Data stored per transition. More... | |
using | tr_store_t = std::vector< stored_transition_t > |
All the automaton's transitions. More... | |
using | tr_cont_t = std::vector< transition_t > |
All the incoming/outgoing transition handles of a state. More... | |
using | st_store_t = std::vector< stored_state_t > |
All the automaton's states. More... | |
using | free_store_t = std::vector< unsigned > |
A list of unused indexes in the states/transitions tables. More... | |
Protected Member Functions | |
void | del_transition_from_src (transition_t t) |
Remove t from the outgoing transitions of the source state. More... | |
void | del_transition_from_dst (transition_t t) |
Remove t from the ingoing transition of the destination state. More... | |
void | del_transition_container (tr_cont_t &tc, bool from_succ) |
template<typename Pred > | |
auto | state_range (state_t b, state_t e, Pred pred) const |
The range of index numbers in [b . More... | |
auto | state_range (state_t b, state_t e) const |
The range of state numbers in [b .. e]. More... | |
Protected Attributes | |
context_t | ctx_ |
The algebraic type of this automaton. More... | |
st_store_t | states_ |
free_store_t | states_fs_ |
Free indexes in states_. More... | |
tr_store_t | transitions_ |
free_store_t | transitions_fs_ |
Free indexes in transitions_. More... | |
label_t | prepost_label_ |
Label for initial and final transitions. More... | |
Bidirectional automata.
using vcsn::detail::mutable_automaton_impl< Context >::context_t = Context |
Definition at line 31 of file mutable-automaton.hh.
|
protected |
A list of unused indexes in the states/transitions tables.
Definition at line 80 of file mutable-automaton.hh.
using vcsn::detail::mutable_automaton_impl< Context >::fresh_automaton_t = mutable_automaton<Ctx> |
The (shared pointer) type to use if we have to create an automaton of the same (underlying) type.
Definition at line 36 of file mutable-automaton.hh.
using vcsn::detail::mutable_automaton_impl< Context >::kind_t = typename context_t::kind_t |
Definition at line 39 of file mutable-automaton.hh.
using vcsn::detail::mutable_automaton_impl< Context >::label_t = typename labelset_t::value_t |
Transition label.
Definition at line 51 of file mutable-automaton.hh.
using vcsn::detail::mutable_automaton_impl< Context >::labelset_ptr = typename context_t::labelset_ptr |
Definition at line 41 of file mutable-automaton.hh.
using vcsn::detail::mutable_automaton_impl< Context >::labelset_t = labelset_t_of<context_t> |
Definition at line 37 of file mutable-automaton.hh.
using vcsn::detail::mutable_automaton_impl< Context >::self_t = mutable_automaton_impl |
Definition at line 32 of file mutable-automaton.hh.
|
protected |
All the automaton's states.
Definition at line 77 of file mutable-automaton.hh.
using vcsn::detail::mutable_automaton_impl< Context >::state_t = index_t_impl<state_tag> |
Definition at line 46 of file mutable-automaton.hh.
|
protected |
Data stored per transition.
Definition at line 60 of file mutable-automaton.hh.
|
protected |
All the incoming/outgoing transition handles of a state.
Definition at line 65 of file mutable-automaton.hh.
|
protected |
All the automaton's transitions.
Definition at line 63 of file mutable-automaton.hh.
using vcsn::detail::mutable_automaton_impl< Context >::transition_t = index_t_impl<transition_tag> |
Definition at line 49 of file mutable-automaton.hh.
using vcsn::detail::mutable_automaton_impl< Context >::weight_t = typename weightset_t::value_t |
Transition weight.
Definition at line 53 of file mutable-automaton.hh.
using vcsn::detail::mutable_automaton_impl< Context >::weightset_ptr = typename context_t::weightset_ptr |
Definition at line 42 of file mutable-automaton.hh.
using vcsn::detail::mutable_automaton_impl< Context >::weightset_t = weightset_t_of<context_t> |
Definition at line 38 of file mutable-automaton.hh.
|
delete |
|
delete |
|
inline |
Definition at line 94 of file mutable-automaton.hh.
|
inline |
Definition at line 100 of file mutable-automaton.hh.
|
inline |
Definition at line 499 of file mutable-automaton.hh.
|
inline |
Definition at line 475 of file mutable-automaton.hh.
|
inline |
Add a transition between two states.
Merge with an existing one with same label.
src | source state |
dst | destination state |
l | label of the transition |
w | weight of the transition |
Definition at line 670 of file mutable-automaton.hh.
References vcsn::detail::mutable_automaton_impl< Context >::get_transition(), vcsn::detail::mutable_automaton_impl< Context >::new_transition(), vcsn::detail::mutable_automaton_impl< Context >::null_transition(), vcsn::detail::mutable_automaton_impl< Context >::set_weight(), vcsn::detail::mutable_automaton_impl< Context >::weight_of(), and vcsn::detail::mutable_automaton_impl< Context >::weightset().
Referenced by vcsn::detail::mutable_automaton_impl< Context >::add_transition(), and vcsn::detail::mutable_automaton_impl< Context >::add_transition_copy().
|
inline |
Same as above, with weight one.
Definition at line 685 of file mutable-automaton.hh.
References vcsn::detail::mutable_automaton_impl< Context >::add_transition(), and vcsn::detail::mutable_automaton_impl< Context >::weightset().
|
inline |
Add a transition between two states, copying the label from the given transition.
Merge with an existing one with same label.
src | source state |
dst | destination state |
aut | the automaton whose transition will be copied. |
t | transition of aut whose label and weight are to copy |
transpose | whether label and weight should be transposed |
Definition at line 700 of file mutable-automaton.hh.
References vcsn::detail::mutable_automaton_impl< Context >::add_transition(), vcsn::conv(), vcsn::detail::mutable_automaton_impl< Context >::labelset(), vcsn::transpose(), and vcsn::detail::mutable_automaton_impl< Context >::weightset().
|
inline |
Definition at line 772 of file mutable-automaton.hh.
References vcsn::detail::mutable_automaton_impl< Context >::set_weight(), vcsn::detail::mutable_automaton_impl< Context >::weight_of(), and vcsn::detail::mutable_automaton_impl< Context >::weightset().
|
inline |
Indexes of all transitions arriving to state s.
Invalidated by del_transition() and del_state().
Definition at line 864 of file mutable-automaton.hh.
References vcsn::detail::mutable_automaton_impl< Context >::has_state().
Referenced by vcsn::detail::mutable_automaton_impl< Context >::print().
|
inline |
Indexes of all transitions leaving state s.
Invalidated by del_transition() and del_state().
Definition at line 855 of file mutable-automaton.hh.
References vcsn::detail::mutable_automaton_impl< Context >::has_state().
Referenced by vcsn::detail::mutable_automaton_impl< Context >::print().
|
inline |
All states including pre()/post().
Guaranteed in increasing order.
Definition at line 821 of file mutable-automaton.hh.
References vcsn::detail::mutable_automaton_impl< Context >::state_range().
Referenced by vcsn::detail::mutable_automaton_impl< Context >::print().
|
inline |
All states including pre()/post() that validate pred.
Guaranteed in increasing order.
Definition at line 829 of file mutable-automaton.hh.
References vcsn::detail::mutable_automaton_impl< Context >::state_range().
|
inline |
All the transition indexes between all states (including pre and post).
Definition at line 842 of file mutable-automaton.hh.
References vcsn::make_container_filter_range(), vcsn::detail::mutable_automaton_impl< Context >::null_state(), and vcsn::detail::mutable_automaton_impl< Context >::src_of().
|
inline |
Definition at line 140 of file mutable-automaton.hh.
|
inline |
Definition at line 427 of file mutable-automaton.hh.
|
inline |
Definition at line 516 of file mutable-automaton.hh.
Referenced by vcsn::detail::mutable_automaton_impl< Context >::set_transition(), and vcsn::detail::mutable_automaton_impl< Context >::set_weight().
|
inline |
Remove the transition (src, l, dst).
Definition at line 529 of file mutable-automaton.hh.
|
inlineprotected |
Definition at line 364 of file mutable-automaton.hh.
|
inlineprotected |
Remove t from the ingoing transition of the destination state.
Definition at line 353 of file mutable-automaton.hh.
|
inlineprotected |
Remove t from the outgoing transitions of the source state.
Definition at line 341 of file mutable-automaton.hh.
|
inline |
Definition at line 322 of file mutable-automaton.hh.
|
inline |
Final weight of s.
Definition at line 252 of file mutable-automaton.hh.
|
inline |
Initial weight of s.
Definition at line 240 of file mutable-automaton.hh.
|
inline |
Definition at line 267 of file mutable-automaton.hh.
Referenced by vcsn::detail::mutable_automaton_impl< Context >::add_transition().
|
inline |
Whether state s belongs to the automaton.
Definition at line 191 of file mutable-automaton.hh.
Referenced by vcsn::detail::mutable_automaton_impl< Context >::all_in(), and vcsn::detail::mutable_automaton_impl< Context >::all_out().
|
inline |
Definition at line 304 of file mutable-automaton.hh.
|
inline |
Definition at line 310 of file mutable-automaton.hh.
|
inline |
Whether s is final.
Definition at line 232 of file mutable-automaton.hh.
|
inline |
Whether s is initial.
Definition at line 225 of file mutable-automaton.hh.
|
inline |
Whether a given state's outgoing transitions have been computed.
Definition at line 208 of file mutable-automaton.hh.
|
inline |
Whether a given state's incoming transitions have been computed.
Definition at line 217 of file mutable-automaton.hh.
|
inline |
Definition at line 323 of file mutable-automaton.hh.
|
inline |
Definition at line 142 of file mutable-automaton.hh.
Referenced by vcsn::detail::mutable_automaton_impl< Context >::add_transition_copy().
|
inlinestatic |
Invalid transition that shows that the state's outgoing transitions are unknown.
Definition at line 161 of file mutable-automaton.hh.
|
inline |
Definition at line 778 of file mutable-automaton.hh.
References vcsn::detail::mutable_automaton_impl< Context >::set_weight(), vcsn::detail::mutable_automaton_impl< Context >::weight_of(), and vcsn::detail::mutable_automaton_impl< Context >::weightset().
|
inline |
Create a new state and return its id.
Definition at line 381 of file mutable-automaton.hh.
|
inline |
Create a transition between two states.
There must not exist a previous transition with same (src, dst, l).
src | source state |
dst | destination state |
l | label of the transition |
w | weight of the transition |
Definition at line 547 of file mutable-automaton.hh.
Referenced by vcsn::detail::mutable_automaton_impl< Context >::add_transition().
|
inline |
Same as above, with weight one.
Definition at line 609 of file mutable-automaton.hh.
|
inline |
Copy the label of a transition between two states, creating a new transition.
There must not exist a previous transition with same (src, dst, label_of(l)).
src | source state |
dst | destination state |
aut | the automaton whose transition will be copied |
t | transition of aut whose label and weight are to copy |
transpose | whether label and weight should be transposed |
Definition at line 591 of file mutable-automaton.hh.
|
inlinestatic |
Invalid state.
Definition at line 156 of file mutable-automaton.hh.
Referenced by vcsn::detail::mutable_automaton_impl< Context >::all_transitions().
|
inlinestatic |
Invalid transition.
Definition at line 158 of file mutable-automaton.hh.
Referenced by vcsn::detail::mutable_automaton_impl< Context >::add_transition(), vcsn::detail::mutable_automaton_impl< Context >::set_transition(), vcsn::detail::mutable_automaton_impl< Context >::set_weight(), and vcsn::detail::mutable_automaton_impl< Context >::state_range().
|
inline |
Definition at line 174 of file mutable-automaton.hh.
|
inline |
Definition at line 177 of file mutable-automaton.hh.
|
inline |
Definition at line 176 of file mutable-automaton.hh.
|
inline |
Definition at line 175 of file mutable-automaton.hh.
|
inline |
Definition at line 178 of file mutable-automaton.hh.
|
inline |
Definition at line 107 of file mutable-automaton.hh.
|
inlinestatic |
Definition at line 154 of file mutable-automaton.hh.
Referenced by vcsn::detail::mutable_automaton_impl< Context >::states().
|
inlinestatic |
Definition at line 153 of file mutable-automaton.hh.
|
inline |
Label for preinitial and postfinal transitions.
Definition at line 164 of file mutable-automaton.hh.
|
inline |
Print a transition, for debugging.
Definition at line 717 of file mutable-automaton.hh.
Referenced by vcsn::detail::mutable_automaton_impl< Context >::print().
|
inline |
Print an automaton, for debugging.
Definition at line 736 of file mutable-automaton.hh.
References vcsn::detail::mutable_automaton_impl< Context >::all_in(), vcsn::detail::mutable_automaton_impl< Context >::all_out(), vcsn::detail::mutable_automaton_impl< Context >::all_states(), vcsn::detail::mutable_automaton_impl< Context >::print(), and vcsn::detail::mutable_automaton_impl< Context >::print_state_name().
|
inline |
Definition at line 133 of file mutable-automaton.hh.
|
inline |
Definition at line 401 of file mutable-automaton.hh.
|
inline |
Definition at line 413 of file mutable-automaton.hh.
Referenced by vcsn::detail::mutable_automaton_impl< Context >::print().
|
inline |
Definition at line 784 of file mutable-automaton.hh.
References vcsn::detail::mutable_automaton_impl< Context >::set_weight(), vcsn::detail::mutable_automaton_impl< Context >::weight_of(), and vcsn::detail::mutable_automaton_impl< Context >::weightset().
|
inline |
Definition at line 487 of file mutable-automaton.hh.
|
inline |
Definition at line 493 of file mutable-automaton.hh.
|
inline |
Definition at line 439 of file mutable-automaton.hh.
|
inline |
Definition at line 445 of file mutable-automaton.hh.
|
inline |
Definition at line 451 of file mutable-automaton.hh.
|
inline |
Definition at line 463 of file mutable-automaton.hh.
|
inline |
Set a transition between two states.
Override any possible existing transition with same states and label.
src | source state |
dst | destination state |
l | label of the transition |
w | weight of the transition |
Definition at line 625 of file mutable-automaton.hh.
References vcsn::detail::mutable_automaton_impl< Context >::del_transition(), and vcsn::detail::mutable_automaton_impl< Context >::null_transition().
Referenced by vcsn::detail::mutable_automaton_impl< Context >::set_transition().
|
inline |
Same as above, with unit weight.
Definition at line 654 of file mutable-automaton.hh.
References vcsn::detail::mutable_automaton_impl< Context >::set_transition(), and vcsn::detail::mutable_automaton_impl< Context >::weightset().
|
inline |
Definition at line 759 of file mutable-automaton.hh.
References vcsn::detail::mutable_automaton_impl< Context >::del_transition(), vcsn::detail::mutable_automaton_impl< Context >::null_transition(), and vcsn::detail::mutable_automaton_impl< Context >::weightset().
Referenced by vcsn::detail::mutable_automaton_impl< Context >::add_transition(), vcsn::detail::mutable_automaton_impl< Context >::add_weight(), vcsn::detail::mutable_automaton_impl< Context >::lweight(), and vcsn::detail::mutable_automaton_impl< Context >::rweight().
|
inlinestatic |
Definition at line 126 of file mutable-automaton.hh.
References vcsn::res, and vcsn::sname().
|
inline |
Definition at line 321 of file mutable-automaton.hh.
Referenced by vcsn::detail::mutable_automaton_impl< Context >::all_transitions().
|
inlinestatic |
Definition at line 421 of file mutable-automaton.hh.
|
inlineprotected |
The range of index numbers in [b .
. e] that validate the predicate pred.
Definition at line 798 of file mutable-automaton.hh.
References vcsn::make_container_filter_range(), vcsn::detail::mutable_automaton_impl< Context >::null_transition(), and vcsn::detail::mutable_automaton_impl< Context >::stored_state_t::succ.
Referenced by vcsn::detail::mutable_automaton_impl< Context >::all_states(), vcsn::detail::mutable_automaton_impl< Context >::state_range(), and vcsn::detail::mutable_automaton_impl< Context >::states().
|
inlineprotected |
The range of state numbers in [b .. e].
Definition at line 813 of file mutable-automaton.hh.
References vcsn::detail::mutable_automaton_impl< Context >::state_range().
|
inline |
All states excluding pre()/post().
Guaranteed in increasing order.
Definition at line 836 of file mutable-automaton.hh.
References vcsn::detail::mutable_automaton_impl< Context >::post(), and vcsn::detail::mutable_automaton_impl< Context >::state_range().
|
inline |
Definition at line 505 of file mutable-automaton.hh.
|
inline |
Definition at line 481 of file mutable-automaton.hh.
|
inline |
Definition at line 328 of file mutable-automaton.hh.
Referenced by vcsn::detail::mutable_automaton_impl< Context >::add_transition(), vcsn::detail::mutable_automaton_impl< Context >::add_weight(), vcsn::detail::mutable_automaton_impl< Context >::lweight(), and vcsn::detail::mutable_automaton_impl< Context >::rweight().
|
inline |
Definition at line 141 of file mutable-automaton.hh.
Referenced by vcsn::detail::mutable_automaton_impl< Context >::add_transition(), vcsn::detail::mutable_automaton_impl< Context >::add_transition_copy(), vcsn::detail::mutable_automaton_impl< Context >::add_weight(), vcsn::detail::mutable_automaton_impl< Context >::lweight(), vcsn::detail::mutable_automaton_impl< Context >::rweight(), vcsn::detail::mutable_automaton_impl< Context >::set_transition(), and vcsn::detail::mutable_automaton_impl< Context >::set_weight().
|
protected |
The algebraic type of this automaton.
Definition at line 57 of file mutable-automaton.hh.
|
protected |
Label for initial and final transitions.
Definition at line 89 of file mutable-automaton.hh.
|
protected |
Definition at line 82 of file mutable-automaton.hh.
|
protected |
Free indexes in states_.
Definition at line 84 of file mutable-automaton.hh.
|
protected |
Definition at line 85 of file mutable-automaton.hh.
|
protected |
Free indexes in transitions_.
Definition at line 87 of file mutable-automaton.hh.