Empirical
UnorderedIndexMap.h
Go to the documentation of this file.
1 
14 #ifndef EMP_UNORDERED_INDEX_MAP_H
15 #define EMP_UNORDERED_INDEX_MAP_H
16 
17 #include "../base/vector.h"
18 
19 namespace emp {
20 
24  private:
25  // Internally, item_weight should be thought of as following tree_weight as a vector, both of
26  // which are the length of the number of values stored. Note that portions are mutable so
27  // that we can do a lazy updating of tree_weight when needs_refresh is set.
28 
29  size_t num_items;
30  size_t num_nodes;
31  mutable bool needs_refresh;
32  mutable emp::vector<double> weights;
33 
35  size_t ParentID(size_t id) const { return (id-1) / 2; }
36 
38  size_t LeftID(size_t id) const { return 2*id + 1; }
39 
41  size_t RightID(size_t id) const { return 2*id + 2; }
42 
44  class Proxy {
45  private:
46  UnorderedIndexMap & index_map;
47  size_t id;
48  public:
49  Proxy(UnorderedIndexMap & _im, size_t _id) : index_map(_im), id(_id) { ; }
50  operator double() const { return index_map.RawWeight(id); }
51  Proxy & operator=(double new_weight) { index_map.RawAdjust(id, new_weight); return *this; }
52  };
53 
55  void ResolveRefresh() const {
56  if (!needs_refresh) return;
57 
58  // Internal nodes sum their two sub-trees.
59  const size_t pivot = num_items - 1; // Transition between internal and leaf nodes.
60  for (size_t i = pivot-1; i < pivot; i--) {
61  weights[i] = weights[LeftID(i)] + weights[RightID(i)];
62  }
63 
64  needs_refresh = false;
65  }
66 
67  public:
70  UnorderedIndexMap(size_t _items=0, double init_weight=0.0)
71  : num_items(_items), num_nodes(_items-1), needs_refresh(_items && init_weight), weights(0)
72  { if (_items > 0) weights.resize(_items*2-1, init_weight); }
73  UnorderedIndexMap(const UnorderedIndexMap &) = default;
75  ~UnorderedIndexMap() = default;
76  UnorderedIndexMap & operator=(const UnorderedIndexMap &) = default;
78 
80  size_t GetSize() const { return num_items; }
81 
83  double GetWeight() const { ResolveRefresh(); return weights[0]; }
84 
86  double RawWeight(size_t id) const { return weights[id]; }
87  double GetWeight(size_t id) const { return RawWeight(id + num_nodes); }
88 
90  double RawProb(size_t id) const { ResolveRefresh(); return weights[id] / weights[0]; }
91  double GetProb(size_t id) const { return RawProb(id + num_nodes); }
92 
94  void Resize(size_t new_size, double def_value=0.0) {
95  const size_t min_size = std::min(num_items, new_size);
96  emp::vector<double> new_weights(2*new_size - 1);
97 
98  // Copy over all values that still exist.
99  for (size_t i = 0; i < min_size; i++) {
100  new_weights[new_size - 1 + i] = weights[num_nodes + i];
101  }
102 
103  // Set to default all new values.
104  for (size_t i = min_size; i < new_size; i++) {
105  new_weights[new_size - 1 + i] = def_value;
106  }
107 
108  // Finalize info for new UnorderedIndexMap size.
109  needs_refresh = true; // Update the tree weights when needed.
110  num_items = new_size;
111  num_nodes = num_items - 1;
112  std::swap(weights, new_weights);
113  }
114 
115  size_t size() const { return num_items; }
116  void resize(size_t new_size) { Resize(new_size); }
117 
119  void Clear() {
120  for (auto & x : weights) { x = 0.0; } // Set all weights to zero since map is now empty.
121  needs_refresh = false; // Given all weights are zero, no refresh needed.
122  }
123 
125  void ResizeClear(size_t new_size) {
126  if (new_size == 0) weights.resize(0); // If there are no items, zero-out weights array.
127  else weights.resize(2*new_size - 1); // Else size for N values and N-1 internal nodes.
128  num_items = new_size;
129  num_nodes = num_items - 1;
130  Clear();
131  }
132 
136  void RawAdjust(size_t id, const double new_weight) {
137  // Update this node.
138  const double weight_diff = new_weight - weights[id]; // Track change size for tree weights.
139  weights[id] = new_weight; // Update THIS item weight
140 
141  if (needs_refresh) return; // If we already need a refresh don't update tree weights!
142 
143  // Update tree to root.
144  while (id > 0) {
145  id = ParentID(id);
146  weights[id] += weight_diff;
147  }
148  }
149 
150  void Adjust(size_t id, const double new_weight) { RawAdjust(id + num_nodes, new_weight); }
151 
153  void Adjust(const emp::vector<double> & new_weights) {
154  num_items = new_weights.size();
155  num_nodes = num_items - 1;
156  if (num_items > 0) {
157  weights.resize(num_items*2 - 1);
158  for (size_t i = 0; i < num_items; i++) weights[i + num_nodes] = new_weights[i];
159  }
160  needs_refresh = true;
161  }
162 
164  void AdjustAll(double new_weight) {
165  for (size_t i = 0; i < num_items; i++) weights[i + num_nodes] = new_weight;
166  needs_refresh = true;
167  }
168 
170  size_t Index(double index, size_t cur_id=0) const {
171  ResolveRefresh();
172 
173  // Make sure we don't try to index beyond end of map.
174  emp_assert(index < weights[cur_id], index, cur_id, weights.size(), weights[cur_id]);
175 
176  // If we are on a leaf, we have our answer!
177  if (cur_id >= num_nodes) return cur_id - num_nodes;
178 
179  const size_t left_id = LeftID(cur_id);
180  const double left_weight = weights[left_id];
181 
182  if (index < left_weight) return Index(index, left_id);
183  return Index(index-left_weight, left_id+1);
184  }
185 
186  // size_t operator[](double index) { return Index(index,0); }
187 
189  Proxy operator[](size_t id) { return Proxy(*this, id + num_nodes); }
190  double operator[](size_t id) const { return weights[id + num_nodes]; }
191 
194  emp_assert(size() == in_map.size());
195  for (size_t i = 0; i < in_map.size(); i++) {
196  weights[i+num_nodes] += in_map.weights[i+num_nodes];
197  }
198  needs_refresh = true;
199  return *this;
200  }
201 
204  emp_assert(size() == in_map.size());
205  for (size_t i = 0; i < in_map.size(); i++) {
206  weights[i+num_nodes] -= in_map.weights[i+num_nodes];
207  }
208  needs_refresh = true;
209  return *this;
210  }
211 
215  void DeferRefresh() {
216  needs_refresh = true;
217  }
218 
219  };
220 }
221 
222 #endif
void AdjustAll(double new_weight)
Adjust all index weights to the set provided.
Definition: UnorderedIndexMap.h:164
void ResizeClear(size_t new_size)
Change the size of this map AND change all weights to zero.
Definition: UnorderedIndexMap.h:125
void Adjust(size_t id, const double new_weight)
Definition: UnorderedIndexMap.h:150
void Adjust(const emp::vector< double > &new_weights)
Adjust all index weights to the set provided.
Definition: UnorderedIndexMap.h:153
void Clear()
Reset all item weights to zero.
Definition: UnorderedIndexMap.h:119
size_t size() const
Standard library compatibility.
Definition: UnorderedIndexMap.h:115
size_t size() const
Definition: vector.h:151
double GetProb(size_t id) const
Definition: UnorderedIndexMap.h:91
double GetWeight() const
What is the total weight of all indices in this map?
Definition: UnorderedIndexMap.h:83
size_t GetSize() const
How many indices are in this map?
Definition: UnorderedIndexMap.h:80
void resize(size_t new_size)
Definition: vector.h:161
void resize(size_t new_size)
Standard library compatibility.
Definition: UnorderedIndexMap.h:116
void DeferRefresh()
Definition: UnorderedIndexMap.h:215
UnorderedIndexMap & operator+=(UnorderedIndexMap &in_map)
Add the weights in another index map to this one.
Definition: UnorderedIndexMap.h:193
If we are in emscripten, make sure to include the header.
Definition: array.h:37
#define emp_assert(...)
Definition: assert.h:199
Proxy operator[](size_t id)
Index into a specified ID.
Definition: UnorderedIndexMap.h:189
double RawProb(size_t id) const
What is the probability of the specified index being selected?
Definition: UnorderedIndexMap.h:90
~UnorderedIndexMap()=default
UnorderedIndexMap & operator-=(UnorderedIndexMap &in_map)
Substract the weigthes from another index map from this one.
Definition: UnorderedIndexMap.h:203
Definition: UnorderedIndexMap.h:23
size_t Index(double index, size_t cur_id=0) const
Determine the ID at the specified index position.
Definition: UnorderedIndexMap.h:170
UnorderedIndexMap(size_t _items=0, double init_weight=0.0)
Definition: UnorderedIndexMap.h:70
double operator[](size_t id) const
Definition: UnorderedIndexMap.h:190
double RawWeight(size_t id) const
What is the current weight of the specified index?
Definition: UnorderedIndexMap.h:86
void RawAdjust(size_t id, const double new_weight)
Definition: UnorderedIndexMap.h:136
double GetWeight(size_t id) const
Definition: UnorderedIndexMap.h:87
void Resize(size_t new_size, double def_value=0.0)
Change the number of indecies in the map.
Definition: UnorderedIndexMap.h:94
UnorderedIndexMap & operator=(const UnorderedIndexMap &)=default