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

Standard library compatibility.

inline void resize(size_t new_size)

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 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?