DynTree.h

/**************************************************************************
* BASF2 (Belle Analysis Framework 2)                                     *
* Copyright(C) 2015 - Belle II Collaboration                             *
*                                                                        *
* Author: The Belle II Collaboration                                     *
* Contributors: Viktor Trusov, Thomas Hauth, Oliver Frost                *
*                                                                        *
* This software is provided "as is" without any warranty.                *
**************************************************************************/
#pragma once
 
#include <tracking/trackFindingCDC/utilities/Algorithms.h>
#include <tracking/trackFindingCDC/utilities/Functional.h>
#include <framework/logging/Logger.h>
#include <vector>
#include <deque>
#include <map>
#include <functional>
#include <type_traits>
 
#include <cmath>
#include <cassert>
 
namespace Belle2 {
  namespace TrackFindingCDC {
 
    template<class AProperties, class ASubPropertiesFactory>
    class DynTree {
 
      using This = DynTree<AProperties, ASubPropertiesFactory>;
 
      using Properties = AProperties;
 
      using SubPropertiesFactory = ASubPropertiesFactory;
 
    public:
      class Node : public AProperties {
 
      public:
        using Tree = This;
 
        friend Tree;
 
        using Properties = AProperties;
 
        using Children = std::vector<Node>;
 
      private:
        using AProperties::AProperties;
 
      public:
        using AProperties::operator=;
 
      public:
        Children* getChildren()
        { return m_children; }
 
        const Children* getChildren() const
        { return m_children; }
 
        void createChildren()
        {
          // ensure the level value fits into unsigned char
          B2ASSERT("DynTree datastructure only supports levels < 255", getLevel() < 255);
 
          // Call out to the tree, which is providing the memory for the nodes.
          Node* parentNode = this;
          m_children = getTree()->createChildren(parentNode);
 
          for (Node& child : *m_children) {
            child.m_level = getLevel() + 1;
            child.m_parent = this;
            child.m_tree = getTree();
          }
        }
 
      private:
        void unlink()
        {
          m_parent = nullptr;
          m_level = 0;
          m_children = nullptr;
          m_tree = nullptr;
        }
 
      public:
        template<class AWalker>
        void walk(AWalker& walker)
        {
          static_assert(std::is_assignable<std::function<bool(Node*)>, AWalker>(), "");
 
          bool walkChildren = walker(this);
          Children* children = getChildren();
          if (children and walkChildren) {
            for (Node& childNode : *children) {
              childNode.walk(walker);
            }
          }
        }
 
        template<class AWalker, class APriorityMeasure>
        void walk(AWalker& walker, APriorityMeasure& priority)
        {
          static_assert(std::is_assignable<std::function<bool(Node*)>, AWalker>(), "");
          static_assert(std::is_assignable<std::function<float(Node*)>, APriorityMeasure>(), "");
 
          bool walkChildren = walker(this);
          Children* children = getChildren();
          if (children and walkChildren) {
            std::vector<std::pair<float, Node*> > prioritisedChildNodes;
            size_t nChildren = children->size();
 
            prioritisedChildNodes.reserve(nChildren);
            // Priorities the child nodes with the priority function.
            for (Node& childNode : *children) {
              float childPriority = priority(&childNode);
              if (std::isnan(childPriority)) continue;
              prioritisedChildNodes.push_back(std::make_pair(childPriority, &childNode));
            }
 
            std::make_heap(prioritisedChildNodes.begin(), prioritisedChildNodes.end());
 
            while (not prioritisedChildNodes.empty()) {
              std::pop_heap(prioritisedChildNodes.begin(), prioritisedChildNodes.end());
              Node* priorityChildNode = prioritisedChildNodes.back().second;
              prioritisedChildNodes.pop_back();
 
              priorityChildNode->walk(walker, priority);
 
              // After the walking the children we reevaluate the priority
              bool reheap = false;
              erase_remove_if(prioritisedChildNodes,
              [&reheap, &priority](std::pair<float, Node*>& prioritisedChildNode) {
                float childPriority = priority(prioritisedChildNode.second);
                if (std::isnan(childPriority)) return true;
                // Check if weights changed and a reordering is due.
                reheap |= prioritisedChildNode.first != childPriority;
                prioritisedChildNode.first = childPriority;
                return false;
              });
 
              if (reheap) {
                std::make_heap(prioritisedChildNodes.begin(), prioritisedChildNodes.end());
              }
            }
            assert(prioritisedChildNodes.empty());
          }
        }
 
