Dynamic tree structure with weighted items in each node which are markable through out the tree. More...

#include <WeightedFastHoughTree.h>

Inheritance diagram for WeightedFastHoughTree< T, ADomain, ADomainDivsion >:

Public Types
using	Node = typename Super::Node
	Type of the node in the tree.

Public Member Functions
template<class Ts >
void	seed (const Ts &items)
	Take the item set and insert them into the top node of the hough space.

template<class AItemInDomainMeasure >
std::vector< std::pair< ADomain, std::vector< T > > >	findHeavyLeavesDisjoint (AItemInDomainMeasure &weightItemInDomain, int maxLevel, double minWeight)
	Find all children node at maximum level and add them to the result list. Skip nodes if their weight is below minWeight.

template<class AItemInDomainMeasure , class ASkipNodePredicate >
std::vector< std::pair< ADomain, std::vector< T > > >	findLeavesDisjoint (AItemInDomainMeasure &weightItemInDomain, int maxLevel, ASkipNodePredicate &skipNode)
	Find all children node at maximum level and add them to the result list. Skip nodes if skipNode returns true.

template<class AItemInDomainMeasure >
std::vector< std::pair< ADomain, std::vector< T > > >	findHeaviestLeafRepeated (AItemInDomainMeasure &weightItemInDomain, int maxLevel, const Weight minWeight=NAN)
	Go through all children until maxLevel is reached and find the heaviest leaves.

template<class AItemInDomainMeasure , class ASkipNodePredicate >
std::vector< std::pair< ADomain, std::vector< T > > >	findHeaviestLeafRepeated (AItemInDomainMeasure &weightItemInDomain, int maxLevel, ASkipNodePredicate &skipNode)
	Go through all children until maxLevel is reached and find the heaviest leaves.

template<class AItemInDomainMeasure , class ASkipNodePredicate >
std::unique_ptr< std::pair< ADomain, std::vector< T > > >	findHeaviestLeafSingle (AItemInDomainMeasure &weightItemInDomain, int maxLevel, ASkipNodePredicate &skipNode)
	Go through all children until the maxLevel is reached and find the leaf with the highest weight.

template<class AItemInDomainMeasure , class ASkipNodePredicate >
Node *	findHeaviestLeaf (AItemInDomainMeasure &weightItemInDomain, int maxLevel, ASkipNodePredicate &skipNode)
	Go through all children until the maxLevel is reached and find the leaf with the highest weight.

template<class AItemInDomainMeasure , class AIsLeafPredicate >
void	fillWalk (AItemInDomainMeasure &weightItemInDomain, AIsLeafPredicate &isLeaf)
	Walk through the children and fill them if necessary until isLeaf returns true.

template<class ATreeWalker >
void	walkHeighWeightFirst (ATreeWalker &walker)
	Walk the tree investigating the heaviest children with priority.

void	fell ()
	Fell to tree meaning deleting all child nodes from the tree. Keeps the top node.

void	raze ()
	Like fell but also releases all memory the tree has acquired during long executions.

Node &	getTopNode ()
	Getter for the top node of the tree.

const Node &	getTopNode () const
	Constant getter for the top node of the tree.

int	getNNodes () const
	Gets the number of nodes currently contained in the tree Also demonstrates how to walk over the tree.

std::map< int, int >	getNNodesByLevel () const
	Gets the number of nodes by level in the tree Also demonstrates how to walk over the tree.

template<class AWalker >
void	walk (AWalker &walker)
	Forward walk to the top node.

template<class AWalker , class APriorityMeasure >
void	walk (AWalker &walker, APriorityMeasure &priority)
	Forward walk to the top node.

Public Attributes
SubPropertiesFactory	m_subPropertiesFactory
	Instance of the properties factory for the sub nodes.

Node	m_topNode
	Memory for the top node of the tree.

std::deque< typename Node::Children >	m_children
	Central point to provide memory for the child structures.

size_t	m_nUsedChildren = 0
	Last index of used children.

