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