Build a trie automaton (prefix-tree-like automaton). More...

#include <trie.hh>

Collaboration diagram for vcsn::detail::trie_builder< Context, Dir >:

Public Types
using	context_t = Context

using	self_t = trie_builder

using	automaton_t = mutable_automaton< context_t >
	The type of the result. More...

using	work_automaton_t = std::conditional_t< Dir==direction::forward, automaton_t, transpose_automaton< automaton_t > >
	The type of the automaton we work on. More...

using	labelset_t = labelset_t_of< context_t >
	The input labelset, free/letterized or not. More...

using	letter_t = letter_t_of< context_t >

using	word_t = word_t_of< context_t >

using	weightset_t = weightset_t_of< context_t >

using	weight_t = weight_t_of< context_t >

using	state_t = state_t_of< automaton_t >

using	polynomialset_t = word_polynomialset_t< context_t >
	Polynomialset for the input: weighted words. More...

using	polynomial_t = typename polynomialset_t::value_t

using	monomial_t = typename polynomialset_t::monomial_t

Public Member Functions
	trie_builder (const context_t &c)

void	add (const word_t &l, const weight_t &w=weightset_t::one())
	Add a monomial. More...

void	add (const monomial_t &m)
	Add a monomial. More...

void	add (const polynomial_t &p)
	Add a polynomial. More...

void	add_words (std::istream &is)
	Add all the words (one per line) in this stream. More...

void	add_monomials (std::istream &is)
	Add all the monomials (one per line) in this stream. More...

void	add (std::istream &is, const std::string &format)
	Add all the monomials in this stream. More...

template<direction D = Dir>
auto	result () -> std::enable_if_t< D==direction::forward, automaton_t >
	Get the result for the forward trie. More...

template<direction D = Dir>
auto	result () -> std::enable_if_t< D==direction::backward, automaton_t >
	Get the result for a backward trie. More...

Private Member Functions
void	add_ (const word_t &lbl, const weight_t &wgt)
	Add a monomial. More...

state_t	next_ (state_t s, letter_t l)
	Follow a transition, possibly creating it. More...

Private Attributes
work_automaton_t	res_
	The automaton being built. More...

const context_t &	ctx_ = res_->context()
	The context of the automaton: letterized. More...

letterized_t< labelset_t >::value_t	padding_ = letterized_t<labelset_t>::one()
	Padding, in case it is needed. More...

Detailed Description

template<typename Context, direction Dir>
class vcsn::detail::trie_builder< Context, Dir >

Build a trie automaton (prefix-tree-like automaton).

Template Parameters

Context	the context of the mutable_automaton to build. It is typically a letterset, even though we feed it with words.
Dir	if `forward` build a trie (single initial state) otherwise (`backward`) build a reversed trie (single final state, but many initial states).

Definition at line 51 of file trie.hh.

Member Typedef Documentation

◆ automaton_t

template<typename Context , direction Dir>

using vcsn::detail::trie_builder< Context, Dir >::automaton_t = mutable_automaton<context_t>

The type of the result.

Definition at line 57 of file trie.hh.

◆ context_t

template<typename Context , direction Dir>

using vcsn::detail::trie_builder< Context, Dir >::context_t = Context

Definition at line 54 of file trie.hh.

◆ labelset_t

template<typename Context , direction Dir>

using vcsn::detail::trie_builder< Context, Dir >::labelset_t = labelset_t_of<context_t>

The input labelset, free/letterized or not.

Definition at line 64 of file trie.hh.

◆ letter_t

template<typename Context , direction Dir>

using vcsn::detail::trie_builder< Context, Dir >::letter_t = letter_t_of<context_t>

Definition at line 65 of file trie.hh.

◆ monomial_t

template<typename Context , direction Dir>

using vcsn::detail::trie_builder< Context, Dir >::monomial_t = typename polynomialset_t::monomial_t

Definition at line 74 of file trie.hh.

◆ polynomial_t

template<typename Context , direction Dir>

using vcsn::detail::trie_builder< Context, Dir >::polynomial_t = typename polynomialset_t::value_t

Definition at line 73 of file trie.hh.

◆ polynomialset_t

template<typename Context , direction Dir>

using vcsn::detail::trie_builder< Context, Dir >::polynomialset_t = word_polynomialset_t<context_t>

Polynomialset for the input: weighted words.

Definition at line 72 of file trie.hh.

◆ self_t

template<typename Context , direction Dir>

using vcsn::detail::trie_builder< Context, Dir >::self_t = trie_builder

Definition at line 55 of file trie.hh.

◆ state_t

template<typename Context , direction Dir>

using vcsn::detail::trie_builder< Context, Dir >::state_t = state_t_of<automaton_t>

Definition at line 69 of file trie.hh.

◆ weight_t

template<typename Context , direction Dir>

using vcsn::detail::trie_builder< Context, Dir >::weight_t = weight_t_of<context_t>

Definition at line 68 of file trie.hh.

◆ weightset_t

template<typename Context , direction Dir>

using vcsn::detail::trie_builder< Context, Dir >::weightset_t = weightset_t_of<context_t>

Definition at line 67 of file trie.hh.

◆ word_t

template<typename Context , direction Dir>

using vcsn::detail::trie_builder< Context, Dir >::word_t = word_t_of<context_t>

Definition at line 66 of file trie.hh.

◆ work_automaton_t

template<typename Context , direction Dir>

using vcsn::detail::trie_builder< Context, Dir >::work_automaton_t = std::conditional_t<Dir == direction::forward, automaton_t, transpose_automaton<automaton_t> >

