UnorderedIndexMap.hpp

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

Todo:

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

Should operator[] index by element count or by weight?

Note

Status: BETA

class UnorderedIndexMap

#include <UnorderedIndexMap.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 UnorderedIndexMap(size_t _items = 0, double init_weight = 0.0): Construct an UnorderedIndexMap where num_items is the maximum number of items that can be placed into the data structure. All item weights default to zero.

inline UnorderedIndexMap(const vector<double> &in_weights): Construct an UnorderedIndexMap with a specified initial set of weights.

UnorderedIndexMap(const UnorderedIndexMap&) = default

UnorderedIndexMap(UnorderedIndexMap&&) = default

~UnorderedIndexMap() = default

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

UnorderedIndexMap &operator=(UnorderedIndexMap&&) = 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 RawWeight(size_t id) const: What is the current weight of the specified index?

inline double GetWeight(size_t id) const

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

inline double GetProb(size_t id) const

inline void Resize(size_t new_size, double def_value = 0.0): Change the number of indices in the 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 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 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 single weight 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 UnorderedIndexMap &operator+=(UnorderedIndexMap &in_map): Add the weights in another index map to this one.

inline UnorderedIndexMap &operator-=(UnorderedIndexMap &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 occurring 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 void ResolveRefresh() const: Check if we need to do a refresh, and if so do it!

Private Members

size_t num_items: Num items stored in this UnorderedIndexMap.

size_t num_nodes: Num internal nodes to organize items (num_items-1)

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(UnorderedIndexMap &_im, size_t _id)

inline operator double() const

inline Proxy &operator=(double new_weight)

Private Members

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

size_t id: Which id does it represent?