BinaryTree class: Recursively defined, generalised binary tree. More...

#include <binary_tree.h>

Inheritance diagram for oomph::BinaryTree:

Public Member Functions
virtual	~BinaryTree ()
	Destructor. Note: Deleting a binary tree also deletes the objects associated with all non-leaf nodes! More...

	BinaryTree (const BinaryTree &dummy)=delete
	Broken copy constructor. More...

void	operator= (const BinaryTree &)=delete
	Broken assignment operator. More...

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 Tree. More...

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 regarding the relative size of the neighbour: More...

unsigned	self_test ()
	Self-test: Check all neighbours. Return success (0) if the maximum distance between corresponding points in the neighbours is less than the tolerance specified in the static value BinaryTree::Max_neighbour_finding_tolerance. More...

Public Member Functions inherited from oomph::Tree
virtual	~Tree ()
	Destructor. Note: Deleting a tree also deletes the objects associated with its non-leave nodes. More...

	Tree (const Tree &dummy)=delete
	Broken copy constructor. More...

void	operator= (const Tree &)=delete
	Broken assignment operator. More...

RefineableElement *	object_pt () const
	Return the pointer to the object (RefineableElement) represented by the tree. More...

void	flush_object ()
	Flush the object represented by the tree. More...

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 been defined for specific trees. However, these are simply aliases for ints and the general interface can be implemented once, here. More...

void	set_son_pt (const Vector< Tree * > &son_pt)
	Set vector of pointers to sons, indexed by the appropriate enum that identies son types. (To aid code readability specific enums have been defined for specific trees. However, these are simply aliases for ints and the general interface can be implemented once, here). More...

