25 #ifdef ROBIN_HOOD_H_INCLUDED 26 #define lazylookup_umap robin_hood::unordered_map 28 #include <unordered_map> 29 #define lazylookup_umap std::unordered_map 47 template<
class M,
typename K,
typename V>
53 std::function<V(K)> Fn;
58 : dummyVal(dummy), Fn(fn), nfilled(0) { ; }
62 auto res = m.insert(std::pair<K,V>(key,dummyVal));
66 res.first->second = Fn(key);
69 return res.first->second;
71 V operator[](K key) {
return at(key); }
73 std::size_t get_n_filled()
const {
return nfilled; }
80 template <
typename K,
typename V>
84 template <
typename K,
typename V>
105 std::vector<bool> filled;
107 std::size_t max_size;
108 std::function<T(std::size_t)> Fn;
110 vec(std::function<T(std::size_t)> fn) : nfilled(0), max_size(0), Fn(fn) {; }
111 vec(std::function<T(std::size_t)> fn, std::size_t N, std::size_t grow_limit = 0) :
112 v(N),filled(N), nfilled(0), max_size(grow_limit), Fn(fn) { ; }
114 void resize(std::size_t N)
121 void set_grow_limit(std::size_t grow_limit) { max_size = grow_limit; }
125 bool must_resize = i >=v.size();
129 if (max_size && i+1 > max_size)
138 if (must_resize || !filled[i])
148 T operator[](std::size_t i) {
return at(i); }
150 std::size_t get_n_filled() {
return nfilled; }
156 template<std::
size_t N,
typename T>
161 std::bitset<N> filled;
163 std::function<T(std::size_t)> Fn;
166 arr(std::function<T(std::size_t)> fn)
167 : nfilled(0), Fn(fn) {;}
184 T operator[](std::size_t i) {
return at(i); }
185 std::size_t get_n_filled() {
return nfilled; }
190 namespace grid_interpolator_storage
209 template <std::
size_t Ndims,
typename Storage =gr
id_
interpolator_storage::dense>
213 std::array<std::size_t,Ndims > Ns;
214 std::array<double,Ndims > mins;
215 std::array<double,Ndims > maxes;
217 std::array<double,Ndims > deltas;
218 std::array<std::size_t,Ndims> prods;
223 std::function<double(const std::array<double, Ndims>&)> Fn;
226 std::size_t global_bin(
const std::array<std::size_t, Ndims> & bins)
229 for (std::size_t i = 0; i < Ndims; i++)
231 bin += prods[i] * bins[i];
235 double bin_val(
const std::array<std::size_t, Ndims> & bins)
237 size_t gbin = global_bin(bins);
238 if (!storage.have(gbin))
240 std::array<double, Ndims> X;
241 for (std::size_t i = 0; i < Ndims; i++)
243 X[i] = mins[i] + bins[i]*deltas[i];
245 storage.fill(gbin, Fn(X));
247 return storage.val(gbin);
251 bool get_bins(
const std::array<double, Ndims> & vals,
252 std::array<std::size_t,Ndims> & low_bins,
253 std::array<std::size_t,Ndims> & high_bins,
254 std::array<double,Ndims> & fracs)
256 for (std::size_t i = 0; i < Ndims; i++)
258 if (vals[i] > maxes[i])
return false;
259 if (vals[i] < mins[i])
return false;
261 double fbin = (vals[i] - mins[i]) / deltas[i];
264 high_bins[i] = ibin+1;
265 fracs[i] = fbin-ibin;
267 if (fracs[i] >= 0 && fracs[i] < eps)
272 else if (fracs[i] < 0 && fracs[i] > -eps)
274 low_bins[i]=high_bins[i];
293 const std::array<std::size_t, Ndims> & dim_Ns,
294 const std::array<double, Ndims> & dim_mins,
295 const std::array<double, Ndims> & dim_maxes,
296 double bin_eps = 1e-4)
297 : Ns(dim_Ns), mins(dim_mins), maxes(dim_maxes) , Nbins(1), eps(bin_eps), Fn(f)
300 for (std::size_t i = 0; i < Ndims; i++)
304 deltas[i] = (maxes[i]-mins[i])/(Ns[i]);
307 storage.make_room(Nbins);
310 double val(
const std::array<double, Ndims> & X )
313 std::array<std::size_t, Ndims > low_bins;
314 std::array<std::size_t, Ndims > high_bins;
315 std::array<double,Ndims> fracs;
318 if (!get_bins(X, low_bins, high_bins, fracs))
328 return !fracs[0] ? bin_val(low_bins) :
329 fracs[0] ==1 ? bin_val(high_bins) :
330 fracs[0] * bin_val(high_bins) + (1-fracs[0]) * bin_val(low_bins);
338 double f00 = (1-fracs[0]) * (1-fracs[1]);
339 double f11 = fracs[0] * fracs[1];
340 double f01 = (1-fracs[0]) * fracs[1];
341 double f10 = (1-fracs[1]) * fracs[0];
343 if (f00) sum+= f00 * bin_val(low_bins);
344 if (f11) sum+= f11 * bin_val(high_bins);
345 if (f10) sum += f10 * bin_val({high_bins[0], low_bins[1]});
346 if (f01) sum += f01 * bin_val({low_bins[0], high_bins[1]});
352 std::array<std::size_t,Ndims> bins;
358 for (std::size_t V = 0; V < (1 << Ndims); V++)
361 for (std::size_t i = 0; i < Ndims; i++)
363 bool high = V & (1 << i);
364 prod *= high ? fracs[i]: 1-fracs[i];
366 bins[i] = high ? high_bins[i] : low_bins[i];
370 sum += prod*bin_val(bins);
376 double operator[](std::array<double,Ndims> where ) {
return val(where); }
380 namespace grid_interpolator_storage
385 template <std::
size_t Ndims,
typename S>
389 void make_room(std::size_t N)
396 bool have(std::size_t bin)
401 void fill(std::size_t bin,
double val)
407 double val(std::size_t bin)
414 std::vector<double> vals;
415 std::vector<bool> filled;
422 template <std::
size_t Ndims,
typename S>
426 void make_room(std::size_t N)
431 bool have(std::size_t bin)
434 cached_insert = m.insert(std::pair<std::size_t,double> (bin,0));
435 return !cached_insert.second;
439 double val(std::size_t bin)
442 return cached_insert.first->second;
445 void fill(std::size_t bin,
double val)
448 cached_insert.first->second = val;
452 lazylookup_umap<std::size_t, double> m;
453 std::pair<lazylookup_umap<std::size_t,double>::iterator,
bool> cached_insert;
grid_interpolator(std::function< double(const std::array< double, Ndims > &)> f, const std::array< std::size_t, Ndims > &dim_Ns, const std::array< double, Ndims > &dim_mins, const std::array< double, Ndims > &dim_maxes, double bin_eps=1e-4)