12 #include <tracking/trackFindingCDC/hough/trees/DynTree.h>
13 #include <tracking/trackFindingCDC/hough/baseelements/WithWeightedItems.h>
14 #include <tracking/trackFindingCDC/hough/baseelements/WithSharedMark.h>
27 namespace TrackFindingCDC {
30 template<
class T,
class ADomain,
class ADomainDivsion>
31 class WeightedParititioningDynTree :
32 public DynTree< WithWeightedItems<ADomain, T>, ADomainDivsion> {
35 using Super = DynTree< WithWeightedItems<ADomain, T>, ADomainDivsion>;
50 template<
class T,
class ADomain,
class ADomainDivsion>
63 using Node =
typename Super::Node;
68 void seed(
const Ts& items)
72 for (
auto && item : items) {
74 bool& markOfItem =
m_marks.back();
75 Weight weight = DBL_MAX;
81 template <
class AItemInDomainMeasure>
82 std::vector<std::pair<ADomain, std::vector<T>>>
87 auto skipLowWeightNode = [minWeight](
const Node * node) {
88 return not(node->getWeight() >= minWeight);
94 template <
class AItemInDomainMeasure,
class ASkipNodePredicate>
95 std::vector<std::pair<ADomain, std::vector<T>>>
98 ASkipNodePredicate& skipNode)
100 std::vector<std::pair<ADomain, std::vector<T> > > found;
101 auto isLeaf = [&found, &skipNode, maxLevel](
Node * node) {
103 if (skipNode(node)) {
110 if (node->getLevel() >= maxLevel) {
111 const ADomain* domain = node;
112 found.emplace_back(*domain, std::vector<T>(node->begin(), node->end()));
124 fillWalk(weightItemInDomain, isLeaf);
135 template <
class AItemInDomainMeasure>
136 std::vector<std::pair<ADomain, std::vector<T>>>
139 const Weight minWeight = NAN)
141 auto skipLowWeightNode = [minWeight](
const Node * node) {
142 return not(node->getWeight() >= minWeight);
154 template <
class AItemInDomainMeasure,
class ASkipNodePredicate>
155 std::vector<std::pair<ADomain, std::vector<T>>>
158 ASkipNodePredicate& skipNode)
160 std::vector<std::pair<ADomain, std::vector<T> > > found;
163 const ADomain* domain = node;
164 found.emplace_back(*domain, std::vector<T>(node->begin(), node->end()));
178 template <
class AItemInDomainMeasure,
class ASkipNodePredicate>
179 std::unique_ptr<std::pair<ADomain, std::vector<T>>>
182 ASkipNodePredicate& skipNode)
184 using Result = std::pair<ADomain, std::vector<T> >;
185 std::unique_ptr<Result> found =
nullptr;
188 const ADomain* domain = node;
189 found.reset(
new Result(*domain, std::vector<T>(node->begin(), node->end())));
202 template <
class AItemInDomainMeasure,
class ASkipNodePredicate>
205 ASkipNodePredicate& skipNode)
207 Node* heaviestNode =
nullptr;
208 Weight heighestWeigth = NAN;
209 auto isLeaf = [&heaviestNode, &heighestWeigth, maxLevel, &skipNode](
Node * node) {
211 if (skipNode(node)) {
215 Weight nodeWeight = node->getWeight();
217 if (not std::isnan(heighestWeigth) and not(nodeWeight > heighestWeigth)) {
224 if (node->getLevel() >= maxLevel) {
226 heighestWeigth = nodeWeight;
231 fillWalk(weightItemInDomain, isLeaf);
240 template<
class AItemInDomainMeasure,
class AIsLeafPredicate>
241 void fillWalk(AItemInDomainMeasure& weightItemInDomain,
242 AIsLeafPredicate& isLeaf)
244 auto walker = [&weightItemInDomain, &isLeaf](
Node * node) {
255 typename Node::Children* children = node->getChildren();
257 node->createChildren();
258 children = node->getChildren();
259 for (
Node& childNode : *children) {
260 assert(childNode.getChildren() ==
nullptr);
261 assert(childNode.size() == 0);
265 T & item(markableItem);
266 return weightItemInDomain(item, &childNode);
268 childNode.insert(*node, measure);
278 template<
class ATreeWalker>
281 auto priority = [](
Node * node) ->
float {
283 auto isMarked = [](
const WithSharedMark<T>& markableItem) ->
bool {
284 return markableItem.isMarked();
286 node->eraseIf(isMarked);
287 return node->getWeight();
290 this->
walk(walker, priority);