binary_tree.h

Go to the documentation of this file.

//LIC// ====================================================================
//LIC// This file forms part of oomph-lib, the object-oriented, 
//LIC// multi-physics finite-element library, available 
//LIC// at http://www.oomph-lib.org.
//LIC// 
//LIC//    Version 1.0; svn revision $LastChangedRevision$
//LIC//
//LIC// $LastChangedDate$
//LIC// 
//LIC// Copyright (C) 2006-2016 Matthias Heil and Andrew Hazel
//LIC// 
//LIC// This library is free software; you can redistribute it and/or
//LIC// modify it under the terms of the GNU Lesser General Public
//LIC// License as published by the Free Software Foundation; either
//LIC// version 2.1 of the License, or (at your option) any later version.
//LIC// 
//LIC// This library is distributed in the hope that it will be useful,
//LIC// but WITHOUT ANY WARRANTY; without even the implied warranty of
//LIC// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
//LIC// Lesser General Public License for more details.
//LIC// 
//LIC// You should have received a copy of the GNU Lesser General Public
//LIC// License along with this library; if not, write to the Free Software
//LIC// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
//LIC// 02110-1301  USA.
//LIC// 
//LIC// The authors may be contacted at oomph-lib@maths.man.ac.uk.
//LIC// 
//LIC//====================================================================
// Header file for binary tree and binary tree forest classes
#ifndef OOMPH_BINARY_TREE_HEADER
#define OOMPH_BINARY_TREE_HEADER

// Config header generated by autoconfig
#ifdef HAVE_CONFIG_H
  #include <oomph-lib-config.h>
#endif

// oomph-lib headers
#include "tree.h"
#include "matrices.h"

namespace oomph
{
 //======================================================================
 /// Namespace for BinaryTree directions
 //======================================================================
 namespace BinaryTreeNames
 {
  /// \short Directions (L/R). OMEGA is used if a direction is undefined 
  /// in a certain context
  enum{L,R,OMEGA=26};
 };
 
 // Forward class definition for class representing the root of a BinaryTree
 class BinaryTreeRoot;
 
 //======================================================================
 /// 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
 /// \f$ {\bf s} \in [-1,1] \f$.
 ///
 /// 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.
 //======================================================================
 class BinaryTree : public virtual Tree
 { 
 public:
  
  /// \short Destructor. Note: Deleting a binary tree also deletes the 
  /// objects associated with all non-leaf nodes!
  virtual ~BinaryTree() {}
  
  /// Broken copy constructor
  BinaryTree(const BinaryTree& dummy) 
   { 
    BrokenCopy::broken_copy("BinaryTree");
   } 
  
  /// Broken assignment operator
  void operator=(const BinaryTree&) 
   {
    BrokenCopy::broken_assign("BinaryTree");
   }
  
  /// \short Overload the function construct_son to ensure that the son
  /// is a specific BinaryTree and not a general Tree.
  Tree* construct_son(RefineableElement* const &object_pt,
                      Tree* const &father_pt, const int &son_type)
   {
    BinaryTree* temp_binary_pt = new BinaryTree(object_pt,father_pt,son_type);
    return temp_binary_pt;
   }
  
  /// \short Return pointer to greater or equal-sized edge neighbour 
  /// in specified \c 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 = \c s_in_neighbour[0] in the neighbouring binary tree.
  /// - We're looking for a neighbour in the specified \c direction. When
  ///   viewed from the neighbouring binary tree, the edge that separates 
  ///   the present binary tree from its neighbour is the neighbour's
  ///   \c 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 \c L [eft] \c direction, \c edge
  ///   will be \c R [ight].
  /// - \c diff_level <= 0 indicates the difference in refinement levels
  ///   between the two neighbours. If \c diff_level==0, the neighbour
  ///   has the same size as the current binary tree.
  /// - \c 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.
  BinaryTree* gteq_edge_neighbour(const int& direction, 
                                  Vector<double>& s_in_neighbour,
                                  int& edge, int& diff_level,
                                  bool &in_neighbouring_tree) const;
    
  /// \short 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.
  unsigned self_test();

  /// \short Set up the static data, reflection schemes, etc.
  static void setup_static_data();
  
  /// \short 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.
  static void doc_neighbours(Vector<Tree*> forest_nodes_pt, 
                             std::ofstream& neighbours_file, 
                             std::ofstream& neighbours_txt_file,
                             double& max_error);
  
  /// Translate (enumerated) directions into strings 
  static Vector<std::string> Direct_string;
  
protected:
  
  /// Default constructor (empty and broken)
  BinaryTree()
   {
    throw OomphLibError
     ("Don't call an empty constructor for a BinaryTree object",
      OOMPH_CURRENT_FUNCTION,OOMPH_EXCEPTION_LOCATION);
   }
  
  /// \short 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.
  BinaryTree(RefineableElement* const &object_pt) : Tree(object_pt) {}
  
  /// \short 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. 
  BinaryTree(RefineableElement* const &object_pt, 
             Tree* const &father_pt, const int& son_type)
   : Tree(object_pt,father_pt,son_type) {}
  
  /// Boolean indicating that static member data has been setup
  static bool Static_data_has_been_setup;
  
 private:
  
  /// \short Find greater or equal-sized edge neighbour in direction.
  /// Auxiliary internal routine which passes additional information around.
  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;
  
  /// Colours for neighbours in various directions
  static Vector<std::string> Colour;
  
