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