The subset construction automaton from another. More...

#include <determinize.hh>

Inheritance diagram for vcsn::detail::determinized_automaton_impl< Aut >:

Collaboration diagram for vcsn::detail::determinized_automaton_impl< Aut >:

Public Types
using	automaton_t = Aut

using	context_t = context_t_of< automaton_t >

template<typename Ctx = context_t>
using	fresh_automaton_t = fresh_automaton_t_of< Aut, Ctx >

using	label_t = label_t_of< automaton_t >

using	labelset_t = labelset_t_of< automaton_t >

using	super_t = automaton_decorator< fresh_automaton_t<>>

using	state_name_t = dynamic_bitset
	The name: set of (input) states. More...

using	state_t = state_t_of< automaton_t >
	Result automaton state type. More...

using	origins_t = std::map< state_t, std::set< state_t >>
	A map from determinized states to sets of original states. More...

Public Types inherited from vcsn::detail::automaton_decorator< fresh_automaton_t_of< Aut > >
using	automaton_t = fresh_automaton_t_of< Aut >
	The type of automaton to wrap. More...

using	context_t = context_t_of< fresh_automaton_t_of< Aut > >

using	element_type = typename automaton_t::element_type
	The automaton type, without shared_ptr. More...

using	fresh_automaton_t = typename element_type::template fresh_automaton_t< Ctx >
	The (shared pointer) type to use it we have to create an automaton of the same (underlying) type. More...

using	kind_t = typename context_t::kind_t

using	labelset_t = typename context_t::labelset_t

using	labelset_ptr = typename context_t::labelset_ptr

using	label_t = typename labelset_t::value_t

using	weightset_t = typename context_t::weightset_t

using	weightset_ptr = typename context_t::weightset_ptr

using	weight_t = typename weightset_t::value_t

using	state_t = state_t_of< automaton_t >

using	transition_t = transition_t_of< automaton_t >

Public Member Functions
	determinized_automaton_impl (const automaton_t &a)
	Build the determinizer. More...

std::ostream &	print_set (std::ostream &o, format fmt={}) const

state_t	state (const state_name_t &ss)
	The state for set of states ss. More...

void	operator() ()
	Determinize all accessible states. More...

bool	state_has_name (state_t s) const

std::ostream &	print_state_name (state_t s, std::ostream &o, format fmt={}, bool delimit=false) const

const origins_t &	origins () const

Public Member Functions inherited from vcsn::detail::automaton_decorator< fresh_automaton_t_of< Aut > >
	automaton_decorator (automaton_t aut)

	automaton_decorator (const automaton_decorator &aut)

	automaton_decorator (const context_t &ctx)

	automaton_decorator (automaton_decorator &&aut)

automaton_decorator &	operator= (automaton_decorator &&that)

automaton_t	strip ()

auto	all_in (Args &&...args) const -> decltype(aut_-> all_in(std::forward< Args >(args)...))

auto	all_out (Args &&...args) const -> decltype(aut_-> all_out(std::forward< Args >(args)...))

auto	all_states (Args &&...args) const -> decltype(aut_-> all_states(std::forward< Args >(args)...))

auto	all_transitions (Args &&...args) const -> decltype(aut_-> all_transitions(std::forward< Args >(args)...))

auto	context (Args &&...args) const -> decltype(aut_-> context(std::forward< Args >(args)...))

auto	dst_of (Args &&...args) const -> decltype(aut_-> dst_of(std::forward< Args >(args)...))

