Empirical
IndexMap.h
Go to the documentation of this file.
1 
14 #ifndef EMP_INDEX_MAP_H
15 #define EMP_INDEX_MAP_H
16 
17 #include "../base/vector.h"
18 
19 namespace emp {
20 
23  class IndexMap {
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 zero_offset;
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  size_t CalcZeroOffset() const {
45  size_t id = 0;
46  while (id < num_items - 1) id = LeftID(id);
47  return id - (num_items - 1);
48  }
49 
50  size_t ToInternalID(size_t id) const {
51  return (id + zero_offset) % num_items + num_items-1;
52  }
53 
54  size_t ToInternalID(size_t id, size_t _items, size_t _offset) const {
55  return (id + _offset) % _items + _items-1;
56  }
57 
58  size_t ToExternalID(size_t id) const {
59  return (id + 1 - zero_offset) % num_items;
60  }
61 
63  class Proxy {
64  private:
65  IndexMap & index_map;
66  size_t id;
67  public:
68  Proxy(IndexMap & _im, size_t _id) : index_map(_im), id(_id) { ; }
69  operator double() const { return index_map.RawWeight(id); }
70  Proxy & operator=(double new_weight) { index_map.RawAdjust(id, new_weight); return *this; }
71  };
72 
74  void ResolveRefresh() const {
75  if (!needs_refresh) return;
76 
77  // Internal nodes sum their two sub-trees.
78  const size_t pivot = num_items - 1; // Transition between internal and leaf nodes.
79  for (size_t i = pivot-1; i < pivot; i--) {
80  weights[i] = weights[LeftID(i)] + weights[RightID(i)];
81  }
82 
83  needs_refresh = false;
84  }
85 
86  public:
89  IndexMap(size_t _items=0)
90  : num_items(_items), zero_offset(CalcZeroOffset()), needs_refresh(false), weights(0)
91  {
92  if (_items > 0) weights.resize(_items*2-1, 0.0);
93  }
94  IndexMap(size_t _items, double init_weight)
95  : num_items(_items), zero_offset(CalcZeroOffset()), needs_refresh(true)
96  , weights(num_items, init_weight) { ; }
97  IndexMap(const IndexMap &) = default;
98  IndexMap(IndexMap &&) = default;
99  ~IndexMap() = default;
100  IndexMap & operator=(const IndexMap &) = default;
101  IndexMap & operator=(IndexMap &&) = default;
102 
104  size_t GetSize() const { return num_items; }
105 
107  double GetWeight() const { ResolveRefresh(); return weights[0]; }
108 
110  double RawWeight(size_t id) const { return weights[id]; }
111  double GetWeight(size_t id) const { return RawWeight(ToInternalID(id)); }
112 
114  double RawProb(size_t id) const { ResolveRefresh(); return weights[id] / weights[0]; }
115  double GetProb(size_t id) const { return RawProb(ToInternalID(id)); }
116 
118  void Resize(size_t new_size, double def_value=0.0) {
119  if (new_size == num_items) return; // Already the right size? Stop!
120 
121  const size_t min_size = std::min(num_items, new_size); // Min size determines how much to copy.
122  emp::vector<double> old_weights(2*new_size - 1); // Create NEW vector to swap into place.
123  size_t old_size = num_items;
124  size_t old_offset = zero_offset;
125 
126  num_items = new_size;
127  zero_offset = CalcZeroOffset();
128  needs_refresh = true; // Update the tree weights when needed.
129  std::swap(weights, old_weights);
130 
131  // Copy over all values that still exist.
132  for (size_t i = 0; i < min_size; i++) {
133  weights[ToInternalID(i)] = old_weights[ToInternalID(i, old_size, old_offset)];
134  }
135 
136  // Set to default all new values.
137  for (size_t i = min_size; i < new_size; i++) {
138  weights[ToInternalID(i)] = def_value;
139  }
140  }
141 
142  size_t size() const { return num_items; }
143  void resize(size_t new_size) { Resize(new_size); }
144 
146  void Clear() {
147  for (auto & x : weights) { x = 0.0; } // Set all weights to zero since map is now empty.
148  needs_refresh = false; // Given all weights are zero, no refresh needed.
149  }
150 
152  void ResizeClear(size_t new_size) {
153  if (new_size == 0) weights.resize(0); // If there are no items, zero-out weights array.
154  else weights.resize(2*new_size - 1); // Else size for N values and N-1 internal nodes.
155  num_items = new_size;
156  Clear();
157  }
158 
162  void RawAdjust(size_t id, const double new_weight) {
163  // Update this node.
164  const double weight_diff = new_weight - weights[id]; // Track change size for tree weights.
165  weights[id] = new_weight; // Update THIS item weight
166 
167  if (needs_refresh) return; // If we already need a refresh don't update tree weights!
168 
169  // Update tree to root.
170  while (id > 0) {
171  id = ParentID(id);
172  weights[id] += weight_diff;
173  }
174  }
175 
176  void Adjust(size_t id, const double new_weight) { RawAdjust(ToInternalID(id), new_weight); }
177 
179  void Adjust(const emp::vector<double> & new_weights) {
180  num_items = new_weights.size();
181  if (num_items > 0) {
182  weights.resize(num_items*2 - 1);
183  zero_offset = CalcZeroOffset();
184  for (size_t i = 0; i < num_items; i++) weights[ToInternalID(i)] = new_weights[i];
185  }
186  needs_refresh = true;
187  }
188 
190  void AdjustAll(double new_weight) {
191  for (size_t i = 0; i < num_items; i++) weights[ToInternalID(i)] = new_weight;
192  needs_refresh = true;
193  }
194 
196  size_t Index(double index, size_t cur_id=0) const {
197  ResolveRefresh();
198 
199  // Make sure we don't try to index beyond end of map.
200  emp_assert(index < weights[cur_id], index, cur_id, weights.size(), weights[cur_id]);
201 
202  // If we are on a leaf, we have our answer!
203  if (cur_id >= num_items - 1) return ToExternalID(cur_id);
204 
205  const size_t left_id = LeftID(cur_id);
206  const double left_weight = weights[left_id];
207 
208  if (index < left_weight) return Index(index, left_id);
209  return Index(index-left_weight, left_id+1);
210  }
211 
212  // size_t operator[](double index) { return Index(index,0); }
213 
215  Proxy operator[](size_t id) { return Proxy(*this, ToInternalID(id)); }
216  double operator[](size_t id) const { return weights[ToInternalID(id)]; }
217 
220  emp_assert(size() == in_map.size());
221  for (size_t i = 0; i < in_map.size(); i++) {
222  weights[i+num_items-1] += in_map.weights[i+num_items-1];
223  }
224  needs_refresh = true;
225  return *this;
226  }
227 
230  emp_assert(size() == in_map.size());
231  for (size_t i = 0; i < in_map.size(); i++) {
232  weights[i+num_items-1] -= in_map.weights[i+num_items-1];
233  }
234  needs_refresh = true;
235  return *this;
236  }
237 
241  void DeferRefresh() {
242  needs_refresh = true;
243  }
244 
245  };
246 }
247 
248 #endif
void Adjust(size_t id, const double new_weight)
Definition: IndexMap.h:176
void DeferRefresh()
Definition: IndexMap.h:241
IndexMap & operator=(const IndexMap &)=default
double RawProb(size_t id) const
What is the probability of the specified index being selected?
Definition: IndexMap.h:114
void Resize(size_t new_size, double def_value=0.0)
Change the number of indecies in the map.
Definition: IndexMap.h:118
size_t Index(double index, size_t cur_id=0) const
Determine the ID at the specified index position.
Definition: IndexMap.h:196
size_t GetSize() const
How many indices are in this map?
Definition: IndexMap.h:104
void ResizeClear(size_t new_size)
Change the size of this map AND change all weights to zero.
Definition: IndexMap.h:152
void RawAdjust(size_t id, const double new_weight)
Definition: IndexMap.h:162
size_t size() const
Standard library compatibility.
Definition: IndexMap.h:142
IndexMap(size_t _items, double init_weight)
Definition: IndexMap.h:94
IndexMap & operator-=(IndexMap &in_map)
Substract the weigthes from another index map from this one.
Definition: IndexMap.h:229
size_t size() const
Definition: vector.h:151
double operator[](size_t id) const
Definition: IndexMap.h:216
IndexMap & operator+=(IndexMap &in_map)
Add the weights in another index map to this one.
Definition: IndexMap.h:219
double GetWeight(size_t id) const
Definition: IndexMap.h:111
double GetWeight() const
What is the total weight of all indices in this map?
Definition: IndexMap.h:107
double RawWeight(size_t id) const
What is the current weight of the specified index?
Definition: IndexMap.h:110
void Clear()
Reset all item weights to zero.
Definition: IndexMap.h:146
void Adjust(const emp::vector< double > &new_weights)
Adjust all index weights to the set provided.
Definition: IndexMap.h:179
void resize(size_t new_size)
Definition: vector.h:161
If we are in emscripten, make sure to include the header.
Definition: array.h:37
Proxy operator[](size_t id)
Index into a specified ID.
Definition: IndexMap.h:215
~IndexMap()=default
void AdjustAll(double new_weight)
Adjust all index weights to the set provided.
Definition: IndexMap.h:190
#define emp_assert(...)
Definition: assert.h:199
IndexMap(size_t _items=0)
Definition: IndexMap.h:89
double GetProb(size_t id) const
Definition: IndexMap.h:115
Definition: IndexMap.h:23
void resize(size_t new_size)
Standard library compatibility.
Definition: IndexMap.h:143