BurstTrieSet< T, GROUP_BITS, BUCKET_SIZE, SORT, POOL > Class Template Reference

#include <bursttriemap.h>

Inheritance diagram for BurstTrieSet< T, GROUP_BITS, BUCKET_SIZE, SORT, POOL >:

Detailed Description

template<typename T, Int GROUP_BITS = 4, Int BUCKET_SIZE = 16, BURSTTRIE_SORT SORT = BURSTTRIE_SORT::LINEAR_SEARCH, template< typename, typename > class POOL = PointerBurstTriePool>
class maxon::BurstTrieSet< T, GROUP_BITS, BUCKET_SIZE, SORT, POOL >

A BurstTrieSet is an implementation of a set using an underlying BurstTrieMap. Like BurstTrieMap, it only supports unsigned integral values. See BurstTrieMap for details about the internal structure and performance.

See HashSet for more examples on how to use sets in general.

Template Parameters

T	Type of elements of the set.
GROUP_BITS	Number of bits which shall be grouped to form an index into the children array of an inner node. This shouldn't exceed 4.
BUCKET_SIZE	Maximum size of a bucket of a leaf node. Reasonable values are between 4 and 40.
SORT	Mode for sorting of the buckets.
POOL	Memory pool for the nodes.

See also

BurstTrieMap

$ref sets

Public Types
using	MapType = BurstTrieMap< T, UnitType, GROUP_BITS, BUCKET_SIZE, SORT, POOL >
using	IsBurstTrieMap = std::true_type
using	IsBurstTrieSet = std::true_type
using	Iterator = typename Super::KeyIterator
using	ConstIterator = typename Super::ConstKeyIterator
Public Types inherited from SetBase0< COLLECTION, VALUETYPE, SUPER, HASH >
using	SetType = COLLECTION
Public Types inherited from Collection< COLLECTION, VALUETYPE, SUPER >
using	Super = BaseCollection< COLLECTION, SUPER >
using	ValueType = VALUETYPE
Public Types inherited from BaseCollection< COLLECTION, SUPER >
using	IsCollection = std::true_type
using	IsBaseArray = std::false_type

Public Member Functions
	BurstTrieSet ()
	BurstTrieSet (BurstTrieSet &&src)
	MAXON_OPERATOR_MOVE_ASSIGNMENT (BurstTrieSet)
MapType &	GetMap ()
const MapType &	GetMap () const
Bool	Contains (T value) const
void	Insert () const
ResultMemT< Iterator >	Insert (T value, Bool &added=BoolLValue())
ResultRef< const T >	InsertKey (T value, Bool &added=BoolLValue())
ResultOk< Bool >	Erase (T value)
ConstIterator	Begin () const
ConstIterator	End () const
Iterator	Begin ()
Iterator	End ()
Iterator	Erase (const Iterator &it)
Iterator	Find (K key)
ConstIterator	Find (K key) const
Int	GetCount () const
Int	GetOperationCountForSearch () const
ResultMem	SetCapacityHint (Int, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::ON_GROW_RESERVE_CAPACITY)
void	Reset ()
void	Flush ()
Int	GetMemorySize () const
Public Member Functions inherited from SetBase< BurstTrieSet< T, 4, 16, BURSTTRIE_SORT::LINEAR_SEARCH, PointerBurstTriePool >, T, Protected< BurstTrieMap< T, UnitType, 4, 16, BURSTTRIE_SORT::LINEAR_SEARCH, PointerBurstTriePool > >, DefaultCompare >
MAXON_ATTRIBUTE_FORCE_INLINE	SetBase (ARGS &&... args)
SetImpl< BurstTrieSet< T, 4, 16, BURSTTRIE_SORT::LINEAR_SEARCH, PointerBurstTriePool > & >	ToSet ()
SetImpl< const BurstTrieSet< T, 4, 16, BURSTTRIE_SORT::LINEAR_SEARCH, PointerBurstTriePool > & >	ToSet () const
MAXON_ATTRIBUTE_FORCE_INLINE	operator SetImpl< BurstTrieSet< T, 4, 16, BURSTTRIE_SORT::LINEAR_SEARCH, PointerBurstTriePool > & > ()
MAXON_ATTRIBUTE_FORCE_INLINE	operator SetImpl< const BurstTrieSet< T, 4, 16, BURSTTRIE_SORT::LINEAR_SEARCH, PointerBurstTriePool > & > () const
Public Member Functions inherited from SetBase0< COLLECTION, VALUETYPE, SUPER, HASH >
template<typename... ARGS>
MAXON_ATTRIBUTE_FORCE_INLINE	SetBase0 (ARGS &&... args)
MAXON_ATTRIBUTE_FORCE_INLINE ResultRef< const VALUETYPE >	Append (typename ByValueParam< VALUETYPE >::type v)
template<typename COLLECTION2 >
Bool	ContainsAllImpl (COLLECTION2 &&other, OverloadRank0) const
template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Result< void >	Add (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::ON_GROW_RESERVE_CAPACITY)
template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Result< void >	AppendAll (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::ON_GROW_RESERVE_CAPACITY)
template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Result< void >	CopyFrom (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::FIT_TO_SIZE)
template<typename COLLECTION2 >
Result< void >	SubtractImpl (COLLECTION2 &&other, OverloadRank0)
template<typename COLLECTION2 , typename COMPARE >
Bool	IsEqualImpl (const COLLECTION2 &other, COMPARE &&cmp, OverloadRank0) const
HashInt	GetHashCode () const
UniqueHash	GetUniqueHashCode () const
Public Member Functions inherited from Collection< COLLECTION, VALUETYPE, SUPER >
template<typename... ARGS>
MAXON_ATTRIBUTE_FORCE_INLINE	Collection (ARGS &&... args)
ResultOk< void >	VariadicAppend ()
template<typename V , typename... VALUES>
Result< void >	VariadicAppend (V &&value, VALUES &&... rest)
	operator ValueReceiver< const VALUETYPE & > ()
	operator ValueReceiver< VALUETYPE && > ()
	operator ValueReceiver< typename std::conditional< STD_IS_REPLACEMENT (scalar, VALUETYPE)