Private Types
using	Super = WeightedParititioningDynTree< WithSharedMark< T >, ADomain, ADomainDivsion >
	Type of the Tree the partitions using markable items the hough space.

using	This = DynTree< AProperties, ASubPropertiesFactory >
	Type of this class.

using	Properties = AProperties
	Type of the Properties.

using	SubPropertiesFactory = ASubPropertiesFactory
	Type of the factory for the sub node properties.

Private Member Functions
std::vector< Node > *	createChildren (Node *parentNode)
	Create child nodes for the given parents.

std::vector< Node > *	getUnusedChildren ()
	Acquire the next unused child node structure, recycling all memory.

Private Attributes
std::deque< bool >	m_marks
	Memory of the used marks of the items.

Detailed Description

template<class T, class ADomain, class ADomainDivsion>
class Belle2::TrackFindingCDC::WeightedFastHoughTree< T, ADomain, ADomainDivsion >

Dynamic tree structure with weighted items in each node which are markable through out the tree.

Used to build fast hough type algorithms, where objects are allowed to carry weights relative to the hough space part (here called a ADomain) they are contained in. The shared marks allow for iterative extraction of hough peaks such that other areas of the hough space notice that certain element have already been consumed.

Definition at line 49 of file WeightedFastHoughTree.h.

Member Typedef Documentation

◆ Node

using Node = typename Super::Node

Type of the node in the tree.

Definition at line 61 of file WeightedFastHoughTree.h.

◆ Properties

using Properties = AProperties

privateinherited

Type of the Properties.

Definition at line 41 of file DynTree.h.

◆ SubPropertiesFactory

using SubPropertiesFactory = ASubPropertiesFactory

privateinherited

Type of the factory for the sub node properties.

Definition at line 44 of file DynTree.h.

◆ Super

using Super = WeightedParititioningDynTree<WithSharedMark<T>, ADomain, ADomainDivsion>

private

Type of the Tree the partitions using markable items the hough space.

Definition at line 54 of file WeightedFastHoughTree.h.

◆ This

using This = DynTree<AProperties, ASubPropertiesFactory>

privateinherited

Type of this class.

Definition at line 38 of file DynTree.h.

Member Function Documentation

◆ createChildren()

std::vector< Node > * createChildren ( Node * parentNode )

inlineprivateinherited

Create child nodes for the given parents.

Definition at line 284 of file DynTree.h.

      {
        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;
      }

◆ fell()

void fell ( )

inline

Fell to tree meaning deleting all child nodes from the tree. Keeps the top node.

Definition at line 292 of file WeightedFastHoughTree.h.

      {
        this->getTopNode().clear();
        m_marks.clear();
        Super::fell();
      }

◆ fillWalk()

void fillWalk	(	AItemInDomainMeasure &	weightItemInDomain,
		AIsLeafPredicate &	isLeaf
	)

inline

Walk through the children and fill them if necessary until isLeaf returns true.

Uses the weightItemInDomain to create weights for the items (or decide if an item belongs to a mode or not).

Definition at line 239 of file WeightedFastHoughTree.h.

      {
        auto walker = [&weightItemInDomain, &isLeaf](Node * node) {
          // Check if node is a leaf
          // Do not create children in this case
          if (isLeaf(node)) {
            // Do not walk children.
            return false;
          }
 
          // Node is not a leaf.
          // Check if it has children.
          // If children have not been created, create and fill them.
          typename Node::Children* children = node->getChildren();
          if (not children) {
            node->createChildren();
            children = node->getChildren();
            for (Node& childNode : *children) {
              assert(childNode.getChildren() == nullptr);
              assert(childNode.size() == 0);
              auto measure =
              [&childNode, &weightItemInDomain](WithSharedMark<T>& markableItem) -> Weight {
                // Weighting function should not see the mark, but only the item itself.
                T & item(markableItem);
                return weightItemInDomain(item, &childNode);
              };
              childNode.insert(*node, measure);
            }
          }
          // Continue to walk the children.
          return true;
        };
        walkHeighWeightFirst(walker);
      }

