AIToolbox::Factored::Trie Class Reference

This class organizes data ids as if in a trie. More...

#include <AIToolbox/Factored/Utils/Trie.hpp>

Public Member Functions
	Trie (Factors F)
	Basic constructor. More...
Factors	getF () const
	This function returns the set state space for the Trie. More...
void	reserve (size_t size)
	This function reserves memory for at least size elements. More...
size_t	insert (const PartialFactors &pf)
	This function inserts a new id using the input as a key. More...
size_t	size () const
	This function returns the number of insertions performed on the Trie. More...
std::vector< size_t >	filter (const Factors &f, size_t offset=0) const
	This function returns all ids where their key matches the input Factors. More...
std::vector< size_t >	filter (const PartialFactors &pf) const
	This function returns all ids where their key matches the input Factors. More...
std::vector< size_t >	refine (const std::vector< size_t > &ids, const PartialFactors &pf) const
	This function refines the input ids with the supplied filter. More...
void	erase (size_t id)
	This function removes the input id from the trie. More...
void	erase (size_t id, const PartialFactors &pf)
	This function removes the input id from the trie. More...
const Factors &	getFactors () const
	This function returns a reference to the underlying Factors. More...

Detailed Description

This class organizes data ids as if in a trie.

This class implements a trie, which is a kind of tree that can be used to sort strings, or in our case partial states. This class tries to be as efficient as possible, with tradeoffs for space and time.

Adding automatically inserts an id one greater than the last as value within the trie, using the specified partial state as key.

This data structure can then be filtered by Factors, and it will match the Factors against all the PartialFactors that completely match it.

Constructor & Destructor Documentation

Trie()

AIToolbox::Factored::Trie::Trie

(

Factors

F

)

Basic constructor.

This constructor simply copies the input state space and uses it as bound to construct its internal data structures.

Parameters

F	The factored space.

Member Function Documentation

erase() [1/2]

void AIToolbox::Factored::Trie::erase

(

size_t

id

)

This function removes the input id from the trie.

Note that this function performs a lookup on all vectors whether the id is really present or not (maybe because you erased it before).

Parameters

id	The id to remove.

erase() [2/2]

void AIToolbox::Factored::Trie::erase	(	size_t	id,
		const PartialFactors &	pf
	)

This function removes the input id from the trie.

This function is faster than erase(size_t) as it already knows what to look for.

Note that this function performs a lookup on all vectors whether the id is really present or not (maybe because you erased it before).

Parameters

id	The id to remove.
pf	The key with which the id was inserted.

filter() [1/2]

std::vector<size_t> AIToolbox::Factored::Trie::filter	(	const Factors &	f,
		size_t	offset = 0
	)		const

This function returns all ids where their key matches the input Factors.

This function is the core of this data structure. For each factor of the input Factors, it maintains a list of all ids which could match it at that factor. It then performs an intersection between all these list, starting from the smaller ones to the larger ones in order to perform the minimum number of comparisons possible.

If an id is found matching in all factors, then such a key was inserted and is added to the returned list.

This function can also be used to filter on Factors smaller than the real one, as long as they are all adjacent. The offset parameter can be used to specify by how many factors to offset the input. For example, an input of {3,5} with offset 0 will look for all inserted PartialFactors with 3 at position 0, and 5 at position 1. The same input with offset 2 will look for all inserted PartialFactors with 3 at position 2, and 5 at position 3.

Parameters

f	The Factors used as filter in the trie.
offset	The offset for each factor in the input.

Returns

The ids of all inserted keys which match the input.

filter() [2/2]

std::vector<size_t> AIToolbox::Factored::Trie::filter

(

const PartialFactors &

pf

)

const

This function returns all ids where their key matches the input Factors.

This function is the core of this data structure. For each factor of the input PartialFactors, it maintains a list of all ids which could match it at that factor. It then performs an intersection between all these list, starting from the smaller ones to the larger ones in order to perform the minimum number of comparisons possible.

If an id is found matching in all factors, then such a key was inserted and is added to the returned list.

Parameters

pf	The PartialFactors used as filter in the trie.

Returns

The ids of all inserted keys which match the input.

getF()

Factors AIToolbox::Factored::Trie::getF

(

)

const

This function returns the set state space for the Trie.

Returns

The set state space.

getFactors()

const Factors& AIToolbox::Factored::Trie::getFactors

(

)

const

This function returns a reference to the underlying Factors.

Returns

The Factors domain of this Trie.

insert()

size_t AIToolbox::Factored::Trie::insert

(

const PartialFactors &

pf

)

This function inserts a new id using the input as a key.

If possible, try to insert keys from smallest to highest, where the ordering is done by the sum of all the partial states values, where unspecified states count as one over the max of their possible value.

This is because the underlying container is a vector, and elements are arranged in numerical order, with unspecified elements at the end. Inserting lower numbered elements before guarantees minimal re-copying within the vectors which allows for fast insertion.

Parameters

pf	The PartialFactors used as key for the insertion.

Returns

The id of the newly inserted key.

refine()

std::vector<size_t> AIToolbox::Factored::Trie::refine	(	const std::vector< size_t > &	ids,
		const PartialFactors &	pf
	)		const

This function refines the input ids with the supplied filter.

Parameters

ids	The ids to consider for filtering.
pf	The PartialFactors used as a filter in the trie.

Returns

The ids in the input which match the filter.

reserve()

void AIToolbox::Factored::Trie::reserve

(

size_t

size

)

This function reserves memory for at least size elements.

It is recommended to call this function if there is a need to insert very many elements to it. This will prevent multiple reallocations after each insertion.

Parameters

size	The number of elements to be reserved.

size()

size_t AIToolbox::Factored::Trie::size

(

)

const

This function returns the number of insertions performed on the Trie.

Returns

The number of insertions done on the tree.

---

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

• include/AIToolbox/Factored/Utils/Trie.hpp