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 
27 namespace 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  }
114 
115 //______________________________________________________________________________
116  template<class _DataPoint>
117  inline const typename KDTree<_DataPoint>::iterator KDTree<_DataPoint>::End() const
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>
147  inline const typename KDTree<_DataPoint>::iterator KDTree<_DataPoint>::First() const
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 
263  KDTree<_DataPoint>* pTree = new KDTree<_DataPoint>();
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>
350  inline const typename KDTree<_DataPoint>::iterator KDTree<_DataPoint>::Last() const
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>
860  Bool_t KDTree<_DataPoint>::BinNode::Insert(const _DataPoint& rPoint)
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>
1040  void KDTree<_DataPoint>::TerminalNode::GetClosestPoints(const _DataPoint& rRef,UInt_t nPoints,
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
ROOT::Math::KDTree::SplitNode::Print
virtual void Print(Int_t iRow=0) const
Definition: KDTree.icc:735
ROOT::Math::KDTree::GetEntries
UInt_t GetEntries() const
Definition: KDTree.icc:243
ROOT::Math::KDTree::TerminalNode::fBucketSize
Double_t fBucketSize
Definition: KDTree.h:298
first
Definition: first.py:1
ROOT::Math::KDTree::GetTotalSumw2
Double_t GetTotalSumw2() const
Definition: KDTree.icc:321
ROOT::Math::KDTree::BinNode::operator=
BinNode & operator=(const BinNode &rhs)
Definition: KDTree.icc:798
e
#define e(i)
Definition: RSha256.hxx:121
ROOT::Math::KDTree::SplitNode::Clone
virtual SplitNode * Clone()
Definition: KDTree.icc:619
ROOT::Math::KDTree::SplitNode::GetCut
const Cut * GetCut() const
Definition: KDTree.h:181
ROOT::Math::KDTree::First
iterator First()
Definition: KDTree.icc:131
ROOT::Math::KDTree::EmptyBins
void EmptyBins()
Definition: KDTree.icc:85
ROOT::Math::KDTree::GetEffectiveEntries
Double_t GetEffectiveEntries() const
Definition: KDTree.icc:224
ROOT::Math::KDTree::BinNode::EmptyBin
virtual void EmptyBin()
Definition: KDTree.icc:788
ROOT::Math::KDTree::fBucketSize
Double_t fBucketSize
Definition: KDTree.h:381
ROOT::Math::KDTree::Dimension
static UInt_t Dimension()
Definition: KDTree.h:56
ROOT::Math::KDTree::fHead
BaseNode * fHead
Definition: KDTree.h:380
ROOT::Math::KDTree::TerminalNode::GetClosestPoints
virtual void GetClosestPoints(const point_type &rRef, UInt_t nPoints, std::vector< std::pair< const _DataPoint *, Double_t > > &vFoundPoints) const
Definition: KDTree.icc:1040
Split
#define Split(a, ahi, alo)
Definition: triangle.c:4775
ROOT::Math::KDTree::ComparePoints::SetAxis
void SetAxis(UInt_t iAxis)
Definition: KDTree.h:70
ROOT::Math::KDTree::SplitNode::FindNode
virtual const BinNode * FindNode(const point_type &rPoint) const
Definition: KDTree.icc:638
ROOT::Math::KDTree::iterator::operator=
iterator & operator=(const iterator &rhs)
Definition: KDTree.icc:1479
ROOT::Math::KDTree::kEffective
@ kEffective
Definition: KDTree.h:58
ROOT::Math::KDTree::BinNode::tBoundary
std::pair< value_type, value_type > tBoundary
Definition: KDTree.h:202
ROOT::Math::KDTree::GetTotalSumw
Double_t GetTotalSumw() const
Definition: KDTree.icc:308
ROOT::Math::KDTree::BinNode::GetBinCenter
point_type GetBinCenter() const
Definition: KDTree.icc:826
ROOT::Math::KDTree::TerminalNode::SetOwner
void SetOwner(Bool_t bIsOwner=true)
Definition: KDTree.h:290
ROOT::Math::KDTree::iterator::operator--
iterator & operator--()
Definition: KDTree.icc:1437
ROOT::Math::KDTree::KDTree
KDTree()
Definition: KDTree.icc:60
ROOT::Math::KDTree::Cut::operator>
Bool_t operator>(const point_type &rPoint) const
Definition: KDTree.icc:476
ROOT::Math::KDTree::BinNode::GetBoundaries
virtual const std::vector< tBoundary > & GetBoundaries() const
Definition: KDTree.h:215
ROOT::Math::KDTree::iterator::fBin
Bin * fBin
Definition: KDTree.h:342
ROOT::Math::KDTree::ComparePoints::operator()
Bool_t operator()(const point_type *pFirst, const point_type *pSecond) const
Definition: KDTree.icc:433
ROOT::Math::KDTree::BinNode
Definition: KDTree.h:198
ROOT::Math::KDTree::BaseNode::Clone
virtual BaseNode * Clone()=0
ROOT::Math::KDTree::BaseNode
Definition: KDTree.h:103
ROOT::Math::KDTree::BinNode::IsInBin
Bool_t IsInBin(const point_type &rPoint) const
Definition: KDTree.icc:878
ROOT::Math::KDTree::kBinContent
@ kBinContent
Definition: KDTree.h:59
ROOT::Math::KDTree::TerminalNode::SplitEffectiveEntries
data_it SplitEffectiveEntries()
Definition: KDTree.icc:1236
ROOT::Math::KDTree::iterator
Definition: KDTree.h:310
ROOT::Math::KDTree::TerminalNode::Print
virtual void Print(int iRow=0) const
Definition: KDTree.icc:1140
ROOT::Math::KDTree::~KDTree
~KDTree()
Definition: KDTree.icc:72
bool
ROOT::Math::KDTree::ComparePoints::fAxis
UInt_t fAxis
Definition: KDTree.h:73
ROOT::Math::KDTree::eSplitOption
eSplitOption
Definition: KDTree.h:57
ROOT::Math::KDTree::TerminalNode::SplitBinContent
data_it SplitBinContent()
Definition: KDTree.icc:1278
ROOT::Math::KDTree::BaseNode::LeftChild
BaseNode *& LeftChild()
Definition: KDTree.h:119
ROOT::Math::KDTree::SplitNode::GetPointsWithinDist
virtual void GetPointsWithinDist(const point_type &rRef, value_type fDist, std::vector< const _DataPoint * > &vFoundPoints) const
Definition: KDTree.icc:689
ROOT::Math::KDTree::BinNode::FindNode
virtual const BinNode * FindNode(const point_type &rPoint) const
Definition: KDTree.icc:814
ROOT::Math::KDTree::BinNode::Insert
virtual Bool_t Insert(const point_type &rPoint)
Definition: KDTree.icc:860
ROOT::Math::KDTree::Cut::GetAxis
UInt_t GetAxis() const
Definition: KDTree.h:83
ROOT::Math::KDTree::GetClosestPoints
void GetClosestPoints(const point_type &rRef, UInt_t nPoints, std::vector< std::pair< const _DataPoint *, Double_t > > &vFoundPoints) const
Definition: KDTree.icc:200
ROOT::Math::KDTree::TerminalNode::GetBoundaries
virtual const std::vector< tBoundary > & GetBoundaries() const
Definition: KDTree.icc:1018
ROOT::Math::KDTree::BaseNode::GetParentPointer
BaseNode *& GetParentPointer()
Definition: KDTree.icc:520
ROOT::Math::KDTree::BinNode::Print
virtual void Print(int iRow=0) const
Definition: KDTree.icc:891
ROOT::Math::KDTree::BinNode::fBoundaries
std::vector< tBoundary > fBoundaries
Definition: KDTree.h:233
ROOT::Math::KDTree::SplitNode::~SplitNode
virtual ~SplitNode()
Definition: KDTree.icc:610
ROOT::Math::fabs
VecExpr< UnaryOp< Fabs< T >, VecExpr< A, T, D >, T >, T, D > fabs(const VecExpr< A, T, D > &rhs)
Definition: UnaryOperators.h:131
ROOT::Math::KDTree::SetSplitOption
void SetSplitOption(eSplitOption opt)
Definition: KDTree.icc:410
ROOT::Math::KDTree::Last
iterator Last()
Definition: KDTree.icc:334
ROOT::Math::KDTree::TerminalNode::ConvertToBinNode
BinNode * ConvertToBinNode()
Definition: KDTree.icc:979
ROOT::Math::KDTree::HeadNode
Definition: KDTree.h:142
ROOT::Math::KDTree::BaseNode::~BaseNode
virtual ~BaseNode()
Definition: KDTree.icc:506
ROOT::Math::KDTree::HeadNode::GetPointsWithinDist
virtual void GetPointsWithinDist(const point_type &rRef, value_type fDist, std::vector< const _DataPoint * > &vFoundPoints) const
Definition: KDTree.icc:580
ROOT::Math::KDTree::TerminalNode::EmptyBin
virtual void EmptyBin()
Definition: KDTree.icc:996
ROOT::Math::KDTree::TerminalNode::TerminalNode
TerminalNode(Double_t iBucketSize, BaseNode *pParent=0)
Definition: KDTree.icc:915
ROOT::Math::KDTree::GetNBins
UInt_t GetNBins() const
Definition: KDTree.icc:273
ROOT::Math::KDTree::TerminalNode::const_data_it
std::vector< const point_type * >::const_iterator const_data_it
Definition: KDTree.h:279
ROOT::Math::KDTree::TerminalNode
Definition: KDTree.h:250
ROOT::Math::KDTree::Reset
void Reset()
Definition: KDTree.icc:366
ROOT::Math::KDTree::SplitNode::SplitNode
SplitNode(UInt_t iAxis, Double_t fCutValue, BaseNode &rLeft, BaseNode &rRight, BaseNode *pParent=0)
Definition: KDTree.icc:588
ROOT::Math::KDTree::BaseNode::BaseNode
BaseNode(BaseNode *pParent=0)
Definition: KDTree.icc:496
ROOT::Math::KDTree::HeadNode::Clone
virtual HeadNode * Clone()
Definition: KDTree.icc:556
ROOT::Math::KDTree::fIsFrozen
Bool_t fIsFrozen
Definition: KDTree.h:382
ROOT::Math::KDTree::BinNode::GetVolume
Double_t GetVolume() const
Definition: KDTree.icc:843
ROOT::Math::KDTree::TerminalNode::fDataPoints
std::vector< const _DataPoint * > fDataPoints
Definition: KDTree.h:300
ROOT::Math::KDTree::TerminalNode::UpdateBoundaries
void UpdateBoundaries()
Definition: KDTree.icc:1318
ROOT::Math::KDTree::iterator::Previous
Bin * Previous() const
Definition: KDTree.icc:1518
ROOT::Math::KDTree::GetPointsWithinDist
void GetPointsWithinDist(const point_type &rRef, value_type fDist, std::vector< const point_type * > &vFoundPoints) const
Definition: KDTree.icc:286
unsigned int
ROOT::Math::KDTree::SplitNode
Definition: KDTree.h:173
ROOT::Math::KDTree::BinNode::fEntries
UInt_t fEntries
Definition: KDTree.h:236
ROOT::Math::KDTree::TerminalNode::~TerminalNode
virtual ~TerminalNode()
Definition: KDTree.icc:963
ROOT::Math::KDTree::BinNode::fSumw2
Double_t fSumw2
Definition: KDTree.h:235
ROOT::Math::KDTree::GetFrozenCopy
KDTree< _DataPoint > * GetFrozenCopy()
Definition: KDTree.icc:256
Double_t
double Double_t
Definition: RtypesCore.h:59
ROOT::Math::KDTree::Cut
Definition: KDTree.h:76
ROOT::Math::KDTree::BaseNode::RightChild
BaseNode *& RightChild()
Definition: KDTree.h:123
ROOT::Math::KDTree::BinNode::BinNode
BinNode(BaseNode *pParent=0)
Definition: KDTree.icc:748
Rgl::Pad::End
void End()
Definition: TGLPadUtils.cxx:1177
ROOT::Math::KDTree::ComparePoints
Definition: KDTree.h:64
ROOT::Math::KDTree::TerminalNode::Split
void Split()
Definition: KDTree.icc:1165
ROOT::Math::KDTree::SetOwner
void SetOwner(Bool_t bIsOwner=true)
Definition: KDTree.icc:391
ROOT::Math::KDTree::Cut::GetCutValue
value_type GetCutValue() const
Definition: KDTree.h:84
ROOT::Math::KDTree::HeadNode::GetClosestPoints
virtual void GetClosestPoints(const point_type &rRef, UInt_t nPoints, std::vector< std::pair< const _DataPoint *, Double_t > > &vFoundPoints) const
Definition: KDTree.icc:572
ROOT::Math::KDTree::BinNode::fSumw
Double_t fSumw
Definition: KDTree.h:234
ROOT::Math::KDTree::TerminalNode::GetPointsWithinDist
virtual void GetPointsWithinDist(const point_type &rRef, value_type fDist, std::vector< const _DataPoint * > &vFoundPoints) const
Definition: KDTree.icc:1085
ROOT::Math::KDTree::value_type
_DataPoint::value_type value_type
Definition: KDTree.h:55
ROOT::Math::KDTree::TerminalNode::Insert
virtual Bool_t Insert(const point_type &rPoint)
Definition: KDTree.icc:1106
ROOT::Math::KDTree::Cut::operator<
Bool_t operator<(const point_type &rPoint) const
Definition: KDTree.icc:456
ROOT::Math::KDTree::BinNode::Clone
virtual BinNode * Clone()
Definition: KDTree.icc:779
ROOT::Math::KDTree::SplitNode::Insert
virtual Bool_t Insert(const point_type &rPoint)
Definition: KDTree.icc:721
ROOT::Math::KDTree::TerminalNode::SetSplitOption
void SetSplitOption(eSplitOption opt)
Definition: KDTree.h:291
ROOT::Math::KDTree::Freeze
void Freeze()
Definition: KDTree.icc:163
ROOT::Math::KDTree::BaseNode::IsHeadNode
virtual Bool_t IsHeadNode() const
Definition: KDTree.h:128
pow
double pow(double, double)
ROOT::Math::KDTree::BaseNode::Parent
BaseNode *& Parent()
Definition: KDTree.h:121
ROOT::Math::KDTree::SplitNode::GetClosestPoints
virtual void GetClosestPoints(const point_type &rRef, UInt_t nPoints, std::vector< std::pair< const _DataPoint *, Double_t > > &vFoundPoints) const
Definition: KDTree.icc:652
ROOT
VSD Structures.
Definition: StringConv.hxx:21
ROOT::Math::KDTree::End
iterator End()
Definition: KDTree.icc:103
Math
ROOT::Math::KDTree::iterator::operator++
iterator & operator++()
Definition: KDTree.icc:1395
ROOT::Math::KDTree::BaseNode::IsLeftChild
Bool_t IsLeftChild() const
Definition: KDTree.icc:542
ROOT::Math::KDTree::iterator::Next
Bin * Next() const
Definition: KDTree.icc:1489
ROOT::Math::KDTree::TerminalNode::data_it
std::vector< const point_type * >::iterator data_it
Definition: KDTree.h:278
ROOT::Math::KDTree
Definition: KDTree.h:45