Chombo + EB  3.0
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 
303  static int oppositeQuadrant(int index);
304  static bool nextIntVect(const Box& box, IntVect& iv);
305  static void nextNode(int& currentDepth);
306  static void cloneNode(const TreeNode& src, TreeNode& dest);
307  // data structures that are needed again and again in the routines
308  // that only change their size during grow() operations. Keep them
309  // around so that we don't have to create and destroy them on every function
310  // call
314 
315  // xlC wasn't like this
316  // so instead of a nice const static integer, we have a MACRO TIVS_NODESIZE
317  //const static int nodeSize = D_TERM(2,*2,*2);
318  static TreeNode full;
319  friend struct Flag;
320  friend class IntVectSet;
321 };
322 
323 void dumpTree(const TreeIntVectSet* set); //in TreeIntVectSet.cpp
324 
326 {
327 public:
330  void define(const TreeIntVectSet& ivs);
331  const IntVect& operator()() const ;
332  bool ok() const;
333  void operator++();
334  void begin();
335  void end();
336  void clear();
337 private:
342  int m_depth;
344 
345  void findNextNode();
346  void findNext(); // parse tree, starting at [depth, index], set m_current
347  //when you find an entry, might run to end of iterator.
348 };
349 
350 inline
352 {
353 }
354 
355 inline
357 {
358  define(ivs);
359 }
360 
361 inline
363 {
364  m_depth = -1;
365  m_ivs = 0;
366 }
367 
368 inline
370 {
371  m_ivs = &ivs;
372  int max = ivs.index.size();
373  // if (max==10) printf("max=10 \n");
374  if (boxes.size() < max)
375  {
376  boxes.resize(max);
377  index.resize(max);
378  nodes.resize(max);
379  }
380  begin();
381 }
382 
383 inline
385 {
386  return m_depth >= 0;
387 }
388 
389 inline
391 {
392  m_depth = -1;
393 }
394 
395 inline
397 {
398  return *this|=Box(iv, iv);
399 }
400 
401 inline
403 {
404  return *this-=Box(iv, iv);
405 }
406 
407 inline
409 {
410  findNext();
411 }
412 
413 inline
415 {
416  return m_current;
417 }
418 
419 //=======================================================
420 
421 inline
423 {
424  clearTree(m_tree);
425 }
426 inline
428 {
429  define(a_tivs);
430 }
431 
432 inline
434 {
435  define(a_box);
436 }
437 
438 inline
440 {
441  m_tree.nodes = 0;
442  m_depth=1;
443 
444 }
445 
446 inline
447 const Box&
449 {
450  return m_minBox;
451 }
452 
453 inline void TreeIntVectSet::nextNode(int& depth)
454 {
455  index[0] = 0;
456  index[depth]++;
457  while (index[depth] == TIVS_NODESIZE)
458  {
459  index[depth] = 0;
460  depth--;
461  index[depth]++;
462  }
463 }
464 
465 #include "NamespaceFooter.H"
466 #endif // TREEINTVECTSET_H
friend void dumpTree(const TreeIntVectSet *set)
static Vector< TreeNode * > parents
Definition: TreeIntVectSet.H:312
bool ok() const
Definition: TreeIntVectSet.H:384
TreeIntVectSet & operator=(const TreeIntVectSet &a_sivs)
void swap(TreeIntVectSet &a_other)
trade internals of two objects
An irregular domain on an integer lattice.
Definition: IntVectSet.H:44
A class to facilitate interaction with physical boundary conditions.
Definition: ProblemDomain.H:130
int numPts() const
TreeIntVectSet & operator-=(const TreeIntVectSet &a_sivs)
not
Vector< Box > createBoxes() const
Returns Vector<Box> representation of this IntVectSet.
void dumpTree(const TreeIntVectSet *set)
TreeIntVectSetIterator()
Definition: TreeIntVectSet.H:351
Vector< const TreeIntVectSet::TreeNode * > nodes
Definition: TreeIntVectSet.H:339
bool contains(const IntVect &iv) const
void define(const Box &)
TreeNode m_tree
Definition: TreeIntVectSet.H:285
static Pool treeNodePoolObject
Definition: TreeIntVectSet.H:292
Vector< Box > boxes
Definition: TreeIntVectSet.H:340
IntVectSet implementation based on tree representation.
Definition: TreeIntVectSet.H:93
const Box & minBox() const
Definition: TreeIntVectSet.H:448
void transfer(TreeNode &node, const Box &a_box)
static void clearTree(TreeNode &tree)
static Vector< int > bufferOffset
Definition: TreeIntVectSet.H:311
void grow(int igrow)
static Vector< int > index
Definition: TreeIntVectSet.H:311
Definition: EBInterface.H:45
void resize(unsigned int isize)
Definition: Vector.H:323
void trimCoarsen(int icoarse)
Box m_minBox
Definition: TreeIntVectSet.H:286
void shift(const IntVect &iv)
slow operation
void clear()
Definition: TreeIntVectSet.H:362
void define(const TreeIntVectSet &ivs)
Definition: TreeIntVectSet.H:369
const TreeIntVectSet * m_ivs
Definition: TreeIntVectSet.H:338
static void cloneNode(const TreeNode &src, TreeNode &dest)
Definition: TreeIntVectSet.H:325
IntVect m_current
Definition: TreeIntVectSet.H:343
int m_depth
Definition: TreeIntVectSet.H:342
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:403
friend struct Flag
Definition: TreeIntVectSet.H:319
static bool nextIntVect(const Box &box, IntVect &iv)
void linearIn(const void *const inBuf)
static void nextNode(int &currentDepth)
Definition: TreeIntVectSet.H:453
int m_depth
Definition: TreeIntVectSet.H:287
A Rectangular Domain on an Integer Lattice.
Definition: Box.H:465
void nestingRegion(int a_radius, const Box &a_domain, int granularity)
static Pool * treeNodePool
Definition: TreeIntVectSet.H:293
void recalcMinBox() const
Box m_spanBox
Definition: TreeIntVectSet.H:286
const IntVect & operator()() const
Definition: TreeIntVectSet.H:414
static void expandNode(TreeNode &node)
bool operator==(const TreeIntVectSet &lhs) const
returns true if
static void quadrantBox(const Box &inputBox, int quadrant, Box &outputQuadrant)
void compact() const
void refine(int iref=2)
fast if iref is power of 2
An integer Vector in SpaceDim-dimensional space.
Definition: CHArray.H:42
bool isEmpty() const
TreeIntVectSet & operator|=(const TreeIntVectSet &a_sivs)
or
size_t size() const
Definition: Vector.H:177
static int oppositeQuadrant(int index)
Vector< int > index
Definition: TreeIntVectSet.H:341
TreeIntVectSet chop(int idir, int chop_pnt)
int linearSize() const
static Vector< Box > boxes
Definition: TreeIntVectSet.H:313
TreeIntVectSet & operator&=(const TreeIntVectSet &s_sivs)
and
Class which manages grid generation.
Definition: MeshRefine.H:26
void linearOut(void *const a_outBuf) const
void operator++()
Definition: TreeIntVectSet.H:408
void end()
Definition: TreeIntVectSet.H:390
static TreeNode full
Definition: TreeIntVectSet.H:318
void coarsen(int iref=2)
fast if iref is power of 2
~TreeIntVectSet()
Definition: TreeIntVectSet.H:422
bool operator<(const TreeIntVectSet &a_sivs) const
TreeIntVectSet()
Definition: TreeIntVectSet.H:439