DummyParamType &	type ()
template<typename FN >
Result< Bool >	ForEach (FN &&callback) const
template<typename FN >
Result< Bool >	ForEach (FN &&callback)
template<typename H = COLLECTION>
H::Iterator	Find (typename ByValueParam< VALUETYPE >::type v)
template<typename H = COLLECTION>
H::ConstIterator	Find (typename ByValueParam< VALUETYPE >::type v) const
Int	FindIndex (typename ByValueParam< VALUETYPE >::type v) const
MAXON_ATTRIBUTE_FORCE_INLINE Bool	Contains (typename ByValueParam< VALUETYPE >::type v) const
Public Member Functions inherited from BaseCollection< COLLECTION, SUPER >
template<typename... ARGS>
MAXON_ATTRIBUTE_FORCE_INLINE	BaseCollection (ARGS &&... args)
template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE std::enable_if< maxon::IsCollection< COLLECTION2 >::value, Bool >::type	operator== (const COLLECTION2 &other) const
template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE std::enable_if< maxon::IsCollection< COLLECTION2 >::value, Bool >::type	operator!= (const COLLECTION2 &other) const
template<typename COMPARE = EqualityCompare, typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE std::enable_if< maxon::IsCollection< COLLECTION2 >::value &&!STD_IS_REPLACEMENT(same, typename std::decay< COMPARE >::type, EQUALITY), Bool >::type	IsEqual (const COLLECTION2 &other, COMPARE &&cmp=COMPARE()) const
template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Result< void >	AppendAll (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::ON_GROW_RESERVE_CAPACITY)
template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Result< void >	CopyFrom (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::FIT_TO_SIZE)
template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Result< void >	Subtract (COLLECTION2 &&other)
template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Result< void >	Intersect (const COLLECTION2 &other)
template<typename COLLECTION2 >
Bool	Intersects (const COLLECTION2 &other) const
template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Result< void >	CopyFromImpl (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags, OverloadRank0)
template<typename COLLECTION2 >
Result< void >	AppendAllImpl (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags, Bool overwrite, OverloadRank0)
template<typename COLLECTION2 >
Result< void >	IntersectImpl (COLLECTION2 &&other, OverloadRank0)
MAXON_ATTRIBUTE_FORCE_INLINE Bool	IsEmpty () const
MAXON_ATTRIBUTE_FORCE_INLINE Bool	IsPopulated () const
String	ToString (const FormatStatement *formatStatement=nullptr) const
template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Bool	ContainsAll (COLLECTION2 &&other) const
template<typename COLLECTION2 >
Bool	ContainsAllImpl (COLLECTION2 &&other, OverloadRank0) const

Public Attributes
friend	MapType
Public Attributes inherited from Collection< COLLECTION, VALUETYPE, SUPER >
	VALUETYPE

Private Types
using	Super = SetBase< BurstTrieSet< T, GROUP_BITS, BUCKET_SIZE, SORT, POOL >, T, Protected< MapType >, DefaultCompare >

Private Member Functions
	MAXON_DISALLOW_COPY_AND_ASSIGN (BurstTrieSet)

Additional Inherited Members
Static Public Member Functions inherited from Collection< COLLECTION, VALUETYPE, SUPER >
static const VALUETYPE &	GetMapKey (const VALUETYPE &key)
Static Public Attributes inherited from SetBase0< COLLECTION, VALUETYPE, SUPER, HASH >
static const COLLECTION_KIND	KIND

