tree.h
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 //Header file for generic tree structures
31 #ifndef OOMPH_TREE_HEADER
32 #define OOMPH_TREE_HEADER
33 
34 // Config header generated by autoconfig
35 #ifdef HAVE_CONFIG_H
36  #include <oomph-lib-config.h>
37 #endif
38 
39 #ifdef OOMPH_HAS_MPI
40 #include "mpi.h"
41 #endif
42 
43 //OOMPH-LIB headers
44 #include "Vector.h"
45 #include "map_matrix.h"
46 
47 namespace oomph
48 {
49 
50 
51 // Forward class definition for class representing the root of a Tree
52 class TreeRoot;
53 
54 class RefineableElement;
55 
56 class Mesh;
57 
58 //========================================================================
59 /// A generalised tree base class that abstracts the common functionality
60 /// between the quad- and octrees used in mesh adaptation in two and
61 /// three dimensions, respectively.
62 ///
63 /// The tree can also be part of a forest. If that is the case, the root
64 /// of the tree will have pointers to the roots of neighbouring trees.
65 ///
66 /// The objects contained in the tree must be RefineableElements.
67 ///
68 /// The tree can be traversed and actions performed
69 /// at all its "nodes" or only at the leaf "nodes" ("nodes" without sons).
70 ///
71 /// Finally, the leaf "nodes" can be split depending on
72 /// a criteria defined by the object.
73 ///
74 /// Note that Trees are only generated by splitting existing
75 /// Trees. Therefore, the constructors are protected. The
76 /// only Tree that "Joe User" can create is
77 /// the (derived) class TreeRoot.
78 //=================================================================
79 class Tree
80 {
81  public:
82 
83 
84  /// \short Destructor. Note: Deleting a tree also deletes the
85  /// objects associated with its non-leave nodes.
86  virtual ~Tree();
87 
88  /// Broken copy constructor
89  Tree(const Tree& dummy)
90  {
92  }
93 
94  /// Broken assignment operator
95  void operator=(const Tree&)
96  {
98  }
99 
100  /// \short Return the pointer to the object (RefineableElement)
101  /// represented by the tree
103 
104  /// Flush the object represented by the tree
106  {
107  Object_pt=0;
108  }
109 
110  /// \short Return pointer to the son for a given index. Note that
111  /// to aid code readability specific enums have been defined for
112  /// specific trees. However, these are simply aliases for ints and
113  /// the general interface can be implemented once, here.
114  Tree* son_pt(const int& son_index) const
115  {
116  //If there are no sons, return NULL (0)
117  if(Son_pt.size()==0) {return 0;}
118  //Otherwise, return the pointer to the appropriate son
119  else {return Son_pt[son_index];}
120  }
121 
122 
123  /// \short Set vector of pointers to sons, indexed by the
124  /// appropriate enum that identies son types.
125  /// (To aid code readability specific enums have been defined for
126  /// specific trees. However, these are simply aliases for ints and
127  /// the general interface can be implemented once, here).
129  {
130  Son_pt=son_pt;
131  }
132 
133  /// Return number of sons (zero if it's a leaf node)
134  unsigned nsons() const {return Son_pt.size();}
135 
136  /// Flush the sons
137  void flush_sons()
138  {
139  Son_pt.clear();
140  }
141 
142  /// Return pointer to root of the tree
143  TreeRoot*& root_pt() {return Root_pt;}
144 
145  /// Return pointer to root of the tree (const version)
146  TreeRoot* root_pt() const {return Root_pt;}
147 
148  ///\short If required, split the leaf and create its sons --
149  /// criterion: bool object_pt()-> to_be_refined() = true
150  template<class ELEMENT>
151  void split_if_required();
152 
153  ///\short If required, p-refine the leaf --
154  /// criterion: bool object_pt()-> to_be_p_refined() = true
155  /// or bool object_pt()-> to_be_p_unrefined() = true
156  template<class ELEMENT>
157  void p_refine_if_required(Mesh* &mesh_pt);
158 
159  /// \short If required, merge the four sons for unrefinement --
160  /// criterion: bool object_pt()-> sons_to_be_unrefined() = true
161  void merge_sons_if_required(Mesh* &mesh_pt);
162 
163  /// \short Call the RefineableElement's deactivate_element() function.
164  void deactivate_object();
165 
166  /// \short A function that constructs a specific type of tree. This
167  /// MUST be overloaded for each specific tree type. The use of such a
168  /// function allows the generic implementation of split_if_required().
170  Tree* const &father_pt, const int &son_type)=0;
171 
172  /// Function pointer to argument-free void Tree member function
173  typedef void (Tree::* VoidMemberFctPt)();
174 
175  /// Function pointer to a void Tree member function that takes a
176  /// pointer to a mesh as its argument
177  typedef void (Tree::* VoidMeshPtArgumentMemberFctPt)(Mesh* &mesh_pt);
178 
179 
180  /// \short Traverse the tree and execute void Tree member function
181  /// member_function() at all its "nodes"
182  void traverse_all(Tree::VoidMemberFctPt member_function);
183 
184  /// \short Traverse the tree and excute void Tree member function
185  /// that takes a pointer to a mesh as an argument
187  Mesh* &mesh_pt);
188 
189  /// \short Traverse the tree and execute void Tree member function
190  /// member_function() at all its "nodes" aparat from the leaves
191  void traverse_all_but_leaves(Tree::VoidMemberFctPt member_function);
192 
193  /// \short Traverse the tree and execute void Tree member function
194  /// member_function() only at its leaves
195  void traverse_leaves(Tree::VoidMemberFctPt member_function);
196 
197  /// \short Traverse the tree and execute void Tree member function
198  /// that takes a pointer to a mesh as an argument only at its leaves
200  Mesh* &mesh_pt);
201 
202  /// Traverse tree and stick pointers to leaf "nodes" (only) into Vector
204 
205  /// Traverse and stick pointers to all "nodes" into Vector
207 
208  /// Return son type
209  int son_type() const {return Son_type;}
210 
211  /// Return true if the tree is a leaf node
212  bool is_leaf()
213  {
214  //If there are no sons, it's a leaf, return true
215  if (Son_pt.size()==0) {return true;}
216  //Otherwise return false
217  else {return false;}
218  }
219 
220  /// Return pointer to father: NULL if it's a root node
221  Tree* father_pt() const {return Father_pt;}
222 
223  /// Set the father
225  {
227  }
228 
229  /// \short Return the level of the Tree (root=0)
230  unsigned level() const {return Level;}
231 
232  /// \short Max. allowed discrepancy in neighbour finding routine
233  /// (distance between points when identified from two neighbouring
234  /// elements)
237 
238  public:
239 
240  /// Default value for an unassigned neighbour
241  static const int OMEGA;
242 
243  protected:
244 
245  /// Default constructor (empty and broken)
247  {
248  //Throw an error
249  throw OomphLibError("Don't call an empty constructor for a Tree object",
250  OOMPH_CURRENT_FUNCTION,OOMPH_EXCEPTION_LOCATION);
251  }
252 
253  /// \short Default constructor for empty (root) tree:
254  /// no father, no sons; just pass a pointer to its object
255  /// Protected because Trees can only be created internally,
256  /// during the split operation. Only TreeRoots can be
257  /// created externally.
259 
260  /// \short Constructor for tree that has a father: Pass it the pointer
261  /// to its object, the pointer to its father and tell it what type
262  /// of son it is.
263  /// Protected because Trees can only be created internally,
264  /// during the split operation. Only TreeRoots can be
265  /// created externally.
267  Tree* const &father_pt, const int& son_type);
268 
269  /// Pointer to the root of the tree
271 
272  protected:
273 
274  /// Pointer to the Father of the Tree
276 
277  /// Vector of pointers to the sons of the Tree
279 
280  /// Level of the Tree (level 0 = root)
281  int Level;
282 
283  /// Son type (e.g. SW/SE/NW/NE in a quadtree)
284  int Son_type;
285 
286  /// Pointer to the object represented by the tree
288 
289  /// \short Max. allowed discrepancy in neighbour finding routine
290  /// (distance between points when identified from two neighbouring
291  /// elements)
293 
294 };
295 
296 
297 //===================================================================
298 /// TreeRoot is a Tree that forms the root of a (recursive)
299 /// tree. The "root node" is special as it holds additional
300 /// information about its neighbours and their relative
301 /// rotation (inside a TreeForest).
302 //==================================================================
303 class TreeRoot : public virtual Tree
304 {
305  protected:
306 
307  /// \short Map of pointers to the neighbouring TreeRoots:
308  /// Neighbour_pt[direction] returns the pointer to the
309  /// TreeRoot's neighbour in the (enumerated) direction.
310  /// Returns NULL if there's no neighbour in this direction.
311  std::map<int,TreeRoot*> Neighbour_pt;
312 
313 
314  /// \short Map of booleans used for periodic boundaries:
315  /// Neighbour_periodic_direction[directon] returns true if the
316  /// neighbour in that direction is actually a periodic neighbour
317  /// --- shared data values, but independent position.
318  /// The default return of the map is false.
319  std::map<int,bool> Neighbour_periodic;
320 
321  public:
322 
323  ///Constructor for the (empty) root tree
324  TreeRoot(RefineableElement* const &object_pt) : Tree(object_pt)
325  {
326  //TreeRoot is the Root
327  Root_pt = this;
328  }
329 
330 
331  /// Broken copy constructor
332  TreeRoot(const TreeRoot& dummy)
333  {
334  BrokenCopy::broken_copy("TreeRoot");
335  }
336 
337  /// Broken assignment operator
338  void operator=(const TreeRoot&)
339  {
340  BrokenCopy::broken_assign("TreeRoot");
341  }
342 
343  /// \short Return the pointer to the neighbouring TreeRoots in specified
344  /// direction. Returns NULL if there's no neighbour in this direction.
345  TreeRoot* &neighbour_pt(const int &direction)
346  {return Neighbour_pt[direction];}
347 
348  /// \short Return whether the neighbour in the particular direction
349  /// is periodic.
350  bool is_neighbour_periodic(const int &direction)
351  {return Neighbour_periodic[direction];}
352 
353  ///\short Set the neighbour in particular direction to be periodic
354  void set_neighbour_periodic(const int &direction)
355  {Neighbour_periodic[direction] = true;}
356 
357  ///\short Set the neighbour in particular direction to be nonperiodic
358  void set_neighbour_nonperiodic(const int &direction)
359  {Neighbour_periodic[direction] = false;}
360 
361  ///Return the number of neighbours
362  unsigned nneighbour()
363  {
364  //Loop over the neighbours and test whether they are non-null
365  unsigned count=0;
366  for(std::map<int,TreeRoot*>::iterator it=Neighbour_pt.begin();
367  it!=Neighbour_pt.end();it++)
368  {
369  if(Neighbour_pt[it->first]!=0) {count++;}
370  }
371  //Return number counted
372  return count;
373  }
374 
375 };
376 
377 
378 //================================================================
379 /// A TreeForest consists of a collection of TreeRoots.
380 /// Each member tree can have neighbours in various enumerated
381 /// directions (e.g. S/W/N/E for a QuadTreeForest)
382 /// and the orientation of their compasses can differ, allowing
383 /// for complex, unstructured meshes.
384 //=================================================================
386 {
387  public:
388 
389  /// \short Constructor for Tree forest: Pass Vector of
390  /// (pointers to) constituents trees.
391  TreeForest(Vector<TreeRoot*>& trees_pt);
392 
393  /// Default constructor (empty and broken)
395  {
396  //Throw an error
397  throw OomphLibError(
398  "Don't call an empty constructor for a TreeForest object",
399  OOMPH_CURRENT_FUNCTION,OOMPH_EXCEPTION_LOCATION);
400  }
401 
402  /// Broken copy constructor
403  TreeForest(const TreeForest& dummy)
404  {
405  BrokenCopy::broken_copy("TreeForest");
406  }
407 
408  /// Broken assignment operator
409  void operator=(const TreeForest&)
410  {
411  BrokenCopy::broken_assign("TreeForest");
412  }
413 
414  /// \short Destructor: Delete the constituent trees (and thus
415  /// the objects associated with its non-leaf nodes!)
416  virtual ~TreeForest();
417 
418  /// Traverse forst and stick pointers to leaf "nodes" into Vector
419  void stick_leaves_into_vector(Vector<Tree* >& forest_nodes);
420 
421  /// Traverse forest and stick pointers to all "nodes" into Vector
423  all_forest_nodes);
424 
425  /// \short Document/check the neighbours of all the nodes in the forest.
426  /// This must be overloaded for different types of forest.
427  virtual void check_all_neighbours(DocInfo &doc_info)=0;
428 
429  /// \short Open output files that will store any hanging nodes in the
430  /// forest. Return a vector of the output streams. This is included in
431  /// the tree structure, so that we can use generic routines for
432  /// mesh adaptation in two and three dimensions. The need for pointers
433  /// to the output streams is because one cannot copy a stream!
434  virtual void open_hanging_node_files(DocInfo &doc_info,
436  &output_stream)=0;
437 
438  /// \short Close output files that will store any hanging nodes in the
439  /// forest and delete any associated storage.
440  /// This can be performed genercially in this base class.
441  void close_hanging_node_files(DocInfo &doc_info,
443  &output_stream);
444 
445  /// Number of trees in forest
446  unsigned ntree() {return Trees_pt.size();}
447 
448  /// Return pointer to i-th tree in forest
449  TreeRoot* tree_pt(const unsigned &i) const {return Trees_pt[i];}
450 
451  /// Flush trees from forest
452  void flush_trees()
453  {
454  // Clear Trees_pt vector
455  Trees_pt.clear();
456  }
457 
458  protected:
459 
460  /// Vector containing the pointers to the trees
462 
463 };
464 
465 }
466 
467 #endif
468 
Vector< Tree * > Son_pt
Vector of pointers to the sons of the Tree.
Definition: tree.h:278
virtual void open_hanging_node_files(DocInfo &doc_info, Vector< std::ofstream * > &output_stream)=0
Open output files that will store any hanging nodes in the forest. Return a vector of the output stre...
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
static double & max_neighbour_finding_tolerance()
Max. allowed discrepancy in neighbour finding routine (distance between points when identified from t...
Definition: tree.h:235
unsigned ntree()
Number of trees in forest.
Definition: tree.h:446
void broken_copy(const std::string &class_name)
Issue error message and terminate execution.
TreeRoot(RefineableElement *const &object_pt)
Constructor for the (empty) root tree.
Definition: tree.h:324
TreeRoot *& neighbour_pt(const int &direction)
Return the pointer to the neighbouring TreeRoots in specified direction. Returns NULL if there's no n...
Definition: tree.h:345
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 set_son_pt(const Vector< Tree * > &son_pt)
Set vector of pointers to sons, indexed by the appropriate enum that identies son types...
Definition: tree.h:128
void deactivate_object()
Call the RefineableElement's deactivate_element() function.
Definition: tree.cc:338
virtual Tree * construct_son(RefineableElement *const &object_pt, Tree *const &father_pt, const int &son_type)=0
A function that constructs a specific type of tree. This MUST be overloaded for each specific tree ty...
unsigned nsons() const
Return number of sons (zero if it's a leaf node)
Definition: tree.h:134
Information for documentation of results: Directory and file number to enable output in the form RESL...
void flush_sons()
Flush the sons.
Definition: tree.h:137
TreeForest()
Default constructor (empty and broken)
Definition: tree.h:394
cstr elem_len * i
Definition: cfortran.h:607
void flush_trees()
Flush trees from forest.
Definition: tree.h:452
bool is_neighbour_periodic(const int &direction)
Return whether the neighbour in the particular direction is periodic.
Definition: tree.h:350
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 operator=(const TreeRoot &)
Broken assignment operator.
Definition: tree.h:338
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
void set_father_pt(Tree *const &father_pt)
Set the father.
Definition: tree.h:224
void traverse_all_but_leaves(Tree::VoidMemberFctPt member_function)
Traverse the tree and execute void Tree member function.
Definition: tree.cc:188
TreeRoot * root_pt() const
Return pointer to root of the tree (const version)
Definition: tree.h:146
TreeRoot(const TreeRoot &dummy)
Broken copy constructor.
Definition: tree.h:332
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 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 set_neighbour_periodic(const int &direction)
Set the neighbour in particular direction to be periodic.
Definition: tree.h:354
unsigned nneighbour()
Return the number of neighbours.
Definition: tree.h:362
Tree(const Tree &dummy)
Broken copy constructor.
Definition: tree.h:89
void set_neighbour_nonperiodic(const int &direction)
Set the neighbour in particular direction to be nonperiodic.
Definition: tree.h:358
std::map< int, TreeRoot * > Neighbour_pt
Map of pointers to the neighbouring TreeRoots: Neighbour_pt[direction] returns the pointer to the Tre...
Definition: tree.h:311
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 broken_assign(const std::string &class_name)
Issue error message and terminate execution.
void operator=(const Tree &)
Broken assignment operator.
Definition: tree.h:95
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
void operator=(const TreeForest &)
Broken assignment operator.
Definition: tree.h:409
TreeForest(const TreeForest &dummy)
Broken copy constructor.
Definition: tree.h:403
virtual void check_all_neighbours(DocInfo &doc_info)=0
Document/check the neighbours of all the nodes in the forest. This must be overloaded for different t...
void p_refine_if_required(Mesh *&mesh_pt)
If required, p-refine the leaf – criterion: bool object_pt()-> to_be_p_refined() = true or bool objec...
unsigned level() const
Return the level of the Tree (root=0)
Definition: tree.h:230
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
bool is_leaf()
Return true if the tree is a leaf node.
Definition: tree.h:212
Tree()
Default constructor (empty and broken)
Definition: tree.h:246
void split_if_required()
If required, split the leaf and create its sons – criterion: bool object_pt()-> to_be_refined() = tru...
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
std::map< int, bool > Neighbour_periodic
Map of booleans used for periodic boundaries: Neighbour_periodic_direction[directon] returns true if ...
Definition: tree.h:319
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
TreeRoot *& root_pt()
Return pointer to root of the tree.
Definition: tree.h:143
void flush_object()
Flush the object represented by the tree.
Definition: tree.h:105