Traverse.h 8.92 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// ============================================================================
// ==                                                                        ==
// == AMDiS - Adaptive multidimensional simulations                          ==
// ==                                                                        ==
// ============================================================================
// ==                                                                        ==
// ==  crystal growth group                                                  ==
// ==                                                                        ==
// ==  Stiftung caesar                                                       ==
// ==  Ludwig-Erhard-Allee 2                                                 ==
// ==  53175 Bonn                                                            ==
// ==  germany                                                               ==
// ==                                                                        ==
// ============================================================================
// ==                                                                        ==
// ==  http://www.caesar.de/cg/AMDiS                                         ==
// ==                                                                        ==
// ============================================================================

/** \file Traverse.h */

/** \defgroup Traverse Traverse module
 * @{ <img src="traverse.png"> @}
 *
 * \brief
 * Contains classes used for mesh traversal.
 */

#ifndef AMDIS_TRAVERSE_H
#define AMDIS_TRAVERSE_H

#include "Flag.h"
#include "Global.h"
#include "ElInfo.h"
Thomas Witkowski's avatar
Thomas Witkowski committed
35
#include "ElInfoStack.h"
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include "MemoryManager.h"
#include <vector>
#include <deque>

namespace AMDiS {

  class MacroElement;
  class Mesh;

  // ===========================================================================
  // ===== class TraverseStack =================================================
  // ===========================================================================

  /** \ingroup Traverse
   * \brief
   * Mesh refinement and coarsening routines are examples of functions which 
   * need a non-recursive access to the mesh elements.
   * The implementation of the non-recursive mesh traversal routines uses a 
   * stack to save the tree path from a macro element to the current element. 
   * TraverseStack holds such information. Before calling the non-recursive mesh
   * traversal routines, such a stack must be allocated. The stack is 
   * initialized by each call to \ref traverseFirst().
   */
  class TraverseStack 
  {
  public:
    MEMORY_MANAGED(TraverseStack);

    /** \brief
     * Creates an empty TraverseStack
     */
67
68
69
70
71
72
73
    TraverseStack() 
      : traverse_mel(NULL),
        stack_size(0),
        stack_used(0),
        save_stack_used(0),
        myThreadId_(0),
        maxThreads_(1)
74
75
76
77
78
79
80
81
82
    {
      id = ElInfo::traverseIdCounter++;
    };

    /** \brief
     * Destructor
     */
    ~TraverseStack() 
    {
83
      for (int i = 0; i < static_cast<int>(elinfo_stack.size()); i++) {
84
85
	DELETE elinfo_stack[i];
      }
86
      for (int i = 0; i < static_cast<int>(save_elinfo_stack.size()); i++) {
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
	DELETE save_elinfo_stack[i];
      }
    };

  public:
    /** \brief
     * Returns the first ElInfo of a non recursive traversal which fullfills the
     * selection criterion specified by level and fill_flag and initializes the
     * stack. After a call of traverseFirst the next Elements are traversed via 
     * \ref traverseNext(). 
     */
    ElInfo* traverseFirst(Mesh *mesh, int level, Flag fill_flag);

    /** \brief
     * Returns the next ElInfo in a traversal initiated by \ref traverseFirst()
     * If NULL is returned, the traversal is finished.
     */
    ElInfo* traverseNext(ElInfo* elinfo_old);

    /** \brief
     * Returns the neighbour-th neighbour of elInfoOld
     */
    ElInfo* traverseNeighbour(ElInfo* elInfoOld, int neighbour);

    /** \brief
     * Returns the neighbour-th neighbour of elInfoOld
     */
    ElInfo* traverseNeighbour3d(ElInfo* elInfoOld, int neighbour);

    /** \brief
     * Returns the neighbour-th neighbour of elInfoOld
     */
    ElInfo* traverseNeighbour2d(ElInfo* elInfoOld, int neighbour);

    /** \brief
     * Not yet implemented
     */
    ElInfo* traverseMultiGridLevel();

    /** \brief
     * Preorder traversal of all elements
     */
    ElInfo* traverseEveryElementPreorder();

    /** \brief
     * Inorder traversal of all elements
     */
    ElInfo* traverseEveryElementInorder();

    /** \brief
     * Postorder traversal of all elements
     */
    ElInfo* traverseEveryElementPostorder();

    /** \brief
     * Only for 3d: Calls update of all ElInfo3d onjects in \ref elinfo_stack
     */
    void update();

146
147
148
149
150
151
152
153
154
155
156
157
158
    /** \brief
     *
     */
    inline void setMyThreadId(int myThreadId) {
      myThreadId_ = myThreadId;
    }

    /** \brief
     *
     */
    inline void setMaxThreads(int maxThreads) {
      maxThreads_ = maxThreads;
    }
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
  private:
    /** \brief
     * Enlargement of the stack
     */
    void enlargeTraverseStack();

