Logo ROOT  
Reference Guide
KDTree.icc
Go to the documentation of this file.
1// @(#)root/mathcore:$Id: IFunction.h 24537 2008-06-25 11:01:23Z moneta $
2// Authors: C. Gumpert 09/2011
3/**********************************************************************
4 * *
5 * Copyright (c) 2011 , LCG ROOT MathLib Team *
6 * *
7 * *
8 **********************************************************************/
9//
10// Implementation file for KDTree class
11//
12
13
14#ifndef KD_TREE_ICC
15#define KD_TREE_ICC
16
17#ifndef ROOT_Math_KDTree
18#error "Do not use KDTree.icc directly. #include \"KDTree.h\" instead."
19#endif // ROOT_Math_KDTree
20
21// STL include(s)
22#include <iostream>
23#include <functional>
24#include <algorithm>
25#include <limits>
26
27namespace ROOT
28{
29 namespace Math
30 {
31//______________________________________________________________________________
32 template<class _DataPoint>
34 fBucketSize(iBucketSize),
35 fIsFrozen(false)
36 {
37 //standard constructor creates an empty k-d tree
38 //
39 //Input: iBucketSize - target population for each bin
40 //
41 //Note: - The actual interpretation of the bucket size as population depends on
42 // the chosen splitting option:
43 // kBinContent - iBucketSize applies to the sum of weights in each bucket
44 // kEffective - iBucketSize applies to the number of effective entries in each bucket
45 // - As long as the tree has not been frozen, it is ensured that no bucket
46 // contains more than 2 x target population but there is no statement about
47 // the minimum bucket population.
48 // However, given a reasonably large bucket size with respect to characteristic
49 // event weights and sufficient statistics, most of the buckets will have
50 // a population between [0.8 * iBucketSize .. 2 * iBucketSize]
51
52 // create dummy terminal node as head
53 TerminalNode* pTerminal = new TerminalNode(iBucketSize);
54 fHead = new HeadNode(*pTerminal);
55 pTerminal->Parent() = fHead;
56 }
57
58//______________________________________________________________________________
59 template<class _DataPoint>
61 fHead(0),
62 fBucketSize(1),
63 fIsFrozen(false)
64 {
65 //private standard constructor creating a not functional tree
66 //
67 //only used by interanl function for creating copies of the tree
68 }
69
70//______________________________________________________________________________
71 template<class _DataPoint>
73 {
74 //standard destructor deleting all nodes
75 //
76 //Note: - In case the option SetOWner(true) has been called beforehand and
77 // the tree is not yet frozen, all contained data point objects are
78 // deleted as well.
79
80 delete fHead;
81 }
82
83//______________________________________________________________________________
84 template<class _DataPoint>
86 {
87 //all buckets are reset
88 //
89 //This call results in empty buckets but the splitting structure is kept.
90 //You can now fill the formerly created binning with 'new' data points.
91 //In order to prevent further splitting, you might want to freeze the tree.
92 //
93 //Note: - In case the option SetOWner(true) has been called beforehand and
94 // the tree is not yet frozen, all contained data point objects are
95 // deleted as well.
96
97 for(iterator it = First(); it != End(); ++it)
98 it->EmptyBin();
99 }
100
101//______________________________________________________________________________
102 template<class _DataPoint>
104 {
105 //return an iterator representing the end of all buckets
106 //
107 //This function can be used the retrieve a limiter for both sides. It
108 //represents the 'one step after the last bin' as well as 'one step before
109 //the first bin'. However, you should not try to increment/decrement this
110 //iterator.
111
112 return iterator(0);
113 }
115//______________________________________________________________________________
116 template<class _DataPoint>
118 {
119 //return an iterator representing the end of all buckets
120 //
121 //This function can be used the retrieve a limiter for both sides. It
122 //represents the 'one step after the last bin' as well as 'one step before
123 //the first bin'. However, you should not try to increment/decrement this
124 //iterator.
125
126 return iterator(0);
127 }
128
129//______________________________________________________________________________
130 template<class _DataPoint>
132 {
133 //return an iterator to the first bucket
134 //
135 //Note: - Buckets are not ordered to any criteria.
136
137 BaseNode* pNode = fHead->Parent();
138 while(pNode->LeftChild())
139 pNode = pNode->LeftChild();
140
141 assert(dynamic_cast<BinNode*>(pNode));
142 return iterator((BinNode*)pNode);
143 }
144
145//______________________________________________________________________________
146 template<class _DataPoint>
148 {
149 //return an iterator to the first bucket
150 //
151 //Note: - Buckets are not ordered to any criteria.
152
153 BaseNode* pNode = fHead->Parent();
154 while(pNode->LeftChild())
155 pNode = pNode->LeftChild();
156
157 assert(dynamic_cast<BinNode*>(pNode));
158 return iterator((BinNode*)pNode);
159 }
160
161//______________________________________________________________________________
162 template<class _DataPoint>
164 {
165 //freeze the current tree
166 //
167 //By calling this function, the current splitting information in the tree is frozen.
168 //No further division of buckets into sub-buckets will occur.
169 //In addition all point related information are dropped. Therefore nearest neighbor
170 //searches or retrieving the data points from a bucket are not possible anymore.
171 //Furthermore, no restrictions on the population in each bucket exist if the tree
172 //is filled with further points.
173 //
174 //Note: - Technically it means that all TerminalNodes are converted to BinNodes
175 // resulting in a loss of all information related to individual data points.
176
177 // do it only once
178 if(!fIsFrozen)
179 {
180 std::vector<TerminalNode*> vBins;
181 // replace all terminal nodes by bin nodes
182 for(iterator it = First(); it != End(); ++it)
183 vBins.push_back(it.TN());
184
185 BinNode* pBin = 0;
186 for(typename std::vector<TerminalNode*>::iterator bit = vBins.begin(); bit != vBins.end(); ++bit)
187 {
188 pBin = (*bit)->ConvertToBinNode();
189 (*bit)->GetParentPointer() = pBin;
190 pBin->Parent() = (*bit)->Parent();
191 delete *bit;
192 }
193
194 fIsFrozen = true;
195 }
196 }
197
198//______________________________________________________________________________
199 template<class _DataPoint>
200 void KDTree<_DataPoint>::GetClosestPoints(const _DataPoint& rRef,UInt_t nPoints,
201 std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const
202 {
203 //returns the nPoints data points closest to the given reference point
204 //
205 //Input: rRef - reference point
206 // nPoints - desired number of closest points (0 < nPoints < total number of points in tree)
207 // vFoundPoints - vector containing all found points
208 //
209 //vFoundPoints contains the nPoints pairs of:
210 // first = pointer to found data point
211 // second = distance between found data point and reference point
212 //
213 //vFoundPoints is ordered in the sense that the point closest to the reference comes first.
214 //
215 //Note: - This method works only if the tree has not yet been frozen.
216
217 // check bad input and that tree is not frozen yet
218 if((nPoints > 0) && (!fIsFrozen))
219 fHead->GetClosestPoints(rRef,nPoints,vFoundPoints);
220 }
221
222//______________________________________________________________________________
223 template<class _DataPoint>
225 {
226 //returns the total effective entries of the tree
227 //
228 //Note: - This is not the sum of effective entries of all buckets!
229
230 Double_t fSumw = 0;
231 Double_t fSumw2 = 0;
232 for(iterator it = First(); it != End(); ++it)
233 {
234 fSumw += it->GetBinContent();
235 fSumw2 += it->GetSumw2();
236 }
237
238 return ((fSumw2) ? fSumw * fSumw / fSumw2 : 0);
239 }
240
241//______________________________________________________________________________
242 template<class _DataPoint>
244 {
245 //returns the number of filled data points
246
247 UInt_t iPoints = 0;
248 for(iterator it = First(); it != End(); ++it)
249 iPoints += it->GetEntries();
250
251 return iPoints;
252 }
253
254//______________________________________________________________________________
255 template<class _DataPoint>
257 {
258 //returns a frozen copy of this k-d tree
259 //
260 //Note: - The current tree remains unchanged.
261 // - The new tree is owned by the user (-> you should invoke 'delete' if you do not need it anymore)!
262
264 pTree->fBucketSize = fBucketSize;
265 pTree->fHead = fHead->Clone();
266 pTree->fIsFrozen = true;
267
268 return pTree;
269 }
270
271//______________________________________________________________________________
272 template<class _DataPoint>
274 {
275 //returns the number of buckets
276
277 UInt_t iBins = 0;
278 for(iterator it = First(); it != End(); ++it)
279 ++iBins;
280
281 return iBins;
282 }
283
284//______________________________________________________________________________
285 template<class _DataPoint>
286 void KDTree<_DataPoint>::GetPointsWithinDist(const _DataPoint& rRef,value_type fDist,
287 std::vector<const _DataPoint*>& vFoundPoints) const
288 {
289 //returns all data points within a given distance around the reference point
290 //
291 //Input: rRef - reference point
292 // fDist - radius of sphere around reference point (0 < fDist)
293 // vFoundPoints - vector to store the results
294 //
295 //vFoundPoints contains the pointers to all data points in the specified sphere.
296 //The points are NOT ordered according to their distance.
297 //
298 //Note - This method works only if the tree has not yet been frozen.
299 // - Distance is defined as euclidian distance in a k-dimensional space.
300
301 // valid distance given and tree not frozen yet
302 if((fDist > 0) && (!fIsFrozen))
303 fHead->GetPointsWithinDist(rRef,fDist,vFoundPoints);
304 }
305
306//______________________________________________________________________________
307 template<class _DataPoint>
309 {
310 //returns the total sum of weights
311
312 Double_t fSumw = 0;
313 for(iterator it = First(); it != End(); ++it)
314 fSumw += it->GetSumw();
315
316 return fSumw;
317 }
318
319//______________________________________________________________________________
320 template<class _DataPoint>
322 {
323 //returns the total sum of weights^2
324
325 Double_t fSumw2 = 0;
326 for(iterator it = First(); it != End(); ++it)
327 fSumw2 += it->GetSumw2();
328
329 return fSumw2;
330 }
331
332//______________________________________________________________________________
333 template<class _DataPoint>
335 {
336 //returns an iterator to the last bucket
337 //
338 //Note: - Buckets are not ordered to any criteria.
339
340 BaseNode* pNode = fHead->Parent();
341 while(pNode->RightChild())
342 pNode = pNode->RightChild();
343
344 assert(dynamic_cast<TerminalNode*>(pNode));
345 return iterator((TerminalNode*)pNode);
346 }
347
348//______________________________________________________________________________
349 template<class _DataPoint>
351 {
352 //returns an iterator to the last bucket
353 //
354 //Note: - Buckets are not ordered to any criteria.
355
356 BaseNode* pNode = fHead->Parent();
357 while(pNode->RightChild())
358 pNode = pNode->RightChild();
359
360 assert(dynamic_cast<BinNode*>(pNode));
361 return iterator((BinNode*)pNode);
362 }
363
364//______________________________________________________________________________
365 template<class _DataPoint>
367 {
368 //resets the tree
369 //
370 //Afterwards the tree is completely empty and all splitting information is lost.
371 //
372 //Note: - In case the option SetOWner(true) has been called beforehand and
373 // the tree is not yet frozen, all contained data point objects are
374 // deleted as well.
375 // - The 'frozen' status is reset to false. Otherwise you won't be able to
376 // create splittings and the tree would consist of only one large bucket.
377
378 // delete current tree
379 delete fHead->Parent();
380 // create new (and empty) top bucket
381 TerminalNode* pTerminal = new TerminalNode(fBucketSize);
382 pTerminal->Parent() = fHead;
383 fHead->Parent() = pTerminal;
384
385 // reset 'freeze' status
386 fIsFrozen = false;
387 }
388
389//______________________________________________________________________________
390 template<class _DataPoint>
392 {
393 //specifies the ownership of data points
394 //
395 //Input: bIsOwner - true: data points are located on the heap and the ownership
396 // is transferred to the tree object
397 // false: the data points are not owned by the tree
398 //
399 //Note: - This function has no effect if the tree is already frozen.
400
401 if(!fIsFrozen)
402 {
403 for(iterator it = First(); it != End(); ++it)
404 it.TN()->SetOwner(bIsOwner);
405 }
406 }
407
408//______________________________________________________________________________
409 template<class _DataPoint>
411 {
412 //sets the splitting option for the buckets
413 //
414 //Buckets are split into two sub-buckets if their population reaches twice the
415 //given bucket size. The definition of population depends on the chosen splitting
416 //option:
417 //kBinContent = population is the sum of weights
418 //kEffective = population is the number of effective entries
419 //
420 //Note: - In principle it possible to change the splitting mode while filling the tree.
421 // However, this should be avoided to ensure an optimal splitting.
422 // - This function has no effect if the tree is already frozen.
423
424 if(!fIsFrozen)
425 {
426 for(iterator it = First(); it != End(); ++it)
427 it.TN()->SetSplitOption(opt);
428 }
429 }
430
431//______________________________________________________________________________
432 template<class _DataPoint>
433 bool KDTree<_DataPoint>::ComparePoints::operator()(const _DataPoint* pFirst,const _DataPoint* pSecond) const
434 {
435 //compares two points along set axis
436 //
437 //Uses the internal comparison axis of the ComparePoints object to evaluate:
438 //
439 // pFirst[Axis] < pSecond[Axis]
440 //
441 //Note: - The template class _DataPoint has to provide a static function:
442 //
443 // static UInt_t _DataPoint::Dimension()
444 //
445 // returning the dimensionality of the data point.
446 // - The dimensionality of the two data points is higher than the currently
447 // set comparison axis.
448
449 assert(pFirst && pSecond && (fAxis < KDTree<_DataPoint>::Dimension()));
450
451 return (pFirst->GetCoordinate(fAxis) < pSecond->GetCoordinate(fAxis));
452 }
453
454//______________________________________________________________________________
455 template<class _DataPoint>
456 bool KDTree<_DataPoint>::Cut::operator<(const _DataPoint& rPoint) const
457 {
458 //comapres a point with the given cut
459 //
460 // this cut value < rPoint.GetCoordinate(this cut axis)
461 //
462 //Note: - The template class _DataPoint has to provide a static function:
463 //
464 // static UInt_t _DataPoint::Dimension()
465 //
466 // returning the dimensionality of the data point.
467 // - The dimensionality of the given data point is higher than the cut
468 // axis.
469
470 assert(Dimension() > fAxis);
471 return (fCutValue < rPoint.GetCoordinate(fAxis));
472 }
473
474//______________________________________________________________________________
475 template<class _DataPoint>
476 bool KDTree<_DataPoint>::Cut::operator>(const _DataPoint& rPoint) const
477 {
478 //comapres a point with the given cut
479 //
480 // this cut value > rPoint.GetCoordinate(this cut axis)
481 //
482 //Note: - The template class _DataPoint has to provide a static function:
483 //
484 // static UInt_t _DataPoint::Dimension()
485 //
486 // returning the dimensionality of the data point.
487 // - The dimensionality of the given data point is higher than the cut
488 // axis.
489
490 assert(Dimension() > fAxis);
491 return (fCutValue > rPoint.GetCoordinate(fAxis));
492 }
493
494//______________________________________________________________________________
495 template<class _DataPoint>
497 fParent(pParent),
498 fLeftChild(0),
499 fRightChild(0)
500 {
501 //standard constructor
502 }
503
504//______________________________________________________________________________
505 template<class _DataPoint>
507 {
508 //standard destructor
509 //
510 //Note: - both children are deleted but no pointer rearrangement is done
511 // -> should not be a problem as long as you do not try to rely on
512 // tree internal information
513
514 delete LeftChild();
515 delete RightChild();
516 }
517
518//______________________________________________________________________________
519 template<class _DataPoint>
521 {
522 //returns a reference to the pointer from the parent node to the current node
523 //
524 //Note: - This shoud never be called for the head node (as it is the head!)
525
526 assert(!IsHeadNode());
527
528 if(Parent()->Parent() == this)
529 return Parent()->Parent();
530 if(Parent()->LeftChild() == this)
531 return Parent()->LeftChild();
532 if(Parent()->RightChild() == this)
533 return Parent()->RightChild();
534
535 // should never reach this line
536 assert(false);
537 return Parent(); // to fix a warning statement
538 }
539
540//______________________________________________________________________________
541 template<class _DataPoint>
543 {
544 //checks whether the current node is a left node
545 //
546 //Note: - returns false in the case of the head node (which is no child at all)
547
548 if(Parent()->IsHeadNode())
549 return false;
550 else
551 return (Parent()->LeftChild() == this);
552 }
553
554//______________________________________________________________________________
555 template<class _DataPoint>
557 {
558 //creates an identical copy
559 //
560 //Note: - The Clone() function is propagated to the whole tree -> the returned
561 // pointer is the head node of a complete new tree.
562
563 BaseNode* pParent = Parent()->Clone();
564 HeadNode* pHead = new HeadNode(*pParent);
565 pParent->Parent() = pHead;
566
567 return pHead;
568 }
569
570//______________________________________________________________________________
571 template<class _DataPoint>
572 inline void KDTree<_DataPoint>::HeadNode::GetClosestPoints(const _DataPoint& rRef,UInt_t nPoints,
573 std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const
574 {
575 Parent()->GetClosestPoints(rRef,nPoints,vFoundPoints);
576 }
577
578//______________________________________________________________________________
579 template<class _DataPoint>
580 inline void KDTree<_DataPoint>::HeadNode::GetPointsWithinDist(const _DataPoint& rRef,value_type fDist,
581 std::vector<const _DataPoint*>& vFoundPoints) const
582 {
583 Parent()->GetPointsWithinDist(rRef,fDist,vFoundPoints);
584 }
585
586//______________________________________________________________________________
587 template<class _DataPoint>
589 BaseNode& rRight,BaseNode* pParent):
590 BaseNode(pParent),
591 fCut(new Cut(iAxis,fCutValue))
592 {
593 //standard constructor for spitting node which represents a splitting hyperplane
594 //
595 //Input: iAxis - axis on which the split is performed
596 // fCutValue - cut value
597 // rLeft - left sub-bucket
598 // rRight - right sub-bucket
599 // pParent - optional pointer to parent node
600 //
601 //Note: - As a split node can never be a leaf, always the two child nodes has to
602 // be passed at construction time.
603
604 this->LeftChild() = &rLeft;
605 this->RightChild() = &rRight;
606 }
607
608//______________________________________________________________________________
609 template<class _DataPoint>
611 {
612 // standard destructor
613
614 delete fCut;
615 }
616
617//______________________________________________________________________________
618 template<class _DataPoint>
620 {
621 //creates a direct copy of this node
622 //
623 //This also involves the copying of the child nodes.
624
625 BaseNode* pLeft = this->LeftChild()->Clone();
626 BaseNode* pRight = this->RightChild()->Clone();
627
628 SplitNode* pSplit = new SplitNode(fCut->GetAxis(),fCut->GetCutValue(),*pLeft,*pRight);
629
630 pLeft->Parent() = pSplit;
631 pRight->Parent() = pSplit;
632
633 return pSplit;
634 }
635
636//______________________________________________________________________________
637 template<class _DataPoint>
638 const typename KDTree<_DataPoint>::BinNode* KDTree<_DataPoint>::SplitNode::FindNode(const _DataPoint& rPoint) const
639 {
640 //finds bin node containing the given reference point
641
642 // pPoint < cut -> left sub tree
643 if(*fCut > rPoint)
644 return this->LeftChild()->FindNode(rPoint);
645 // pPoint >= cut -> right sub tree
646 else
647 return this->RightChild()->FindNode(rPoint);
648 }
649
650//______________________________________________________________________________
651 template<class _DataPoint>
652 void KDTree<_DataPoint>::SplitNode::GetClosestPoints(const _DataPoint& rRef,UInt_t nPoints,
653 std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const
654 {
655 //finds the closest points around the given reference point
656 //
657 //Input: rRef - reference point
658 // nPoints - number of points to look for (should be less than the total number of points in the tree)
659 // vFoundPoints - vector in which the result is stored as pair <pointer to found data point,distance to reference point>
660 //
661 //Note: vFoundPoints is ordered in the sense that the found point closest to the reference point comes first.
662
663 // rRef < cut -> left sub tree
664 if(*fCut > rRef)
665 {
666 this->LeftChild()->GetClosestPoints(rRef,nPoints,vFoundPoints);
667
668 // number of found points lower than wanted number of points
669 // or: sphere with (radius = largest distance between rRef and vFoundPoints) intersects the splitting plane
670 // --> look also in right sub bucket
671 if((vFoundPoints.size() < nPoints) || (vFoundPoints.back().second > fabs(rRef.GetCoordinate(fCut->GetAxis()) - fCut->GetCutValue())))
672 this->RightChild()->GetClosestPoints(rRef,nPoints,vFoundPoints);
673 }
674 // rRef >= cut -> right sub tree
675 else
676 {
677 this->RightChild()->GetClosestPoints(rRef,nPoints,vFoundPoints);
678
679 // number of found points lower than wanted number of points
680 // or: sphere with (radius = largest distance between rRef and vFoundPoints) intersects the splitting plane
681 // --> look also in left sub bucket
682 if((vFoundPoints.size() < nPoints) || (vFoundPoints.back().second > fabs(rRef.GetCoordinate(fCut->GetAxis()) - fCut->GetCutValue())))
683 this->LeftChild()->GetClosestPoints(rRef,nPoints,vFoundPoints);
684 }
685 }
686
687//______________________________________________________________________________
688 template<class _DataPoint>
690 std::vector<const _DataPoint*>& vFoundPoints) const
691 {
692 //returns the points within a certain distance around the reference point
693 //
694 //Input: rRef - reference point
695 // fDist - radius of sphere to scan ( > 0)
696 // vFoundPoints - vector in which all found points are stored
697 //
698 //Note: vFoundPoints ist NOT ordered.
699
700 // does the sphere around rRef intersect the splitting plane?
701 // no -> check only points in sub bucket which rRef belongs to
702 if(fabs(rRef.GetCoordinate(fCut->GetAxis()) - fCut->GetCutValue()) > fDist)
703 {
704 // rRef < cut -> left sub tree
705 if(*fCut > rRef)
706 this->LeftChild()->GetPointsWithinDist(rRef,fDist,vFoundPoints);
707 // rRef >= cut -> right sub tree
708 else
709 this->RightChild()->GetPointsWithinDist(rRef,fDist,vFoundPoints);
710 }
711 // yes -> check points in both sub buckets
712 else
713 {
714 this->RightChild()->GetPointsWithinDist(rRef,fDist,vFoundPoints);
715 this->LeftChild()->GetPointsWithinDist(rRef,fDist,vFoundPoints);
716 }
717 }
718
719//______________________________________________________________________________
720 template<class _DataPoint>
721 inline Bool_t KDTree<_DataPoint>::SplitNode::Insert(const _DataPoint& rPoint)
722 {
723 //inserts a new data point in the tree
724
725 // pPoint < cut -> left sub tree
726 if(*fCut > rPoint)
727 return this->LeftChild()->Insert(rPoint);
728 // pPoint >= cut -> right sub tree
729 else
730 return this->RightChild()->Insert(rPoint);
731 }
732
733//______________________________________________________________________________
734 template<class _DataPoint>
736 {
737 //prints some information about the current node
738
739 std::cout << "SplitNode at " << this << " in row " << iRow << std::endl;
740 std::cout << "cut on " << fCut->GetCutValue() << " at axis " << fCut->GetAxis() << std::endl;
741
742 this->LeftChild()->Print(iRow+1);
743 this->RightChild()->Print(iRow+1);
744 }
745
746//______________________________________________________________________________
747 template<class _DataPoint>
749 BaseNode(pParent),
750 fBoundaries(std::vector<tBoundary>(Dimension(),std::make_pair(0,0))),
751 fSumw(0),
752 fSumw2(0),
753 fEntries(0)
754 {
755 //standard constructor
756 }
757
758//______________________________________________________________________________
759 template<class _DataPoint>
761 BaseNode(),
762 fBoundaries(copy.fBoundaries),
763 fSumw(copy.fSumw),
764 fSumw2(copy.fSumw2),
765 fEntries(copy.fEntries)
766 {
767 //copy constructor
768 //
769 //Note: - The resulting bin node is NOT connected to any other node
770 // -> it is not part of any tree
771
772 this->Parent() = 0;
773 this->LeftChild() = 0;
774 this->RightChild() = 0;
775 }
776
777//______________________________________________________________________________
778 template<class _DataPoint>
780 {
781 //creates indentical copy which is not part of the tree anymore
782
783 return new BinNode(*this);
784 }
785
786//______________________________________________________________________________
787 template<class _DataPoint>
789 {
790 //resets bin content, sumw, asumw2 and entries
791
792 fSumw2 = fSumw = 0;
793 fEntries = 0;
794 }
795
796//______________________________________________________________________________
797 template<class _DataPoint>
799 {
800 //assignment operator
801 //
802 //Note: - Should not be used because it can lead to inconsistencies with respect
803 // bin boundaries.
804
805 fBoundaries = rhs.fBoundaries;
806 fSumw = rhs.fSumw;
807 fSumw2 = rhs.fSumw2;
808 fEntries = rhs.fEntries;
809 return *this;
810 }
811
812//______________________________________________________________________________
813 template<class _DataPoint>
814 const typename KDTree<_DataPoint>::BinNode* KDTree<_DataPoint>::BinNode::FindNode(const _DataPoint& rPoint) const
815 {
816 //finds bin node containing the given reference point
817
818 if(IsInBin(rPoint))
819 return this;
820 else
821 return 0;
822 }
823
824//______________________________________________________________________________
825 template<class _DataPoint>
827 {
828 //returns the bin center of the current node
829 //
830 //Note: - The bin center is defined as
831 // coordinate i = 0.5 * (lower bound i + uper bound i)
832
833 _DataPoint rPoint;
834
835 for(UInt_t k = 0; k < Dimension(); ++k)
836 rPoint.SetCoordinate(k,0.5 * (fBoundaries.at(k).first + fBoundaries.at(k).second));
837
838 return rPoint;
839 }
840
841//______________________________________________________________________________
842 template<class _DataPoint>
844 {
845 //returns the volume of the current bin
846 //
847 //Note: - The volume is defined as
848 // vol = product over i (upper bound i - lower bound i)
849
850 Double_t dVol = 1;
851 for(typename std::vector<tBoundary>::const_iterator it = fBoundaries.begin(); it != fBoundaries.end(); ++it)
852 dVol *= (it->second - it->first);
853
854 return dVol;
855 }
856
857
858//______________________________________________________________________________
859 template<class _DataPoint>
861 {
862 //inserts a new data point in this bin
863
864 if(IsInBin(rPoint))
865 {
866 ++fEntries;
867 fSumw += rPoint.GetWeight();
868 fSumw2 += pow(rPoint.GetWeight(),2);
869
870 return true;
871 }
872 else
873 return false;
874 }
875
876//______________________________________________________________________________
877 template<class _DataPoint>
878 Bool_t KDTree<_DataPoint>::BinNode::IsInBin(const _DataPoint& rPoint) const
879 {
880 //checks whether the given point is inside the boundaries of this bin
881
882 for(UInt_t k = 0; k < Dimension(); ++k)
883 if((rPoint.GetCoordinate(k) < fBoundaries.at(k).first) || (fBoundaries.at(k).second < rPoint.GetCoordinate(k)))
884 return false;
885
886 return true;
887 }
888
889//______________________________________________________________________________
890 template<class _DataPoint>
892 {
893 //prints some information about this bin node
894
895 std::cout << "BinNode at " << this << std::endl;
896 std::cout << "containing " << GetEntries() << " entries" << std::endl;
897 std::cout << "sumw = " << GetBinContent() << " sumw2 = " << GetSumw2() << " => effective entries = " << GetEffectiveEntries() << std::endl;
898 std::cout << "volume = " << GetVolume() << " and bin center at (";
899 _DataPoint rBinCenter = GetBinCenter();
900 for(UInt_t dim = 0; dim < Dimension(); ++dim)
901 {
902 std::cout << rBinCenter.GetCoordinate(dim);
903 if(dim < Dimension() -1)
904 std::cout << ",";
905 }
906 std::cout << ")" << std::endl;
907 std::cout << "boundaries are ";
908 for(typename std::vector<tBoundary>::const_iterator it = fBoundaries.begin(); it != fBoundaries.end(); ++it)
909 std::cout << "(" << it->first << " ... " << it->second << ") ";
910 std::cout << std::endl;
911 }
912
913//______________________________________________________________________________
914 template<class _DataPoint>
916 BinNode(pParent),
917 fOwnData(false),
918 fSplitOption(kEffective),
919 fBucketSize(iBucketSize),
920 fSplitAxis(0)
921 {
922 //standard constructor
923 //
924 //Input: iBucketSize - desired bucket size
925 // pParent - pointer to parent node (optional)
926 //
927 //Note: - The bucket size has to be positive.
928 // - The standard split option is kEffective.
929 // - By default the data points are not owned by the tree.
930
931 assert(fBucketSize > 0);
932 }
933
934//______________________________________________________________________________
935 template<class _DataPoint>
937 BinNode(),
938 fOwnData(false),
939 fSplitOption(kEffective),
940 fBucketSize(iBucketSize),
941 fSplitAxis(iSplitAxis % Dimension()),
942 fDataPoints(std::vector<const _DataPoint*>(first,end))
943 {
944 //internal constructor used for splitting
945 //
946 //Input: iBucketSize - desired bucket size
947 // iSplitAxis - axis for next splitting
948 // first,end - iterators pointing to the beginning and end of data points
949 // which are copied to this TerminalNode
950
951 // recalculate sumw and sumw2
952 for(data_it it = fDataPoints.begin(); it != fDataPoints.end(); ++it)
953 {
954 this->fSumw += (*it)->GetWeight();
955 this->fSumw2 += pow((*it)->GetWeight(),2);
956 }
957
958 this->fEntries = fDataPoints.size();
959 }
960
961//______________________________________________________________________________
962 template<class _DataPoint>
964 {
965 //standard destructor
966 //
967 //Note: - If fOwnData is set, all associated data point objects are deleted
968
969 if(fOwnData)
970 {
971 for(typename std::vector<const _DataPoint*>::iterator it = fDataPoints.begin();
972 it != fDataPoints.end(); ++it)
973 delete *it;
974 }
975 }
976
977//______________________________________________________________________________
978 template<class _DataPoint>
980 {
981 //creates a new BinNode with information of the TerminalNode
982 //
983 //The returned BinNode contains all information of this TerminalNode except the
984 //point-related information.
985 //
986 //Note: - The returned node is not owned by the tree but the user as to take care of it.
987
988 UpdateBoundaries();
989 BinNode* pBin = new BinNode(*this);
990
991 return pBin;
992 }
993
994//______________________________________________________________________________
995 template<class _DataPoint>
997 {
998 //resets the bin content and removes all data points
999 //
1000 //Note: - If fOwnData is set, all associated data points are deleted.
1001
1002 // delete data points
1003 if(fOwnData)
1004 {
1005 for(typename std::vector<const _DataPoint*>::iterator it = fDataPoints.begin();
1006 it != fDataPoints.end(); ++it)
1007 delete *it;
1008 }
1009 fDataPoints.clear();
1010 UpdateBoundaries();
1012 }
1013//______________________________________________________________________________
1014 template<class _DataPoint>
1015#ifdef _AIX
1017#else
1018 const std::vector<typename KDTree<_DataPoint>::TerminalNode::tBoundary>& KDTree<_DataPoint>::TerminalNode::GetBoundaries() const
1019 {
1020 //returns the boundaries of this TerminalNode
1021 //
1022 //Note: - In a high-dimensional space most of the nodes are bounded only on
1023 // one side due to a split. One-sided intervals would result in an
1024 // infinite volume of the bin which is not the desired behaviour.
1025 // Therefore the following convention is used for determining the
1026 // boundaries:
1027 // If a node is not restricted along one axis on one/both side(s) due
1028 // to a split, the corresponding upper/lower boundary is set to
1029 // the minimum/maximum coordinate alogn this axis of all contained
1030 // data points.
1031 // This procedure maximises the density in the bins.
1032
1033 const_cast<TerminalNode*>(this)->UpdateBoundaries();
1034
1035 return BinNode::GetBoundaries();
1036 }
1037#endif
1038//______________________________________________________________________________
1039 template<class _DataPoint>
1041 std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const
1042 {
1043 //finds the closest points around the given reference point
1044 //
1045 //Input: rRef - reference point
1046 // nPoints - number of points to look for (should be less than the total number of points in the tree)
1047 // vFoundPoints - vector in which the result is stored as pair <pointer to found data point,distance to reference point>
1048 //
1049 //Note: vFoundPoints is ordered in the sense that the found point closest to the reference point comes first.
1050
1051 // store maximal distance so far if desired number of points already found
1052 value_type fMaxDist = (vFoundPoints.size() < nPoints) ? std::numeric_limits<value_type>::max() : vFoundPoints.back().second;
1053 value_type fDist;
1054 typedef typename std::vector<std::pair<const _DataPoint*,Double_t> >::iterator t_pit;
1055
1056 // loop over all points and check distances
1057 for(typename std::vector<const _DataPoint*>::const_iterator it = fDataPoints.begin(); it != fDataPoints.end(); ++it)
1058 {
1059 fDist = (*it)->Distance(rRef);
1060 // fDist < fMaxDist -> insert
1061 if(fDist < fMaxDist)
1062 {
1063 // find position at which the current point should be inserted
1064 t_pit pit = vFoundPoints.begin();
1065 while(pit != vFoundPoints.end())
1066 {
1067 if(pit->second > fDist)
1068 break;
1069 else
1070 ++pit;
1071 }
1072
1073 vFoundPoints.insert(pit,std::make_pair(*it,fDist));
1074 // truncate vector of found points at nPoints
1075 if(vFoundPoints.size() > nPoints)
1076 vFoundPoints.resize(nPoints);
1077 // update maximal distance
1078 fMaxDist = (vFoundPoints.size() < nPoints) ? vFoundPoints.back().second : std::numeric_limits<value_type>::max();
1079 }
1080 }
1081 }
1082
1083//______________________________________________________________________________
1084 template<class _DataPoint>
1086 std::vector<const _DataPoint*>& vFoundPoints) const
1087 {
1088 //returns the points within a certain distance around the reference point
1089 //
1090 //Input: rRef - reference point
1091 // fDist - radius of sphere to scan ( > 0)
1092 // vFoundPoints - vector in which all found points are stored
1093 //
1094 //Note: vFoundPoints ist NOT ordered.
1095
1096 // loop over all points and check distances
1097 for(typename std::vector<const _DataPoint*>::const_iterator it = fDataPoints.begin(); it != fDataPoints.end(); ++it)
1098 {
1099 if((*it)->Distance(rRef) <= fDist)
1100 vFoundPoints.push_back(*it);
1101 }
1102 }
1103
1104//______________________________________________________________________________
1105 template<class _DataPoint>
1107 {
1108 //inserts a new data point in this bin
1109 //
1110 //Note: - If the population of this TerminalNode exceeds the limit of
1111 // 2 x fBucketSize, the node is split using the Split() function.
1112
1113 // store pointer to data point
1114 fDataPoints.push_back(&rPoint);
1115
1116 // update weights
1117 this->fSumw += rPoint.GetWeight();
1118 this->fSumw2 += pow(rPoint.GetWeight(),2);
1119 ++this->fEntries;
1120
1121 // split terminal node if necessary
1122 switch(fSplitOption)
1123 {
1124 case kEffective:
1125 if(this->GetEffectiveEntries() > 2 * fBucketSize)
1126 Split();
1127 break;
1128 case kBinContent:
1129 if(this->GetSumw() > 2 * fBucketSize)
1130 Split();
1131 break;
1132 default: assert(false);
1133 }
1134
1135 return true;
1136 }
1137
1138//______________________________________________________________________________
1139 template<class _DataPoint>
1141 {
1142 //prints some information about this TerminalNode
1143
1144 std::cout << "TerminalNode at " << this << " in row " << iRow << std::endl;
1145 const_cast<TerminalNode*>(this)->UpdateBoundaries();
1146 BinNode::Print(iRow);
1147 std::cout << "next split axis: " << fSplitAxis << std::endl << std::endl;
1148 for(const_data_it it = fDataPoints.begin(); it != fDataPoints.end(); ++it)
1149 {
1150 std::cout << "(";
1151 for(UInt_t i = 0; i < Dimension(); ++i)
1152 {
1153 std::cout << (*it)->GetCoordinate(i);
1154 if(i != Dimension() - 1)
1155 std::cout << ",";
1156 }
1157 std::cout << "), w = " << (*it)->GetWeight() << std::endl;
1158 }
1159
1160 std::cout << std::endl;
1161 }
1162
1163//______________________________________________________________________________
1164 template<class _DataPoint>
1166 {
1167 //splits this TerminalNode
1168 //
1169 //A new SplitNode containing the split axis and split value is created. It
1170 //is placed at the current position of this TerminalNode in the tree.
1171 //The data points in this node are divided into two groups according to
1172 //the splitting axis and value. From the second half a new TerminalNode is created.
1173 //
1174 //Sketch: SplitNode
1175 // | |
1176 // ... current TerminalNode (which is split)
1177 //
1178 // |
1179 // V
1180 //
1181 // SplitNode
1182 // | |
1183 // ... new SplitNode
1184 // | |
1185 // current TerminalNode new TerminalNode
1186 // (modified)
1187
1188 data_it cut;
1189 switch(fSplitOption)
1190 {
1191 case kEffective: cut = SplitEffectiveEntries(); break;
1192 case kBinContent: cut = SplitBinContent(); break;
1193 default: assert(false);
1194 }
1195
1196 // store split value
1197 value_type fSplitValue = (*cut)->GetCoordinate(fSplitAxis);
1198 //create second terminal node with second part of (unsorted vector)
1199 TerminalNode* pNew = new TerminalNode(fBucketSize,fSplitAxis+1,cut,fDataPoints.end());
1200 // copy options
1201 pNew->SetOwner(fOwnData);
1202 pNew->SetSplitOption(fSplitOption);
1203
1204 // remove the copied elements from this bucket
1205 fDataPoints.erase(cut,fDataPoints.end());
1206 // recalculate sumw and sumw2
1207 this->fSumw = this->fSumw2 = 0;
1208 for(data_it it = fDataPoints.begin(); it != fDataPoints.end(); ++it)
1209 {
1210 this->fSumw += (*it)->GetWeight();
1211 this->fSumw2 += pow((*it)->GetWeight(),2);
1212 }
1213 this->fEntries = fDataPoints.size();
1214
1215 // create new splitting node
1216 SplitNode* pSplit = new SplitNode(fSplitAxis,fSplitValue,*this,*pNew,this->Parent());
1217
1218 // link new splitting node
1219 this->GetParentPointer() = pSplit;
1220
1221 // set splitting node as new parent of both terminal nodes
1222 this->Parent() = pSplit;
1223 pNew->Parent() = pSplit;
1224
1225 // update boundaries
1226 this->UpdateBoundaries();
1227 pNew->UpdateBoundaries();
1228
1229 // change splitting axis
1230 ++fSplitAxis;
1231 fSplitAxis = fSplitAxis % Dimension();
1232 }
1233
1234//______________________________________________________________________________
1235 template<class _DataPoint>
1237 {
1238 //splits according to the number of effective entries
1239 //
1240 //returns an iterator pointing to the data point at which the vector should be split
1241 //
1242 //Note: - The vector containing the data points is partially ordered according to the
1243 // coordinates of the current split axis at least until the position of cut.
1244
1245 // function pointer for comparing data points
1246 typename KDTree<_DataPoint>::ComparePoints cComp;
1247 cComp.SetAxis(fSplitAxis);
1248
1249 data_it first = fDataPoints.begin();
1250 data_it cut = first;
1251 data_it middle;
1252 UInt_t step = fDataPoints.size();
1253 Double_t fSumwTemp = 0;
1254 Double_t fSumw2Temp = 1e-7;
1255 Double_t fEffective = this->GetEffectiveEntries();
1256
1257 // sort data points along split axis
1258 // find data point at which the cumulative effective entries reach half of the total effective entries
1259 while(((fSumwTemp * fSumwTemp)/fSumw2Temp < fEffective/2) && (step > 1))
1260 {
1261 middle = first + (++step /= 2);
1262 std::partial_sort(first,middle,fDataPoints.end(),cComp);
1263
1264 while(((fSumwTemp * fSumwTemp)/fSumw2Temp < fEffective/2) && (cut != middle-1))
1265 {
1266 fSumwTemp += (*cut)->GetWeight();
1267 fSumw2Temp += pow((*cut)->GetWeight(),2);
1268 ++cut;
1269 }
1270 first = middle;
1271 }
1272
1273 return cut;
1274 }
1275
1276//______________________________________________________________________________
1277 template<class _DataPoint>
1279 {
1280 //splits according to the bin content
1281 //
1282 //returns an iterator pointing to the data point at which the vector should be split
1283 //
1284 //Note: - The vector containing the data points is partially ordered according to the
1285 // coordinates of the current split axis at least until the position of cut.
1286
1287 // function pointer for comparing data points
1288 typename KDTree<_DataPoint>::ComparePoints cComp;
1289 cComp.SetAxis(fSplitAxis);
1290
1291 data_it first = fDataPoints.begin();
1292 data_it cut = first;
1293 data_it middle;
1294 UInt_t step = fDataPoints.size();
1295 Double_t fSumwTemp = 0;
1296 Double_t fBinContent = this->GetSumw();
1297
1298 // sort data points along split axis
1299 // find data point at which the cumulative effective entries reach half of the total effective entries
1300 while((fSumwTemp < fBinContent/2) && (step > 1))
1301 {
1302 middle = first + (++step /= 2);
1303 std::partial_sort(first,middle,fDataPoints.end(),cComp);
1304
1305 while((fSumwTemp < fBinContent/2) && (cut != middle-1))
1306 {
1307 fSumwTemp += (*cut)->GetWeight();
1308 ++cut;
1309 }
1310 first = middle;
1311 }
1312
1313 return cut;
1314 }
1315
1316//______________________________________________________________________________
1317 template<class _DataPoint>
1319 {
1320 //updates the boundaries of this bin and caches them
1321 //
1322 //Note: - In a high-dimensional space most of the nodes are bounded only on
1323 // one side due to a split. One-sided intervals would result in an
1324 // infinite volume of the bin which is not the desired behaviour.
1325 // Therefore the following convention is used for determining the
1326 // boundaries:
1327 // If a node is not restricted along one axis on one/both side(s) due
1328 // to a split, the corresponding upper/lower boundary is set to
1329 // the minimum/maximum coordinate alogn this axis of all contained
1330 // data points.
1331 // This procedure maximises the density in the bins.
1332
1333 const value_type fMAX = 0.4 * std::numeric_limits<value_type>::max();
1334 const value_type fMIN = -1.0 * fMAX;
1335
1336 this->fBoundaries = std::vector<tBoundary>(Dimension(),std::make_pair(fMIN,fMAX));
1337
1338 //walk back the tree and update bounds
1339 const BaseNode* pNode = this->Parent();
1340 const SplitNode* pSplit = 0;
1341 const Cut* pCut = 0;
1342 bool bLeft = this->IsLeftChild();
1343 while(!pNode->IsHeadNode())
1344 {
1345 pSplit = dynamic_cast<const SplitNode*>(pNode);
1346 assert(pSplit);
1347 pCut = pSplit->GetCut();
1348 // left subtree -> cut is upper bound
1349 if(bLeft)
1350 this->fBoundaries.at(pCut->GetAxis()).second = std::min(pCut->GetCutValue(),this->fBoundaries.at(pCut->GetAxis()).second);
1351 // right subtree -> cut is lower bound
1352 else
1353 this->fBoundaries.at(pCut->GetAxis()).first = std::max(pCut->GetCutValue(),this->fBoundaries.at(pCut->GetAxis()).first);
1354
1355 bLeft = pNode->IsLeftChild();
1356 pNode = pNode->Parent();
1357 }
1358
1359 // if there are some data points in this bucket, use their minimum/maximum values to define the open boundaries
1360 if(fDataPoints.size())
1361 {
1362 // loop over bounds and set unspecified values to minimum/maximum coordinate of all points in this bucket
1363 for(UInt_t dim = 0; dim < this->fBoundaries.size(); ++dim)
1364 {
1365 // check lower bound
1366 if(this->fBoundaries.at(dim).first < 0.8*fMIN)
1367 {
1368 this->fBoundaries.at(dim).first = fMAX;
1369 // look for smalles coordinate along axis 'dim'
1370 for(typename std::vector<const _DataPoint*>::const_iterator it = fDataPoints.begin();
1371 it != fDataPoints.end(); ++it)
1372 {
1373 if((*it)->GetCoordinate(dim) < this->fBoundaries.at(dim).first)
1374 this->fBoundaries.at(dim).first = (*it)->GetCoordinate(dim);
1375 }
1376 }
1377 // check upper bound
1378 if(this->fBoundaries.at(dim).second > 0.8*fMAX)
1379 {
1380 this->fBoundaries.at(dim).second = fMIN;
1381 // look for biggest coordinate along axis 'dim'
1382 for(typename std::vector<const _DataPoint*>::const_iterator it = fDataPoints.begin();
1383 it != fDataPoints.end(); ++it)
1384 {
1385 if((*it)->GetCoordinate(dim) > this->fBoundaries.at(dim).second)
1386 this->fBoundaries.at(dim).second = (*it)->GetCoordinate(dim);
1387 }
1388 }
1389 }
1390 }
1391 }
1392
1393//______________________________________________________________________________
1394 template<class _DataPoint>
1396 {
1397 //pre-increment operator
1398
1399 fBin = Next();
1400 return *this;
1401 }
1402
1403//______________________________________________________________________________
1404 template<class _DataPoint>
1406 {
1407 //pre-increment operator
1408
1409 fBin = Next();
1410 return *this;
1411 }
1412
1413//______________________________________________________________________________
1414 template<class _DataPoint>
1416 {
1417 //post-increment operator
1418
1419 iterator tmp(*this);
1420 fBin = Next();
1421 return tmp;
1422 }
1423
1424//______________________________________________________________________________
1425 template<class _DataPoint>
1427 {
1428 //post-increment operator
1429
1430 iterator tmp(*this);
1431 fBin = Next();
1432 return tmp;
1433 }
1434
1435//______________________________________________________________________________
1436 template<class _DataPoint>
1438 {
1439 //pre-decrement operator
1440
1441 fBin = Previous();
1442 return *this;
1443 }
1444
1445//______________________________________________________________________________
1446 template<class _DataPoint>
1448 {
1449 //pre-decrement operator
1450
1451 fBin = Previous();
1452 return *this;
1453 }
1454
1455//______________________________________________________________________________
1456 template<class _DataPoint>
1458 {
1459 //post-decrement operator
1460
1461 iterator tmp(*this);
1462 fBin = Previous();
1463 return tmp;
1464 }
1465
1466//______________________________________________________________________________
1467 template<class _DataPoint>
1469 {
1470 //post-decrement operator
1471
1472 iterator tmp(*this);
1473 fBin = Previous();
1474 return tmp;
1475 }
1476
1477//______________________________________________________________________________
1478 template<class _DataPoint>
1480 {
1481 //assignment operator
1482
1483 fBin = rhs.fBin;
1484 return *this;
1485 }
1486
1487//______________________________________________________________________________
1488 template<class _DataPoint>
1490 {
1491 //advance this iterator to the next bin
1492 //
1493 //Note: - Check for the end of all bins by comparing to End().
1494
1495 BaseNode* pNode = fBin;
1496
1497 while(!pNode->IsHeadNode())
1498 {
1499 if(pNode->IsLeftChild())
1500 {
1501 assert(pNode->Parent()->RightChild());
1502 pNode = pNode->Parent()->RightChild();
1503 while(pNode->LeftChild())
1504 pNode = pNode->LeftChild();
1505
1506 assert(dynamic_cast<BinNode*>(pNode));
1507 return (BinNode*)pNode;
1508 }
1509 else
1510 pNode = pNode->Parent();
1511 }
1512
1513 return 0;
1514 }
1515
1516//______________________________________________________________________________
1517 template<class _DataPoint>
1519 {
1520 //decline this iterator to the previous bin
1521 //
1522 //Note: - Check for the end of all bins by comparing to End().
1523
1524 BaseNode* pNode = fBin;
1525
1526 while(!pNode->IsHeadNode())
1527 {
1528 if(pNode->Parent()->RightChild() == pNode)
1529 {
1530 assert(pNode->Parent()->LeftChild());
1531 pNode = pNode->Parent()->LeftChild();
1532 while(pNode->RightChild())
1533 pNode = pNode->RightChild();
1534
1535 assert(dynamic_cast<BinNode*>(pNode));
1536 return (BinNode*)pNode;
1537 }
1538 else
1539 pNode = pNode->Parent();
1540 }
1541
1542 return 0;
1543 }
1544
1545 }//namespace Math
1546}//namespace ROOT
1547
1548#endif //KD_TREE_ICC
#define e(i)
Definition: RSha256.hxx:103
unsigned int UInt_t
Definition: RtypesCore.h:46
bool Bool_t
Definition: RtypesCore.h:63
double Double_t
Definition: RtypesCore.h:59
BaseNode *& GetParentPointer()
Definition: KDTree.icc:520
BaseNode *& Parent()
Definition: KDTree.h:106
Bool_t IsLeftChild() const
Definition: KDTree.icc:542
virtual Bool_t IsHeadNode() const
Definition: KDTree.h:113
BaseNode(BaseNode *pParent=0)
Definition: KDTree.icc:496
BaseNode *& LeftChild()
Definition: KDTree.h:104
virtual BaseNode * Clone()=0
BaseNode *& RightChild()
Definition: KDTree.h:108
virtual const std::vector< tBoundary > & GetBoundaries() const
Definition: KDTree.h:200
virtual void EmptyBin()
Definition: KDTree.icc:788
std::vector< tBoundary > fBoundaries
Definition: KDTree.h:218
virtual const BinNode * FindNode(const point_type &rPoint) const
Definition: KDTree.icc:814
BinNode(BaseNode *pParent=0)
Definition: KDTree.icc:748
virtual BinNode * Clone()
Definition: KDTree.icc:779
point_type GetBinCenter() const
Definition: KDTree.icc:826
virtual Bool_t Insert(const point_type &rPoint)
Definition: KDTree.icc:860
std::pair< value_type, value_type > tBoundary
Definition: KDTree.h:187
Bool_t IsInBin(const point_type &rPoint) const
Definition: KDTree.icc:878
BinNode & operator=(const BinNode &rhs)
Definition: KDTree.icc:798
virtual void Print(int iRow=0) const
Definition: KDTree.icc:891
BaseNode *& LeftChild()
Definition: KDTree.h:104
BaseNode *& RightChild()
Definition: KDTree.h:108
Double_t GetVolume() const
Definition: KDTree.icc:843
Bool_t operator()(const point_type *pFirst, const point_type *pSecond) const
Definition: KDTree.icc:433
void SetAxis(UInt_t iAxis)
Definition: KDTree.h:55
value_type GetCutValue() const
Definition: KDTree.h:69
UInt_t GetAxis() const
Definition: KDTree.h:68
Bool_t operator>(const point_type &rPoint) const
Definition: KDTree.icc:476
Bool_t operator<(const point_type &rPoint) const
Definition: KDTree.icc:456
virtual void GetPointsWithinDist(const point_type &rRef, value_type fDist, std::vector< const _DataPoint * > &vFoundPoints) const
Definition: KDTree.icc:580
virtual HeadNode * Clone()
Definition: KDTree.icc:556
virtual void GetClosestPoints(const point_type &rRef, UInt_t nPoints, std::vector< std::pair< const _DataPoint *, Double_t > > &vFoundPoints) const
Definition: KDTree.icc:572
SplitNode(UInt_t iAxis, Double_t fCutValue, BaseNode &rLeft, BaseNode &rRight, BaseNode *pParent=0)
Definition: KDTree.icc:588
virtual void GetClosestPoints(const point_type &rRef, UInt_t nPoints, std::vector< std::pair< const _DataPoint *, Double_t > > &vFoundPoints) const
Definition: KDTree.icc:652
virtual void GetPointsWithinDist(const point_type &rRef, value_type fDist, std::vector< const _DataPoint * > &vFoundPoints) const
Definition: KDTree.icc:689
const Cut * GetCut() const
Definition: KDTree.h:166
virtual const BinNode * FindNode(const point_type &rPoint) const
Definition: KDTree.icc:638
virtual SplitNode * Clone()
Definition: KDTree.icc:619
virtual void Print(Int_t iRow=0) const
Definition: KDTree.icc:735
virtual Bool_t Insert(const point_type &rPoint)
Definition: KDTree.icc:721
virtual const std::vector< tBoundary > & GetBoundaries() const
Definition: KDTree.icc:1018
std::vector< constpoint_type * >::iterator data_it
Definition: KDTree.h:263
void SetOwner(Bool_t bIsOwner=true)
Definition: KDTree.h:275
void SetSplitOption(eSplitOption opt)
Definition: KDTree.h:276
virtual void GetPointsWithinDist(const point_type &rRef, value_type fDist, std::vector< const _DataPoint * > &vFoundPoints) const
Definition: KDTree.icc:1085
virtual void Print(int iRow=0) const
Definition: KDTree.icc:1140
TerminalNode(Double_t iBucketSize, BaseNode *pParent=0)
Definition: KDTree.icc:915
virtual Bool_t Insert(const point_type &rPoint)
Definition: KDTree.icc:1106
std::vector< constpoint_type * >::const_iterator const_data_it
Definition: KDTree.h:264
virtual void GetClosestPoints(const point_type &rRef, UInt_t nPoints, std::vector< std::pair< const _DataPoint *, Double_t > > &vFoundPoints) const
Definition: KDTree.icc:1040
std::vector< const _DataPoint * > fDataPoints
Definition: KDTree.h:285
iterator & operator=(const iterator &rhs)
Definition: KDTree.icc:1479
Double_t GetTotalSumw2() const
Definition: KDTree.icc:321
Bool_t fIsFrozen
Definition: KDTree.h:367
void SetOwner(Bool_t bIsOwner=true)
Definition: KDTree.icc:391
KDTree< _DataPoint > * GetFrozenCopy()
Definition: KDTree.icc:256
Double_t GetTotalSumw() const
Definition: KDTree.icc:308
void EmptyBins()
Definition: KDTree.icc:85
_DataPoint::value_type value_type
Definition: KDTree.h:40
UInt_t GetEntries() const
Definition: KDTree.icc:243
void GetPointsWithinDist(const point_type &rRef, value_type fDist, std::vector< const point_type * > &vFoundPoints) const
Definition: KDTree.icc:286
iterator First()
Definition: KDTree.icc:131
UInt_t GetNBins() const
Definition: KDTree.icc:273
iterator Last()
Definition: KDTree.icc:334
Double_t fBucketSize
Definition: KDTree.h:366
Double_t GetEffectiveEntries() const
Definition: KDTree.icc:224
BaseNode * fHead
Definition: KDTree.h:365
void SetSplitOption(eSplitOption opt)
Definition: KDTree.icc:410
void GetClosestPoints(const point_type &rRef, UInt_t nPoints, std::vector< std::pair< const _DataPoint *, Double_t > > &vFoundPoints) const
Definition: KDTree.icc:200
iterator End()
Definition: KDTree.icc:103
static UInt_t Dimension()
Definition: KDTree.h:41
Namespace for new Math classes and functions.
VecExpr< UnaryOp< Fabs< T >, VecExpr< A, T, D >, T >, T, D > fabs(const VecExpr< A, T, D > &rhs)
tbb::task_arena is an alias of tbb::interface7::task_arena, which doesn't allow to forward declare tb...
std::vector< std::string > Split(std::string_view str, std::string_view delims, bool skipEmpty=false)
Splits a string at each character in delims.
Definition: StringUtils.cxx:23
void End()
Definition: first.py:1