OpenFPM_data  0.1.0 Project that contain the implementation and interfaces for basic structure like vectors, grids, graph ... .
HyperCube.hpp
1 #ifndef HYPERCUBE_HPP
2 #define HYPERCUBE_HPP
3
4 #include "Grid/grid_sm.hpp"
5 #include "Grid/comb.hpp"
6 #include "util/mathutil.hpp"
7
8 template<unsigned int dim, unsigned int subdim> class SubHyperCube;
9
16 template<unsigned int dim> std::ostream& operator<<(std::ostream& str, const comb<dim> & c)
17 {
18  // print the combination of ostream
19  for (size_t i = 0 ; i < dim-1 ; i++)
20  str << c.c[i] << ";";
21
22  str << c.c[dim-1];
23
24  return str;
25 }
26
53 template<unsigned int dim>
54 class HyperCube
55 {
56 public:
57
64  static size_t getNumberOfElements_R(size_t d)
65  {
66  // The formula to calculate the number of element of size d is given by
67  //
68  // 2^(dim-d) * C(dim,d) with C(dim,d) = dim!/(d!(dim-d)!)
69
70  return pow(2,dim-d) * openfpm::math::C(dim,d);
71  }
72
80  static size_t getNumberOfElementsTo_R(size_t d_t)
81  {
82  size_t N_ele = 0;
83
84  for (size_t i = 0 ; i <= d_t ; i++)
85  N_ele += getNumberOfElements_R(i);
86
87  return N_ele;
88  }
89
97  static std::vector<comb<dim>> getCombinations_R(size_t d)
98  {
99 #ifdef SE_CLASS1
100  if (d > dim)
101  std::cerr << "Error: " << __FILE__ << ":" << __LINE__ << " " << d << " must be smaller than " << "\n";
102 #endif
103
104  // Create an Iterator_g_const
105  // And a vector that store all the combination
106
107  std::vector<comb<dim>> v;
108  Iterator_g_const it(dim-d,dim);
109
110  // for each non-zero elements
111  // basically the key will store the position of the
112  // non zero elements, while BinPermutations will
113  // fill the array of all the permutations
114  //
115
116  while (it.isNext())
117  {
118  grid_key_dx_r & key = it.get();
119
120  // Calculate the permutation
121
122  BinPermutations(key,v);
123  ++it;
124  }
125
126  // case when d == dim
127
128  if (d == dim)
129  {
130  comb<dim> c;
131  c.zero();
132
133  v.push_back(c);
134  }
135
136  // return the combinations
137
138  return v;
139  }
140
160  static void BinPermutations(grid_key_dx_r & pos, std::vector<comb<dim>> & v)
161  {
162  size_t p_stop = pow(2,pos.getDim());
163  for (size_t p = 0 ; p < p_stop ; p++)
164  {
165  // Create a new permutation
166  struct comb<dim> c;
167
168  // zero the combination
169  c.zero();
170
171  // the bit of p give the permutations 0 mean bottom 1 mean up
172  // Fill the combination based on the bit of p
173
174  for (size_t k = 0 ; k < pos.getDim() ; k++)
175  {
176  // bit of p
177  bool bit = (p >> k) & 0x01;
178
179  // Fill the combination
180  c.c[pos.get(k)] = (bit == 0)? 1 : -1;
181  }
182
183  // save the combination
184
185  v.push_back(c);
186  }
187  }
188
222  static void BinPermutationsSt(std::vector<comb<dim>> & v)
223  {
224  size_t p_stop = pow(2,dim);
225  for (size_t p = 0 ; p < p_stop ; p++)
226  {
227  // Create a new permutation
228  struct comb<dim> c;
229
230  // zero the combination
231  c.zero();
232
233  // the bit of p give the permutations 0 mean bottom 1 mean up
234  // Fill the combination based on the bit of p
235
236  for (size_t k = 0 ; k < dim ; k++)
237  {
238  // bit of p
239  bool bit = (p >> k) & 0x01;
240
241  // Fill the combination
242  c.c[k] = (bit == 0)? 0 : -1;
243  }
244
245  // save the combination
246
247  v.push_back(c);
248  }
249  }
250
264  static size_t LinPerm(comb<dim> & c)
265  {
266  size_t id = 0;
267
268  for (size_t i = 0 ; i < dim ; i++)
269  {
270  if (c.c[i] == -1)
271  {id = id | (1 << i);}
272  }
273
274  return id;
275  }
276
277  /*
278  static SubHyperCube<dim,dim-1> getSubHyperCube(int d)
279  {
280  SubHyperCube<dim,dim-1> sub;
281
282  return sub;
283  }*/
284
294  static size_t LinId(comb<dim> & c)
295  {
296  // calculate the numbers of non-zero
297  size_t d = 0;
298
299  size_t pos_n_zero[dim];
300
301  for (size_t i = 0 ; i < dim ; i++)
302  {
303  if (c.c[i] != 0)
304  {d++;}
305  }
306
307  // Get the position of the non-zero
308  size_t pn_zero = 0;
309  for (size_t i = 0 ; i < dim ; i++)
310  {
311  if (c.c[i] != 0)
312  {
313  pos_n_zero[d-pn_zero-1] = i;
314  pn_zero++;
315  }
316  }
317
318  size_t lin_id = 0;
319
320  // Cumulative value
321  long int val = 0;
322  long int cum_val = 0;
323  for(long int i = d - 1; i >= 0 ; i--)
324  {
325  // check the out-of-bound, outside is assumed to be -1 so (- pos_n_zero[i+1] - 1) = 0
326  if (i+1 < (long int)d)
327  val = pos_n_zero[i] - pos_n_zero[i+1] - 1;
328  else
329  val = pos_n_zero[i];
330
331  for (long int j = 0 ; j < (long int)val; j++)
332  {
333  // C is not safe, check the limit
334  if (((long int)dim)-cum_val-j-1 >= 0 && i > 0 && ((long int)dim)-cum_val-j >= i)
335  lin_id += openfpm::math::C(dim-cum_val-j-1,i);
336  else
337  lin_id += 1;
338  }
339
340  cum_val += (val + 1);
341  }
342
343  // multiply for the permutation
344  lin_id *= pow(2,d);
345
346  // calculate the permutation position
347  size_t id = 0;
348
349  for (size_t i = 0 ; i < d ; i++)
350  {
351  if (c.c[pos_n_zero[i]] == -1)
352  {id = id | (1 << i);}
353  }
354
355  // return the correct id
356
357  return lin_id + id;
358  }
359
369  static bool isPositive(size_t d)
370  {
371  return (d % 2) == 0;
372  }
373
381  static int positiveFace(int d)
382  {
383  return d * 2;
384  }
385
393  static int negativeFace(int d)
394  {
395  return d * 2 + 1;
396  }
397 };
398
415 template<unsigned int dim, unsigned int subdim>
416 class SubHyperCube : public HyperCube<subdim>
417 {
418 public:
419
427  static std::vector<comb<dim>> getCombinations_R(comb<dim> c, int d)
428  {
429 #ifdef DEBUG
430  if (c.n_zero() < d)
431  {
432  std::cerr << "Error SubHyperCube: " << __FILE__ << " " << __LINE__ << " the hyper-cube selected must have dimensionality bigger than the dimensionality of the requested combinations, or the number of zero in c must me bigger than d" << "\n";
433  }
434 #endif
435
436  // if sub-dim == 0 return c
437
438  if (subdim == 0)
439  {
440  std::vector<comb<dim>> vc;
441  vc.push_back(c);
442
443  return vc;
444  }
445
446  // Create an Iterator_g_const
447  // And a vector that store all the combination
448
449  std::vector<comb<subdim>> v = HyperCube<subdim>::getCombinations_R(d);
450
451  // Create new combinations
452  std::vector<comb<dim>> vc(v.size());
453
454  // for each combination
455  for (size_t i = 0 ; i < v.size() ; i++)
456  {
457  // sub j counter
458  int sub_j = 0;
459  // for each zero (direction spanned by the sub-hyper-cube)
460  for (size_t j = 0 ; j < dim ; j++)
461  {
462  if (c.c[j] == 0)
463  {
464  // take the combination from the sub-hyper-cube
465  vc[i].c[j] = v[i].c[sub_j];
466  sub_j++;
467  }
468  else
469  {
470  // take the combination from the hyper-cube position
471  vc[i].c[j] = c.c[j];
472  }
473  }
474  }
475
476  // return the combinations
477  return vc;
478  }
479 };
480
481 #endif
static size_t LinPerm(comb< dim > &c)
Linearize the Permitation given by BinPermutationSt.
Definition: HyperCube.hpp:264
static size_t getNumberOfElements_R(size_t d)
Get the number of Elements of dimension d.
Definition: HyperCube.hpp:64
static std::vector< comb< dim > > getCombinations_R(size_t d)
Definition: HyperCube.hpp:97
Position of the element of dimension d in the hyper-cube of dimension dim.
Definition: comb.hpp:34
static void BinPermutations(grid_key_dx_r &pos, std::vector< comb< dim >> &v)
Binary permutations.
Definition: HyperCube.hpp:160
This represent a sub-hyper-cube of an hyper-cube like a face or an edge of a cube.
Definition: HyperCube.hpp:8
Emulate grid_key_dx with runtime dimensionality.
Definition: grid_sm.hpp:732
static int positiveFace(int d)
return the combination of the positive face on direction d
Definition: HyperCube.hpp:381
static void BinPermutationsSt(std::vector< comb< dim >> &v)
Binary permutations.
Definition: HyperCube.hpp:222
mem_id get(size_t i)
get the i index
Definition: grid_sm.hpp:802
static bool isPositive(size_t d)
isPositive return if the combination d is a positive or a negative
Definition: HyperCube.hpp:369
static size_t LinId(comb< dim > &c)
Linearize the combination.
Definition: HyperCube.hpp:294
void zero()
Set all the elements to zero.
Definition: comb.hpp:83
This class is a trick to indicate the compiler a specific specialization pattern. ...
Definition: memory_c.hpp:202
static size_t getNumberOfElementsTo_R(size_t d_t)
Get the sum of the number of elements from d to d_t (included)
Definition: HyperCube.hpp:80
grid_key_dx_r & get()
Return the actual key.
Definition: grid_sm.hpp:982
bool isNext()
Check if there is the next element.
Definition: grid_sm.hpp:957
static std::vector< comb< dim > > getCombinations_R(comb< dim > c, int d)
Definition: HyperCube.hpp:427
static int negativeFace(int d)
Return the combination of the negative face on direction d.
Definition: HyperCube.hpp:393
This class calculate elements of the hyper-cube.
Definition: HyperCube.hpp:54
size_t getDim()
Get the dimensionality of the key.
Definition: grid_sm.hpp:744
char c[dim]
Array that store the combination.
Definition: comb.hpp:37