◆ findHeaviestLeaf()

Node * findHeaviestLeaf	(	AItemInDomainMeasure &	weightItemInDomain,
		int	maxLevel,
		ASkipNodePredicate &	skipNode
	)

inline

Go through all children until the maxLevel is reached and find the leaf with the highest weight.

If no node could be found, return a nullptr. A node is skipped if skipNode is returns true for this node.

Definition at line 201 of file WeightedFastHoughTree.h.

      {
        Node* heaviestNode = nullptr;
        Weight heighestWeigth = NAN;
        auto isLeaf = [&heaviestNode, &heighestWeigth, maxLevel, &skipNode](Node * node) {
          // Skip the expansion and the filling of the children
          if (skipNode(node)) {
            return true;
          }
 
          Weight nodeWeight = node->getWeight();
          // Skip the expansion and filling of the children if the node has not enough weight
          if (not std::isnan(heighestWeigth) and not(nodeWeight > heighestWeigth)) {
            return true;
          }
 
          // Node is a leaf at the maximum level and is heavier than everything seen before.
          // Save its content
          // Do not walk children
          if (node->getLevel() >= maxLevel) {
            heaviestNode = node;
            heighestWeigth = nodeWeight;
            return true;
          }
          return false;
        };
        fillWalk(weightItemInDomain, isLeaf);
        return heaviestNode;
      }

◆ findHeaviestLeafRepeated() [1/2]

std::vector< std::pair< ADomain, std::vector< T > > > findHeaviestLeafRepeated	(	AItemInDomainMeasure &	weightItemInDomain,
		int	maxLevel,
		ASkipNodePredicate &	skipNode
	)

inline

Go through all children until maxLevel is reached and find the heaviest leaves.

For this, the single heaviest leaf is found and added to an internal list. The process is repeated until no leaf can be found anymore. A node is skipped if skipNode is returns true for this node.

Definition at line 154 of file WeightedFastHoughTree.h.

      {
        std::vector<std::pair<ADomain,  std::vector<T> > > found;
        Node* node = findHeaviestLeaf(weightItemInDomain, maxLevel, skipNode);
        while (node) {
          const ADomain* domain = node;
          found.emplace_back(*domain, std::vector<T>(node->begin(), node->end()));
          for (WithSharedMark<T>& markableItem : *node) {
            markableItem.mark();
          }
          node = findHeaviestLeaf(weightItemInDomain, maxLevel, skipNode);
        }
        return found;
      }

◆ findHeaviestLeafRepeated() [2/2]

std::vector< std::pair< ADomain, std::vector< T > > > findHeaviestLeafRepeated	(	AItemInDomainMeasure &	weightItemInDomain,
		int	maxLevel,
		const Weight	minWeight = `NAN`
	)

inline

Go through all children until maxLevel is reached and find the heaviest leaves.

For this, the single heaviest leaf is found and added to an internal list. The process is repeated until no leaf can be found anymore. A node is skipped if the weight is below minWeight.

Definition at line 135 of file WeightedFastHoughTree.h.

      {
        auto skipLowWeightNode = [minWeight](const Node * node) {
          return not(node->getWeight() >= minWeight);
        };
        return findHeaviestLeafRepeated(weightItemInDomain, maxLevel, skipLowWeightNode);
      }

◆ findHeaviestLeafSingle()

std::unique_ptr< std::pair< ADomain, std::vector< T > > > findHeaviestLeafSingle	(	AItemInDomainMeasure &	weightItemInDomain,
		int	maxLevel,
		ASkipNodePredicate &	skipNode
	)

inline

Go through all children until the maxLevel is reached and find the leaf with the highest weight.

If no node could be found, return an empty list, otherwise return a list with just on element. A node is skipped if skipNode is returns true for this node.