  /// \short S_base(direction): Initial value for coordinate s on the edge
  /// indicated by direction (L/R)
  static Vector<double> S_base;
  
  /// Get opposite edge, e.g. Reflect_edge[L]=R
  static Vector<int> Reflect_edge;
  
  /// \short Array of direction/segment adjacency scheme: 
  /// Is_adjacent(i_vertex,j_segment): Is vertex adjacent to segment?
  static DenseMatrix<bool> Is_adjacent;
  
  /// \short Reflection scheme: Reflect(direction,segment): Get mirror 
  /// of segment in specified direction. E.g. Reflect(L,L)=R.
  static DenseMatrix<int> Reflect;
  
 };
 
 
 //======================================================================
 /// BinaryTreeRoot is a BinaryTree that forms the root of a (recursive)
 /// binary tree. The "root node" is special as it holds additional 
 /// information about its neighbours.
 //======================================================================
 class BinaryTreeRoot : public virtual BinaryTree, public virtual TreeRoot
 {

  public:
  
  /// Constructor for the (empty) root binary tree: Pass pointer to 
  /// associated object, a RefineableQElement<1>.
  BinaryTreeRoot(RefineableElement* const &object_pt) : Tree(object_pt),
   BinaryTree(object_pt), TreeRoot(object_pt)
   {
    
#ifdef PARANOID
    // Check that static member data has been setup
    if(!Static_data_has_been_setup)
     {
      std::string error_message =
       "Static member data hasn't been setup yet.\n";
      error_message +=
       "Call BinaryTree::setup_static_data() before creating\n";
      error_message += "any BinaryTreeRoots\n";
      
      throw OomphLibError(error_message,
                          OOMPH_CURRENT_FUNCTION,
                          OOMPH_EXCEPTION_LOCATION);
     }
#endif

   }
    
  /// Broken copy constructor
  BinaryTreeRoot(const BinaryTreeRoot& dummy) : TreeRoot(dummy) 
   { 
    BrokenCopy::broken_copy("BinaryTreeRoot");
   } 
  
  /// Broken assignment operator
  void operator=(const BinaryTreeRoot&) 
   {
    BrokenCopy::broken_assign("BinaryTreeRoot");
   }
  
  /// \short If binary_tree_root_pt is a neighbour, return the direction
  /// (L/R) in which it is found, otherwise return OMEGA
  int direction_of_neighbour(BinaryTreeRoot* binary_tree_root_pt)
   {
    using namespace BinaryTreeNames;
    
    if(Neighbour_pt[L]==binary_tree_root_pt) { return L; }
    if(Neighbour_pt[R]==binary_tree_root_pt) { return R; }
    
    // If we get here, it's not a neighbour
    return OMEGA;
   }
  
 };
 
 
 //======================================================================
 /// A BinaryTreeForest consists of a collection of BinaryTreeRoots.
 /// Each member tree can have neighbours to its left and right.
 //======================================================================
 class BinaryTreeForest : public TreeForest
 { 

 public:
  
  /// Default constructor (empty and broken)
  BinaryTreeForest()
   {
    //Throw an error
    throw OomphLibError(
     "Don't call an empty constructor for a BinaryTreeForest object",
     OOMPH_CURRENT_FUNCTION,OOMPH_EXCEPTION_LOCATION);
   }
  
  /// \short Constructor: Pass vector of pointers to the roots of the
  /// constituent BinaryTrees
  BinaryTreeForest(Vector<TreeRoot* >& trees_pt);
  
  /// Broken copy constructor
  BinaryTreeForest(const BinaryTreeForest& dummy) 
   { 
    BrokenCopy::broken_copy("BinaryTreeForest");
   } 
  
  /// Broken assignment operator
  void operator=(const BinaryTreeForest&) 
   {
    BrokenCopy::broken_assign("BinaryTreeForest");
   }
  
  /// \short Destructor: Delete the constituent binary trees (and thus 
  /// the objects associated with its non-leaf nodes!)
  virtual ~BinaryTreeForest() {}
  
  /// \short Document and check all the neighbours of all the nodes in
  /// the forest. DocInfo object specifies the output directory and file
  /// numbers for the various files. If \c doc_info.disable_doc() has been
  /// called, no output is created.
  void check_all_neighbours(DocInfo &doc_info);
  
  /// A line mesh cannot have hanging nodes so make this function empty
  void open_hanging_node_files(DocInfo &doc_info,
                               Vector<std::ofstream*> &output_stream) {}
  
  /// \short 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.
  unsigned self_test();

 private:
  
  /// Construct the neighbour lookup scheme
  void find_neighbours();
  
  /// Return pointer to i-th root binary tree in this forest (performs
  /// a dynamic cast from the TreeRoot to a BinaryTreeRoot).
  BinaryTreeRoot* binary_tree_pt(const unsigned &i)
   { return dynamic_cast<BinaryTreeRoot*>(Trees_pt[i]); }
  
  /// \short Given the number i of the root binary tree in this forest,
  /// return a pointer to its neighbour in the specified direction.
  /// NULL if neighbour doesn't exist. (This does the dynamic cast 
  /// from a TreeRoot to a BinaryTreeRoot internally).
  BinaryTreeRoot* binary_neigh_pt(const unsigned &i, const int &direction)
   {
    return dynamic_cast<BinaryTreeRoot*>(Trees_pt[i]->neighbour_pt(direction));
   }
  
 };

} // End of namespace

#endif