AIToolbox
A library that offers tools for AI problem solving.
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 FactorsgetFactors () 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
FThe 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
idThe 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
idThe id to remove.
pfThe 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
fThe Factors used as filter in the trie.
offsetThe 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
pfThe 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
pfThe 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
idsThe ids to consider for filtering.
pfThe 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
sizeThe 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: