Belle II Software development
WeightedFastHoughTree< T, ADomain, ADomainDivsion > Class Template Reference

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 >:
WeightedParititioningDynTree< WithSharedMark< T >, ADomain, ADomainDivsion > DynTree< AProperties, ASubPropertiesFactory >

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 >
NodefindHeaviestLeaf (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.
 
NodegetTopNode ()
 Getter for the top node of the tree.
 
const NodegetTopNode () 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.

285 {
286 std::vector<Node>* result = getUnusedChildren();
287 auto subProperties = m_subPropertiesFactory(*parentNode);
288 if (subProperties.empty()) {
289 result->clear();
290 } else {
291 // Initialize new elements with dummy property.
292 result->resize(subProperties.size(), Node(subProperties.back()));
293 size_t iSubNode = 0;
294 for (auto& properties : subProperties) {
295 clearIfApplicable(result->at(iSubNode));
296 result->at(iSubNode) = properties;
297 ++iSubNode;
298 }
299 }
300 return result;
301 }
std::vector< Node > * getUnusedChildren()
Acquire the next unused child node structure, recycling all memory.
Definition: DynTree.h:304
SubPropertiesFactory m_subPropertiesFactory
Instance of the properties factory for the sub nodes.
Definition: DynTree.h:358

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

293 {
294 this->getTopNode().clear();
295 m_marks.clear();
296 Super::fell();
297 }
void fell()
Fell to tree meaning deleting all child nodes from the tree. Keeps the top node.
Definition: DynTree.h:334
Node & getTopNode()
Getter for the top node of the tree.
Definition: DynTree.h:237
std::deque< bool > m_marks
Memory of the used marks of the items.

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

241 {
242 auto walker = [&weightItemInDomain, &isLeaf](Node * node) {
243 // Check if node is a leaf
244 // Do not create children in this case
245 if (isLeaf(node)) {
246 // Do not walk children.
247 return false;
248 }
249
250 // Node is not a leaf.
251 // Check if it has children.
252 // If children have not been created, create and fill them.
253 typename Node::Children* children = node->getChildren();
254 if (not children) {
255 node->createChildren();
256 children = node->getChildren();
257 for (Node& childNode : *children) {
258 assert(childNode.getChildren() == nullptr);
259 assert(childNode.size() == 0);
260 auto measure =
261 [&childNode, &weightItemInDomain](WithSharedMark<T>& markableItem) -> Weight {
262 // Weighting function should not see the mark, but only the item itself.
263 T & item(markableItem);
264 return weightItemInDomain(item, &childNode);
265 };
266 childNode.insert(*node, measure);
267 }
268 }
269 // Continue to walk the children.
270 return true;
271 };
272 walkHeighWeightFirst(walker);
273 }
void walkHeighWeightFirst(ATreeWalker &walker)
Walk the tree investigating the heaviest children with priority.
typename Super::Node Node
Type of the node in the tree.

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

204 {
205 Node* heaviestNode = nullptr;
206 Weight heighestWeigth = NAN;
207 auto isLeaf = [&heaviestNode, &heighestWeigth, maxLevel, &skipNode](Node * node) {
208 // Skip the expansion and the filling of the children
209 if (skipNode(node)) {
210 return true;
211 }
212
213 Weight nodeWeight = node->getWeight();
214 // Skip the expansion and filling of the children if the node has not enough weight
215 if (not std::isnan(heighestWeigth) and not(nodeWeight > heighestWeigth)) {
216 return true;
217 }
218
219 // Node is a leaf at the maximum level and is heavier than everything seen before.
220 // Save its content
221 // Do not walk children
222 if (node->getLevel() >= maxLevel) {
223 heaviestNode = node;
224 heighestWeigth = nodeWeight;
225 return true;
226 }
227 return false;
228 };
229 fillWalk(weightItemInDomain, isLeaf);
230 return heaviestNode;
231 }
void fillWalk(AItemInDomainMeasure &weightItemInDomain, AIsLeafPredicate &isLeaf)
Walk through the children and fill them if necessary until isLeaf returns true.

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

157 {
158 std::vector<std::pair<ADomain, std::vector<T> > > found;
159 Node* node = findHeaviestLeaf(weightItemInDomain, maxLevel, skipNode);
160 while (node) {
161 const ADomain* domain = node;
162 found.emplace_back(*domain, std::vector<T>(node->begin(), node->end()));
163 for (WithSharedMark<T>& markableItem : *node) {
164 markableItem.mark();
165 }
166 node = findHeaviestLeaf(weightItemInDomain, maxLevel, skipNode);
167 }
168 return found;
169 }
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.

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

138 {
139 auto skipLowWeightNode = [minWeight](const Node * node) {
140 return not(node->getWeight() >= minWeight);
141 };
142 return findHeaviestLeafRepeated(weightItemInDomain, maxLevel, skipLowWeightNode);
143 }
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.

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

181 {
182 using Result = std::pair<ADomain, std::vector<T> >;
183 std::unique_ptr<Result> found = nullptr;
184 Node* node = findHeaviestLeaf(weightItemInDomain, maxLevel, skipNode);
185 if (node) {
186 const ADomain* domain = node;
187 found.reset(new Result(*domain, std::vector<T>(node->begin(), node->end())));
188 for (WithSharedMark<T>& markableItem : *node) {
189 markableItem.mark();
190 }
191 }
192 return found;
193 }

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

84 {
85 auto skipLowWeightNode = [minWeight](const Node * node) {
86 return not(node->getWeight() >= minWeight);
87 };
88 return findLeavesDisjoint(weightItemInDomain, maxLevel, skipLowWeightNode);
89 }
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 retur...

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

97 {
98 std::vector<std::pair<ADomain, std::vector<T> > > found;
99 auto isLeaf = [&found, &skipNode, maxLevel](Node * node) {
100 // Skip the expansion and the filling of the children
101 if (skipNode(node)) {
102 return true;
103 }
104
105 // Node is a leaf at the maximum level
106 // Save its content
107 // Do not walk children
108 if (node->getLevel() >= maxLevel) {
109 const ADomain* domain = node;
110 found.emplace_back(*domain, std::vector<T>(node->begin(), node->end()));
111 for (WithSharedMark<T>& markableItem : *node) {
112 markableItem.mark();
113 }
114 return true;
115 }
116
117 // Else to node has enough weight and is not at the lowest level
118 // Signal that it is not a leaf
119 // Continue to create and fill children.
120 return false;
121 };
122 fillWalk(weightItemInDomain, isLeaf);
123 return found;
124 }

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

249 {
250 int nNodes = 0;
251 auto countNodes = [&nNodes](const Node*) -> bool {
252 ++nNodes;
253 return true;
254 };
255 const_cast<DynTree&>(*this).walk(countNodes);
256 //walk(countNodes);
257 return nNodes;
258 }
DynTree(const Properties &properties, const SubPropertiesFactory &subPropertiesFactory=SubPropertiesFactory())
Constructor taking properties with which the top node of the tree is initialised.
Definition: DynTree.h:221

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

265 {
266 std::map<int, int> nNodesByLevel;
267 auto countNodes = [&nNodesByLevel](const Node * node) -> bool {
268 if (nNodesByLevel.count(node->getLevel()) == 0)
269 {
270 nNodesByLevel[node->getLevel()] = 1;
271 } else
272 {
273 nNodesByLevel[node->getLevel()]++;
274 }
275 return true;
276 };
277 const_cast<DynTree&>(*this).walk(countNodes);
278 //walk(countNodes);
279 return nNodesByLevel;
280 }

◆ 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; }
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.

