#include <trie.hpp>

Inheritance diagram for tetengo::trie::trie< Key, Value, KeySerializer >:

Collaboration diagram for tetengo::trie::trie< Key, Value, KeySerializer >:

Public Types
using	key_type = Key
	The key type.

using	value_type = Value
	The value type.

using	key_serializer_type = KeySerializer
	The key serializer_type.

using	iterator = trie_iterator< value_type >
	The iterator type.

using	building_observer_set_type = trie_impl::building_observer_set_type
	The building observer set type.

Public Member Functions
	trie (const key_serializer_type &key_serializer=default_serializer< key_type >{ true })
	Creates a trie.

	trie (std::initializer_list< std::pair< key_type, value_type > > elements, const key_serializer_type &key_serializer=default_serializer< key_type >{ true }, const building_observer_set_type &building_observer_set=null_building_observer_set(), std::size_t double_array_density_factor=default_double_array_density_factor())
	Creates a trie.

template<typename InputIterator >
	trie (InputIterator first, InputIterator last, const key_serializer_type &key_serializer=default_serializer< key_type >{ true }, const building_observer_set_type &building_observer_set=null_building_observer_set(), std::size_t double_array_density_factor=default_double_array_density_factor())
	Creates a trie.

template<typename InputIterator >
	trie (std::move_iterator< InputIterator > first, std::move_iterator< InputIterator > last, const key_serializer_type &key_serializer=default_serializer< key_type >{ true }, const building_observer_set_type &building_observer_set=null_building_observer_set(), std::size_t double_array_density_factor=default_double_array_density_factor())
	Creates a trie.

	trie (std::unique_ptr< storage > &&p_storage, const key_serializer_type &key_serializer=default_serializer< key_type >{ true })
	Creates a trie.

bool	empty () const
	Returns true when the trie is empty.

std::size_t	size () const
	Returns the size of the trie.

bool	contains (const key_type &key) const
	Returns true when the trie contains the given key.

const value_type *	find (const key_type &key) const
	Finds the value object correspoinding the given key.

iterator	begin () const
	Returns the first iterator.

iterator	end () const
	Returns the last iterator.

std::unique_ptr< trie >	subtrie (const key_type &key_prefix) const
	Returns a subtrie.

const storage &	get_storage () const
	Returns the storage.

Static Public Member Functions
static const building_observer_set_type &	null_building_observer_set ()
	Returns the null building observer set.

static std::size_t	default_double_array_density_factor ()
	Returns the default double array density factor.

Detailed Description

template<typename Key, typename Value, typename KeySerializer = default_serializer<Key>>
class tetengo::trie::trie< Key, Value, KeySerializer >

A trie.

Template Parameters

Key	A key type.
Value	A value type.
KeySerializer	A key serializer type.

Constructor & Destructor Documentation

◆ trie() [1/5]

template<typename Key , typename Value , typename KeySerializer = default_serializer<Key>>

tetengo::trie::trie< Key, Value, KeySerializer >::trie ( const key_serializer_type & key_serializer = default_serializer<key_type>{ true } )

inlineexplicit

Creates a trie.

Parameters

key_serializer A key serializer.

◆ trie() [2/5]

template<typename Key , typename Value , typename KeySerializer = default_serializer<Key>>

tetengo::trie::trie< Key, Value, KeySerializer >::trie	(	std::initializer_list< std::pair< key_type, value_type > >	elements,
		const key_serializer_type &	key_serializer = `default_serializer<key_type>{ true }`,
		const building_observer_set_type &	building_observer_set = `null_building_observer_set()`,
		std::size_t	double_array_density_factor = `default_double_array_density_factor()`
	)

inlineexplicit

Creates a trie.

Parameters

elements	Initial elements.
key_serializer	A key serializer.
building_observer_set	A building observer set.
double_array_density_factor	A double array density factor.

◆ trie() [3/5]

template<typename Key , typename Value , typename KeySerializer = default_serializer<Key>>

template<typename InputIterator >

tetengo::trie::trie< Key, Value, KeySerializer >::trie	(	InputIterator	first,
		InputIterator	last,
		const key_serializer_type &	key_serializer = `default_serializer<key_type>{ true }`,
		const building_observer_set_type &	building_observer_set = `null_building_observer_set()`,
		std::size_t	double_array_density_factor = `default_double_array_density_factor()`
	)

inline

Creates a trie.

Template Parameters

InputIterator An input iterator type.

Parameters

first	An iterator to the first element.
last	An iterator to the last element.
key_serializer	A key serializer.
building_observer_set	A building observer set.
double_array_density_factor	A double array density factor.

◆ trie() [4/5]

template<typename Key , typename Value , typename KeySerializer = default_serializer<Key>>

