Chombo + EB + MF  3.2
TreeIntVectSet.H
Go to the documentation of this file.
1 #ifdef CH_LANG_CC
2 /*
3  * _______ __
4  * / ___/ / ___ __ _ / / ___
5  * / /__/ _ \/ _ \/ V \/ _ \/ _ \
6  * \___/_//_/\___/_/_/_/_.__/\___/
7  * Please refer to Copyright.txt, in Chombo's root directory.
8  */
9 #endif
10 
11 #ifndef _TREEINTVECTSET_H_
12 #define _TREEINTVECTSET_H_
13 
14 #include "Box.H"
15 #include "Pool.H"
16 #include "NamespaceHeader.H"
17 
18 class IntVectSet;
19 class ProblemDomain;
20 
21 // xlC doesn't like the static const int inside this class.
22 // so instead of a nice variable we have a macro: TIVS_NODESIZE
23 // Currently, this only affects two files: this one and the .cpp
24 #ifdef TIVS_NODESIZE
25 #undef TIVS_NODESIZE
26 #endif
27 #if (CH_SPACEDIM==1)
28 #define TIVS_NODESIZE 2
29 #elif (CH_SPACEDIM==2)
30 #define TIVS_NODESIZE 4
31 #elif (CH_SPACEDIM==3)
32 #define TIVS_NODESIZE 8
33 #elif (CH_SPACEDIM==4)
34 #define TIVS_NODESIZE 16
35 #elif (CH_SPACEDIM==5)
36 #define TIVS_NODESIZE 32
37 #elif (CH_SPACEDIM==6)
38 #define TIVS_NODESIZE 64
39 #else
40 //error -- only tested for dimensions 2 and 3 (ndk)
41 #error TIVS_NODESIZE is only defined for 1D, 2D, 3D, 4D, 5D, or 6D
42 #endif
43 
44 /// IntVectSet implementation based on tree representation.
45 /**
46  For explanations of these functions please look at IntVectSet class
47  when the documentation doesn't appear here.
48 
49  @see IntVectSet
50 
51 <HR>
52 
53 <PRE>
54  Further details of how non-recursive TreeNode design works:
55 
56  (for a 2D tree)
57 
58  (m_tree)
59  + -- 0
60 
61  (a)+ - 0
62  1
63  1 +
64  1 <------you are here
65 
66  + - + - 0
67  0 1
68  0 1
69  0 0
70 
71  for the node indicated, the 'index' vector would contain
72 
73  index=[ 0 1 3 ...............]
74  parents=[&m_tree &a ..................]
75 
76 or directly refered to as m_tree.nodes[1].nodes[3]
77 
78  the tree indicates a covering of an index space in either
79  1 or 0. 1 is stored in the tree by pointing at the static
80  'full' data member, 0 is stored as a 0.
81 
82  every 'nodes' member of a TreeNode object can be either
83 
84  0, &full, or a pointer .
85 
86  The interpretation of the tree depends on what m_spanBox is.
87  nodes[i] indicates whether the i'th quadrant of the parent
88  Box is full, empty, or needs to be parsed deeper.
89 
90 </PRE>
91 
92  */
94 {
95 public:
96  ///
97  inline TreeIntVectSet();
98 
99  ///
100  TreeIntVectSet(const Box&);
101 
102  ///
103  TreeIntVectSet(const TreeIntVectSet& a_sivs);
104 
105  ///
106  ~TreeIntVectSet();
107 
108  ///
109  void define(const Box&);
110 
111  ///
112  void define(const TreeIntVectSet& a_sivs);
113 
114  /// trade internals of two objects
115  void swap(TreeIntVectSet& a_other);
116 
117  ///
118  TreeIntVectSet& operator=(const TreeIntVectSet& a_sivs);
119 
120  ///or
121  TreeIntVectSet& operator|=(const TreeIntVectSet& a_sivs);
122 
123  ///
124  TreeIntVectSet& operator|=(const IntVect& a_iv);
125 
126  ///
127  TreeIntVectSet& operator|=(const Box& a_box);
128 
129  ///and
130  TreeIntVectSet& operator&=(const TreeIntVectSet& s_sivs);
131 
132  ///and
133  TreeIntVectSet& operator&=(const Box& a_box);
134 
135  ///and
136  TreeIntVectSet& operator&=(const ProblemDomain& a_domain);
137 
138  ///not
139  TreeIntVectSet& operator-=(const TreeIntVectSet& a_sivs);
140 
141  ///not
142  TreeIntVectSet& operator-=(const IntVect& a_iv);
143 
144  ///not
145  TreeIntVectSet& operator-=(const Box& a_box);
146 
147  ///returns true if
148  bool operator==(const TreeIntVectSet& lhs) const;
149 
150  /**
151  Primary sorting criterion: numPts().
152  Secondary sorting criterion: lexigraphical ordering of the IntVects, taken
153  in the order traversed by TreeIntVectSetIterator.
154  In a total tie, returns false.
155  */
156  bool operator<(const TreeIntVectSet& a_sivs) const;
157 
158  /// Returns Vector<Box> representation of this IntVectSet.
159  /**
160  Returns Vector<Box> representation of this IntVectSet.
161  */
162  Vector<Box> createBoxes() const;
163 
164  /// Returns Vector<Box> representation of this IntVectSet.
165  /**
166  Returns Vector<Box> representation of this IntVectSet.
167  */
168  void createBoxes(Vector<Box>& boxes, int& size) const;
169 
170  ///
171  bool contains(const IntVect& iv) const;
172 
173  ///
174  bool contains(const Box& box) const;
175 
176  ///
177  /**
178  somewhat expensive, but shouldn't be ;-) @see IntVectSet::chop
179  */
180  TreeIntVectSet chop(int idir, int chop_pnt);
181 
182  ///
183  /**
184  a proper faster chop function that does it all in-place and saves the giant memory cost.
185  */
186  void chop(int dir, int chop_pnt, TreeIntVectSet& a_hi);
187 
188  ///@see IntVectSet::grow
189  /**
190  expensive
191  */
192  void grow(int igrow);
193 
194  ///
195  /**
196  expensive
197  */
198  void grow(int idir, int igrow);
199 
200  ///
201  /**
202  @see IntVectSet::growHi
203  expensive
204  */
205  void growHi();
206 
207  ///
208  /**
209  @see IntVectSet::growHi(int)
210  expensive
211  */
212  void growHi(int a_dir);
213 
214  ///fast if iref is power of 2
215  /**
216  fast if iref is power of 2
217  */
218  void refine(int iref = 2);
219 
220  ///fast if iref is power of 2
221  /**
222  fast if iref is power of 2
223  */
224  void coarsen(int iref = 2);
225 
226  /// slow operation
227  /**
228 
229  */
230  void shift(const IntVect& iv);
231 
232  ///
233  void clear();
234 
235  ///
236  void nestingRegion(int a_radius, const Box& a_domain, int granularity);
237 
238  ///
239  void nestingRegion(int a_radius, const ProblemDomain& a_domain, int granularity);
240 
241  ///
242  inline const Box& minBox() const;
243 
244  ///
245  bool isEmpty() const;
246 
247  ///
248  int numPts() const;
249 
250  friend void dumpTree(const TreeIntVectSet* set);
251 
252  ///
253  void compact() const; // logically const operation;
254 
255  ///
256  void recalcMinBox() const;
257 
258  /** \name Linearization routines */
259  /*@{*/
260  int linearSize() const;
261 
262  void linearIn(const void* const inBuf);
263 
264  void linearOut(void* const a_outBuf) const;
265  /*@}*/
266 
267 private:
268 
270  friend class MeshRefine;
271 
272 #ifndef DOXYGEN
273  struct TreeNode
274  {
275  TreeNode* nodes;
276 
277  TreeNode()
278  :
279  nodes(0)
280  {
281  }
282  };
283 #endif
284 
285  TreeNode m_tree;
287  int m_depth;
288 
289  void trimCoarsen(int icoarse);
290 
291  //===============
294 
295  static void quadrantBox(const Box& inputBox, int quadrant, Box& outputQuadrant);
296  static void clearTree(TreeNode& tree);
297  static void expandNode(TreeNode& node);
298  void growTree();
299  void remove(const Box& box, TreeIntVectSet* resdiual);
300  void transfer(TreeNode& node, const Box& a_box);
301 
302  static int oppositeQuadrant(int index);
303  static bool nextIntVect(const Box& box, IntVect& iv);
304  static void nextNode(int& currentDepth);
305  static void cloneNode(const TreeNode& src, TreeNode& dest);
306  // data structures that are needed again and again in the routines
307  // that only change their size during grow() operations. Keep them
308  // around so that we don't have to create and destroy them on every function
309  // call
310 // static Vector<int> index, otherIndex;
311 // static Vector<TreeNode*> parents, P1;
312 // static Vector<const TreeNode*> otherParents, P2;
313 // static Vector<Box> boxes, otherBoxes;
314  static int index[24], otherIndex[24];
315  static TreeNode* parents[24];
316  static TreeNode* P1[24];
317  static const TreeNode* otherParents[24];
318  static const TreeNode* P2[24];
319  static Box boxes[24], otherBoxes[24];
320 #pragma omp threadprivate(boxes,otherBoxes)
321 #pragma omp threadprivate(parents,otherParents,P1,P2)
322 #pragma omp threadprivate(index, otherIndex)
323 
324 
325  // xlC wasn't like this
326  // so instead of a nice const static integer, we have a MACRO TIVS_NODESIZE
327  //const static int nodeSize = D_TERM(2,*2,*2);
328  static TreeNode full;
329  friend struct Flag;
330  friend class IntVectSet;
331 };
332 
333 void dumpTree(const TreeIntVectSet* set); //in TreeIntVectSet.cpp
334 
336 {
337 public:
340  void define(const TreeIntVectSet& ivs);
341  const IntVect& operator()() const ;
342  bool ok() const;
343  void operator++();
344  void begin();
345  void end();
346  void clear();
347 private:
352  int m_depth;
354 
355  void findNextNode();
356  void findNext(); // parse tree, starting at [depth, index], set m_current
357  //when you find an entry, might run to end of iterator.
358 };
359 
360 inline
362 {
363 }
364 
365 inline
367 {
368  define(ivs);
369 }
370 
371 inline
373 {
374  m_depth = -1;
375  m_ivs = 0;
376 }
377 
378 inline
380 {
381  m_ivs = &ivs;
382  int max = 24;
383  // if (max==10) printf("max=10 \n");
384  if (boxes.size() < max)
385  {
386  boxes.resize(max);
387  index.resize(max);
388  nodes.resize(max);
389  }
390  begin();
391 }
392 
393 inline
395 {
396  return m_depth >= 0;
397 }
398 
399 inline
401 {
402  m_depth = -1;
403 }
404 
405 inline
407 {
408  return *this|=Box(iv, iv);
409 }
410 
411 inline
413 {
414  return *this-=Box(iv, iv);
415 }
416 
417 inline
419 {
420  findNext();
421 }
422 
423 inline
425 {
426  return m_current;
427 }
428 
429 //=======================================================
430 
431 inline
433 {
434  clearTree(m_tree);
435 }
436 inline
438 {
439  define(a_tivs);
440 }
441 
442 inline
444 {
445  define(a_box);
446 }
447 
448 inline
449 std::ostream& operator<<(std::ostream& os, const TreeIntVectSet& ivs)
450 {
451  Vector<Box> b=ivs.createBoxes();
452  for (int i=0; i<b.size(); ++i) os<<b[i]<<std::endl;
453  return os;
454 }
455 
456 inline
458 {
459  m_tree.nodes = 0;
460  m_depth=1;
461 
462 }
463 
464 inline
465 const Box&
467 {
468  return m_minBox;
469 }
470 
471 inline void TreeIntVectSet::nextNode(int& depth)
472 {
473  index[0] = 0;
474  index[depth]++;
475  while (index[depth] == TIVS_NODESIZE)
476  {
477  index[depth] = 0;
478  depth--;
479  index[depth]++;
480  }
481 }
482 
483 #include "NamespaceFooter.H"
484 #endif // TREEINTVECTSET_H
void compact() const
friend void dumpTree(const TreeIntVectSet *set)
bool contains(const IntVect &iv) const
const IntVect & operator()() const
Definition: TreeIntVectSet.H:424
int linearSize() const
TreeIntVectSet & operator=(const TreeIntVectSet &a_sivs)
void swap(TreeIntVectSet &a_other)
trade internals of two objects
TreeIntVectSet & operator &=(const TreeIntVectSet &s_sivs)
and
An irregular domain on an integer lattice.
Definition: IntVectSet.H:44
static int otherIndex[24]
Definition: TreeIntVectSet.H:314
void linearOut(void *const a_outBuf) const
A class to facilitate interaction with physical boundary conditions.
Definition: ProblemDomain.H:141
static int index[24]
Definition: TreeIntVectSet.H:314
bool ok() const
Definition: TreeIntVectSet.H:394
TreeIntVectSet & operator-=(const TreeIntVectSet &a_sivs)
not
TreeIntVectSetIterator()
Definition: TreeIntVectSet.H:361
static Box otherBoxes[24]
Definition: TreeIntVectSet.H:319
int numPts() const
Vector< const TreeIntVectSet::TreeNode * > nodes
Definition: TreeIntVectSet.H:349
void define(const Box &)
bool operator<(const TreeIntVectSet &a_sivs) const
TreeNode m_tree
Definition: TreeIntVectSet.H:285
static Pool treeNodePoolObject
Definition: TreeIntVectSet.H:292
Vector< Box > boxes
Definition: TreeIntVectSet.H:350
IntVectSet implementation based on tree representation.
Definition: TreeIntVectSet.H:93
bool isEmpty() const
void transfer(TreeNode &node, const Box &a_box)
static void clearTree(TreeNode &tree)
static const TreeNode * P2[24]
Definition: TreeIntVectSet.H:318
void grow(int igrow)
Definition: EBInterface.H:45
void resize(unsigned int isize)
Definition: Vector.H:346
void trimCoarsen(int icoarse)
static Box boxes[24]
Definition: TreeIntVectSet.H:319
Box m_minBox
Definition: TreeIntVectSet.H:286
void shift(const IntVect &iv)
slow operation
void clear()
Definition: TreeIntVectSet.H:372
void define(const TreeIntVectSet &ivs)
Definition: TreeIntVectSet.H:379
const TreeIntVectSet * m_ivs
Definition: TreeIntVectSet.H:348
static void cloneNode(const TreeNode &src, TreeNode &dest)
Definition: TreeIntVectSet.H:335
IntVect m_current
Definition: TreeIntVectSet.H:353
int m_depth
Definition: TreeIntVectSet.H:352
Pool is a class to optimize memory allocation.
Definition: Pool.H:63
IndexTM< T, N > max(const IndexTM< T, N > &a_p1, const IndexTM< T, N > &a_p2)
Definition: IndexTMI.H:401
friend struct Flag
Definition: TreeIntVectSet.H:329
size_t size() const
Definition: Vector.H:192
static bool nextIntVect(const Box &box, IntVect &iv)
void linearIn(const void *const inBuf)
static void nextNode(int &currentDepth)
Definition: TreeIntVectSet.H:471
std::ostream & operator<<(std::ostream &os, const TreeIntVectSet &ivs)
Definition: TreeIntVectSet.H:449
static TreeNode * P1[24]
Definition: TreeIntVectSet.H:316
int m_depth
Definition: TreeIntVectSet.H:287
A Rectangular Domain on an Integer Lattice.
Definition: Box.H:469
void nestingRegion(int a_radius, const Box &a_domain, int granularity)
friend class TreeIntVectSetIterator
Definition: TreeIntVectSet.H:269
static Pool * treeNodePool
Definition: TreeIntVectSet.H:293
void recalcMinBox() const
Box m_spanBox
Definition: TreeIntVectSet.H:286
static void expandNode(TreeNode &node)
static void quadrantBox(const Box &inputBox, int quadrant, Box &outputQuadrant)
void refine(int iref=2)
fast if iref is power of 2
An integer Vector in SpaceDim-dimensional space.
Definition: CHArray.H:42
TreeIntVectSet & operator|=(const TreeIntVectSet &a_sivs)
or
static const TreeNode * otherParents[24]
Definition: TreeIntVectSet.H:317
bool operator==(const TreeIntVectSet &lhs) const
returns true if
static int oppositeQuadrant(int index)
const Box & minBox() const
Definition: TreeIntVectSet.H:466
Vector< int > index
Definition: TreeIntVectSet.H:351
TreeIntVectSet chop(int idir, int chop_pnt)
Class which manages grid generation.
Definition: MeshRefine.H:26
static TreeNode * parents[24]
Definition: TreeIntVectSet.H:315
void operator++()
Definition: TreeIntVectSet.H:418
void end()
Definition: TreeIntVectSet.H:400
static TreeNode full
Definition: TreeIntVectSet.H:328
void coarsen(int iref=2)
fast if iref is power of 2
Vector< Box > createBoxes() const
Returns Vector<Box> representation of this IntVectSet.
~TreeIntVectSet()
Definition: TreeIntVectSet.H:432
TreeIntVectSet()
Definition: TreeIntVectSet.H:457