auto	final_transitions (Args &&...args) const -> decltype(aut_-> final _transitions(std

auto	get_final_weight (Args &&...args) const -> decltype(aut_-> get_ final _weight(std

auto	get_initial_weight (Args &&...args) const -> decltype(aut_-> get_initial_weight(std::forward< Args >(args)...))

auto	get_transition (Args &&...args) const -> decltype(aut_-> get_transition(std::forward< Args >(args)...))

auto	has_state (Args &&...args) const -> decltype(aut_-> has_state(std::forward< Args >(args)...))

auto	has_transition (Args &&...args) const -> decltype(aut_-> has_transition(std::forward< Args >(args)...))

auto	in (Args &&...args) const -> decltype(aut_-> in(std::forward< Args >(args)...))

auto	initial_transitions (Args &&...args) const -> decltype(aut_-> initial_transitions(std::forward< Args >(args)...))

auto	is_final (Args &&...args) const -> decltype(aut_-> is_ final(std

auto	is_initial (Args &&...args) const -> decltype(aut_-> is_initial(std::forward< Args >(args)...))

auto	label_of (Args &&...args) const -> decltype(aut_-> label_of(std::forward< Args >(args)...))

auto	labelset (Args &&...args) const -> decltype(aut_-> labelset(std::forward< Args >(args)...))

auto	num_all_states (Args &&...args) const -> decltype(aut_-> num_all_states(std::forward< Args >(args)...))

auto	num_finals (Args &&...args) const -> decltype(aut_-> num_ final s(std

auto	num_initials (Args &&...args) const -> decltype(aut_-> num_initials(std::forward< Args >(args)...))

auto	num_states (Args &&...args) const -> decltype(aut_-> num_states(std::forward< Args >(args)...))

auto	num_transitions (Args &&...args) const -> decltype(aut_-> num_transitions(std::forward< Args >(args)...))

auto	out (Args &&...args) const -> decltype(aut_-> out(std::forward< Args >(args)...))

auto	outin (Args &&...args) const -> decltype(aut_-> outin(std::forward< Args >(args)...))

auto	prepost_label (Args &&...args) const -> decltype(aut_-> prepost_label(std::forward< Args >(args)...))

auto	print_set (Args &&...args) const -> decltype(aut_-> print_set(std::forward< Args >(args)...))

auto	print_state (Args &&...args) const -> decltype(aut_-> print_state(std::forward< Args >(args)...))

auto	print_state_name (Args &&...args) const -> decltype(aut_-> print_state_name(std::forward< Args >(args)...))

auto	src_of (Args &&...args) const -> decltype(aut_-> src_of(std::forward< Args >(args)...))

auto	state_has_name (Args &&...args) const -> decltype(aut_-> state_has_name(std::forward< Args >(args)...))

auto	state_is_strict (Args &&...args) const -> decltype(aut_-> state_is_strict(std::forward< Args >(args)...))

auto	states (Args &&...args) const -> decltype(aut_-> states(std::forward< Args >(args)...))

auto	transitions (Args &&...args) const -> decltype(aut_-> transitions(std::forward< Args >(args)...))

auto	weight_of (Args &&...args) const -> decltype(aut_-> weight_of(std::forward< Args >(args)...))

auto	weightset (Args &&...args) const -> decltype(aut_-> weightset(std::forward< Args >(args)...))

auto	add_final (Args &&...args) -> decltype(aut_-> add_ final(std

auto	add_initial (Args &&...args) -> decltype(aut_-> add_initial(std::forward< Args >(args)...))

auto	add_transition (Args &&...args) -> decltype(aut_-> add_transition(std::forward< Args >(args)...))

auto	add_transition_copy (Args &&...args) -> decltype(aut_-> add_transition_copy(std::forward< Args >(args)...))

auto	add_weight (Args &&...args) -> decltype(aut_-> add_weight(std::forward< Args >(args)...))

auto	del_state (Args &&...args) -> decltype(aut_-> del_state(std::forward< Args >(args)...))

auto	del_transition (Args &&...args) -> decltype(aut_-> del_transition(std::forward< Args >(args)...))

auto	lmul_weight (Args &&...args) -> decltype(aut_-> lmul_weight(std::forward< Args >(args)...))

auto	new_state (Args &&...args) -> decltype(aut_-> new_state(std::forward< Args >(args)...))

auto	new_transition (Args &&...args) -> decltype(aut_-> new_transition(std::forward< Args >(args)...))

auto	new_transition_copy (Args &&...args) -> decltype(aut_-> new_transition_copy(std::forward< Args >(args)...))

auto	rmul_weight (Args &&...args) -> decltype(aut_-> rmul_weight(std::forward< Args >(args)...))

auto	set_final (Args &&...args) -> decltype(aut_-> set_ final(std

auto	set_initial (Args &&...args) -> decltype(aut_-> set_initial(std::forward< Args >(args)...))

auto	set_transition (Args &&...args) -> decltype(aut_-> set_transition(std::forward< Args >(args)...))

auto	set_weight (Args &&...args) -> decltype(aut_-> set_weight(std::forward< Args >(args)...))

auto	unset_final (Args &&...args) -> decltype(aut_-> unset_ final(std

auto	unset_initial (Args &&...args) -> decltype(aut_-> unset_initial(std::forward< Args >(args)...))

Static Public Member Functions
static symbol	sname ()

Static Public Member Functions inherited from vcsn::detail::automaton_decorator< fresh_automaton_t_of< Aut > >
static constexpr auto	null_state (Args &&...args) -> decltype(element_type::null_state(std::forward< Args >(args)...))

static constexpr auto	null_transition (Args &&...args) -> decltype(element_type::null_transition(std::forward< Args >(args)...))

static constexpr auto	post (Args &&...args) -> decltype(element_type::post(std::forward< Args >(args)...))

static constexpr auto	pre (Args &&...args) -> decltype(element_type::pre(std::forward< Args >(args)...))

static constexpr auto	sname (Args &&...args) -> decltype(element_type::sname(std::forward< Args >(args)...))

Public Attributes
origins_t	origins_

Private Types
using	map_t = std::unordered_map< state_name_t, state_t >
	Set of input states -> output state. More...

using	stack = std::stack< state_name_t >
	The sets of (input) states waiting to be processed. More...

using	label_map_t = std::unordered_map< label_t, state_name_t, vcsn::hash< labelset_t >, vcsn::equal_to< labelset_t >>
	successors[SOURCE-STATE][LABEL] = DEST-STATESET. More...

using	successors_t = std::map< state_t, label_map_t >

Private Attributes
map_t	map_

automaton_t	input_
	Input automaton. More...

size_t	state_size_ = input_->all_states().back() + 1
	We use state numbers as indexes, so we need to know the last state number. More...

stack	todo_

state_name_t	finals_
	Set of final states in the input automaton. More...

successors_t	successors_

Additional Inherited Members
Protected Attributes inherited from vcsn::detail::automaton_decorator< fresh_automaton_t_of< Aut > >
automaton_t	aut_
	The wrapped automaton, possibly const. More...

Detailed Description

template<typename Aut>
class vcsn::detail::determinized_automaton_impl< Aut >

The subset construction automaton from another.

Template Parameters

Aut	the input automaton type.

Precondition: labelset is free.; weightset is Boolean.

Definition at line 37 of file determinize.hh.

Member Typedef Documentation

template<typename Aut >

using vcsn::detail::determinized_automaton_impl< Aut >::automaton_t = Aut

Definition at line 46 of file determinize.hh.

template<typename Aut >

using vcsn::detail::determinized_automaton_impl< Aut >::context_t = context_t_of<automaton_t>

Definition at line 47 of file determinize.hh.

template<typename Aut >

template<typename Ctx = context_t>

using vcsn::detail::determinized_automaton_impl< Aut >::fresh_automaton_t = fresh_automaton_t_of<Aut, Ctx>

Definition at line 49 of file determinize.hh.

template<typename Aut >

using vcsn::detail::determinized_automaton_impl< Aut >::label_map_t = std::unordered_map<label_t, state_name_t, vcsn::hash<labelset_t>, vcsn::equal_to<labelset_t>>

private

successors[SOURCE-STATE][LABEL] = DEST-STATESET.

Definition at line 237 of file determinize.hh.

template<typename Aut >

using vcsn::detail::determinized_automaton_impl< Aut >::label_t = label_t_of<automaton_t>

Definition at line 50 of file determinize.hh.

template<typename Aut >

using vcsn::detail::determinized_automaton_impl< Aut >::labelset_t = labelset_t_of<automaton_t>

Definition at line 51 of file determinize.hh.

template<typename Aut >

using vcsn::detail::determinized_automaton_impl< Aut >::map_t = std::unordered_map<state_name_t, state_t>

private

Set of input states -> output state.

Definition at line 216 of file determinize.hh.

template<typename Aut >

using vcsn::detail::determinized_automaton_impl< Aut >::origins_t = std::map<state_t, std::set<state_t>>

A map from determinized states to sets of original states.

Definition at line 195 of file determinize.hh.

template<typename Aut >

using vcsn::detail::determinized_automaton_impl< Aut >::stack = std::stack<state_name_t>

private

The sets of (input) states waiting to be processed.

Definition at line 228 of file determinize.hh.

template<typename Aut >

using vcsn::detail::determinized_automaton_impl< Aut >::state_name_t = dynamic_bitset

The name: set of (input) states.

Definition at line 55 of file determinize.hh.

template<typename Aut >

using vcsn::detail::determinized_automaton_impl< Aut >::state_t = state_t_of<automaton_t>

Result automaton state type.

Definition at line 58 of file determinize.hh.

template<typename Aut >

using vcsn::detail::determinized_automaton_impl< Aut >::successors_t = std::map<state_t, label_map_t>

private

Definition at line 238 of file determinize.hh.

template<typename Aut >

using vcsn::detail::determinized_automaton_impl< Aut >::super_t = automaton_decorator<fresh_automaton_t<>>

Definition at line 52 of file determinize.hh.

Constructor & Destructor Documentation

template<typename Aut >

vcsn::detail::determinized_automaton_impl< Aut >::determinized_automaton_impl ( const automaton_t & a )

inline

Build the determinizer.

Parameters

a	the automaton to determinize

Definition at line 62 of file determinize.hh.

References vcsn::detail::determinized_automaton_impl< Aut >::finals_, vcsn::detail::determinized_automaton_impl< Aut >::input_, vcsn::detail::determinized_automaton_impl< Aut >::map_, vcsn::detail::automaton_decorator< Aut, Context >::pre(), vcsn::detail::determinized_automaton_impl< Aut >::state_size_, and vcsn::detail::determinized_automaton_impl< Aut >::todo_.

Here is the call graph for this function:

Member Function Documentation

template<typename Aut >

void vcsn::detail::determinized_automaton_impl< Aut >::operator() ( )

inline

Determinize all accessible states.

Definition at line 117 of file determinize.hh.

template<typename Aut >

const origins_t& vcsn::detail::determinized_automaton_impl< Aut >::origins ( ) const

inline

Definition at line 199 of file determinize.hh.

template<typename Aut >

std::ostream& vcsn::detail::determinized_automaton_impl< Aut >::print_set	(	std::ostream &	o,
		format	fmt = `{}`
	)		const

inline

Definition at line 86 of file determinize.hh.

template<typename Aut >

std::ostream& vcsn::detail::determinized_automaton_impl< Aut >::print_state_name	(	state_t	s,
		std::ostream &	o,
		format	fmt = `{}`,
		bool	delimit = `false`
	)		const