IndexMap.hpp

A simple class to weight items differently within a container and return the correct index.

An IndexMap is a container where each item has a specified weight (specified as a double). The total weight of the container determines the max index point. When indexing into the container, each item is represented by a range of values equal to it’s weight. Randomly indexing into the container will provide either item with a probability proportional to its weight.

In this regular IndexMap, all items are kept in order (so the map starts at 0, then 1, then 2, etc.) If order is not required, UnorderedIndexMap is slightly faster.

Todo:

Convert to a template that acts as a glorified vector, simplifying random selection?

Make Raw*() function private.

Note

Status: BETA

class IndexMap

#include <IndexMap.hpp>

A map of weighted indices. If a random index is selected, the probability of an index being returned is directly proportional to its weight.

Public Functions

inline IndexMap(size_t _items = 0): Construct an IndexMap where num_items is the maximum number of items that can be placed into the data structure. All item weights default to zero.

inline IndexMap(size_t _items, double init_weight)

IndexMap(const IndexMap&) = default

IndexMap(IndexMap&&) = default

~IndexMap() = default

IndexMap &operator=(const IndexMap&) = default

IndexMap &operator=(IndexMap&&) = default

inline size_t GetSize() const: How many indices are in this map?

inline double GetWeight() const: What is the total weight of all indices in this map?

inline double GetWeight(size_t id) const: What is the current weight of the specified index?

inline double GetProb(size_t id) const: What is the probability of the specified index being selected?

inline void Resize(size_t new_size, double def_value = 0.0): Change the number of indices in the map.

inline void PushBack(double new_value): Added a new value to the end of the index map.

inline void Clear(): Reset all item weights to zero.

inline void ResizeClear(size_t new_size): Change the size of this map AND change all weights to zero.

inline void Adjust(size_t id, const double new_weight)

inline void Adjust(const vector<double> &new_weights): Adjust all index weights to the set provided.

inline void AdjustAll(double new_weight): Adjust all index weights to the set provided.

inline size_t Index(double index, size_t cur_id = 0) const: Determine the ID at the specified index position.

inline Proxy operator[](size_t id): Index into a specified ID.

inline double operator[](size_t id) const

inline IndexMap &operator+=(IndexMap &in_map): Add the weights in another index map to this one.

inline IndexMap &operator-=(IndexMap &in_map): Substract the weights from another index map from this one.

inline void DeferRefresh(): Indicate that we need to adjust weights before relying on them in the future; this will prevent refreshes from occuring immediately and is useful when many updates to weights are likely to be done before any are accessed again.

Private Functions

inline size_t ParentID(size_t id) const: Which ID is the parent of the ID provided?

inline size_t LeftID(size_t id) const: Which ID is the left child of the ID provided?

inline size_t RightID(size_t id) const: Which ID is the right child of the ID provided?

inline size_t CalcZeroOffset() const: Sift through the nodes to find where index zero maps to.

inline size_t ToInternalID(size_t id) const: Convert an item ID to the internal position where it’s stored.

inline size_t ToInternalID(size_t id, size_t _items, size_t _offset) const

inline size_t ToExternalID(size_t id) const: Convert and internal position to the item ID to which it refers.

inline double RawWeight(size_t id) const

inline double RawProb(size_t id) const

inline void RawAdjust(size_t id, const double new_weight)

Adjust the weight associated with a particular index in the map.

Parameters:

id – is the identification number of the item whose weight is being adjusted.
new_weight – is the new weight for that entry.

inline void ResolveRefresh() const: Check if we need to do a refresh, and if so do it!

Private Members

size_t num_items: How many items are being stored in this IndexMap?

size_t zero_offset: Position of id zero.

mutable bool needs_refresh: Are tree weights out of date?

mutable vector<double> weights: The total weights in each sub-tree.

class Proxy

A Proxy class so that an index can be treated as an l-value.

Public Functions

inline Proxy(IndexMap &_im, size_t _id)

inline operator double() const

inline Proxy &operator=(double new_weight)

Private Members

IndexMap &index_map: Which index map is this proxy from?

size_t id: Which id does it represent?