Definition at line 178 of file WeightedFastHoughTree.h.

      {
        using Result = std::pair<ADomain,  std::vector<T> >;
        std::unique_ptr<Result> found = nullptr;
        Node* node = findHeaviestLeaf(weightItemInDomain, maxLevel, skipNode);
        if (node) {
          const ADomain* domain = node;
          found.reset(new Result(*domain, std::vector<T>(node->begin(), node->end())));
          for (WithSharedMark<T>& markableItem : *node) {
            markableItem.mark();
          }
        }
        return found;
      }

◆ findHeavyLeavesDisjoint()

std::vector< std::pair< ADomain, std::vector< T > > > findHeavyLeavesDisjoint	(	AItemInDomainMeasure &	weightItemInDomain,
		int	maxLevel,
		double	minWeight
	)

inline

Find all children node at maximum level and add them to the result list. Skip nodes if their weight is below minWeight.

Definition at line 81 of file WeightedFastHoughTree.h.

      {
        auto skipLowWeightNode = [minWeight](const Node * node) {
          return not(node->getWeight() >= minWeight);
        };
        return findLeavesDisjoint(weightItemInDomain, maxLevel, skipLowWeightNode);
      }

◆ findLeavesDisjoint()

std::vector< std::pair< ADomain, std::vector< T > > > findLeavesDisjoint	(	AItemInDomainMeasure &	weightItemInDomain,
		int	maxLevel,
		ASkipNodePredicate &	skipNode
	)

inline

Find all children node at maximum level and add them to the result list. Skip nodes if skipNode returns true.

Definition at line 94 of file WeightedFastHoughTree.h.

      {
        std::vector<std::pair<ADomain,  std::vector<T> > > found;
        auto isLeaf = [&found, &skipNode, maxLevel](Node * node) {
          // Skip the expansion and the filling of the children
          if (skipNode(node)) {
            return true;
          }
 
          // Node is a leaf at the maximum level
          // Save its content
          // Do not walk children
          if (node->getLevel() >= maxLevel) {
            const ADomain* domain = node;
            found.emplace_back(*domain, std::vector<T>(node->begin(), node->end()));
            for (WithSharedMark<T>& markableItem : *node) {
              markableItem.mark();
            }
            return true;
          }
 
          // Else to node has enough weight and is not at the lowest level
          // Signal that it is not a leaf
          // Continue to create and fill children.
          return false;
        };
        fillWalk(weightItemInDomain, isLeaf);
        return found;
      }

◆ getNNodes()

int getNNodes ( ) const

inlineinherited

Gets the number of nodes currently contained in the tree Also demonstrates how to walk over the tree.

Definition at line 248 of file DynTree.h.

      {
        int nNodes = 0;
        auto countNodes = [&nNodes](const Node*) -> bool {
          ++nNodes;
          return true;
        };
        const_cast<DynTree&>(*this).walk(countNodes);
        //walk(countNodes);
        return nNodes;
      }

◆ getNNodesByLevel()

std::map< int, int > getNNodesByLevel ( ) const

inlineinherited

Gets the number of nodes by level in the tree Also demonstrates how to walk over the tree.

Definition at line 264 of file DynTree.h.

      {
        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;
      }

◆ getTopNode() [1/2]

Node & getTopNode ( )

inlineinherited

Getter for the top node of the tree.

Definition at line 237 of file DynTree.h.

238 { return m_topNode; }

Belle2::TrackFindingCDC::DynTree::m_topNode

Node m_topNode

Memory for the top node of the tree.

Definition: DynTree.h:361

◆ getTopNode() [2/2]

const Node & getTopNode ( ) const

inlineinherited

Constant getter for the top node of the tree.

Definition at line 241 of file DynTree.h.

242 { return m_topNode; }

◆ getUnusedChildren()

std::vector< Node > * getUnusedChildren ( )

inlineprivateinherited

Acquire the next unused child node structure, recycling all memory.

Definition at line 304 of file DynTree.h.

      {
        if (m_nUsedChildren >= m_children.size()) {
          m_children.emplace_back();
        }
        ++m_nUsedChildren;
        return &(m_children[m_nUsedChildren - 1]);
      }

