AIToolbox::Factored::FasterTrie Class Reference

This class is a generally faster implementation of a Trie. More...

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

Public Types
using	Entry = std::pair< size_t, PartialFactors >
using	Entries = std::vector< Entry >

Public Member Functions
	FasterTrie (Factors f)
	Basic constructor. More...
size_t	insert (PartialFactors pf)
	This function inserts a new id using the input as a key. More...
void	erase (size_t id, const PartialFactors &pf)
	This function erases the id with the input key. More...
std::vector< size_t >	filter (const Factors &f) const
	This function returns all ids of the keys that match the input Factors. More...
std::tuple< Entries, Factors >	reconstruct (const PartialFactors &pf, bool remove=false)
	This function returns a set of Entries which match the input and each other. More...
size_t	size () const
	This function returns the number of keys in the FasterTrie. More...
const Factors &	getF () const
	This function returns a reference of the internal Factors space. More...

Detailed Description

This class is a generally faster implementation of a Trie.

This class stores keys in a different way from Trie, which allows it to be much faster when retrieving. On the other hand, it is slightly less flexible in what it can do.

Member Typedef Documentation

Entries

using AIToolbox::Factored::FasterTrie::Entries = std::vector<Entry>

Entry

using AIToolbox::Factored::FasterTrie::Entry = std::pair<size_t, PartialFactors>

Constructor & Destructor Documentation

FasterTrie()

AIToolbox::Factored::FasterTrie::FasterTrie

(

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()

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

This function erases the id with the input key.

This operation takes an amount of time proportional to the number of keys with the same first element (key,value) of the input PartialFactors.

Parameters

id	The id to remove.
pf	The PartialFactors used as key for the insertion.

filter()

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

(

const Factors &

f

)

const

This function returns all ids of the keys that match the input Factors.

The output is not sorted.

The input can have fewer elements than the space; the output will be matched on those elements. Differently from Trie, it's not possible to provide an offset.

Parameters

f	The Factors to match against.

Returns

The unsorted ids of all keys which match the input.

getF()

const Factors& AIToolbox::Factored::FasterTrie::getF

(

)

const

This function returns a reference of the internal Factors space.

insert()

size_t AIToolbox::Factored::FasterTrie::insert

(

PartialFactors

pf

)

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

Differently from Trie, we don't store the keys in an ordered way, so this operation takes constant time (bar reallocations).

Parameters

pf	The PartialFactors used as key for the insertion.

Returns

The id of the newly inserted key.

reconstruct()

std::tuple<Entries, Factors> AIToolbox::Factored::FasterTrie::reconstruct	(	const PartialFactors &	pf,
		bool	remove = false
	)

This function returns a set of Entries which match the input and each other.

The output set is constructed randomly to avoid bias. The output of this function is thus randomized and not deterministic.

We additionally return the Factors constructed by merging all matches together. Any elements who couldn't be filled will be set as the value of their space.

Parameters

pf	The PartialFactors to match against.
remove	Whether the matches should be removed from the FasterTrie.

Returns

A set of Entry that match the input and each other, the Factors obtained by combining the input with the returned set.

size()

size_t AIToolbox::Factored::FasterTrie::size

(

)

const

This function returns the number of keys in the FasterTrie.

Returns

The size of the FasterTrie.

---

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

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