        int getLevel() const { return m_level; }
 
        Node* getParent() { return m_parent; }
 
        const Node* getParent() const { return m_parent; }
 
        Tree* getTree() const { return m_tree; }
 
      private:
        Tree* m_tree = nullptr;
 
        Children* m_children = nullptr;
 
        int m_level = 0;
 
        Node* m_parent = nullptr;
      };
 
    public:
      DynTree(const Properties& properties,
              const SubPropertiesFactory& subPropertiesFactory = SubPropertiesFactory()) :
        m_subPropertiesFactory(subPropertiesFactory),
        m_topNode(properties),
        m_children()
      {
        m_topNode.m_tree = this;
      }
 
      DynTree(const DynTree& node) = delete;
 
      DynTree& operator=(const DynTree&) = delete;
 
      Node& getTopNode()
      { return m_topNode; }
 
      const Node& getTopNode() const
      { return m_topNode; }
 
      int getNNodes() const
      {
        int nNodes = 0;
        auto countNodes = [&nNodes](const Node*) -> bool {
          ++nNodes;
          return true;
        };
        const_cast<DynTree&>(*this).walk(countNodes);
        //walk(countNodes);
        return nNodes;
      }
 
      std::map<int, int> getNNodesByLevel() const
      {
        std::map<int, int> nNodesByLevel;
        auto countNodes = [&nNodesByLevel](const Node * node) -> bool {
          if (nNodesByLevel.count(node->getLevel()) == 0)
          {
            nNodesByLevel[node->getLevel()] = 1;
          } else {
            nNodesByLevel[node->getLevel()]++;
          }
          return true;
        };
        const_cast<DynTree&>(*this).walk(countNodes);
        //walk(countNodes);
        return nNodesByLevel;
      }
 
    private:
      std::vector<Node>* createChildren(Node* parentNode)
      {
        std::vector<Node>* result = getUnusedChildren();
        auto subProperties = m_subPropertiesFactory(*parentNode);
        if (subProperties.empty()) {
          result->clear();
        } else {
          // Initialize new elements with dummy property.
          result->resize(subProperties.size(), Node(subProperties.back()));
          size_t iSubNode = 0;
          for (auto& properties : subProperties) {
            clearIfApplicable(result->at(iSubNode));
            result->at(iSubNode) = properties;
            ++iSubNode;
          }
        }
        return result;
      }
 
      std::vector<Node>* getUnusedChildren()
      {
        if (m_nUsedChildren >= m_children.size()) {
          m_children.emplace_back();
        }
        ++m_nUsedChildren;
        return &(m_children[m_nUsedChildren - 1]);
      }
 
    public:
      template<class AWalker>
      void walk(AWalker& walker)
      {
        static_assert(std::is_assignable<std::function<bool(Node*)>, AWalker>(), "");
 
        getTopNode().walk(walker);
      }
 
      template<class AWalker, class APriorityMeasure>
      void walk(AWalker& walker, APriorityMeasure& priority)
      {
        static_assert(std::is_assignable<std::function<bool(Node*)>, AWalker>(), "");
        static_assert(std::is_assignable<std::function<float(Node*)>, APriorityMeasure>(), "");
 
        getTopNode().walk(walker, priority);
      }
 
      void fell()
      {
        clearIfApplicable(m_topNode);
        m_topNode.unlink();
        m_topNode.m_tree = this;
        for (typename Node::Children& children : m_children) {
          for (Node& node : children) {
            clearIfApplicable(node);
            node.unlink();
          }
        }
        m_nUsedChildren = 0;
      }
 
      void raze()
      {
        this->fell();
        m_children.clear();
        m_children.shrink_to_fit();
      }
 
    public:
      SubPropertiesFactory m_subPropertiesFactory;
 
      Node m_topNode;
 
      std::deque<typename Node::Children> m_children;
 
      size_t m_nUsedChildren = 0;
    };
  }
}