◆ raze()

void raze ( )

inline

Like fell but also releases all memory the tree has acquired during long executions.

Definition at line 300 of file WeightedFastHoughTree.h.

      {
        this->fell();
        Super::raze();
        m_marks.shrink_to_fit();
      }

◆ seed()

void seed ( const Ts & items )

inline

Take the item set and insert them into the top node of the hough space.

Definition at line 66 of file WeightedFastHoughTree.h.

      {
        this->fell();
        Node& topNode = this->getTopNode();
        for (auto&& item : items) {
          m_marks.push_back(false);
          bool& markOfItem = m_marks.back();
          Weight weight = DBL_MAX;
          topNode.insert(WithSharedMark<T>(T(item), &markOfItem), weight);
        }
      }

◆ walk() [1/2]

void walk ( AWalker & walker )

inlineinherited

Forward walk to the top node.

Definition at line 316 of file DynTree.h.

      {
        static_assert(std::is_assignable<std::function<bool(Node*)>, AWalker>(), "");
 
        getTopNode().walk(walker);
      }

◆ walk() [2/2]

void walk	(	AWalker &	walker,
		APriorityMeasure &	priority
	)

inlineinherited

Forward walk to the top node.

Definition at line 325 of file DynTree.h.

      {
        static_assert(std::is_assignable<std::function<bool(Node*)>, AWalker>(), "");
        static_assert(std::is_assignable<std::function<float(Node*)>, APriorityMeasure>(), "");
 
        getTopNode().walk(walker, priority);
      }

◆ walkHeighWeightFirst()

void walkHeighWeightFirst ( ATreeWalker & walker )

inline

Walk the tree investigating the heaviest children with priority.

Clear items that have been marked as used before evaluating the weight.

Definition at line 277 of file WeightedFastHoughTree.h.

      {
        auto priority = [](Node * node) -> float {
          auto isMarked = [](const WithSharedMark<T>& markableItem) -> bool {
            return markableItem.isMarked();
          };
          node->eraseIf(isMarked);
          return node->getWeight();
        };
 
        this->walk(walker, priority);
      }

Member Data Documentation

◆ m_children

std::deque<typename Node::Children> m_children

inherited

Central point to provide memory for the child structures.

Definition at line 364 of file DynTree.h.

◆ m_marks

std::deque<bool> m_marks

private

Memory of the used marks of the items.

Definition at line 309 of file WeightedFastHoughTree.h.

◆ m_nUsedChildren

size_t m_nUsedChildren = 0

inherited

Last index of used children.

Definition at line 367 of file DynTree.h.

◆ m_subPropertiesFactory

SubPropertiesFactory m_subPropertiesFactory

inherited

Instance of the properties factory for the sub nodes.

Definition at line 358 of file DynTree.h.

◆ m_topNode

Node m_topNode

inherited

Memory for the top node of the tree.

Definition at line 361 of file DynTree.h.

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

tracking/trackFindingCDC/hough/trees/include/WeightedFastHoughTree.h

Public Types

Public Member Functions

Public Attributes

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Node

◆ Properties

◆ SubPropertiesFactory

◆ Super

◆ This

Member Function Documentation

◆ createChildren()

◆ fell()

◆ fillWalk()

◆ findHeaviestLeaf()

◆ findHeaviestLeafRepeated() [1/2]

◆ findHeaviestLeafRepeated() [2/2]

◆ findHeaviestLeafSingle()

◆ findHeavyLeavesDisjoint()

◆ findLeavesDisjoint()

◆ getNNodes()

◆ getNNodesByLevel()

◆ getTopNode() [1/2]

◆ getTopNode() [2/2]

◆ getUnusedChildren()

◆ raze()

◆ seed()

◆ walk() [1/2]

◆ walk() [2/2]

◆ walkHeighWeightFirst()

Member Data Documentation

◆ m_children

◆ m_marks

◆ m_nUsedChildren

◆ m_subPropertiesFactory

◆ m_topNode