10#include <tracking/trackFindingCDC/hough/trees/DynTree.h>
11#include <tracking/trackFindingCDC/hough/baseelements/WithWeightedItems.h>
12#include <tracking/trackFindingCDC/hough/baseelements/WithSharedMark.h>
25 namespace TrackFindingCDC {
28 template<
class T,
class ADomain,
class ADomainDivsion>
30 public DynTree< WithWeightedItems<ADomain, T>, ADomainDivsion> {
48 template<
class T,
class ADomain,
class ADomainDivsion>
70 for (
auto&& item : items) {
72 bool& markOfItem =
m_marks.back();
73 Weight weight = DBL_MAX;
79 template <
class AItemInDomainMeasure>
80 std::vector<std::pair<ADomain, std::vector<T>>>
85 auto skipLowWeightNode = [minWeight](
const Node * node) {
86 return not(node->getWeight() >= minWeight);
92 template <
class AItemInDomainMeasure,
class ASkipNodePredicate>
93 std::vector<std::pair<ADomain, std::vector<T>>>
96 ASkipNodePredicate& skipNode)
98 std::vector<std::pair<ADomain, std::vector<T> > > found;
99 auto isLeaf = [&found, &skipNode, maxLevel](
Node * node) {
101 if (skipNode(node)) {
108 if (node->getLevel() >= maxLevel) {
109 const ADomain* domain = node;
110 found.emplace_back(*domain, std::vector<T>(node->begin(), node->end()));
122 fillWalk(weightItemInDomain, isLeaf);
133 template <
class AItemInDomainMeasure>
134 std::vector<std::pair<ADomain, std::vector<T>>>
137 const Weight minWeight = NAN)
139 auto skipLowWeightNode = [minWeight](
const Node * node) {
140 return not(node->getWeight() >= minWeight);
152 template <
class AItemInDomainMeasure,
class ASkipNodePredicate>
153 std::vector<std::pair<ADomain, std::vector<T>>>
156 ASkipNodePredicate& skipNode)
158 std::vector<std::pair<ADomain, std::vector<T> > > found;
161 const ADomain* domain = node;
162 found.emplace_back(*domain, std::vector<T>(node->begin(), node->end()));
176 template <
class AItemInDomainMeasure,
class ASkipNodePredicate>
177 std::unique_ptr<std::pair<ADomain, std::vector<T>>>
180 ASkipNodePredicate& skipNode)
182 using Result = std::pair<ADomain, std::vector<T> >;
183 std::unique_ptr<Result> found =
nullptr;
186 const ADomain* domain = node;
187 found.reset(
new Result(*domain, std::vector<T>(node->begin(), node->end())));
200 template <
class AItemInDomainMeasure,
class ASkipNodePredicate>
203 ASkipNodePredicate& skipNode)
205 Node* heaviestNode =
nullptr;
206 Weight heighestWeigth = NAN;
207 auto isLeaf = [&heaviestNode, &heighestWeigth, maxLevel, &skipNode](
Node * node) {
209 if (skipNode(node)) {
213 Weight nodeWeight = node->getWeight();
215 if (not std::isnan(heighestWeigth) and not(nodeWeight > heighestWeigth)) {
222 if (node->getLevel() >= maxLevel) {
224 heighestWeigth = nodeWeight;
229 fillWalk(weightItemInDomain, isLeaf);
238 template<
class AItemInDomainMeasure,
class AIsLeafPredicate>
239 void fillWalk(AItemInDomainMeasure& weightItemInDomain,
240 AIsLeafPredicate& isLeaf)
242 auto walker = [&weightItemInDomain, &isLeaf](
Node * node) {
253 typename Node::Children* children = node->getChildren();
255 node->createChildren();
256 children = node->getChildren();
257 for (
Node& childNode : *children) {
258 assert(childNode.getChildren() ==
nullptr);
259 assert(childNode.size() == 0);
263 T & item(markableItem);
264 return weightItemInDomain(item, &childNode);
266 childNode.insert(*node, measure);
276 template<
class ATreeWalker>
279 auto priority = [](
Node * node) ->
float {
282 return markableItem.isMarked();
284 node->eraseIf(isMarked);
285 return node->getWeight();
288 this->
walk(walker, priority);
Class for a node in the tree.
This is the base class for all hough trees.
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 execution.
Node & getTopNode()
Getter for the top node of the tree.
void walk(AWalker &walker)
Forward walk to the top node.
Dynamic tree structure with weighted items in each node which are markable through out the tree.
void fell()
Fell to tree meaning deleting all child nodes from the tree. Keeps the top node.
void seed(const Ts &items)
Take the item set and insert them into the top node of the hough space.
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.
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...
void raze()
Like fell but also releases all memory the tree has acquired during long executions.
std::deque< bool > m_marks
Memory of the used marks of the items.
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.
void fillWalk(AItemInDomainMeasure &weightItemInDomain, AIsLeafPredicate &isLeaf)
Walk through the children and fill them if necessary until isLeaf returns true.
void walkHeighWeightFirst(ATreeWalker &walker)
Walk the tree investigating the heaviest children with priority.
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 i...
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.
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.
typename Super::Node Node
Type of the node in the tree.
Type of tree for partitioning the hough space.
WeightedParititioningDynTree(ADomain topDomain, ADomainDivsion domainDivsion)
Constructor attaching a vector of the weighted items to the top most node domain.
Mixin class to attach a mark that is shared among many instances.
A mixin class to attach a set of weighted items to a class.
Abstract base class for different kinds of events.