template<typename InputIterator >

tetengo::trie::trie< Key, Value, KeySerializer >::trie	(	std::move_iterator< InputIterator >	first,
		std::move_iterator< InputIterator >	last,
		const key_serializer_type &	key_serializer = `default_serializer<key_type>{ true }`,
		const building_observer_set_type &	building_observer_set = `null_building_observer_set()`,
		std::size_t	double_array_density_factor = `default_double_array_density_factor()`
	)

inline

Creates a trie.

Template Parameters

InputIterator An input iterator type.

Parameters

first	An iterator to the first element.
last	An iterator to the last element.
key_serializer	A key serializer.
building_observer_set	A building observer set.
double_array_density_factor	A double array density factor.

◆ trie() [5/5]

template<typename Key , typename Value , typename KeySerializer = default_serializer<Key>>

tetengo::trie::trie< Key, Value, KeySerializer >::trie	(	std::unique_ptr< storage > &&	p_storage,
		const key_serializer_type &	key_serializer = `default_serializer<key_type>{ true }`
	)

inlineexplicit

Creates a trie.

Parameters

p_storage	A unique pointer to a storage.
key_serializer	A key serializer.

Member Function Documentation

◆ begin()

template<typename Key , typename Value , typename KeySerializer = default_serializer<Key>>

iterator tetengo::trie::trie< Key, Value, KeySerializer >::begin ( ) const

inline

Returns the first iterator.

Returns: The first iterator.

◆ contains()

template<typename Key , typename Value , typename KeySerializer = default_serializer<Key>>

bool tetengo::trie::trie< Key, Value, KeySerializer >::contains ( const key_type & key ) const

inline

Returns true when the trie contains the given key.

Parameters

key A key.

Return values

true	When the trie contains the given key.
false	Otherwise.

◆ default_double_array_density_factor()

template<typename Key , typename Value , typename KeySerializer = default_serializer<Key>>

static std::size_t tetengo::trie::trie< Key, Value, KeySerializer >::default_double_array_density_factor ( )

inlinestatic

Returns the default double array density factor.

Returns: The default double array density factor.

◆ empty()

template<typename Key , typename Value , typename KeySerializer = default_serializer<Key>>

bool tetengo::trie::trie< Key, Value, KeySerializer >::empty ( ) const

inline

Returns true when the trie is empty.

Return values

true	When the trie is empty.
false	Otherwise.

◆ end()

template<typename Key , typename Value , typename KeySerializer = default_serializer<Key>>

iterator tetengo::trie::trie< Key, Value, KeySerializer >::end ( ) const

inline

Returns the last iterator.

Returns: The last iterator.

◆ find()

template<typename Key , typename Value , typename KeySerializer = default_serializer<Key>>

const value_type * tetengo::trie::trie< Key, Value, KeySerializer >::find ( const key_type & key ) const

inline

Finds the value object correspoinding the given key.

Parameters

key A key.

Returns: A pointer to the value object. Or nullptr when the trie does not have the given key.

◆ get_storage()

template<typename Key , typename Value , typename KeySerializer = default_serializer<Key>>

const storage & tetengo::trie::trie< Key, Value, KeySerializer >::get_storage ( ) const

inline

Returns the storage.

Returns: The storage.

◆ null_building_observer_set()

template<typename Key , typename Value , typename KeySerializer = default_serializer<Key>>

static const building_observer_set_type & tetengo::trie::trie< Key, Value, KeySerializer >::null_building_observer_set ( )

inlinestatic

Returns the null building observer set.

Returns: The null bulding observer set.

◆ size()

template<typename Key , typename Value , typename KeySerializer = default_serializer<Key>>

std::size_t tetengo::trie::trie< Key, Value, KeySerializer >::size ( ) const

inline

Returns the size of the trie.

Returns: The size.

◆ subtrie()

template<typename Key , typename Value , typename KeySerializer = default_serializer<Key>>

std::unique_ptr< trie > tetengo::trie::trie< Key, Value, KeySerializer >::subtrie ( const key_type & key_prefix ) const

inline

Returns a subtrie.

Parameters

key_prefix A key prefix.

Returns: A unique pointer to a subtrie. Or nullptr when the trie does not have the given key prefix.

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

library/trie/cpp/include/tetengo/trie/trie.hpp

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ trie() [1/5]

◆ trie() [2/5]

◆ trie() [3/5]

◆ trie() [4/5]

◆ trie() [5/5]

Member Function Documentation

◆ begin()

◆ contains()

◆ default_double_array_density_factor()

◆ empty()

◆ end()

◆ find()

◆ get_storage()

◆ null_building_observer_set()

◆ size()

◆ subtrie()