Member Typedef Documentation

MapType

using MapType = BurstTrieMap<T, UnitType, GROUP_BITS, BUCKET_SIZE, SORT, POOL>

Super

using Super = SetBase<BurstTrieSet<T, GROUP_BITS, BUCKET_SIZE, SORT, POOL>, T, Protected<MapType>, DefaultCompare>

private

IsBurstTrieMap

using IsBurstTrieMap = std::true_type

IsBurstTrieSet

using IsBurstTrieSet = std::true_type

Iterator

using Iterator = typename Super::KeyIterator

ConstIterator

using ConstIterator = typename Super::ConstKeyIterator

Constructor & Destructor Documentation

BurstTrieSet() [1/2]

BurstTrieSet

(

)

BurstTrieSet() [2/2]

BurstTrieSet

(

BurstTrieSet< T, GROUP_BITS, BUCKET_SIZE, SORT, POOL > &&

src

)

Member Function Documentation

MAXON_DISALLOW_COPY_AND_ASSIGN()

MAXON_DISALLOW_COPY_AND_ASSIGN ( BurstTrieSet< T, GROUP_BITS, BUCKET_SIZE, SORT, POOL >  )

private

MAXON_OPERATOR_MOVE_ASSIGNMENT()

MAXON_OPERATOR_MOVE_ASSIGNMENT

(

BurstTrieSet< T, GROUP_BITS, BUCKET_SIZE, SORT, POOL >

)

GetMap() [1/2]

MapType& GetMap

(

)

GetMap() [2/2]

const MapType& GetMap

(

)

const

Contains()

Bool Contains

(

T

value

)

const

Checks if this set contains value.

Parameters

[in]

value

The value to check.

Returns

True if this set contains value.

Insert() [1/2]

void Insert

(

)

const

Insert() [2/2]

ResultMemT<Iterator> Insert	(	T	value,
		Bool &	added = BoolLValue()
	)

Adds value to this set. If value is already contained in this set, nothing happens, and added is set to false.

Parameters

[in]	value	Value to add to this set.
[out]	added	This will be set to true if the element didn't exist before in the set and it could be added successfully, otherwise it will be set to false.

Returns

Iterator to the entry for the given key or OutOfMemoryError if the allocation failed.

InsertKey()

ResultRef<const T> InsertKey	(	T	value,
		Bool &	added = BoolLValue()
	)

Adds value to this set. If value is already contained in this set, nothing happens, and added is set to false.

Parameters

[in]	value	Value to add to this set.
[out]	added	This will be set to true if the element didn't exist before in the set and it could be added successfully, otherwise it will be set to false.

Returns

Pointer to the value in the set, or nullptr if the element had to be added, but the allocation failed.

Erase() [1/2]

ResultOk<Bool> Erase

(

T

value

)

Remove value from this set. If value isn't contained in this set, nothing happens.

Parameters

[in]

value

Value to remove from this set.

Returns

Always true for a BurstTrieSet (even if key isn't contained in the set).

True if an entry was found and removed for value, otherwise false.

Begin() [1/2]

ConstIterator Begin

(

)

const

End() [1/2]

ConstIterator End

(

)

const

Begin() [2/2]

Iterator Begin

(

)

End() [2/2]

Iterator End

(

)

Erase() [2/2]

Iterator Erase

(

const Iterator &

it

)

Find() [1/2]

Iterator Find

Finds the entry for the given key in this map.

Parameters

[in]

key

Key to search for.

Returns

Iterator pointing to the entry with the given key, or an invalid iterator if this doesn't exist.

Find() [2/2]

ConstIterator Find

Finds the entry for the given key in this map.

Parameters

[in]

key

Key to search for.

Returns

Iterator pointing to the entry with the given key, or an invalid iterator if this doesn't exist.

GetCount()

Int GetCount

Returns the number of entries in this map.

Returns

Number of entries.

GetOperationCountForSearch()

Int GetOperationCountForSearch

Returns an estimate of the number of operations needed to locate a given key in this map. This is used when two collections are compared: The iteration goes over the collection which would require more operations for search, and each entry is searched in the other collection.

Returns

Estimate for the number of operations.

SetCapacityHint()

ResultMem SetCapacityHint

Does nothing for a BurstTrieMap.

Returns

Always true.

Reset()

void Reset

Resets the map. This destructs all entries and frees any memory held by the map, so the map will be in a state as if it had been newly constructed.

Flush()

void Flush

Flushes the map. For a BurstTrieMap, this does the same as Reset(), namely it destructs all entries and frees any memory held by the map.

GetMemorySize()

Int GetMemorySize

Returns the memory usage of this map.

Returns

Memory size in bytes.

Member Data Documentation

MapType

friend MapType