binary_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 binary tree and binary tree forest classes
31 #ifndef OOMPH_BINARY_TREE_HEADER
32 #define OOMPH_BINARY_TREE_HEADER
33 
34 // Config header generated by autoconfig
35 #ifdef HAVE_CONFIG_H
36  #include <oomph-lib-config.h>
37 #endif
38 
39 // oomph-lib headers
40 #include "tree.h"
41 #include "matrices.h"
42 
43 namespace oomph
44 {
45  //======================================================================
46  /// Namespace for BinaryTree directions
47  //======================================================================
48  namespace BinaryTreeNames
49  {
50  /// \short Directions (L/R). OMEGA is used if a direction is undefined
51  /// in a certain context
52  enum{L,R,OMEGA=26};
53  };
54 
55  // Forward class definition for class representing the root of a BinaryTree
56  class BinaryTreeRoot;
57 
58  //======================================================================
59  /// BinaryTree class: Recursively defined, generalised binary tree.
60  ///
61  /// A BinaryTree has:
62  /// - a pointer to the object (of type RefineableQElement<1>) that it
63  /// represents in a mesh refinement context.
64  /// - a Vector of pointers to its two (L/R) sons (which are
65  /// themselves binary trees). If the Vector of pointers to the sons
66  /// has zero length, the BinaryTree is a "leaf node" in the overall
67  /// binary tree.
68  /// - a pointer to its father. If this pointer is NULL, the BinaryTree
69  /// is the root node of the overall binary tree.
70  /// This data is stored in the Tree base class.
71  ///
72  /// The tree can also be part of a forest. If that is the case, the root
73  /// will have pointers to the roots of neighbouring binary trees.
74  ///
75  /// The objects contained in the binary tree are assumed to be
76  /// line elements whose geometry is parametrised by local coordinates
77  /// \f$ {\bf s} \in [-1,1] \f$.
78  ///
79  /// The tree can be traversed and actions performed at all its
80  /// "nodes" or only at the leaf "nodes" ("nodes" without sons).
81  ///
82  /// Finally, the leaf "nodes" can be split depending on
83  /// a criteria defined by the object.
84  ///
85  /// Note that BinaryTrees are only generated by splitting existing
86  /// BinaryTrees. Therefore, the constructors are protected. The
87  /// only BinaryTree that "Joe User" can create is the (derived) class
88  /// BinaryTreeRoot.
89  //======================================================================
90  class BinaryTree : public virtual Tree
91  {
92  public:
93 
94  /// \short Destructor. Note: Deleting a binary tree also deletes the
95  /// objects associated with all non-leaf nodes!
96  virtual ~BinaryTree() {}
97 
98  /// Broken copy constructor
99  BinaryTree(const BinaryTree& dummy)
100  {
101  BrokenCopy::broken_copy("BinaryTree");
102  }
103 
104  /// Broken assignment operator
105  void operator=(const BinaryTree&)
106  {
107  BrokenCopy::broken_assign("BinaryTree");
108  }
109 
110  /// \short Overload the function construct_son to ensure that the son
111  /// is a specific BinaryTree and not a general Tree.
113  Tree* const &father_pt, const int &son_type)
114  {
115  BinaryTree* temp_binary_pt = new BinaryTree(object_pt,father_pt,son_type);
116  return temp_binary_pt;
117  }
118 
119  /// \short Return pointer to greater or equal-sized edge neighbour
120  /// in specified \c direction; also provide info regarding the relative
121  /// size of the neighbour:
122  /// - In the present binary tree, the left vertex is located at the local
123  /// coordinate s = -1. This point is located at the local coordinate
124  /// s = \c s_in_neighbour[0] in the neighbouring binary tree.
125  /// - We're looking for a neighbour in the specified \c direction. When
126  /// viewed from the neighbouring binary tree, the edge that separates
127  /// the present binary tree from its neighbour is the neighbour's
128  /// \c edge edge. Since in 1D there can be no rotation between the two
129  /// binary trees, this is a simple reflection. For instance, if we're
130  /// looking for a neighhbour in the \c L [eft] \c direction, \c edge
131  /// will be \c R [ight].
132  /// - \c diff_level <= 0 indicates the difference in refinement levels
133  /// between the two neighbours. If \c diff_level==0, the neighbour
134  /// has the same size as the current binary tree.
135  /// - \c in_neighbouring_tree indicates whether the neighbour is actually
136  /// in another tree in the forest. The introduction of this flag
137  /// was necessitated by periodic problems where a TreeRoot can be its
138  /// own neighbour.
139  BinaryTree* gteq_edge_neighbour(const int& direction,
140  Vector<double>& s_in_neighbour,
141  int& edge, int& diff_level,
142  bool &in_neighbouring_tree) const;
143 
144  /// \short Self-test: Check all neighbours. Return success (0)
145  /// if the maximum distance between corresponding points in the
146  /// neighbours is less than the tolerance specified in the
147  /// static value BinaryTree::Max_neighbour_finding_tolerance.
148  unsigned self_test();
149 
150  /// \short Set up the static data, reflection schemes, etc.
151  static void setup_static_data();
152 
153  /// \short Doc/check all neighbours of binary tree (nodes) contained in the
154  /// Vector forest_node_pt. Output into neighbours_file which can be viewed
155  /// from tecplot with BinaryTreeNeighbours.mcr. Neighbour info and errors
156  /// are displayed on neighbours_txt_file. Finally, compute the maximum
157  /// error between vertices when viewed from the neighbouring element.
158  /// If the two filestreams are closed, output is suppressed.
159  static void doc_neighbours(Vector<Tree*> forest_nodes_pt,
160  std::ofstream& neighbours_file,
161  std::ofstream& neighbours_txt_file,
162  double& max_error);
163 
164  /// Translate (enumerated) directions into strings
166 
167 protected:
168 
169  /// Default constructor (empty and broken)
171  {
172  throw OomphLibError
173  ("Don't call an empty constructor for a BinaryTree object",
174  OOMPH_CURRENT_FUNCTION,OOMPH_EXCEPTION_LOCATION);
175  }
176 
177  /// \short Default constructor for empty (root) tree: no father, no sons;
178  /// just pass a pointer to its object. Protected because BinaryTrees can
179  /// only be created internally, during the split operation. Only
180  /// BinaryTreeRoots can be created externally.
181  BinaryTree(RefineableElement* const &object_pt) : Tree(object_pt) {}
182 
183  /// \short Constructor for tree that has a father: Pass it the pointer
184  /// to its object, the pointer to its father and tell it what type of son
185  /// (L/R) it is. Protected because BinaryTrees can only be created
186  /// internally, during the split operation. Only BinaryTreeRoots can be
187  /// created externally.
189  Tree* const &father_pt, const int& son_type)
190  : Tree(object_pt,father_pt,son_type) {}
191 
192  /// Boolean indicating that static member data has been setup
194 
195  private:
196 
197  /// \short Find greater or equal-sized edge neighbour in direction.
198  /// Auxiliary internal routine which passes additional information around.
199  BinaryTree* gteq_edge_neighbour(const int& direction,
200  double& s_diff,
201  int& diff_level,
202  bool& in_neighbouring_tree,
203  int max_level,
204  BinaryTreeRoot* const &orig_root_pt) const;
205 
206  /// Colours for neighbours in various directions
208 
209  /// \short S_base(direction): Initial value for coordinate s on the edge
210  /// indicated by direction (L/R)
212 
213  /// Get opposite edge, e.g. Reflect_edge[L]=R
215 
216  /// \short Array of direction/segment adjacency scheme:
217  /// Is_adjacent(i_vertex,j_segment): Is vertex adjacent to segment?
219 
220  /// \short Reflection scheme: Reflect(direction,segment): Get mirror
221  /// of segment in specified direction. E.g. Reflect(L,L)=R.
223 
224  };
225 
226 
227  //======================================================================
228  /// BinaryTreeRoot is a BinaryTree that forms the root of a (recursive)
229  /// binary tree. The "root node" is special as it holds additional
230  /// information about its neighbours.
231  //======================================================================
232  class BinaryTreeRoot : public virtual BinaryTree, public virtual TreeRoot
233  {
234 
235  public:
236 
237  /// Constructor for the (empty) root binary tree: Pass pointer to
238  /// associated object, a RefineableQElement<1>.
240  BinaryTree(object_pt), TreeRoot(object_pt)
241  {
242 
243 #ifdef PARANOID
244  // Check that static member data has been setup
246  {
247  std::string error_message =
248  "Static member data hasn't been setup yet.\n";
249  error_message +=
250  "Call BinaryTree::setup_static_data() before creating\n";
251  error_message += "any BinaryTreeRoots\n";
252 
253  throw OomphLibError(error_message,
254  OOMPH_CURRENT_FUNCTION,
255  OOMPH_EXCEPTION_LOCATION);
256  }
257 #endif
258 
259  }
260 
261  /// Broken copy constructor
262  BinaryTreeRoot(const BinaryTreeRoot& dummy) : TreeRoot(dummy)
263  {
264  BrokenCopy::broken_copy("BinaryTreeRoot");
265  }
266 
267  /// Broken assignment operator
268  void operator=(const BinaryTreeRoot&)
269  {
270  BrokenCopy::broken_assign("BinaryTreeRoot");
271  }
272 
273  /// \short If binary_tree_root_pt is a neighbour, return the direction
274  /// (L/R) in which it is found, otherwise return OMEGA
275  int direction_of_neighbour(BinaryTreeRoot* binary_tree_root_pt)
276  {
277  using namespace BinaryTreeNames;
278 
279  if(Neighbour_pt[L]==binary_tree_root_pt) { return L; }
280  if(Neighbour_pt[R]==binary_tree_root_pt) { return R; }
281 
282  // If we get here, it's not a neighbour
283  return OMEGA;
284  }
285 
286  };
287 
288 
289  //======================================================================
290  /// A BinaryTreeForest consists of a collection of BinaryTreeRoots.
291  /// Each member tree can have neighbours to its left and right.
292  //======================================================================
294  {
295 
296  public:
297 
298  /// Default constructor (empty and broken)
300  {
301  //Throw an error
302  throw OomphLibError(
303  "Don't call an empty constructor for a BinaryTreeForest object",
304  OOMPH_CURRENT_FUNCTION,OOMPH_EXCEPTION_LOCATION);
305  }
306 
307  /// \short Constructor: Pass vector of pointers to the roots of the
308  /// constituent BinaryTrees
310 
311  /// Broken copy constructor
313  {
314  BrokenCopy::broken_copy("BinaryTreeForest");
315  }
316 
317  /// Broken assignment operator
319  {
320  BrokenCopy::broken_assign("BinaryTreeForest");
321  }
322 
323  /// \short Destructor: Delete the constituent binary trees (and thus
324  /// the objects associated with its non-leaf nodes!)
325  virtual ~BinaryTreeForest() {}
326 
327  /// \short Document and check all the neighbours of all the nodes in
328  /// the forest. DocInfo object specifies the output directory and file
329  /// numbers for the various files. If \c doc_info.disable_doc() has been
330  /// called, no output is created.
331  void check_all_neighbours(DocInfo &doc_info);
332 
333  /// A line mesh cannot have hanging nodes so make this function empty
335  Vector<std::ofstream*> &output_stream) {}
336 
337  /// \short Self-test: Check all neighbours. Return success (0) if the
338  /// maximum distance between corresponding points in the neighbours is
339  /// less than the tolerance specified in the static value
340  /// BinaryTree::Max_neighbour_finding_tolerance.
341  unsigned self_test();
342 
343  private:
344 
345  /// Construct the neighbour lookup scheme
346  void find_neighbours();
347 
348  /// Return pointer to i-th root binary tree in this forest (performs
349  /// a dynamic cast from the TreeRoot to a BinaryTreeRoot).
350  BinaryTreeRoot* binary_tree_pt(const unsigned &i)
351  { return dynamic_cast<BinaryTreeRoot*>(Trees_pt[i]); }
352 
353  /// \short Given the number i of the root binary tree in this forest,
354  /// return a pointer to its neighbour in the specified direction.
355  /// NULL if neighbour doesn't exist. (This does the dynamic cast
356  /// from a TreeRoot to a BinaryTreeRoot internally).
357  BinaryTreeRoot* binary_neigh_pt(const unsigned &i, const int &direction)
358  {
359  return dynamic_cast<BinaryTreeRoot*>(Trees_pt[i]->neighbour_pt(direction));
360  }
361 
362  };
363 
364 } // End of namespace
365 
366 #endif
367 
void open_hanging_node_files(DocInfo &doc_info, Vector< std::ofstream * > &output_stream)
A line mesh cannot have hanging nodes so make this function empty.
Definition: binary_tree.h:334
void broken_copy(const std::string &class_name)
Issue error message and terminate execution.
Tree * construct_son(RefineableElement *const &object_pt, Tree *const &father_pt, const int &son_type)
Overload the function construct_son to ensure that the son is a specific BinaryTree and not a general...
Definition: binary_tree.h:112
RefineableElement * object_pt() const
Return the pointer to the object (RefineableElement) represented by the tree.
Definition: tree.h:102
static bool Static_data_has_been_setup
Boolean indicating that static member data has been setup.
Definition: binary_tree.h:193
static void doc_neighbours(Vector< Tree * > forest_nodes_pt, std::ofstream &neighbours_file, std::ofstream &neighbours_txt_file, double &max_error)
Doc/check all neighbours of binary tree (nodes) contained in the Vector forest_node_pt. Output into neighbours_file which can be viewed from tecplot with BinaryTreeNeighbours.mcr. Neighbour info and errors are displayed on neighbours_txt_file. Finally, compute the maximum error between vertices when viewed from the neighbouring element. If the two filestreams are closed, output is suppressed.
Definition: binary_tree.cc:666
Information for documentation of results: Directory and file number to enable output in the form RESL...
BinaryTree(const BinaryTree &dummy)
Broken copy constructor.
Definition: binary_tree.h:99
cstr elem_len * i
Definition: cfortran.h:607
BinaryTreeRoot(const BinaryTreeRoot &dummy)
Broken copy constructor.
Definition: binary_tree.h:262
static Vector< std::string > Direct_string
Translate (enumerated) directions into strings.
Definition: binary_tree.h:165
BinaryTree(RefineableElement *const &object_pt)
Default constructor for empty (root) tree: no father, no sons; just pass a pointer to its object...
Definition: binary_tree.h:181
BinaryTreeRoot * binary_neigh_pt(const unsigned &i, const int &direction)
Given the number i of the root binary tree in this forest, return a pointer to its neighbour in the s...
Definition: binary_tree.h:357
BinaryTree * gteq_edge_neighbour(const int &direction, Vector< double > &s_in_neighbour, int &edge, int &diff_level, bool &in_neighbouring_tree) const
Return pointer to greater or equal-sized edge neighbour in specified direction; also provide info reg...
Definition: binary_tree.cc:179
BinaryTreeRoot * binary_tree_pt(const unsigned &i)
Definition: binary_tree.h:350
static void setup_static_data()
Set up the static data, reflection schemes, etc.
Definition: binary_tree.cc:90
static DenseMatrix< int > Reflect
Reflection scheme: Reflect(direction,segment): Get mirror of segment in specified direction...
Definition: binary_tree.h:222
static Vector< std::string > Colour
Colours for neighbours in various directions.
Definition: binary_tree.h:207
BinaryTree(RefineableElement *const &object_pt, Tree *const &father_pt, const int &son_type)
Constructor for tree that has a father: Pass it the pointer to its object, the pointer to its father ...
Definition: binary_tree.h:188
void operator=(const BinaryTreeForest &)
Broken assignment operator.
Definition: binary_tree.h:318
static DenseMatrix< bool > Is_adjacent
Array of direction/segment adjacency scheme: Is_adjacent(i_vertex,j_segment): Is vertex adjacent to s...
Definition: binary_tree.h:218
void operator=(const BinaryTree &)
Broken assignment operator.
Definition: binary_tree.h:105
BinaryTree()
Default constructor (empty and broken)
Definition: binary_tree.h:170
BinaryTreeForest()
Default constructor (empty and broken)
Definition: binary_tree.h:299
int direction_of_neighbour(BinaryTreeRoot *binary_tree_root_pt)
If binary_tree_root_pt is a neighbour, return the direction (L/R) in which it is found, otherwise return OMEGA.
Definition: binary_tree.h:275
static Vector< int > Reflect_edge
Get opposite edge, e.g. Reflect_edge[L]=R.
Definition: binary_tree.h:214
static Vector< double > S_base
S_base(direction): Initial value for coordinate s on the edge indicated by direction (L/R) ...
Definition: binary_tree.h:211
BinaryTreeForest(const BinaryTreeForest &dummy)
Broken copy constructor.
Definition: binary_tree.h:312
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
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.
std::string string(const unsigned &i)
Return the i-th string or "" if the relevant string hasn't been defined.
void operator=(const BinaryTreeRoot &)
Broken assignment operator.
Definition: binary_tree.h:268
BinaryTreeRoot(RefineableElement *const &object_pt)
Definition: binary_tree.h:239
virtual ~BinaryTreeForest()
Destructor: Delete the constituent binary trees (and thus the objects associated with its non-leaf no...
Definition: binary_tree.h:325
unsigned self_test()
Self-test: Check all neighbours. Return success (0) if the maximum distance between corresponding poi...
Definition: binary_tree.cc:394
Tree * father_pt() const
Return pointer to father: NULL if it's a root node.
Definition: tree.h:221
virtual ~BinaryTree()
Destructor. Note: Deleting a binary tree also deletes the objects associated with all non-leaf nodes!...
Definition: binary_tree.h:96