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 size_t size() const

Standard library compatibility.

inline void resize(size_t new_size)

Standard library compatibility.

inline void push_back(double new_value)

Standard library compatibility.

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?