1/*
2 * SparseGrid_iterator.hpp
3 *
4 * Created on: Oct 24, 2017
5 * Author: i-bird
6 */
7
8#ifndef OPENFPM_DATA_SRC_SPARSEGRID_SPARSEGRID_ITERATOR_HPP_
9#define OPENFPM_DATA_SRC_SPARSEGRID_SPARSEGRID_ITERATOR_HPP_
10
11/*! \brief It store the position in space of the sparse grid
12 *
13 * linearized index
14 *
15 */
16class grid_key_sparse_lin_dx
17{
18 //! chunk id
19 size_t chunk;
20
21 //! linearized id
22 size_t lin_id;
23
24public:
25
26 inline grid_key_sparse_lin_dx(size_t chunk, size_t lin_id)
27 :chunk(chunk),lin_id(lin_id)
28 {
29
30 }
31
32 /*! \brief Return the chunk id
33 *
34 * \return the chunk id
35 *
36 */
37 inline size_t getChunk() const
38 {
39 return chunk;
40 }
41
42 /*! \brief Return the linearized position in the chunk
43 *
44 * \return the linearized position in the chunk
45 *
46 */
47 inline size_t getPos() const
48 {
49 return lin_id;
50 }
51};
52
53
54/*! \brief This function fill the set of all non zero elements
55 *
56 *
57 */
58template<unsigned int n_ele>
59inline void fill_mask(short unsigned int (& mask_it)[n_ele],
60 const unsigned char (& mask)[n_ele],
61 int & mask_nele)
62{
63 mask_nele = 0;
64
65 for (size_t i = 0 ; i < n_ele ; i++)
66 {
67 if (mask[i] & 1)
68 {
69 mask_it[mask_nele] = i;
70 mask_nele++;
71 }
72 }
73}
74
75/*! \brief This function fill the set of all non zero elements
76 *
77 *
78 */
79template<unsigned int dim, unsigned int n_ele>
80inline void fill_mask_box(short unsigned int (& mask_it)[n_ele],
81 const unsigned char (& mask)[n_ele],
82 size_t & mask_nele,
83 Box<dim,size_t> & bx,
84 const grid_key_dx<dim> (& loc_grid)[n_ele])
85{
86 mask_nele = 0;
87
88 for (size_t i = 0 ; i < n_ele ; i++)
89 {
90 size_t id = i;
91
92 bool is_inside = true;
93 // we check the point is inside inte
94 for (size_t j = 0 ; j < dim ; j++)
95 {
96 if (loc_grid[id].get(j) < (long int)bx.getLow(j) ||
97 loc_grid[id].get(j) > (long int)bx.getHigh(j))
98 {
99 is_inside = false;
100
101 break;
102 }
103 }
104
105 if (is_inside == true && (mask[i] & 1))
106 {
107 mask_it[mask_nele] = id;
108 mask_nele++;
109 }
110 }
111}
112
113/*! \brief This structure contain the information of a chunk
114 *
115 * \tparam dim dimensionality of the chunk
116 * \tparam n_ele number of elements in the chunk
117 *
118 */
119template<unsigned int n_ele>
120struct mheader
121{
122 //! which elements in the chunks are set
123 unsigned char mask[n_ele];
124};
125
126
127/*! \brief This structure contain the information of a chunk
128 *
129 * \tparam dim dimensionality of the chunk
130 * \tparam n_ele number of elements in the chunk
131 *
132 */
133template<unsigned int dim>
134struct cheader
135{
136 //! where is located the chunk
137 grid_key_dx<dim> pos;
138
139 //! how many elements in the chunk are set
140 int nele;
141};
142
143/*! \brief Grid key sparse iterator on a sub-part of the domain
144 *
145 *
146 */
147template<unsigned dim, unsigned int n_ele>
148class grid_key_sparse_dx_iterator_sub
149{
150 const static int cnk_pos = 0;
151 const static int cnk_nele = 1;
152 const static int cnk_mask = 2;
153
154 //! It store the information of each chunk mask
155 const openfpm::vector<mheader<n_ele>> * header_mask;
156
157 //! it store the information of each chunk
158 const openfpm::vector<cheader<dim>> * header_inf;
159
160 //! linearized id to position in coordinates conversion
161 const grid_key_dx<dim> (* lin_id_pos)[n_ele];
162
163 //! point to the actual chunk
164 size_t chunk_id;
165
166 //! Number of points in mask_it
167 size_t mask_nele;
168
169 //! Actual point in mask it
170 size_t mask_it_pnt;
171
172 //! Starting point
173 grid_key_dx<dim> start;
174
175 //! Stop point
176 grid_key_dx<dim> stop;
177
178 //! Sub-grid box
179 Box<dim,size_t> bx;
180
181 //! Chunk size
182 size_t sz_cnk[dim];
183
184 //! set of index in the chunk on which we have to iterate
185 short unsigned int mask_it[n_ele];
186
187 /*! \brief Everytime we move to a new chunk we calculate on which indexes we have to iterate
188 *
189 *
190 */
191 void SelectValidAndFill_mask_it()
192 {
193 mask_it_pnt = 0;
194 mask_nele = 0;
195
196 while (mask_nele == 0 && chunk_id < header_inf->size())
197 {
198 auto & mask = header_mask->get(chunk_id).mask;
199
200 Box<dim,size_t> cnk_box;
201
202 for (size_t i = 0 ; i < dim ; i++)
203 {
204 cnk_box.setLow(i,header_inf->get(chunk_id).pos.get(i));
205 cnk_box.setHigh(i,header_inf->get(chunk_id).pos.get(i) + sz_cnk[i] - 1);
206 }
207
208 Box<dim,size_t> inte;
209
210 if (bx.Intersect(cnk_box,inte) == true)
211 {
212 inte -= header_inf->get(chunk_id).pos.toPoint();
213 fill_mask_box<dim,n_ele>(mask_it,mask,mask_nele,inte,*lin_id_pos);
214 }
215 else
216 {mask_nele = 0;}
217
218 chunk_id = (mask_nele == 0)?chunk_id + 1:chunk_id;
219
220 }
221 }
222
223public:
224
225 /*! \brief Default constructor
226 *
227 * \warning extremely unsafe
228 * If you use this constructor before use the iterator you should call reinitialize first
229 *
230 */
231 grid_key_sparse_dx_iterator_sub() {};
232
233 grid_key_sparse_dx_iterator_sub(const openfpm::vector<mheader<n_ele>> & header_mask,
234 const openfpm::vector<cheader<dim>> & header_inf,
235 const grid_key_dx<dim> (& lin_id_pos)[n_ele],
236 const grid_key_dx<dim> & start,
237 const grid_key_dx<dim> & stop,
238 const size_t (& sz_cnk)[dim])
239 :header_mask(&header_mask),header_inf(&header_inf),lin_id_pos(&lin_id_pos),chunk_id(1),
240 mask_nele(0),mask_it_pnt(0),start(start),stop(stop)
241 {
242 for (size_t i = 0 ; i < dim ; i++)
243 {
244 this->sz_cnk[i] = sz_cnk[i];
245
246 bx.setLow(i,start.get(i));
247 bx.setHigh(i,stop.get(i));
248 }
249
250 SelectValidAndFill_mask_it();
251 }
252
253 /*! \brief Reinitialize the iterator
254 *
255 * it re-initialize the iterator with the passed grid_key_dx_iterator_sub
256 * the actual position of the grid_key_dx_iterator_sub is ignored
257 *
258 * \param g_s_it grid_key_dx_iterator_sub
259 *
260 */
261 inline void reinitialize(const grid_key_sparse_dx_iterator_sub<dim,n_ele> & g_s_it)
262 {
263 header_inf = g_s_it.header_inf;
264 header_mask = g_s_it.header_mask;
265 lin_id_pos = g_s_it.lin_id_pos;
266 chunk_id = g_s_it.chunk_id;
267 mask_nele = g_s_it.mask_nele;
268 mask_it_pnt = g_s_it.mask_it_pnt;
269 start = g_s_it.start;
270 stop = g_s_it.stop;
271 bx = g_s_it.bx;
272 for (size_t i = 0 ; i < dim ; i++)
273 {sz_cnk[i] = g_s_it.sz_cnk[i];}
274
275 memcpy(mask_it,g_s_it.mask_it,sizeof(short unsigned int)*n_ele);
276 }
277
278 inline grid_key_sparse_dx_iterator_sub<dim,n_ele> & operator++()
279 {
280 mask_it_pnt++;
281
282 if (mask_it_pnt < mask_nele)
283 {
284 return *this;
285 }
286
287 chunk_id++;
288 mask_it_pnt = 0;
289
290 if (chunk_id < header_inf->size())
291 {
292 SelectValidAndFill_mask_it();
293 }
294
295 return *this;
296 }
297
298
299 /*! \brief Return the position of the actual point in coordinates
300 *
301 * \return the position
302 *
303 */
304 inline grid_key_dx<dim> get() const
305 {
306 grid_key_dx<dim> k_pos;
307
308 size_t lin_id = mask_it[mask_it_pnt];
309
310 for (size_t i = 0 ; i < dim ; i++)
311 {
312 k_pos.set_d(i,(*lin_id_pos)[lin_id].get(i) + header_inf->get(chunk_id).pos.get(i));
313 }
314
315 return k_pos;
316 }
317
318 /*! \brief Return the actual point linearized
319 *
320 * The disadvantage is that in general you cannot use move in this type of key
321 *
322 * \return the actual point
323 *
324 */
325 inline grid_key_sparse_lin_dx getKeyF()
326 {
327 return grid_key_sparse_lin_dx(chunk_id,mask_it[mask_it_pnt]);
328 }
329
330 /*! \brief Return true if there is a next grid point
331 *
332 * \return true if there is the next grid point
333 *
334 */
335 bool isNext()
336 {
337 return chunk_id < header_inf->size();
338 }
339
340 /*! \brief Return the starting point for the iteration
341 *
342 * \return the starting point
343 *
344 */
345 const grid_key_dx<dim> & getStart() const
346 {
347 return start;
348 }
349
350 /*! \brief Return the stop point for the iteration
351 *
352 * \return the stop point
353 *
354 */
355 const grid_key_dx<dim> & getStop() const
356 {
357 return stop;
358 }
359
360 /*! \brief Return the private member header
361 *
362 * \return header
363 *
364 */
365 const openfpm::vector<cheader<dim>> * private_get_header_inf() const
366 {return header_inf;}
367
368 /*! \brief Return the private member header
369 *
370 * \return header
371 *
372 */
373 const openfpm::vector<mheader<n_ele>> * private_get_header_mask() const
374 {return header_mask;}
375
376 /*! \brief Return the private member lin_id_pos
377 *
378 * \return lin_id_pos
379 *
380 */
381 const grid_key_dx<dim> (* private_get_lin_id_pos() const)[n_ele]
382 {return lin_id_pos;}
383
384 /*! \brief Return the private member chunk_id
385 *
386 * \return chunk_id
387 *
388 */
389 size_t private_get_chunk_id() const
390 {return chunk_id;}
391
392 /*! \brief Return the private member mask_nele
393 *
394 * \return mask_nele
395 *
396 */
397 size_t private_get_mask_nele() const
398 {return mask_nele;}
399
400
401 /*! \brief Return the private member mask_it_pnt
402 *
403 * \return mask_it_pnt
404 *
405 */
406 size_t private_get_mask_it_pnt() const
407 {return mask_it_pnt;}
408
409 /*! \brief Return the private member mask_it
410 *
411 * \return mask_it
412 *
413 */
414 const short unsigned int (& private_get_mask_it() const) [n_ele]
415 {
416 return mask_it;
417 }
418};
419
420/*! \brief Grid key sparse iterator
421 *
422 *
423 */
424template<unsigned dim, unsigned int n_ele>
425class grid_key_sparse_dx_iterator
426{
427 //! It store the information of each chunk
428 const openfpm::vector<mheader<n_ele>> * header_mask;
429
430 //! It store the information of each chunk
431 const openfpm::vector<cheader<dim>> * header_inf;
432
433 //! linearized id to position in coordinates conversion
434 const grid_key_dx<dim> (* lin_id_pos)[n_ele];
435
436 //! point to the actual chunk
437 size_t chunk_id;
438
439 //! Number of points in mask_it
440 int mask_nele;
441
442 //! Actual point in mask it
443 size_t mask_it_pnt;
444
445 //! set of index in the chunk on which we have to iterate
446 short unsigned int mask_it[n_ele];
447
448 /*! \brief Everytime we move to a new chunk we calculate on which indexes we have to iterate
449 *
450 *
451 */
452 void SelectValidAndFill_mask_it()
453 {
454 mask_nele = 0;
455 mask_it_pnt = 0;
456
457 while (mask_nele == 0 && chunk_id < header_inf->size())
458 {
459 auto & mask = header_mask->get(chunk_id).mask;
460
461 fill_mask<n_ele>(mask_it,mask,mask_nele);
462
463 chunk_id = (mask_nele == 0)?chunk_id + 1:chunk_id;
464
465 }
466 }
467
468public:
469
470 /*! \brief Default constructor
471 *
472 * \warning extremely unsafe
473 * If you use this constructor before use the iterator you should call reinitialize first
474 *
475 */
476 grid_key_sparse_dx_iterator() {};
477
478 grid_key_sparse_dx_iterator(const openfpm::vector<mheader<n_ele>> * header_mask,
479 const openfpm::vector<cheader<dim>> * header_inf,
480 const grid_key_dx<dim> (* lin_id_pos)[n_ele])
481 :header_mask(header_mask),header_inf(header_inf),lin_id_pos(lin_id_pos),chunk_id(1),mask_nele(0),mask_it_pnt(0)
482 {
483 SelectValidAndFill_mask_it();
484 }
485
486 inline grid_key_sparse_dx_iterator<dim,n_ele> & operator++()
487 {
488 mask_it_pnt++;
489
490 if (mask_it_pnt < mask_nele)
491 {
492 return *this;
493 }
494
495 chunk_id++;
496 mask_it_pnt = 0;
497
498 if (chunk_id < header_inf->size())
499 {
500 SelectValidAndFill_mask_it();
501 }
502
503 return *this;
504 }
505
506 /*! \brief Reinitialize the iterator
507 *
508 * it re-initialize the iterator with the passed grid_key_dx_iterator_sub
509 * the actual position of the grid_key_dx_iterator_sub is ignored
510 *
511 * \param g_s_it grid_key_dx_iterator
512 *
513 */
514 inline void reinitialize(const grid_key_sparse_dx_iterator<dim,n_ele> & g_s_it)
515 {
516 header_mask = g_s_it.header_mask;
517 header_inf = g_s_it.header_inf;
518 lin_id_pos = g_s_it.lin_id_pos;
519 chunk_id = g_s_it.chunk_id;
520 mask_nele = g_s_it.mask_nele;
521 mask_it_pnt = g_s_it.mask_it_pnt;
522
523 memcpy(mask_it,g_s_it.mask_it,sizeof(short unsigned int)*n_ele);
524 }
525
526 /*! \brief Reinitialize the iterator
527 *
528 * it re-initialize the iterator with the passed grid_key_dx_iterator_sub
529 * the actual position of the grid_key_dx_iterator_sub is ignored
530 *
531 * \param g_s_it grid_key_dx_iterator
532 *
533 */
534 inline void reinitialize(const grid_key_sparse_dx_iterator_sub<dim,n_ele> & g_s_it)
535 {
536 header_mask = g_s_it.private_get_header_mask();
537 header_inf = g_s_it.private_get_header_inf();
538 lin_id_pos = g_s_it.private_get_lin_id_pos();
539 chunk_id = 0;
540
541 SelectValidAndFill_mask_it();
542 }
543
544 /*! \brief Return the actual point
545 *
546 * \warning the key that this function return cannot be used with function like move
547 *
548 * \return the actual point
549 *
550 */
551 inline grid_key_sparse_lin_dx getKeyF()
552 {
553 return grid_key_sparse_lin_dx(chunk_id,mask_it[mask_it_pnt]);
554 }
555
556 /*! \brief Return the position of the actual point in coordinates
557 *
558 * \return the position
559 *
560 */
561 inline grid_key_dx<dim> get() const
562 {
563 grid_key_dx<dim> k_pos;
564
565 size_t lin_id = mask_it[mask_it_pnt];
566
567 for (size_t i = 0 ; i < dim ; i++)
568 {
569 k_pos.set_d(i,(*lin_id_pos)[lin_id].get(i) + header_inf->get(chunk_id).pos.get(i));
570 }
571
572 return k_pos;
573 }
574
575 /*! \brief Return true if there is a next grid point
576 *
577 * \return true if there is the next grid point
578 *
579 */
580 bool isNext()
581 {
582 return chunk_id < header_inf->size();
583 }
584};
585
586#endif /* OPENFPM_DATA_SRC_SPARSEGRID_SPARSEGRID_ITERATOR_HPP_ */
587