Containers¶

SlotMap¶

namespace Tangent¶

template<typename DataType, typename KeyType = TypedSlotMapKey<DataType>> class SlotMap¶

#include <SlotMap.h>

This is a slot map as defined by allan deutsch.

Public Types

typedef DataType data_type¶

typedef KeyType key_type¶

Public Functions

inline SlotMap()¶

inline std::vector<DataType>::iterator at(const KeyType &key)¶: O(1) returns end() if key is invalid.

inline std::vector<DataType>::const_iterator at(const KeyType &key) const¶

inline std::vector<DataType>::iterator begin()¶: O(1) iterator pointing to the beginning of this containers internal data container.

inline std::vector<DataType>::const_iterator begin() const¶

inline void clear()¶: Emptys the slot map while retaining its memory.

inline std::vector<DataType>::iterator end()¶: O(1) iterator pointing to one past the end of this containers internal data container.

inline std::vector<DataType>::const_iterator end() const¶

inline void erase(const KeyType &key)¶: O(1)

inline KeyType getKeyFromDataIndex(size_t dataIndex)¶

O(1) constructs a variable key index and generation from a data index.

Asserts that the data index is valid.

inline KeyType insert(DataType value)¶: O(1)

inline size_t size() const¶: O(1) number of elements currently stored the slot map.

inline KeyType updateSlotGeneration(const KeyType &key)¶

O(1)

Increments the generation of a slot to invalidate all previously returned keys. The key must be a valid key, otherwise an invalid key is returned.

Equivalent to: data = at(key1); erase(key1); key2 = insert(data);

Private Members

std::vector<DataType> data¶

std::vector<size_t> dataToSlotIndex¶

std::vector<size_t> freeSlots¶

std::vector<Slot> slots¶

struct Slot¶

Public Members

size_t dataIndex¶

bool free = true¶

KeyType::generation_type generation = 0¶

struct SlotMapKeyBase¶

#include <SlotMap.h>

Subclassed by Tangent::ErrorTermKey< T >, Tangent::TypedSlotMapKey< T >, Tangent::VariableKey< T >

Public Types

using generation_type = size_t¶

using index_type = size_t¶

Public Functions

inline bool isInvalid()¶

inline void setInvalid()¶

Public Members

generation_type generation = 0¶

index_type index = std::numeric_limits<index_type>::max()¶

template<typename T> struct TypedSlotMapKey : public Tangent::SlotMapKeyBase ¶

#include <SlotMap.h>

Public Types

typedef T variable_type¶: A compile time helper to get the variable type of this key.

Public Functions

inline bool operator==(const TypedSlotMapKey<T> &other) const¶: Compares two keys by their index and generation.

SlotArray¶

namespace Tangent

template<typename DataType, typename KeyType> class SlotArray¶

#include <SlotArray.h>

The slot array is basically a vector which uses keys and 1 layer of indirection to allow for constant time insert, erase, and access.

Additionally, this implementation allows for fast iteration.

Public Types

enum InsertResult¶

Values:

enumerator SUCCESS_NO_OVERWRITE¶

enumerator SUCCESS_OVERWRITE¶

enumerator FAILURE¶

Public Functions

inline SlotArray()¶

inline std::vector<DataType>::iterator at(const KeyType &key)¶: O(1) returns end() if key is invalid.

inline std::vector<DataType>::const_iterator at(const KeyType &key) const¶

inline std::vector<DataType>::iterator begin()¶: O(1) iterator pointing to the beginning of this containers internal data container.

inline std::vector<DataType>::const_iterator begin() const¶

inline void clear()¶: O(n) Removes all data stored in this slot array.

inline std::vector<DataType>::iterator end()¶: O(1) iterator pointing to one past the end of this containers internal data container.

inline std::vector<DataType>::const_iterator end() const¶

inline void erase(const KeyType &key)¶: O(1)

inline KeyType getKeyFromDataIndex(size_t dataIndex) const¶

O(1) constructs a variable key index and generation from a data index.

Asserts that the data index is valid.

inline DataType &insert(KeyType key)¶

O(1) This variant of insert requires that the data type has a default constructor.

If, data already exists at this key the data is returned by reference. If, the key does not exist, data is emplaced and returned.

inline InsertResult insert(KeyType key, DataType value)¶: O(1) The insert result lets the user know if an element was overwritten, or if a failure occured.

inline size_t size() const¶: O(1) number of elements currently stored the slot map.

Private Members

std::vector<DataType> data¶

std::vector<size_t> dataToSlotIndex¶

std::vector<Slot> slots¶

struct Slot¶

Public Members

size_t dataIndex¶

bool free = true¶

KeyType::generation_type generation¶: The current generation of this slot.

Key¶

namespace Tangent

template<typename T> class ErrorTermKey : public Tangent::SlotMapKeyBase ¶

#include <Key.h>

Public Types

typedef T errorterm_type¶

Public Functions

inline bool operator<(const ErrorTermKey<T> &other) const¶

template<typename T> class VariableKey : public Tangent::SlotMapKeyBase ¶

#include <Key.h>

Public Types

typedef T variable_type¶

Public Functions

inline bool operator<(const VariableKey<T> &other) const¶

template<typename Other> inline bool operator==(const VariableKey<Other> &other) const¶: Compares two keys by their index, but not generation.

inline bool operator==(const VariableKey<T> &other) const¶: Compares two keys by their index, but not generation.