    /** \brief
     * Used by \ref traverseFirst() \ref traverseNext()
     */
    ElInfo* traverseLeafElement();

    /** \brief
     * Used by \ref traverseFirst() \ref traverseNext()
     */
    ElInfo* traverseLeafElementLevel();

    /** \brief
     * Used by \ref traverseFirst() \ref traverseNext()
     */
    ElInfo* traverseElementLevel();

    /** \brief
     * Avoids copy of a traverse stack. If copy should be possible
     * the operator must be implemented (deep copy not flat copy!)
     */
    void operator=(const TraverseStack& /*rhs*/) {
      FUNCNAME("TraverseStack::operator=");
      ERROR_EXIT("not implemented");
    };

    /** \brief
     * Avoids copy of a traverse stack. If copy should be possible
     * the operator must be implemented (deep copy not flat copy!)
     */
    TraverseStack(const TraverseStack&) {
      FUNCNAME("TraverseStack::TraverseStack(const TraverseStack&)");
      ERROR_EXIT("not implemented");
    };

  private:
    /** \brief
     * Iterator to the current MacroElement
     */
202
    std::deque<MacroElement*>::const_iterator currentMacro;
203
204
205
206

    /** \brief
     * Mesh which is currently traversed
     */
207
    Mesh* traverse_mesh;
208
209
210
211
212

    /** \brief
     * Traverse level. Used if CALL_EL_LEVEL or CALL_LEAF_EL_LEVEL are set in
     * \ref traverse_fill_flag
     */
213
    int traverse_level;
214
215
216
217
218

    /** \brief
     * Flags for traversal. Specifies which elements are visited and which
     * information are filled to the ElInfo objects.
     */
219
    Flag traverse_fill_flag;
220
221
222
223
224
225
226
227
228
  
    /** \brief
     * current macro element
     */
    const MacroElement *traverse_mel;

    /** \brief
     * Current size of the stack
     */
229
    int stack_size;
230
231
232
233

    /** \brief
     * Used size of the stack
     */
234
    int stack_used;
235
236
237
238

    /** \brief
     * 
     */
239
    std::vector<ElInfo*> elinfo_stack;
240
241
242
243

    /** \brief
     * 
     */
244
    std::vector<unsigned char> info_stack;
245
246
247
248
249
250
251
252
253
  
    /** \brief
     * 
     */
    const MacroElement *save_traverse_mel;

    /** \brief
     * 
     */
254
    std::vector<ElInfo*> save_elinfo_stack;
255
256
257
258

    /** \brief
     * 
     */
259
    std::vector<unsigned char> save_info_stack;
260
261
262
263

    /** \brief
     * 
     */
264
    int save_stack_used;
265
266
267
268
269
  
    /** \brief
     * 
     */
    int id;
270
271
272
273
274
275
276
277
278
279
280
281
282
283

    /** \brief
     * Is used for parallel mesh traverse. The thread with the id
     * myThreadId is only allowed to access coarse elements, which id
     * satisfies: elId % maxThreads = myThreadId.
     */
    int myThreadId_;

    /** \brief
     * Is used for parallel mesh traverse. The thread with the id
     * myThreadId is only allowed to access coarse elements, which id
     * satisfies: elId % maxThreads = myThreadId.
     */
    int maxThreads_;
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
  };

  // ============================================================================
  // ===== class Traverse =======================================================
  // ============================================================================

  /** \ingroup Traverse
   * \brief
   * Class for recursive mesh traversal. Used in \ref Mesh::traverse()
   */
  class Traverse 
  {
  public:
    MEMORY_MANAGED(Traverse);

    /** \brief
     * Creates a Traverse object for Mesh m with fill flags f and level l.
     * el_fct is a pointer to a the function that will be called for every 
     * visited element.
     */
    Traverse(Mesh* m,
	     const Flag f,
	     const unsigned char l,
	     int (*ef)(ElInfo*))
Thomas Witkowski's avatar
Thomas Witkowski committed
308
309
310
311
      : mesh(m),
        flag(f),
        level(l),
        el_fct(ef) 
312
313
314
315
316
317
318
319
    {
      TEST_EXIT(m)("No traverse without mesh!\n");
      id = ElInfo::traverseIdCounter++;
    };

    /** \brief
     * Performs the recursive traversal
     */  
Thomas Witkowski's avatar
Thomas Witkowski committed
320
321
    //    int recursive(ElInfo*);
    int recursive(ElInfoStack*);
322
323
324
  
  private:
    Mesh *mesh;
325

326
    Flag flag; 
327

328
    unsigned char level;
329

330
331
    int (*el_fct)(ElInfo*);

332
    int id;
333
334
335

    Traverse();

336
    Traverse(const Traverse&);
337
338
339
340
341
342
  };

}

#endif  // AMDIS_TRAVERSE_H