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
TType of elements of the set.
GROUP_BITSNumber of bits which shall be grouped to form an index into the children array of an inner node. This shouldn't exceed 4.
BUCKET_SIZEMaximum size of a bucket of a leaf node. Reasonable values are between 4 and 40.
SORTMode for sorting of the buckets.
POOLMemory 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)
 
MapTypeGetMap ()
 
const MapTypeGetMap () const
 
Bool Contains (T value) const
 
void Insert () const
 
ResultMemT< IteratorInsert (T value, Bool &added=BoolLValue())
 
ResultRef< const T > InsertKey (T value, Bool &added=BoolLValue())
 
ResultOk< BoolErase (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 VALUETYPEAppend (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< BoolForEach (FN &&callback) const
 
template<typename FN >
Result< BoolForEach (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 VALUETYPEGetMapKey (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() [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 ( value) const

Checks if this set contains value.

Parameters
[in]valueThe value to check.
Returns
True if this set contains value.

◆ Insert() [1/2]

void Insert ( ) const

◆ Insert() [2/2]

ResultMemT<Iterator> Insert ( 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]valueValue to add to this set.
[out]addedThis 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 ( 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]valueValue to add to this set.
[out]addedThis 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 ( value)

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

Parameters
[in]valueValue 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]keyKey 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]

Finds the entry for the given key in this map.

Parameters
[in]keyKey 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 ( void  )

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

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

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

Returns the memory usage of this map.

Returns
Memory size in bytes.

Member Data Documentation

◆ MapType

friend MapType