unsigned	nsons () const
	Return number of sons (zero if it's a leaf node) More...

void	flush_sons ()
	Flush the sons. More...

TreeRoot *&	root_pt ()
	Return pointer to root of the tree. More...

TreeRoot *	root_pt () const
	Return pointer to root of the tree (const version) More...

template<class ELEMENT >
void	split_if_required ()
	If required, split the leaf and create its sons – criterion: bool object_pt()-> to_be_refined() = true. More...

template<class ELEMENT >
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 object_pt()-> to_be_p_unrefined() = true. More...

void	merge_sons_if_required (Mesh *&mesh_pt)
	If required, merge the four sons for unrefinement – criterion: bool object_pt()-> sons_to_be_unrefined() = true. More...

void	deactivate_object ()
	Call the RefineableElement's deactivate_element() function. More...

void	traverse_all (Tree::VoidMemberFctPt member_function)
	Traverse the tree and execute void Tree member function member_function() at all its "nodes". More...

void	traverse_all (Tree::VoidMeshPtArgumentMemberFctPt member_function, Mesh *&mesh_pt)
	Traverse the tree and excute void Tree member function that takes a pointer to a mesh as an argument. More...

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 from the leaves. More...

void	traverse_leaves (Tree::VoidMemberFctPt member_function)
	Traverse the tree and execute void Tree member function member_function() only at its leaves. More...

void	traverse_leaves (Tree::VoidMeshPtArgumentMemberFctPt member_function, Mesh *&mesh_pt)
	Traverse the tree and execute void Tree member function that takes a pointer to a mesh as an argument only at its leaves. More...

void	stick_leaves_into_vector (Vector< Tree * > &)
	Traverse tree and stick pointers to leaf "nodes" (only) into Vector. More...

void	stick_all_tree_nodes_into_vector (Vector< Tree * > &)
	Traverse and stick pointers to all "nodes" into Vector. More...

int	son_type () const
	Return son type. More...

bool	is_leaf ()
	Return true if the tree is a leaf node. More...

Tree *	father_pt () const
	Return pointer to father: NULL if it's a root node. More...

void	set_father_pt (Tree *const &father_pt)
	Set the father. More...

unsigned	level () const
	Return the level of the Tree (root=0) More...

Static Public Member Functions
static void	setup_static_data ()
	Set up the static data, reflection schemes, etc. More...

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. More...

Static Public Member Functions inherited from oomph::Tree
static double &	max_neighbour_finding_tolerance ()
	Max. allowed discrepancy in neighbour finding routine (distance between points when identified from two neighbouring elements) More...

Static Public Attributes
static Vector< std::string >	Direct_string
	Translate (enumerated) directions into strings. More...

Static Public Attributes inherited from oomph::Tree
static const int	OMEGA = 26
	Default value for an unassigned neighbour. More...

Protected Member Functions
	BinaryTree ()
	Default constructor (empty and broken) More...

	BinaryTree (RefineableElement *const &object_pt)
	Default constructor for empty (root) tree: no father, no sons; just pass a pointer to its object. Protected because BinaryTrees can only be created internally, during the split operation. Only BinaryTreeRoots can be created externally. More...

	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 and tell it what type of son (L/R) it is. Protected because BinaryTrees can only be created internally, during the split operation. Only BinaryTreeRoots can be created externally. More...

Protected Member Functions inherited from oomph::Tree
	Tree ()
	Default constructor (empty and broken) More...

	Tree (RefineableElement *const &object_pt)
	Default constructor for empty (root) tree: no father, no sons; just pass a pointer to its object Protected because Trees can only be created internally, during the split operation. Only TreeRoots can be created externally. More...

	Tree (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 and tell it what type of son it is. Protected because Trees can only be created internally, during the split operation. Only TreeRoots can be created externally. More...

Static Protected Attributes
static bool	Static_data_has_been_setup = false
	Boolean indicating that static member data has been setup. More...

Static Protected Attributes inherited from oomph::Tree
static double	Max_neighbour_finding_tolerance = 1.0e-14
	Max. allowed discrepancy in neighbour finding routine (distance between points when identified from two neighbouring elements) More...

Private Member Functions
BinaryTree *	gteq_edge_neighbour (const int &direction, double &s_diff, int &diff_level, bool &in_neighbouring_tree, int max_level, BinaryTreeRoot *const &orig_root_pt) const
	Find greater or equal-sized edge neighbour in direction. Auxiliary internal routine which passes additional information around. More...

Static Private Attributes
static Vector< std::string >	Colour
	Colours for neighbours in various directions. More...

static Vector< double >	S_base
	S_base(direction): Initial value for coordinate s on the edge indicated by direction (L/R) More...

static Vector< int >	Reflect_edge
	Get opposite edge, e.g. Reflect_edge[L]=R. More...

static DenseMatrix< bool >	Is_adjacent
	Array of direction/segment adjacency scheme: Is_adjacent(i_vertex,j_segment): Is vertex adjacent to segment? More...

static DenseMatrix< int >	Reflect
	Reflection scheme: Reflect(direction,segment): Get mirror of segment in specified direction. E.g. Reflect(L,L)=R. More...

Additional Inherited Members
Public Types inherited from oomph::Tree
typedef void(Tree::*	VoidMemberFctPt) ()
	Function pointer to argument-free void Tree member function. More...

typedef void(Tree::*	VoidMeshPtArgumentMemberFctPt) (Mesh *&mesh_pt)
	Function pointer to a void Tree member function that takes a pointer to a mesh as its argument. More...

Protected Attributes inherited from oomph::Tree
TreeRoot *	Root_pt
	Pointer to the root of the tree. More...

Tree *	Father_pt
	Pointer to the Father of the Tree. More...

Vector< Tree * >	Son_pt
	Vector of pointers to the sons of the Tree. More...

int	Level
	Level of the Tree (level 0 = root) More...

int	Son_type
	Son type (e.g. SW/SE/NW/NE in a quadtree) More...

RefineableElement *	Object_pt
	Pointer to the object represented by the tree. More...

Detailed Description

BinaryTree class: Recursively defined, generalised binary tree.

A BinaryTree has:

a pointer to the object (of type RefineableQElement<1>) that it represents in a mesh refinement context.
a Vector of pointers to its two (L/R) sons (which are themselves binary trees). If the Vector of pointers to the sons has zero length, the BinaryTree is a "leaf node" in the overall binary tree.
a pointer to its father. If this pointer is NULL, the BinaryTree is the root node of the overall binary tree. This data is stored in the Tree base class.

The tree can also be part of a forest. If that is the case, the root will have pointers to the roots of neighbouring binary trees.

The objects contained in the binary tree are assumed to be line elements whose geometry is parametrised by local coordinates ${\bf s} \in [-1,1]$ .

The tree can be traversed and actions performed at all its "nodes" or only at the leaf "nodes" ("nodes" without sons).

Finally, the leaf "nodes" can be split depending on a criteria defined by the object.

Note that BinaryTrees are only generated by splitting existing BinaryTrees. Therefore, the constructors are protected. The only BinaryTree that "Joe User" can create is the (derived) class BinaryTreeRoot.

Definition at line 91 of file binary_tree.h.

Constructor & Destructor Documentation

◆ ~BinaryTree()

virtual oomph::BinaryTree::~BinaryTree ( )

inlinevirtual

Destructor. Note: Deleting a binary tree also deletes the objects associated with all non-leaf nodes!

Definition at line 96 of file binary_tree.h.

◆ BinaryTree() [1/4]

oomph::BinaryTree::BinaryTree ( const BinaryTree & dummy )

delete

Broken copy constructor.

◆ BinaryTree() [2/4]

oomph::BinaryTree::BinaryTree ( )

inlineprotected

Default constructor (empty and broken)

Definition at line 166 of file binary_tree.h.

Referenced by construct_son().

◆ BinaryTree() [3/4]

oomph::BinaryTree::BinaryTree ( RefineableElement *const & object_pt )

inlineprotected

Default constructor for empty (root) tree: no father, no sons; just pass a pointer to its object. Protected because BinaryTrees can only be created internally, during the split operation. Only BinaryTreeRoots can be created externally.

Definition at line 178 of file binary_tree.h.

◆ BinaryTree() [4/4]

oomph::BinaryTree::BinaryTree	(	RefineableElement *const &	object_pt,
		Tree *const &	father_pt,
		const int &	son_type
	)

inlineprotected

Constructor for tree that has a father: Pass it the pointer to its object, the pointer to its father and tell it what type of son (L/R) it is. Protected because BinaryTrees can only be created internally, during the split operation. Only BinaryTreeRoots can be created externally.

Definition at line 185 of file binary_tree.h.

Member Function Documentation

◆ construct_son()

Tree* oomph::BinaryTree::construct_son	(	RefineableElement *const &	object_pt,
		Tree *const &	father_pt,
		const int &	son_type
	)

inlinevirtual

Overload the function construct_son to ensure that the son is a specific BinaryTree and not a general Tree.

Implements oomph::Tree.

Definition at line 106 of file binary_tree.h.

References BinaryTree(), oomph::Tree::father_pt(), oomph::Tree::object_pt(), and oomph::Tree::son_type().

◆ doc_neighbours()

void oomph::BinaryTree::doc_neighbours	(	Vector< Tree * >	forest_nodes_pt,
		std::ofstream &	neighbours_file,
		std::ofstream &	neighbours_txt_file,
		double &	max_error
	)

static

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.

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 neighbouring element. Output is suppressed if the output streams are closed.

Definition at line 668 of file binary_tree.cc.

References oomph::FiniteElement::get_x(), gteq_edge_neighbour(), i, oomph::TreeRoot::is_neighbour_periodic(), oomph::BinaryTreeNames::L, oomph::RefineableElement::nodes_built(), oomph::RefineableElement::number(), oomph::Tree::object_pt(), oomph::BinaryTreeNames::OMEGA, oomph::BinaryTreeNames::R, oomph::Tree::root_pt(), and s.

Referenced by oomph::BinaryTreeForest::check_all_neighbours(), self_test(), and oomph::BinaryTreeForest::self_test().

◆ gteq_edge_neighbour() [1/2]

BinaryTree * oomph::BinaryTree::gteq_edge_neighbour	(	const int &	direction,
		double &	s_diff,
		int &	diff_level,
		bool &	in_neighbouring_tree,
		int	max_level,
		BinaryTreeRoot *const &	orig_root_pt
	)		const

private

Find greater or equal-sized edge neighbour in direction. Auxiliary internal routine which passes additional information around.

Find ‘greater-or-equal-sized edge neighbour’ in given direction (L/R).

This is an auxiliary routine which allows neighbour finding in adjacent binary trees. Needs to keep track of previous son types and the maximum level to which search is performed.

Parameters:

direction (L/R): Direction in which neighbour has to be found.
s_diff: Offset of left vertex from corresponding vertex in neighbour. Note that this is input/output as it needs to be incremented/decremented during the recursive calls to this function.
edge: We're looking for the neighbour across our edge 'direction' (L/R). When viewed from the neighbour, this edge is ‘edge’ (L/R). Since there is no relative rotation between neighbours this is a mere reflection, e.g. direction=L --> edge=R etc.
diff_level <= 0 indicates the difference in binary tree levels between the current element and its neighbour.
max_level is the maximum level to which the neighbour search is allowed to proceed. This is again necessary because in a forest, the neighbour search isn't based on pure recursion.
orig_root_pt identifies the root node of the element whose neighbour we're really trying to find by all these recursive calls.

Definition at line 257 of file binary_tree.cc.

References oomph::Tree::Father_pt, gteq_edge_neighbour(), Is_adjacent, oomph::BinaryTreeNames::L, oomph::Tree::Level, oomph::TreeRoot::neighbour_pt(), oomph::BinaryTreeNames::R, Reflect, oomph::Tree::Root_pt, oomph::Tree::Son_pt, and oomph::Tree::Son_type.

◆ gteq_edge_neighbour() [2/2]

BinaryTree * oomph::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 regarding the relative size of the neighbour:

In the present binary tree, the left vertex is located at the local coordinate s = -1. This point is located at the local coordinate s = s_in_neighbour[0] in the neighbouring binary tree.
We're looking for a neighbour in the specified direction. When viewed from the neighbouring binary tree, the edge that separates the present binary tree from its neighbour is the neighbour's edge edge. Since in 1D there can be no rotation between the two binary trees, this is a simple reflection. For instance, if we're looking for a neighhbour in the L [eft] direction, edge will be R [ight].
diff_level <= 0 indicates the difference in refinement levels between the two neighbours. If diff_level==0, the neighbour has the same size as the current binary tree.
in_neighbouring_tree indicates whether the neighbour is actually in another tree in the forest. The introduction of this flag was necessitated by periodic problems where a TreeRoot can be its own neighbour.
In the present binary tree, the left vertex is located at the local coordinate s = -1. This point is located at the local coordinate s = s_in_neighbour[0] in the neighbouring binary tree.
We're looking for a neighbour in the specified direction. When viewed from the neighbouring binary tree, the edge that separates the present binary tree from its neighbour is the neighbour's edge edge. Since in 1D there can be no rotation between the two binary trees, this is a simple reflection. For instance, if we're looking for a neighhbour in the L [eft] direction, edge will be R [ight].
diff_level <= 0 indicates the difference in refinement levels between the two neighbours. If diff_level==0, the neighbour has the same size as the current binary tree.
in_neighbouring_tree returns true if we have had to flip to a different root, even if that root is actually the same (as it can be in periodic problems).

Definition at line 172 of file binary_tree.cc.

References oomph::BinaryTreeNames::L, oomph::Tree::Level, oomph::BinaryTreeNames::R, Reflect_edge, oomph::Tree::Root_pt, and S_base.

Referenced by oomph::RefineableQElement< 1 >::check_integrity(), doc_neighbours(), gteq_edge_neighbour(), and oomph::RefineableQElement< 1 >::node_created_by_neighbour().

◆ operator=()

void oomph::BinaryTree::operator= ( const BinaryTree & )

delete

Broken assignment operator.

◆ self_test()

unsigned oomph::BinaryTree::self_test ( )

Self-test: Check all neighbours. Return success (0) if the maximum distance between corresponding points in the neighbours is less than the tolerance specified in the static value BinaryTree::Max_neighbour_finding_tolerance.

Self-test: Check neighbour finding routine. For each element in the tree and for each vertex, determine the distance between the vertex and its position in the neighbour. If the difference is less than Tree::Max_neighbour_finding_tolerance return success (0), otherwise failure (1).

Definition at line 393 of file binary_tree.cc.

References doc_neighbours(), i, oomph::Tree::Max_neighbour_finding_tolerance, oomph::oomph_info, and oomph::Tree::stick_all_tree_nodes_into_vector().

◆ setup_static_data()

void oomph::BinaryTree::setup_static_data ( )

static

Set up the static data, reflection schemes, etc.

Set up the static data stored in the BinaryTree – this needs to be called before BinaryTrees can be used. Automatically called by RefineableLineMesh constructor.

Definition at line 86 of file binary_tree.cc.

References Colour, Direct_string, Is_adjacent, oomph::BinaryTreeNames::L, oomph::Tree::OMEGA, oomph::BinaryTreeNames::R, Reflect, Reflect_edge, oomph::DenseMatrix< T >::resize(), S_base, and Static_data_has_been_setup.

Referenced by oomph::RefineableLineMesh< ELEMENT >::RefineableLineMesh().

Member Data Documentation

◆ Colour

Vector< std::string > oomph::BinaryTree::Colour

staticprivate

Colours for neighbours in various directions.

Colours for neighbours in various directions (static data).

Definition at line 206 of file binary_tree.h.

Referenced by setup_static_data().

◆ Direct_string

Vector< std::string > oomph::BinaryTree::Direct_string

static

Translate (enumerated) directions into strings.

Translate (enumerated) directions into strings (static data).

Definition at line 162 of file binary_tree.h.

Referenced by setup_static_data().

◆ Is_adjacent

DenseMatrix< bool > oomph::BinaryTree::Is_adjacent

staticprivate

Array of direction/segment adjacency scheme: Is_adjacent(i_vertex,j_segment): Is vertex adjacent to segment?

Array of direction/segment adjacency scheme: Is_adjacent(i_vertex,j_segment): Is vertex adjacent to segment? (static data)

Definition at line 217 of file binary_tree.h.

Referenced by gteq_edge_neighbour(), and setup_static_data().

◆ Reflect

DenseMatrix< int > oomph::BinaryTree::Reflect

staticprivate

Reflection scheme: Reflect(direction,segment): Get mirror of segment in specified direction. E.g. Reflect(L,L)=R.

Reflection scheme: Reflect(direction,segment): Get mirror of segment in specified direction. E.g. Reflect(L,L)=R (static data)

Definition at line 221 of file binary_tree.h.

Referenced by gteq_edge_neighbour(), and setup_static_data().

◆ Reflect_edge

Vector< int > oomph::BinaryTree::Reflect_edge

staticprivate

Get opposite edge, e.g. Reflect_edge[L]=R.

Get opposite edge, e.g. Reflect_edge[N]=S (static data)

Definition at line 213 of file binary_tree.h.

Referenced by gteq_edge_neighbour(), and setup_static_data().

◆ S_base

Vector< double > oomph::BinaryTree::S_base

staticprivate

S_base(direction): Initial value for coordinate s on the edge indicated by direction (L/R)

S_base(direction): Initial value for coordinate s on the edge indicated by direction (L/R) (static data).

Definition at line 210 of file binary_tree.h.

Referenced by gteq_edge_neighbour(), and setup_static_data().

◆ Static_data_has_been_setup

bool oomph::BinaryTree::Static_data_has_been_setup = false

staticprotected

Boolean indicating that static member data has been setup.

Definition at line 193 of file binary_tree.h.

Referenced by oomph::BinaryTreeRoot::BinaryTreeRoot(), and setup_static_data().

The documentation for this class was generated from the following files:

Public Member Functions

Static Public Member Functions

Static Public Attributes

Protected Member Functions

Static Protected Attributes

Private Member Functions

Static Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ ~BinaryTree()

◆ BinaryTree() [1/4]

◆ BinaryTree() [2/4]

◆ BinaryTree() [3/4]

◆ BinaryTree() [4/4]

Member Function Documentation

◆ construct_son()

◆ doc_neighbours()

◆ gteq_edge_neighbour() [1/2]

◆ gteq_edge_neighbour() [2/2]

◆ operator=()

◆ self_test()

◆ setup_static_data()

Member Data Documentation

◆ Colour

◆ Direct_string

◆ Is_adjacent

◆ Reflect

◆ Reflect_edge

◆ S_base

◆ Static_data_has_been_setup