Marine systems simulation
Classes | Public Member Functions | Static Public Attributes | Protected Attributes | List of all members
CoRiBoDynamics::DataStructures::RadixSparseSet Class Reference

#include <DataStructures.h>

+ Collaboration diagram for CoRiBoDynamics::DataStructures::RadixSparseSet:

Classes

struct  ARRAY
 

Public Member Functions

void insert (int value)
 
bool insert_and_check (int value)
 
bool check (int value)
 
LINKEDLIST * getValues ()
 
void reset ()
 

Static Public Attributes

static const unsigned int BUFFER_SIZE = 128
 
static const unsigned int BRANCH_FACTOR = 4
 
static const unsigned int TREE_DEPTH = 4
 
static const unsigned int BLOCK_SIZE = 0x1<<BRANCH_FACTOR
 
static const unsigned int BIT_MASK = BLOCK_SIZE-1
 
static const unsigned int MAX_INDEX = 0x1<<(TREE_DEPTH*BRANCH_FACTOR)
 

Protected Attributes

ARRAY m_rootArray
 
ObjectFactoryStack< ARRAY > m_ARRAY_factory
 
ObjectFactoryStack< LINKEDLIST > m_List_factory
 

Detailed Description

set of integers of size 0 to 65536 (2^16) used mainly to avoid duplicate return values from Sparse3DArray this set does not support "remove". use pattern is incremental build, and destroy all

good cache behaviour for lookup/insertion of close integer values little/no dynamic allocation once "warmed up" to correct size

Stores the integers in a tree structure. Each node in the tree has BLOCK_SIZE number of children, and the tree is TREE_DEPTH levels deep. The BRANCH_FACTOR most significant binary digits are used to place the member at the root level The next most significant digits are used at the next level, and so on and so forth. At the leaf nodes, instead of pointing to the next node, the bits of the pointer are set to 1 to indicate that the element is present

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