ntree.h

Go to the documentation of this file.

/*
 * Copyright (c) 2013-2015:  G-CSC, Goethe University Frankfurt
 * Author: Sebastian Reiter
 * 
 * This file is part of UG4.
 * 
 * UG4 is free software: you can redistribute it and/or modify it under the
 * terms of the GNU Lesser General Public License version 3 (as published by the
 * Free Software Foundation) with the following additional attribution
 * requirements (according to LGPL/GPL v3 §7):
 * 
 * (1) The following notice must be displayed in the Appropriate Legal Notices
 * of covered and combined works: "Based on UG4 (www.ug4.org/license)".
 * 
 * (2) The following notice must be displayed at a prominent place in the
 * terminal output of covered works: "Based on UG4 (www.ug4.org/license)".
 * 
 * (3) The following bibliography is recommended for citation and must be
 * preserved in all covered files:
 * "Reiter, S., Vogel, A., Heppner, I., Rupp, M., and Wittum, G. A massively
 *   parallel geometric multigrid solver on hierarchically distributed grids.
 *   Computing and visualization in science 16, 4 (2013), 151-164"
 * "Vogel, A., Reiter, S., Rupp, M., Nägel, A., and Wittum, G. UG4 -- a novel
 *   flexible software system for simulating pde based models on high performance
 *   computers. Computing and visualization in science 16, 4 (2013), 165-179"
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU Lesser General Public License for more details.
 */
 
#ifndef __H__UG__ntree__
#define __H__UG__ntree__
 
#include "ntree_iterator.h"
 
namespace ug{
 
template <int tree_dim, int world_dim, class elem_t, class common_data_t>
struct ntree_traits
{
  typedef int real_t;
  typedef int vector_t;
  typedef int box_t;
 
  static void calculate_center(vector_t& centerOut, const elem_t& e,
                     const common_data_t& commonData);
 
  static void calculate_bounding_box(box_t& boxOut, const elem_t& e,
                     const common_data_t& commonData);
 
  static void grow_box(box_t& boxOut, const box_t& box,
             const vector_t& offset);
 
  static vector_t box_diagonal(const box_t& box);
 
  static bool box_contains_point(const box_t& box, const vector_t& point);
 
  static bool box_box_intersection(const box_t& box1, const box_t& box2);
 
  static void merge_boxes(box_t& boxOut, const box_t& box1, const box_t& box2);
 
 
  static void split_box(box_t* boxesOut, const box_t& box, const vector_t& splitPoint);
 
  static bool contains_point(const elem_t& e, const vector_t& point,
                 const common_data_t& commonData);
//
//  real_t distance_point_to_entry(const elem_t& e, const vector_t& point,
//                   const elem_data_t& elemData,
//                   const common_data_t& commonData);
//
//  bool ray_intersects_entry(real_t distOut, const elem_t& elem,
//                const vector_t& rayFrom, const vector_t& rayTo,
//                const elem_data_t& elemData,
//                const common_data_t& commonData);
};
 
 
 
 
struct NTreeDesc{
  size_t maxDepth;
  size_t splitThreshold;
  //todo: split-strategy (center-of-space, center-of-mass)
 
  NTreeDesc() : maxDepth(32), splitThreshold(16)  {}
};
 
 
 
template <int tree_dim, int world_dim, class TElem, class TCommonData>
class ntree
{
  private:
    struct Entry;
 
  public:
    typedef TElem                   elem_t;
    typedef TCommonData                 common_data_t;
    typedef ntree_traits<tree_dim, world_dim, elem_t, common_data_t> traits;
    typedef typename traits::real_t           real_t;
    typedef typename traits::vector_t         vector_t;
    typedef typename traits::box_t            box_t;
    typedef const_ntree_element_iterator<elem_t, Entry> elem_iterator_t;
 
    ntree();
 
    void clear();
 
 
    void enable_warnings(bool enable) {m_warningsEnabled = enable;}
    bool warnings_enabled () const    {return m_warningsEnabled;}
 
 
    void set_desc(const NTreeDesc& desc);
 
    const NTreeDesc& desc() const;
 
    void set_common_data(const common_data_t& commonData);
 
    const common_data_t& common_data() const;
 
    bool empty() const;
 
    size_t size() const;
 
 
    size_t num_delayed_elements() const;
 
 
    void add_element(const elem_t& elem);
 
 
    void rebalance();
 
    size_t num_nodes() const;
 
    size_t num_child_nodes(size_t nodeId) const;
 
 
    const size_t* child_node_ids(size_t nodeId) const;
 
    elem_iterator_t elems_begin(size_t nodeId) const;
 
 
    elem_iterator_t elems_end(size_t nodeId) const;
 
    size_t num_elements(size_t nodeId) const;
 
    size_t level(size_t nodeId) const;
 
    const box_t& bounding_box(size_t nodeId) const;
 
  private:
  
    void clear_nodes ();
    
    template <size_t n, size_t exponent>
    struct pow;
 
    template <size_t n>
    struct pow<n, 0>  {static const size_t val = 1;};
 
    template <size_t n, size_t exponent>
    struct pow  {static const size_t val = n * pow<n, exponent - 1>::val;};
 
    static const size_t s_numChildren = pow<2, tree_dim>::val;
 
    static const size_t s_invalidIndex = -1;
 
 
 
    struct Entry{
        elem_t    elem;
        size_t  nextEntryInd;
 
        Entry(const elem_t& e) :
          elem(e), nextEntryInd(s_invalidIndex) {}
    };
 
 
    struct Node{
      size_t    childNodeInd[s_numChildren]; 
      size_t    firstEntryInd; 
      size_t    lastEntryInd; 
      size_t    numEntries; 
      size_t    level;
      box_t   tightBox; 
      box_t   looseBox; 
 
      Node() : firstEntryInd(s_invalidIndex), lastEntryInd(s_invalidIndex),
           numEntries(0), level(s_invalidIndex)
      {
        tightBox = looseBox;
        for(size_t i = 0; i < s_numChildren; ++i)
          childNodeInd[i] = s_invalidIndex;
      }
 
      Node(const Node& n) : firstEntryInd(n.firstEntryInd), lastEntryInd(n.lastEntryInd),
                  numEntries(n.numEntries), level(n.level),
                  tightBox(n.tightBox), looseBox(n.looseBox)
      {
        for(size_t i = 0; i < s_numChildren; ++i)
          childNodeInd[i] = n.childNodeInd[i];
      }
    };
 
 
    void split_leaf_node(size_t nodeIndex);
 
 
    size_t find_leaf_node(const vector_t& point, size_t curNode = 0);
 
    void add_entry_to_node(Node& node, size_t entryInd);
 
    void update_loose_bounding_box(Node& node);
 
    vector_t calculate_center_of_mass(Node& node);
 
    NTreeDesc       m_desc;
    common_data_t     m_commonData;
    std::vector<Node>   m_nodes; 
    std::vector<Entry>    m_entries;
    size_t          m_numDelayedElements;
    bool          m_warningsEnabled;
};
 
 
}// end of namespace
 
 
//  include implementation
#include "ntree_impl.hpp"
 
#endif