OpenFPM_pdata  1.1.0
Project that contain the implementation of distributed structures
 All Data Structures Namespaces Functions Variables Typedefs Enumerations Friends Pages
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  {
21  /* coverity[dead_error_line] */
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  {
401  /* coverity[dead_error_line] */
402  val = pos_n_zero[i] - pos_n_zero[i+1] - 1;
403  }
404  else
405  val = pos_n_zero[i];
406 
407  for (long int j = 0 ; j < (long int)val; j++)
408  {
409  // C is not safe, check the limit
410  /* coverity[dead_error_line] */
411  if (((long int)dim)-cum_val-j-1 >= 0 && i > 0 && ((long int)dim)-cum_val-j >= i)
412  lin_id += openfpm::math::C(dim-cum_val-j-1,i);
413  else
414  lin_id += 1;
415  }
416 
417  cum_val += (val + 1);
418  }
419 
420  // multiply for the permutation
421  lin_id *= pow(2,d);
422 
423  // calculate the permutation position
424  size_t id = 0;
425 
426  for (size_t i = 0 ; i < d ; i++)
427  {
428  if (c.c[pos_n_zero[i]] == -1)
429  {id = id | (1 << i);}
430  }
431 
432  // return the correct id
433 
434  return lin_id + id;
435  }
436 
448  static bool isPositive(size_t d)
449  {
450  return (d % 2) == 0;
451  }
452 
460  static int positiveFace(int d)
461  {
462  return d * 2;
463  }
464 
472  static int negativeFace(int d)
473  {
474  return d * 2 + 1;
475  }
476 };
477 
494 template<unsigned int dim, unsigned int subdim>
495 class SubHyperCube : public HyperCube<subdim>
496 {
497 public:
498 
506  static std::vector<comb<dim>> getCombinations_R(comb<dim> c, int d)
507  {
508 #ifdef DEBUG
509  if (c.n_zero() < d)
510  {
511  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";
512  }
513 #endif
514 
515  // if sub-dim == 0 return c
516 
517  if (subdim == 0)
518  {
519  std::vector<comb<dim>> vc;
520  vc.push_back(c);
521 
522  return vc;
523  }
524 
525  // Create an Iterator_g_const
526  // And a vector that store all the combination
527 
528  std::vector<comb<subdim>> v = HyperCube<subdim>::getCombinations_R(d);
529 
530  // Create new combinations
531  std::vector<comb<dim>> vc(v.size());
532 
533  // for each combination
534  for (size_t i = 0 ; i < v.size() ; i++)
535  {
536  // sub j counter
537  int sub_j = 0;
538  // for each zero (direction spanned by the sub-hyper-cube)
539  for (size_t j = 0 ; j < dim ; j++)
540  {
541  if (c.c[j] == 0)
542  {
543  // take the combination from the sub-hyper-cube
544  vc[i].c[j] = v[i].c[sub_j];
545  sub_j++;
546  }
547  else
548  {
549  // take the combination from the hyper-cube position
550  vc[i].c[j] = c.c[j];
551  }
552  }
553  }
554 
555  // return the combinations
556  return vc;
557  }
558 };
559 
560 #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:833
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:750
static int positiveFace(int d)
return the combination of the positive face on direction d
Definition: HyperCube.hpp:460
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:820
static bool isPositive(size_t d)
isPositive return if the combination d is a positive or a negative
Definition: HyperCube.hpp:448
static size_t LinId(comb< dim > &c)
Linearize the combination.
Definition: HyperCube.hpp:367
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:201
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:1000
bool isNext()
Check if there is the next element.
Definition: grid_sm.hpp:975
static std::vector< comb< dim > > getCombinations_R(comb< dim > c, int d)
Definition: HyperCube.hpp:506
static int negativeFace(int d)
Return the combination of the negative face on direction d.
Definition: HyperCube.hpp:472
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:762
char c[dim]
Array that store the combination.
Definition: comb.hpp:37