tree.cc
Go to the documentation of this file.
1// LIC// ====================================================================
2// LIC// This file forms part of oomph-lib, the object-oriented,
3// LIC// multi-physics finite-element library, available
4// LIC// at http://www.oomph-lib.org.
5// LIC//
6// LIC// Copyright (C) 2006-2022 Matthias Heil and Andrew Hazel
7// LIC//
8// LIC// This library is free software; you can redistribute it and/or
9// LIC// modify it under the terms of the GNU Lesser General Public
10// LIC// License as published by the Free Software Foundation; either
11// LIC// version 2.1 of the License, or (at your option) any later version.
12// LIC//
13// LIC// This library is distributed in the hope that it will be useful,
14// LIC// but WITHOUT ANY WARRANTY; without even the implied warranty of
15// LIC// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16// LIC// Lesser General Public License for more details.
17// LIC//
18// LIC// You should have received a copy of the GNU Lesser General Public
19// LIC// License along with this library; if not, write to the Free Software
20// LIC// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
21// LIC// 02110-1301 USA.
22// LIC//
23// LIC// The authors may be contacted at oomph-lib@maths.man.ac.uk.
24// LIC//
25// LIC//====================================================================
26// Non-inline and non-templated functions for Tree and TreeForest
27// classes
28
29// Config header generated by autoconfig
30#ifdef HAVE_CONFIG_H
31#include <oomph-lib-config.h>
32#endif
33
34
35// oomph-lib headers
36#include "tree.h"
37
38// Need to include this so that we can use the member functions of
39// RefineableElement
40#include "refineable_elements.h"
41
42namespace oomph
43{
44 //========================================================================
45 /// Static value used to represent unassigned quantities.
46 /// This has to remain consistent with the enumerations in
47 /// the Octree and Quadtree namespaces!
48 //========================================================================
49 const int Tree::OMEGA = 26;
50
51 //========================================================================
52 /// Maximum tolerance for neighbour finding (distance between points
53 /// when identified from the two neighbours)
54 //========================================================================
56
57 //================================================================
58 /// Constructor for empty (root) Tree: No father, no sons.
59 /// Pass pointer to the object that this tree (root) contains.
60 /// Protected because Trees can only be created internally,
61 /// during the split operation.
62 //=================================================================
63 Tree::Tree(RefineableElement* const& object_pt) : Object_pt(object_pt)
64 {
65 // No father node:
66 Father_pt = 0;
67
68 // I'm not a son, so I don't have a son type either....
70
71 // I am the root
72 Level = 0;
73
74 // Root pointer must be set in the TreeRoot constructor
75 Root_pt = 0;
76
77 // No sons just yet:
78 Son_pt.resize(0);
79
80 // Tell the object which tree it's represented by
82 };
83
84
85 //================================================================
86 /// Constructor for Tree: This one has a father
87 /// and is a son of a certain type, but has no sons
88 /// of its own (just yet), so it's a leaf node.
89 /// Protected because Trees can only be created internally,
90 /// during the split operation.
91 //=================================================================
92 Tree::Tree(RefineableElement* const& object_pt,
93 Tree* const& father_pt,
94 const int& son_type)
95 : Object_pt(object_pt)
96 {
97 // Set the father node
99
100 // Set the son type
102
103 // My level is one deeper than that of my father
104 Level = father_pt->Level + 1;
105
106 // I have no sons of my own just yet:
107 Son_pt.resize(0);
108
109 // Inherit root pointer from father
111
112 // Tell the object which tree it's represented by
113 object_pt->set_tree_pt(this);
114 }
115
116 //================================================================
117 /// Destructor for Tree: Recursively kill all sons and the
118 /// associated objects of the non-leaf nodes. However, the objects
119 /// of the leaf nodes are not destroyed. Their destruction is handled
120 /// by the Mesh destructor.
121 //=================================================================
123 {
124 // Loop over all the sons and delete them
125 unsigned nsons = Son_pt.size();
126 for (unsigned i = 0; i < nsons; i++)
127 {
128 // This will call the son's destructor (a subtle recursion)
129 delete Son_pt[i];
130 Son_pt[i] = 0;
131 }
132
133 // Delete the object only if the Tree has sons (is not a leaf node)
134 if (nsons > 0)
135 {
136 delete Object_pt;
137 Object_pt = 0;
138 }
139 }
140
141 //================================================================
142 /// Preorder traverse the tree and execute void Tree member function
143 /// at all nodes
144 //=================================================================
146 {
147 // Process the object contained in (well, pointed to) by current
148 // Tree
149 (this->*member_function)();
150
151 // Now do the sons (if they exist)
152 unsigned numsons = Son_pt.size();
153 for (unsigned i = 0; i < numsons; i++)
154 {
155 Son_pt[i]->traverse_all(member_function);
156 }
157 }
158
159
160 //================================================================
161 /// Preorder traverse the tree and execute a void Tree member function
162 /// that takes one argument at all nodes.
163 //=================================================================
165 Mesh*& mesh_pt)
166 {
167 // Process the object contained in (well, pointed to) by current
168 // Tree
169 (this->*member_function)(mesh_pt);
170
171 // Now do the sons (if they exist)
172 unsigned numsons = Son_pt.size();
173 for (unsigned i = 0; i < numsons; i++)
174 {
175 Son_pt[i]->traverse_all(member_function, mesh_pt);
176 }
177 }
178
179
180 //==================================================================
181 /// Preorder traverse the tree and execute a void Tree member function
182 /// for all elements that are not leaf elements.
183 //==================================================================
185 {
186 // Find the number of sons
187 unsigned n_sons = Son_pt.size();
188 // If the Tree has sons,
189 if (n_sons > 0)
190 {
191 // Execute the function
192 (this->*member_function)();
193 // Proceed to the sons
194 for (unsigned i = 0; i < n_sons; i++)
195 {
196 Son_pt[i]->traverse_all_but_leaves(member_function);
197 }
198 }
199 // If the tree has no sons, the function will not be executed
200 }
201
202
203 //================================================================
204 /// Preorder traverse the tree and execute void Tree member function
205 /// at the leaves only (ignore "grey" = non-leaf nodes)
206 //=================================================================
208 {
209 // If the Tree has sons
210 unsigned numsons = Son_pt.size();
211 if (numsons > 0)
212 {
213 // Proceed to the sons (if they exist)
214 for (unsigned i = 0; i < numsons; i++)
215 {
216 Son_pt[i]->traverse_leaves(member_function);
217 }
218 }
219 else
220 {
221 // Call the member function
222 (this->*member_function)();
223 }
224 }
225
226 //================================================================
227 /// Preorder traverse the tree and execute void Tree member function
228 /// that takes one argument at the leaves only
229 /// (ignore "grey" = non-leaf nodes)
230 //=================================================================
232 Tree::VoidMeshPtArgumentMemberFctPt member_function, Mesh*& mesh_pt)
233 {
234 // If the Tree has sons
235 unsigned numsons = Son_pt.size();
236 if (numsons > 0)
237 {
238 // Proceed to the sons (if they exist)
239 for (unsigned i = 0; i < numsons; i++)
240 {
241 Son_pt[i]->traverse_leaves(member_function, mesh_pt);
242 }
243 }
244 else
245 {
246 // Call the member function
247 (this->*member_function)(mesh_pt);
248 }
249 }
250
251 //================================================================
252 /// Traverse Tree: Preorder traverse and stick pointers to leaf
253 /// nodes (only) into Vector
254 //=================================================================
256 {
257 // If the Tree has sons
258 unsigned numsons = Son_pt.size();
259 if (numsons > 0)
260 {
261 // Now do the sons (if they exist)
262 for (unsigned i = 0; i < numsons; i++)
263 {
264 Son_pt[i]->stick_leaves_into_vector(tree_nodes);
265 }
266 }
267 else
268 {
269 tree_nodes.push_back(this);
270 }
271 }
272
273 //================================================================
274 /// Traverse Tree: Preorder traverse and stick pointer to all
275 /// nodes (incl. "grey"=non-leaf ones) into Vector
276 //=================================================================
278 {
279 all_tree_nodes.push_back(this);
280
281 // If the Tree has sons
282 unsigned numsons = Son_pt.size();
283 if (numsons > 0)
284 {
285 // Now do the sons (if they exist)
286 for (unsigned i = 0; i < numsons; i++)
287 {
288 Son_pt[i]->stick_all_tree_nodes_into_vector(all_tree_nodes);
289 }
290 }
291 }
292
293 //================================================================
294 /// If required, kill the sons to perform unrefinement.
295 ///
296 /// Unrefinement is performed if
297 ///
298 /// object_pt()->sons_to_be_unrefined()
299 ///
300 /// returns true.
301 //=================================================================
303 {
304 // Check if unrefinement is required
306 {
307 // Rebuild the father from sons
308 object_pt()->rebuild_from_sons(mesh_pt);
309
310 // Find the number of sons
311 unsigned n_sons = nsons();
312 // Kill all the sons
313 for (unsigned ison = 0; ison < n_sons; ison++)
314 {
315 // Unbuild the element by marking the nodes as obsolete
316 son_pt(ison)->object_pt()->unbuild();
317
318 // Delete the object. This must be done here, because the
319 // destructor of a tree does not delete the leaf nodes
320 // (the actual elements that are used in the mesh).
321 // In general, the destruction of the leaf nodes is handled by the
322 // mesh destructors.
323 delete son_pt(ison)->object_pt();
324
325 // Now delete the tree representation
326 delete son_pt(ison);
327 }
328
329 Son_pt.resize(0);
330
331 // Have merged my sons -- can't do it again...
333 }
334 }
335
336 //===================================================================
337 /// Call the RefineableElement's deactivate_element() function that
338 /// is used to perform any final changes to internal data storage
339 /// of deactivated objects.
340 //===================================================================
342 {
343 // Call the function
345 }
346
347
348 //================================================================
349 /// Constructor for TreeForest:
350 ///
351 /// Pass:
352 /// - trees_pt[], the Vector of pointers to the constituent trees
353 /// (TreeRoot objects)
354 ///
355 /// Note that the pointers to the neighbour's of each tree must have
356 /// been allocated before the constructor is called, otherwise the
357 /// relative rotation scheme will not be constructed correctly.
358 //=================================================================
359 TreeForest::TreeForest(Vector<TreeRoot*>& trees_pt) : Trees_pt(trees_pt) {}
360
361 //================================================================
362 /// Kill tree forest: Delete the constituent trees
363 //=================================================================
365 {
366 long int numtrees = Trees_pt.size();
367 for (long int i = 0; i < numtrees; i++)
368 {
369 // Kill the trees
370 delete Trees_pt[i];
371 Trees_pt[i] = 0;
372 }
373 }
374
375 //================================================================
376 /// Traverse TreeForest: Preorder traverse and stick
377 /// pointers to leaf nodes (only) into Vector
378 //=================================================================
380 {
381 unsigned numtrees = ntree();
382 for (unsigned itree = 0; itree < numtrees; itree++)
383 {
384 // Now do the sons (if they exist)
385 unsigned numsons = tree_pt(itree)->nsons();
386 if (numsons > 0)
387 {
388 for (unsigned i = 0; i < numsons; i++)
389 {
390 tree_pt(itree)->son_pt(i)->stick_leaves_into_vector(forest_nodes);
391 }
392 }
393 else
394 {
395 forest_nodes.push_back(tree_pt(itree));
396 }
397 }
398 }
399
400
401 //================================================================
402 /// Traverse TreeForest: Preorder traverse and stick
403 /// pointers to all nodes into Vector
404 //=================================================================
406 Vector<Tree*>& all_forest_nodes)
407 {
408 unsigned numtrees = ntree();
409 for (unsigned itree = 0; itree < numtrees; itree++)
410 {
411 all_forest_nodes.push_back(tree_pt(itree));
412
413 // Now do the sons (if they exist)
414 unsigned numsons = tree_pt(itree)->nsons();
415 if (numsons > 0)
416 {
417 // Now do the sons (if they exist)
418 for (unsigned i = 0; i < numsons; i++)
419 {
421 all_forest_nodes);
422 }
423 }
424 }
425 }
426
427
428 //====================================================================
429 /// Close the hanging node output files and delete storage allocated at
430 /// the pointers. This can be done generically at the base level
431 //====================================================================
433 DocInfo& doc_info, Vector<std::ofstream*>& output_stream)
434 {
435 // Find the number of files
436 unsigned n_file = output_stream.size();
437 // If we opened the files, close them
438 if (doc_info.is_doc_enabled())
439 {
440 for (unsigned n = 0; n < n_file; n++)
441 {
442 output_stream[n]->close();
443 }
444 }
445
446 // We should have always created ofstreams, so delete them and null out
447 for (unsigned n = n_file; n > 0; n--)
448 {
449 delete output_stream[n - 1];
450 output_stream[n - 1] = 0;
451 }
452
453 // Finally clear out the vector
454 output_stream.clear();
455 }
456
457} // namespace oomph
cstr elem_len * i
Definition: cfortran.h:603
Information for documentation of results: Directory and file number to enable output in the form RESL...
bool is_doc_enabled() const
Are we documenting?
A general mesh class.
Definition: mesh.h:67
RefineableElements are FiniteElements that may be subdivided into children to provide a better local ...
virtual void rebuild_from_sons(Mesh *&mesh_pt)=0
Rebuild the element, e.g. set internal values in line with those of the sons that have now merged.
virtual void unbuild()
Unbuild the element, i.e. mark the nodes that were created during its creation for possible deletion.
virtual void deactivate_element()
Final operations that must be performed when the element is no longer active in the mesh,...
void set_tree_pt(Tree *my_tree_pt)
Set pointer to quadtree representation of this element.
bool sons_to_be_unrefined()
Has the element been selected for unrefinement?
void deselect_sons_for_unrefinement()
No unrefinement will be performed by merging the four sons of this element.
void stick_all_tree_nodes_into_vector(Vector< Tree * > &all_forest_nodes)
Traverse forest and stick pointers to all "nodes" into Vector.
Definition: tree.cc:405
unsigned ntree()
Number of trees in forest.
Definition: tree.h:460
void stick_leaves_into_vector(Vector< Tree * > &forest_nodes)
Traverse forst and stick pointers to leaf "nodes" into Vector.
Definition: tree.cc:379
Vector< TreeRoot * > Trees_pt
Vector containing the pointers to the trees.
Definition: tree.h:480
TreeRoot * tree_pt(const unsigned &i) const
Return pointer to i-th tree in forest.
Definition: tree.h:466
virtual ~TreeForest()
Destructor: Delete the constituent trees (and thus the objects associated with its non-leaf nodes!...
Definition: tree.cc:364
TreeForest()
Default constructor (empty and broken)
Definition: tree.h:416
void close_hanging_node_files(DocInfo &doc_info, Vector< std::ofstream * > &output_stream)
Close output files that will store any hanging nodes in the forest and delete any associated storage....
Definition: tree.cc:432
A generalised tree base class that abstracts the common functionality between the quad- and octrees u...
Definition: tree.h:74
Tree * Father_pt
Pointer to the Father of the Tree.
Definition: tree.h:296
void traverse_leaves(Tree::VoidMemberFctPt member_function)
Traverse the tree and execute void Tree member function member_function() only at its leaves.
Definition: tree.cc:207
void stick_all_tree_nodes_into_vector(Vector< Tree * > &)
Traverse and stick pointers to all "nodes" into Vector.
Definition: tree.cc:277
unsigned nsons() const
Return number of sons (zero if it's a leaf node)
Definition: tree.h:129
void traverse_all(Tree::VoidMemberFctPt member_function)
Traverse the tree and execute void Tree member function member_function() at all its "nodes".
Definition: tree.cc:145
void(Tree::* VoidMeshPtArgumentMemberFctPt)(Mesh *&mesh_pt)
Function pointer to a void Tree member function that takes a pointer to a mesh as its argument.
Definition: tree.h:182
TreeRoot * Root_pt
Pointer to the root of the tree.
Definition: tree.h:292
RefineableElement * Object_pt
Pointer to the object represented by the tree.
Definition: tree.h:308
void(Tree::* VoidMemberFctPt)()
Function pointer to argument-free void Tree member function.
Definition: tree.h:178
int son_type() const
Return son type.
Definition: tree.h:214
RefineableElement * object_pt() const
Return the pointer to the object (RefineableElement) represented by the tree.
Definition: tree.h:88
int Son_type
Son type (e.g. SW/SE/NW/NE in a quadtree)
Definition: tree.h:305
Tree * son_pt(const int &son_index) const
Return pointer to the son for a given index. Note that to aid code readability specific enums have be...
Definition: tree.h:103
int Level
Level of the Tree (level 0 = root)
Definition: tree.h:302
static const int OMEGA
Default value for an unassigned neighbour.
Definition: tree.h:262
Tree * father_pt() const
Return pointer to father: NULL if it's a root node.
Definition: tree.h:235
Vector< Tree * > Son_pt
Vector of pointers to the sons of the Tree.
Definition: tree.h:299
void stick_leaves_into_vector(Vector< Tree * > &)
Traverse tree and stick pointers to leaf "nodes" (only) into Vector.
Definition: tree.cc:255
virtual ~Tree()
Destructor. Note: Deleting a tree also deletes the objects associated with its non-leave nodes.
Definition: tree.cc:122
Tree()
Default constructor (empty and broken)
Definition: tree.h:266
void deactivate_object()
Call the RefineableElement's deactivate_element() function.
Definition: tree.cc:341
void traverse_all_but_leaves(Tree::VoidMemberFctPt member_function)
Traverse the tree and execute void Tree member function member_function() at all its "nodes" aparat f...
Definition: tree.cc:184
static double Max_neighbour_finding_tolerance
Max. allowed discrepancy in neighbour finding routine (distance between points when identified from t...
Definition: tree.h:313
void merge_sons_if_required(Mesh *&mesh_pt)
If required, merge the four sons for unrefinement – criterion: bool object_pt()-> sons_to_be_unrefine...
Definition: tree.cc:302
A slight extension to the standard template vector class so that we can include "graceful" array rang...
Definition: Vector.h:58
//////////////////////////////////////////////////////////////////// ////////////////////////////////...