The type of the automaton we work on.

Definition at line 62 of file trie.hh.

Constructor & Destructor Documentation

◆ trie_builder()

template<typename Context , direction Dir>

vcsn::detail::trie_builder< Context, Dir >::trie_builder ( const context_t & c )

inline

Definition at line 76 of file trie.hh.

Member Function Documentation

◆ add() [1/4]

template<typename Context , direction Dir>

void vcsn::detail::trie_builder< Context, Dir >::add	(	const word_t &	l,
		const weight_t &	w = `weightset_t::one()`
	)

inline

Add a monomial.

Parameters

l	the word to add.
w	its associated weight.

Definition at line 83 of file trie.hh.

◆ add() [2/4]

template<typename Context , direction Dir>

void vcsn::detail::trie_builder< Context, Dir >::add ( const monomial_t & m )

inline

Add a monomial.

Definition at line 89 of file trie.hh.

References vcsn::label_of(), and vcsn::weight_of().

Here is the call graph for this function:

◆ add() [3/4]

template<typename Context , direction Dir>

void vcsn::detail::trie_builder< Context, Dir >::add ( const polynomial_t & p )

inline

Add a polynomial.

Definition at line 95 of file trie.hh.

◆ add() [4/4]

template<typename Context , direction Dir>

void vcsn::detail::trie_builder< Context, Dir >::add	(	std::istream &	is,
		const std::string &	format
	)

inline

Add all the monomials in this stream.

Definition at line 123 of file trie.hh.

References vcsn::dyn::format(), and vcsn::detail::map().

Here is the call graph for this function:

◆ add_()

template<typename Context , direction Dir>

void vcsn::detail::trie_builder< Context, Dir >::add_	(	const word_t &	lbl,
		const weight_t &	wgt
	)

inlineprivate

Add a monomial.

Take the direction into account (i.e., transpose the word if needed).

Parameters

lbl	the word to add.
wgt	its associated weight.

Definition at line 159 of file trie.hh.

References vcsn::forward.

◆ add_monomials()

template<typename Context , direction Dir>

void vcsn::detail::trie_builder< Context, Dir >::add_monomials ( std::istream & is )

inline

Add all the monomials (one per line) in this stream.

Definition at line 115 of file trie.hh.

References vcsn::detail::make_word_polynomialset().

Here is the call graph for this function:

◆ add_words()

template<typename Context , direction Dir>

void vcsn::detail::trie_builder< Context, Dir >::add_words ( std::istream & is )

inline

Add all the words (one per line) in this stream.

Definition at line 102 of file trie.hh.

References vcsn::conv(), vcsn::detail::make_wordset(), and vcsn::detail::quote().

Here is the call graph for this function:

◆ next_()

template<typename Context , direction Dir>

state_t vcsn::detail::trie_builder< Context, Dir >::next_	(	state_t	s,
		letter_t	l
	)

inlineprivate

Follow a transition, possibly creating it.

Returns: the destination state.

Definition at line 175 of file trie.hh.

References vcsn::detail::front(), and vcsn::detail::out().

Here is the call graph for this function:

◆ result() [1/2]

template<typename Context , direction Dir>

template<direction D = Dir>

auto vcsn::detail::trie_builder< Context, Dir >::result ( ) -> std::enable_if_t<D == direction::forward, automaton_t>

inline

Get the result for the forward trie.

Definition at line 139 of file trie.hh.

◆ result() [2/2]

template<typename Context , direction Dir>

template<direction D = Dir>

auto vcsn::detail::trie_builder< Context, Dir >::result ( ) -> std::enable_if_t<D == direction::backward, automaton_t>

inline

Get the result for a backward trie.

Definition at line 147 of file trie.hh.

References vcsn::transpose().

Here is the call graph for this function:

Member Data Documentation

◆ ctx_

template<typename Context , direction Dir>

const context_t& vcsn::detail::trie_builder< Context, Dir >::ctx_ = res_->context()

private

The context of the automaton: letterized.

Definition at line 192 of file trie.hh.

◆ padding_

template<typename Context , direction Dir>

letterized_t<labelset_t>::value_t vcsn::detail::trie_builder< Context, Dir >::padding_ = letterized_t<labelset_t>::one()

private

Padding, in case it is needed.

Definition at line 195 of file trie.hh.

◆ res_

template<typename Context , direction Dir>

work_automaton_t vcsn::detail::trie_builder< Context, Dir >::res_

private

The automaton being built.

Definition at line 190 of file trie.hh.

The documentation for this class was generated from the following file:

vcsn/algos/trie.hh

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<typename Context, direction Dir> class vcsn::detail::trie_builder< Context, Dir >

Member Typedef Documentation

◆ automaton_t

◆ context_t

◆ labelset_t

◆ letter_t

◆ monomial_t

◆ polynomial_t

◆ polynomialset_t

◆ self_t

◆ state_t

◆ weight_t

◆ weightset_t

◆ word_t

◆ work_automaton_t

Constructor & Destructor Documentation

◆ trie_builder()

Member Function Documentation

◆ add() [1/4]

◆ add() [2/4]

◆ add() [3/4]

◆ add() [4/4]

◆ add_()

◆ add_monomials()

◆ add_words()

◆ next_()

◆ result() [1/2]

◆ result() [2/2]

Member Data Documentation

◆ ctx_

◆ padding_

◆ res_

template<typename Context, direction Dir>
class vcsn::detail::trie_builder< Context, Dir >