305 {
306 if (m_nUsedChildren >= m_children.size()) {
307 m_children.emplace_back();
308 }
310 return &(m_children[m_nUsedChildren - 1]);
311 }
std::deque< typename Node::Children > m_children
Central point to provide memory for the child structures.
Definition: DynTree.h:364
size_t m_nUsedChildren
Last index of used children.
Definition: DynTree.h:367

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

301 {
302 this->fell();
303 Super::raze();
304 m_marks.shrink_to_fit();
305 }
void raze()
Like fell but also releases all memory the tree has acquired during long execution.
Definition: DynTree.h:349
void fell()
Fell to tree meaning deleting all child nodes from the tree. Keeps the top node.

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

67 {
68 this->fell();
69 Node& topNode = this->getTopNode();
70 for (auto&& item : items) {
71 m_marks.push_back(false);
72 bool& markOfItem = m_marks.back();
73 Weight weight = DBL_MAX;
74 topNode.insert(WithSharedMark<T>(T(item), &markOfItem), weight);
75 }
76 }

◆ walk() [1/2]

void walk ( AWalker &  walker)
inlineinherited

Forward walk to the top node.

Definition at line 316 of file DynTree.h.

317 {
318 static_assert(std::is_assignable<std::function<bool(Node*)>, AWalker>(), "");
319
320 getTopNode().walk(walker);
321 }
void walk(AWalker &walker)
Calls the walker with each node starting with the top node and continues depth first The walker can s...
Definition: DynTree.h:120

◆ walk() [2/2]

void walk ( AWalker &  walker,
APriorityMeasure &  priority 
)
inlineinherited

Forward walk to the top node.

Definition at line 325 of file DynTree.h.

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

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

278 {
279 auto priority = [](Node * node) -> float {
281 auto isMarked = [](const WithSharedMark<T>& markableItem) -> bool {
282 return markableItem.isMarked();
283 };
284 node->eraseIf(isMarked);
285 return node->getWeight();
286 };
287
288 this->walk(walker, priority);
289 }
void walk(AWalker &walker)
Forward walk to the top node.
Definition: DynTree.h:316

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: