OpenFPM_pdata  4.1.0 Project that contain the implementation of distributed structures
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  {
22  str << c.c[i] << ";";
23  }
24
25  str << c.c[dim-1];
26
27  return str;
28 }
29
56 template<unsigned int dim>
57 class HyperCube
58 {
59 public:
60
67  static size_t getNumberOfElements_R(size_t d)
68  {
69  // The formula to calculate the number of element of size d is given by
70  //
71  // 2^(dim-d) * C(dim,d) with C(dim,d) = dim!/(d!(dim-d)!)
72
73  return pow(2,dim-d) * openfpm::math::C(dim,d);
74  }
75
83  static size_t getNumberOfElementsTo_R(size_t d_t)
84  {
85  size_t N_ele = 0;
86
87  for (size_t i = 0 ; i <= d_t ; i++)
88  N_ele += getNumberOfElements_R(i);
89
90  return N_ele;
91  }
92
100  static std::vector<comb<dim>> getCombinations_R(size_t d)
101  {
102 #ifdef SE_CLASS1
103  if (d > dim)
104  std::cerr << "Error: " << __FILE__ << ":" << __LINE__ << " " << d << " must be smaller than " << "\n";
105 #endif
106
107  // Create an Iterator_g_const
108  // And a vector that store all the combination
109
110  std::vector<comb<dim>> v;
111  Iterator_g_const it(dim-d,dim);
112
113  // for each non-zero elements
114  // basically the key will store the position of the
115  // non zero elements, while BinPermutations will
116  // fill the array of all the permutations
117  //
118
119  while (it.isNext())
120  {
121  grid_key_dx_r & key = it.get();
122
123  // Calculate the permutation
124
125  BinPermutations(key,v);
126  ++it;
127  }
128
129  // case when d == dim
130
131  if (d == dim)
132  {
133  comb<dim> c;
134  c.zero();
135
136  v.push_back(c);
137  }
138
139  // return the combinations
140
141  return v;
142  }
143
151  static std::vector<comb<dim>> getCombinations_R_bc(size_t d, const size_t (& bc)[dim])
152  {
153 #ifdef SE_CLASS1
154  if (d > dim)
155  std::cerr << "Error: " << __FILE__ << ":" << __LINE__ << " " << d << " must be smaller than " << "\n";
156 #endif
157
158  size_t dg[dim];
159
160  size_t k = 0;
161  // get the indexes of the free degree of freedom
162  for (size_t i = 0 ; i < dim ; i++)
163  {
164  if (bc[i] == PERIODIC)
165  {
166  dg[k] = i;
167  k++;
168  }
169  }
170
171  // Create an Iterator_g_const
172  // And a vector that store all the combination
173
174  std::vector<comb<dim>> v;
175  Iterator_g_const it(k-(d-(dim - k)),k);
176
177  // for each non-zero elements
178  // basically the key will store the position of the
179  // non zero elements, while BinPermutations will
180  // fill the array of all the permutations
181  //
182
183  while (it.isNext())
184  {
185  grid_key_dx_r key = it.get();
186
187  // Now we adjust the non zero position
188
189  for (size_t i = 0 ; i < key.getDim() ; i++)
190  {key.set_d(i,dg[key.get(i)]);}
191
192  // Calculate the permutation
193
194  BinPermutations(key,v);
195  ++it;
196  }
197
198  // case when d == dim
199
200  if (d == dim)
201  {
202  comb<dim> c;
203  c.zero();
204
205  v.push_back(c);
206  }
207
208  // return the combinations
209
210  return v;
211  }
212
232  static void BinPermutations(grid_key_dx_r & pos, std::vector<comb<dim>> & v)
233  {
234  size_t p_stop = pow(2,pos.getDim());
235  for (size_t p = 0 ; p < p_stop ; p++)
236  {
237  // Create a new permutation
238  struct comb<dim> c;
239
240  // zero the combination
241  c.zero();
242
243  // the bit of p give the permutations 0 mean bottom 1 mean up
244  // Fill the combination based on the bit of p
245
246  for (size_t k = 0 ; k < pos.getDim() ; k++)
247  {
248  // bit of p
249  bool bit = (p >> k) & 0x01;
250
251  // Fill the combination
252  c.c[pos.get(k)] = (bit == 0)? 1 : -1;
253  }
254
255  // save the combination
256
257  v.push_back(c);
258  }
259  }
260
293  static void BinPermutationsSt(std::vector<comb<dim>> & v)
294  {
295  size_t p_stop = pow(2,dim);
296  for (size_t p = 0 ; p < p_stop ; p++)
297  {
298  // Create a new permutation
299  struct comb<dim> c;
300
301  // zero the combination
302  c.zero();
303
304  // the bit of p give the permutations 0 mean bottom 1 mean up
305  // Fill the combination based on the bit of p
306
307  for (size_t k = 0 ; k < dim ; k++)
308  {
309  // bit of p
310  bool bit = (p >> k) & 0x01;
311
312  // Fill the combination
313  c.c[k] = (bit == 0)? 0 : -1;
314  }
315
316  // save the combination
317
318  v.push_back(c);
319  }
320  }
321
337  static size_t LinPerm(comb<dim> & c)
338  {
339  size_t id = 0;
340
341  for (size_t i = 0 ; i < dim ; i++)
342  {
343  if (c.c[i] == -1)
344  {id = id | (1 << i);}
345  }
346
347  return id;
348  }
349
350  /*
351  static SubHyperCube<dim,dim-1> getSubHyperCube(int d)
352  {
353  SubHyperCube<dim,dim-1> sub;
354
355  return sub;
356  }*/
357
367  static size_t LinId(comb<dim> & c)
368  {
369  // calculate the numbers of non-zero
370  size_t d = 0;
371
372  size_t pos_n_zero[dim];
373
374  for (size_t i = 0 ; i < dim ; i++)
375  {
376  if (c.c[i] != 0)
377  {d++;}
378  }
379
380  // Get the position of the non-zero
381  size_t pn_zero = 0;
382  for (size_t i = 0 ; i < dim ; i++)
383  {
384  if (c.c[i] != 0)
385  {
386  pos_n_zero[d-pn_zero-1] = i;
387  pn_zero++;
388  }
389  }
390
391  size_t lin_id = 0;
392
393  // Cumulative value
394  long int val = 0;
395  long int cum_val = 0;
396  for(long int i = d - 1; i >= 0 ; i--)
397  {
398  // check the out-of-bound, outside is assumed to be -1 so (- pos_n_zero[i+1] - 1) = 0
399  if (i+1 < (long int)d)
400  {
402  val = pos_n_zero[i] - pos_n_zero[i+1] - 1;
403  }
404  else
405  {
406  /* coverty[uninit_use] */
407  val = pos_n_zero[i];
408  }
409
410  for (long int j = 0 ; j < (long int)val; j++)
411  {
412  // C is not safe, check the limit
414  if (((long int)dim)-cum_val-j-1 >= 0 && i > 0 && ((long int)dim)-cum_val-j >= i)
415  lin_id += openfpm::math::C(dim-cum_val-j-1,i);
416  else
417  lin_id += 1;
418  }
419
420  cum_val += (val + 1);
421  }
422
423  // multiply for the permutation
424  lin_id *= pow(2,d);
425
426  // calculate the permutation position
427  size_t id = 0;
428
429  for (size_t i = 0 ; i < d ; i++)
430  {
431  if (c.c[pos_n_zero[i]] == -1)
432  {id = id | (1 << i);}
433  }
434
435  // return the correct id
436
437  return lin_id + id;
438  }
439
451  static bool isPositive(size_t d)
452  {
453  return (d % 2) == 0;
454  }
455
463  static int positiveFace(int d)
464  {
465  return d * 2;
466  }
467
475  static int negativeFace(int d)
476  {
477  return d * 2 + 1;
478  }
479 };
480
497 template<unsigned int dim, unsigned int subdim>
498 class SubHyperCube : public HyperCube<subdim>
499 {
500 public:
501
509  static std::vector<comb<dim>> getCombinations_R(comb<dim> c, int d)
510  {
511 #ifdef DEBUG
512  if (c.n_zero() < d)
513  {
514  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";
515  }
516 #endif
517
518  // if sub-dim == 0 return c
519
520  if (subdim == 0)
521  {
522  std::vector<comb<dim>> vc;
523  vc.push_back(c);
524
525  return vc;
526  }
527
528  // Create an Iterator_g_const
529  // And a vector that store all the combination
530
531  std::vector<comb<subdim>> v = HyperCube<subdim>::getCombinations_R(d);
532
533  // Create new combinations
534  std::vector<comb<dim>> vc(v.size());
535
536  // for each combination
537  for (size_t i = 0 ; i < v.size() ; i++)
538  {
539  // sub j counter
540  int sub_j = 0;
541  // for each zero (direction spanned by the sub-hyper-cube)
542  for (size_t j = 0 ; j < dim ; j++)
543  {
544  if (c.c[j] == 0)
545  {
546  // take the combination from the sub-hyper-cube
547  vc[i].c[j] = v[i].c[sub_j];
548  sub_j++;
549  }
550  else
551  {
552  // take the combination from the hyper-cube position
553  vc[i].c[j] = c.c[j];
554  }
555  }
556  }
557
558  // return the combinations
559  return vc;
560  }
561 };
562
563 #endif
static size_t LinPerm(comb< dim > &c)
Linearize the permutation given by BinPermutationSt.
Definition: HyperCube.hpp:337
static size_t getNumberOfElements_R(size_t d)
Get the number of Elements of dimension d.
Definition: HyperCube.hpp:67
static std::vector< comb< dim > > getCombinations_R(size_t d)
Definition: HyperCube.hpp:100
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:232
void set_d(size_t i, mem_id id)
Set the i index.
Definition: grid_sm.hpp:1011
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:928
static int positiveFace(int d)
return the combination of the positive face on direction d
Definition: HyperCube.hpp:463
static void BinPermutationsSt(std::vector< comb< dim >> &v)
Binary permutations.
Definition: HyperCube.hpp:293
static std::vector< comb< dim > > getCombinations_R_bc(size_t d, const size_t(&bc)[dim])
Definition: HyperCube.hpp:151
mem_id get(size_t i)
get the i index
Definition: grid_sm.hpp:998
static bool isPositive(size_t d)
isPositive return if the combination d is a positive or a negative
Definition: HyperCube.hpp:451
static size_t LinId(comb< dim > &c)
Linearize the combination.
Definition: HyperCube.hpp:367
KeyT const ValueT ValueT OffsetIteratorT OffsetIteratorT int
[in] The number of segments that comprise the sorting data
void zero()
Set all the elements to zero.
Definition: comb.hpp:83
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:83
grid_key_dx_r & get()
Return the actual key.
Definition: grid_sm.hpp:1178
bool isNext()
Check if there is the next element.
Definition: grid_sm.hpp:1153
static std::vector< comb< dim > > getCombinations_R(comb< dim > c, int d)
Definition: HyperCube.hpp:509
static int negativeFace(int d)
Return the combination of the negative face on direction d.
Definition: HyperCube.hpp:475
This class calculate elements of the hyper-cube.
Definition: HyperCube.hpp:57
size_t getDim()
Get the dimensionality of the key.
Definition: grid_sm.hpp:940
char c[dim]
Array that store the combination.
Definition: comb.hpp:37