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