Logo ROOT  
Reference Guide
KDTree.h
Go to the documentation of this file.
1 // @(#)root/mathcore:$Id$
2 // Authors: C. Gumpert 09/2011
3 /**********************************************************************
4  * *
5  * Copyright (c) 2011 , LCG ROOT MathLib Team *
6  * *
7  * *
8  **********************************************************************/
9 //
10 // Header file for KDTree class
11 //
12 
13 
14 #ifndef ROOT_Math_KDTree
15 #define ROOT_Math_KDTree
16 
17 //STL header
18 #include <cassert>
19 #include <vector>
20 #include <cmath>
21 #include <utility>
22 
23 // ROOT include(s)
24 #include "RtypesCore.h"
25 
26 namespace ROOT
27 {
28  namespace Math
29  {
30 
31  //______________________________________________________________________________
32  //Begin_Html
33  //End_Html
34  template<class _DataPoint>
35  class KDTree
36  {
37  public:
38 
39  typedef _DataPoint point_type;
40  typedef typename _DataPoint::value_type value_type;
41  static UInt_t Dimension() {return _DataPoint::Dimension();}
42  enum eSplitOption {
43  kEffective = 0, //split according to effective entries
44  kBinContent //split according to bin content
45  };
46 
47  private:
48 
49  class ComparePoints
50  {
51  public:
52  Bool_t operator()(const point_type* pFirst,const point_type* pSecond) const;
53 
54  UInt_t GetAxis() const {return fAxis;}
55  void SetAxis(UInt_t iAxis) {fAxis = iAxis;}
56 
57  private:
58  UInt_t fAxis; //axis at which the points are compared
59  };
60 
61  class Cut
62  {
63  public:
64  Cut():fAxis(0),fCutValue(0) {}
65  Cut(UInt_t iAxis,Double_t fNewCutValue):fAxis(iAxis),fCutValue(fNewCutValue) {}
66  ~Cut() {}
67 
68  UInt_t GetAxis() const {return fAxis;}
69  value_type GetCutValue() const {return fCutValue;}
70  void SetAxis(UInt_t iAxis) {fAxis = iAxis;}
71  void SetCutValue(Double_t fNewCutValue) {fCutValue = fNewCutValue;}
72 
73  Bool_t operator<(const point_type& rPoint) const;
74  Bool_t operator>(const point_type& rPoint) const;
75 
76  private:
77  UInt_t fAxis; //axis at which the splitting is done
78  Double_t fCutValue; //split value
79  };
80 
81  //forward declarations
82  class BaseNode;
83  class HeadNode;
84  class SplitNode;
85  class BinNode;
86  class TerminalNode;
87 
88  class BaseNode
89  {
90  public:
91  //constructor and destructor
92  BaseNode(BaseNode* pParent = 0);
93  virtual ~BaseNode();
94 
95  //providing usual functionality of a tree
96  virtual BaseNode* Clone() = 0;
97  virtual const BinNode* FindNode(const point_type& rPoint) const = 0;
98  virtual void GetClosestPoints(const point_type& rRef,UInt_t nPoints,std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const = 0;
99  virtual void GetPointsWithinDist(const point_type& rRef,value_type fDist,std::vector<const point_type*>& vFoundPoints) const = 0;
100  virtual Bool_t Insert(const point_type& rPoint) = 0;
101  virtual void Print(int iRow = 0) const = 0;
102 
103  //navigating the tree
104  BaseNode*& LeftChild() {return fLeftChild;}
105  const BaseNode* LeftChild() const {return fLeftChild;}
106  BaseNode*& Parent() {return fParent;}
107  const BaseNode* Parent() const {return fParent;}
108  BaseNode*& RightChild() {return fRightChild;}
109  const BaseNode* RightChild() const {return fRightChild;}
110 
111  //information about relative position of current node
113  virtual Bool_t IsHeadNode() const {return false;}
114  Bool_t IsLeftChild() const;
115 
116  private:
117  // node should never be copied or assigned
118  BaseNode(const BaseNode& ) {}
119  BaseNode& operator=(const BaseNode& ) {return *this;}
120 
121  //links to adjacent nodes
122  BaseNode* fParent; //!pointer to parent node
123  BaseNode* fLeftChild; //!pointer to left child
124  BaseNode* fRightChild; //!pointer to right child
125  };
126 
127  class HeadNode : public BaseNode
128  {
129  public:
130  //constructor and destructor
131  HeadNode(BaseNode& rNode):BaseNode(&rNode) {}
132  virtual ~HeadNode() {delete Parent();}
133 
134  //delegate everything to the actual root node of the tree
135  virtual const BinNode* FindNode(const point_type& rPoint) const {return Parent()->FindNode(rPoint);}
136  virtual void GetClosestPoints(const point_type& rRef,UInt_t nPoints,std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const;
137  virtual void GetPointsWithinDist(const point_type& rRef,value_type fDist,std::vector<const _DataPoint*>& vFoundPoints) const;
138  virtual Bool_t Insert(const point_type& rPoint) {return Parent()->Insert(rPoint);}
139  virtual void Print(Int_t) const {Parent()->Print();}
140 
141  private:
142  // node should never be copied
143  HeadNode(const HeadNode& ) {}
144  HeadNode& operator=(const HeadNode& ) {return *this;}
145 
146  virtual HeadNode* Clone();
147  virtual bool IsHeadNode() const {return true;}
148 
149  // only delegate everything else is private and should not be used
151  using BaseNode::LeftChild;
152  using BaseNode::RightChild;
153 
155  using BaseNode::IsLeftChild;
156  };
157 
158  class SplitNode : public BaseNode
159  {
160  public:
161  // constructors and destructors
162  SplitNode(UInt_t iAxis,Double_t fCutValue,BaseNode& rLeft,BaseNode& rRight,BaseNode* pParent = 0);
163  virtual ~SplitNode();
164 
165  //accessing information about this split node
166  const Cut* GetCut() const {return fCut;}
167  virtual void Print(Int_t iRow = 0) const;
168 
169  private:
170  // node should never be copied
171  SplitNode(const SplitNode& ) {}
172  SplitNode& operator=(const SplitNode& ) {return *this;}
173 
174  virtual SplitNode* Clone();
175  virtual const BinNode* FindNode(const point_type& rPoint) const;
176  virtual void GetClosestPoints(const point_type& rRef,UInt_t nPoints,std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const;
177  virtual void GetPointsWithinDist(const point_type& rRef,value_type fDist,std::vector<const _DataPoint*>& vFoundPoints) const;
178  virtual Bool_t Insert(const point_type& rPoint);
179 
180  const Cut* fCut; //pointer to cut object owned by this node
181  };
182 
183  class BinNode : public BaseNode
184  {
185  protected:
186  //save some typing
187  typedef std::pair<value_type,value_type> tBoundary;
188  public:
189  // constructors and destructors
190  BinNode(BaseNode* pParent = 0);
191  BinNode(const BinNode& copy);
192  virtual ~BinNode() {}
193 
194  // usual bin operations
195  virtual void EmptyBin();
196  virtual const BinNode* FindNode(const point_type& rPoint) const;
197  point_type GetBinCenter() const;
198  Double_t GetBinContent() const {return GetSumw();}
199 #ifndef _AIX
200  virtual const std::vector<tBoundary>& GetBoundaries() const {return fBoundaries;}
201 #else
202  virtual void GetBoundaries() const { }
203 #endif
204  Double_t GetDensity() const {return GetBinContent()/GetVolume();}
205  Double_t GetEffectiveEntries() const {return (GetSumw2()) ? std::pow(GetSumw(),2)/GetSumw2() : 0;}
206  UInt_t GetEntries() const {return fEntries;}
208  Double_t GetSumw() const {return fSumw;}
209  Double_t GetSumw2() const {return fSumw2;}
210  virtual Bool_t Insert(const point_type& rPoint);
211  Bool_t IsInBin(const point_type& rPoint) const;
212  virtual void Print(int iRow = 0) const;
213 
214  protected:
215  virtual BinNode* Clone();
216 
217  // intrinsic bin properties
218  std::vector<tBoundary> fBoundaries; //bin boundaries
219  Double_t fSumw; //sum of weights
220  Double_t fSumw2; //sum of weights^2
221  UInt_t fEntries; //number of entries
222 
223  private:
224  BinNode& operator=(const BinNode& rhs);
225 
226  // bin does not contain any point like information
227  virtual void GetClosestPoints(const point_type&,UInt_t,std::vector<std::pair<const _DataPoint*,Double_t> >&) const {}
228  virtual void GetPointsWithinDist(const point_type&,value_type,std::vector<const point_type*>&) const {}
229 
230  // a bin does not have children
231  using BaseNode::LeftChild;
232  using BaseNode::RightChild;
233  };
234 
235  class TerminalNode : public BinNode
236  {
237  friend class KDTree<_DataPoint>;
238  //save some typing
239  typedef std::pair<value_type,value_type> tBoundary;
240 
241  public:
242  //constructor and desctructor
243  TerminalNode(Double_t iBucketSize,BaseNode* pParent = 0);
244  virtual ~TerminalNode();
245 
246  virtual void EmptyBin();
247 #ifndef _AIX
248  virtual const std::vector<tBoundary>& GetBoundaries() const;
249 #else
250  virtual void GetBoundaries() const;
251 #endif
252  virtual void GetClosestPoints(const point_type& rRef,UInt_t nPoints,std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const;
253  const std::vector<const point_type*>& GetPoints() const {return fDataPoints;}
254  virtual void GetPointsWithinDist(const point_type& rRef,value_type fDist,std::vector<const _DataPoint*>& vFoundPoints) const;
255  virtual void Print(int iRow = 0) const;
256 
257  private:
258  // node should never be copied
259  TerminalNode(const TerminalNode& ) {}
260  TerminalNode& operator=(const TerminalNode& ) {return *this;}
261 
262  // save some typing
263  typedef typename std::vector<const point_type* >::iterator data_it;
264  typedef typename std::vector<const point_type* >::const_iterator const_data_it;
265 
266  // creating new Terminal Node when splitting, copying elements in the given range
267  TerminalNode(Double_t iBucketSize,UInt_t iSplitAxis,data_it first,data_it end);
268 
269  //tree operations
270  virtual BinNode* Clone() {return ConvertToBinNode();}
272  virtual const BinNode* FindNode(const point_type&) const {return this;}
273  virtual Bool_t Insert(const point_type& rPoint);
274  void Split();
275  void SetOwner(Bool_t bIsOwner = true) {fOwnData = bIsOwner;}
276  void SetSplitOption(eSplitOption opt) {fSplitOption = opt;}
280 
281  Bool_t fOwnData; // terminal node owns the data objects (default = false)
282  eSplitOption fSplitOption; // according to which figure of merit the node is splitted
283  Double_t fBucketSize; // target number of entries per bucket
284  UInt_t fSplitAxis; // axis at which the next split will occur
285  std::vector<const _DataPoint*> fDataPoints; // data points in this bucket
286  };
287 
288  public:
289  //////////////////////////////////////////////////////////////////////
290  //
291  // template<class _DataPoint> class KDTree<_DataPoint>::iterator
292  //
293  //////////////////////////////////////////////////////////////////////
294  typedef BinNode Bin;
295  class iterator
296  {
297  friend class KDTree<_DataPoint>;
298  public:
299  iterator(): fBin(0) {}
300  iterator(const iterator& copy): fBin(copy.fBin) {}
301  ~iterator() {}
302 
303  iterator& operator++();
304  const iterator& operator++() const;
305  iterator operator++(int);
306  const iterator operator++(int) const;
307  iterator& operator--();
308  const iterator& operator--() const;
310  const iterator operator--(int) const;
311  bool operator==(const iterator& rIterator) const {return (fBin == rIterator.fBin);}
312  bool operator!=(const iterator& rIterator) const {return !(*this == rIterator);}
313  iterator& operator=(const iterator& rhs);
314  Bin& operator*() {return *fBin;}
315  const Bin& operator*() const {return *fBin;}
316  Bin* operator->() {return fBin;}
317  const Bin* operator->() const {return fBin;}
318 
319  TerminalNode* TN() {assert(dynamic_cast<TerminalNode*>(fBin)); return (TerminalNode*)fBin;}
320 
321  private:
322  iterator(BinNode* pNode): fBin(pNode) {}
323 
324  Bin* Next() const;
325  Bin* Previous() const;
326 
327  mutable Bin* fBin;
328  };
329 
330  //constructor and destructor
331  KDTree(UInt_t iBucketSize);
333 
334  //public member functions
335  void EmptyBins();
336  iterator End();
337  const iterator End() const;
338  const Bin* FindBin(const point_type& rPoint) const {return fHead->FindNode(rPoint);}
339  iterator First();
340  const iterator First() const;
341  void Freeze();
343  void GetClosestPoints(const point_type& rRef,UInt_t nPoints,std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const;
346  UInt_t GetNBins() const;
347  UInt_t GetEntries() const;
348  void GetPointsWithinDist(const point_type& rRef,value_type fDist,std::vector<const point_type*>& vFoundPoints) const;
349  Double_t GetTotalSumw() const;
350  Double_t GetTotalSumw2() const;
351  Bool_t Insert(const point_type& rData) {return fHead->Parent()->Insert(rData);}
352  Bool_t IsFrozen() const {return fIsFrozen;}
354  const iterator Last() const;
355  void Print() {fHead->Parent()->Print();}
356  void Reset();
357  void SetOwner(Bool_t bIsOwner = true);
358  void SetSplitOption(eSplitOption opt);
359 
360  private:
361  KDTree();
362  KDTree(const KDTree<point_type>& ) {}
363  KDTree<point_type>& operator=(const KDTree<point_type>& ) {return *this;}
364 
365  BaseNode* fHead;
368  };
369 
370 
371  }//namespace Math
372 }//namespace ROOT
373 
374 #include "Math/KDTree.icc"
375 
376 #endif // ROOT_Math_KDTree
ROOT::Math::KDTree::SplitNode::operator=
SplitNode & operator=(const SplitNode &)
Definition: KDTree.h:187
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::FindNode
virtual const BinNode * FindNode(const point_type &) const
Definition: KDTree.h:287
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
ROOT::Math::KDTree::BinNode::GetPointsWithinDist
virtual void GetPointsWithinDist(const point_type &, value_type, std::vector< const point_type * > &) const
Definition: KDTree.h:243
ROOT::Math::KDTree::TerminalNode::fSplitOption
eSplitOption fSplitOption
Definition: KDTree.h:297
ROOT::Math::KDTree::Insert
Bool_t Insert(const point_type &rData)
Definition: KDTree.h:366
ROOT::Math::KDTree::BaseNode::Print
virtual void Print(int iRow=0) const =0
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::BinNode::GetEffectiveEntries
Double_t GetEffectiveEntries() const
Definition: KDTree.h:220
ROOT::Math::KDTree::First
iterator First()
Definition: KDTree.icc:131
ROOT::Math::KDTree::EmptyBins
void EmptyBins()
Definition: KDTree.icc:85
ROOT::Math::KDTree::iterator::operator==
bool operator==(const iterator &rIterator) const
Definition: KDTree.h:326
ROOT::Math::KDTree::iterator::operator->
Bin * operator->()
Definition: KDTree.h:331
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::iterator::TN
TerminalNode * TN()
Definition: KDTree.h:334
ROOT::Math::KDTree::point_type
_DataPoint point_type
Definition: KDTree.h:54
ROOT::Math::KDTree::Bin
BinNode Bin
Definition: KDTree.h:309
ROOT::Math::KDTree::BinNode::GetSumw2
Double_t GetSumw2() const
Definition: KDTree.h:224
ROOT::Math::KDTree::fHead
BaseNode * fHead
Definition: KDTree.h:380
ROOT::Math::KDTree::TerminalNode::fSplitAxis
UInt_t fSplitAxis
Definition: KDTree.h:299
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
ROOT::Math::KDTree::ComparePoints::SetAxis
void SetAxis(UInt_t iAxis)
Definition: KDTree.h:70
ROOT::Math::KDTree::BaseNode::FindNode
virtual const BinNode * FindNode(const point_type &rPoint) const =0
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::HeadNode::Insert
virtual Bool_t Insert(const point_type &rPoint)
Definition: KDTree.h:153
ROOT::Math::KDTree::iterator::operator*
Bin & operator*()
Definition: KDTree.h:329
ROOT::Math::KDTree::BinNode::tBoundary
std::pair< value_type, value_type > tBoundary
Definition: KDTree.h:202
ROOT::Math::KDTree::TerminalNode::tBoundary
std::pair< value_type, value_type > tBoundary
Definition: KDTree.h:254
ROOT::Math::KDTree::GetTotalSumw
Double_t GetTotalSumw() const
Definition: KDTree.icc:308
ROOT::Math::KDTree::FindBin
const Bin * FindBin(const point_type &rPoint) const
Definition: KDTree.h:353
ROOT::Math::KDTree::BinNode::GetBinCenter
point_type GetBinCenter() const
Definition: KDTree.icc:826
ROOT::Math::KDTree::TerminalNode::GetPoints
const std::vector< const point_type * > & GetPoints() const
Definition: KDTree.h:268
ROOT::Math::KDTree::TerminalNode::SetOwner
void SetOwner(Bool_t bIsOwner=true)
Definition: KDTree.h:290
ROOT::Math::KDTree::ComparePoints::GetAxis
UInt_t GetAxis() const
Definition: KDTree.h:69
ROOT::Math::KDTree::BaseNode::operator=
BaseNode & operator=(const BaseNode &)
Definition: KDTree.h:134
ROOT::Math::KDTree::iterator::operator--
iterator & operator--()
Definition: KDTree.icc:1437
ROOT::Math::KDTree::Cut::fCutValue
Double_t fCutValue
Definition: KDTree.h:93
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::BinNode::GetClosestPoints
virtual void GetClosestPoints(const point_type &, UInt_t, std::vector< std::pair< const _DataPoint *, Double_t > > &) const
Definition: KDTree.h:242
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::GetSumw
Double_t GetSumw() const
Definition: KDTree.h:223
ROOT::Math::KDTree::BinNode::GetBinContent
Double_t GetBinContent() const
Definition: KDTree.h:213
ROOT::Math::KDTree::BinNode
Definition: KDTree.h:198
ROOT::Math::KDTree::iterator::iterator
iterator()
Definition: KDTree.h:314
ROOT::Math::KDTree::BaseNode::Clone
virtual BaseNode * Clone()=0
ROOT::Math::KDTree::Cut::~Cut
~Cut()
Definition: KDTree.h:81
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
Bool_t
bool Bool_t
Definition: RtypesCore.h:63
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::BaseNode::GetClosestPoints
virtual void GetClosestPoints(const point_type &rRef, UInt_t nPoints, std::vector< std::pair< const _DataPoint *, Double_t > > &vFoundPoints) const =0
ROOT::Math::KDTree::TerminalNode::GetBoundaries
virtual const std::vector< tBoundary > & GetBoundaries() const
Definition: KDTree.icc:1018
ROOT::Math::KDTree::SplitNode::fCut
const Cut * fCut
Definition: KDTree.h:195
ROOT::Math::KDTree::Cut::SetCutValue
void SetCutValue(Double_t fNewCutValue)
Definition: KDTree.h:86
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::~BinNode
virtual ~BinNode()
Definition: KDTree.h:207
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::KDTree::SetSplitOption
void SetSplitOption(eSplitOption opt)
Definition: KDTree.icc:410
RooFit::Cut
RooCmdArg Cut(const char *cutSpec)
Definition: RooGlobalFunc.cxx:80
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::iterator::operator!=
bool operator!=(const iterator &rIterator) const
Definition: KDTree.h:327
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::iterator::~iterator
~iterator()
Definition: KDTree.h:316
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::HeadNode::IsHeadNode
virtual bool IsHeadNode() const
Definition: KDTree.h:162
ROOT::Math::KDTree::operator=
KDTree< point_type > & operator=(const KDTree< point_type > &)
Definition: KDTree.h:378
ROOT::Math::KDTree::TerminalNode
Definition: KDTree.h:250
ROOT::Math::KDTree::BaseNode::fParent
BaseNode * fParent
Definition: KDTree.h:137
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::HeadNode::operator=
HeadNode & operator=(const HeadNode &)
Definition: KDTree.h:159
ROOT::Math::KDTree::BaseNode::BaseNode
BaseNode(BaseNode *pParent=0)
Definition: KDTree.icc:496
ROOT::Math::KDTree::IsFrozen
Bool_t IsFrozen() const
Definition: KDTree.h:367
ROOT::Math::KDTree::HeadNode::Clone
virtual HeadNode * Clone()
Definition: KDTree.icc:556
UInt_t
unsigned int UInt_t
Definition: RtypesCore.h:46
ROOT::Math::KDTree::fIsFrozen
Bool_t fIsFrozen
Definition: KDTree.h:382
ROOT::Math::KDTree::TerminalNode::fOwnData
Bool_t fOwnData
Definition: KDTree.h:296
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::HeadNode::HeadNode
HeadNode(BaseNode &rNode)
Definition: KDTree.h:146
ROOT::Math::KDTree::BinNode::GetDensity
Double_t GetDensity() const
Definition: KDTree.h:219
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::Cut::fAxis
UInt_t fAxis
Definition: KDTree.h:92
ROOT::Math::KDTree::HeadNode::Print
virtual void Print(Int_t) const
Definition: KDTree.h:154
ROOT::Math::KDTree::SplitNode
Definition: KDTree.h:173
ROOT::Math::KDTree::BinNode::fEntries
UInt_t fEntries
Definition: KDTree.h:236
ROOT::Math::KDTree::BaseNode::fLeftChild
BaseNode * fLeftChild
pointer to parent node
Definition: KDTree.h:138
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
ROOT::Math::KDTree::BaseNode::GetPointsWithinDist
virtual void GetPointsWithinDist(const point_type &rRef, value_type fDist, std::vector< const point_type * > &vFoundPoints) const =0
Double_t
double Double_t
Definition: RtypesCore.h:59
ROOT::Math::KDTree::Cut
Definition: KDTree.h:76
RtypesCore.h
ROOT::Math::KDTree::HeadNode::FindNode
virtual const BinNode * FindNode(const point_type &rPoint) const
Definition: KDTree.h:150
ROOT::Math::KDTree::Print
void Print()
Definition: KDTree.h:370
ROOT::Math::KDTree::HeadNode::~HeadNode
virtual ~HeadNode()
Definition: KDTree.h:147
ROOT::Math::KDTree::BaseNode::RightChild
BaseNode *& RightChild()
Definition: KDTree.h:123
ROOT::Math::KDTree::GetBucketSize
Double_t GetBucketSize() const
Definition: KDTree.h:357
ROOT::Math::KDTree::BinNode::BinNode
BinNode(BaseNode *pParent=0)
Definition: KDTree.icc:748
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::BaseNode::Insert
virtual Bool_t Insert(const point_type &rPoint)=0
ROOT::Math::KDTree::TerminalNode::Clone
virtual BinNode * Clone()
Definition: KDTree.h:285
ROOT::Math::KDTree::BinNode::GetEntries
UInt_t GetEntries() const
Definition: KDTree.h:221
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::TerminalNode::operator=
TerminalNode & operator=(const TerminalNode &)
Definition: KDTree.h:275
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::BaseNode::fRightChild
BaseNode * fRightChild
pointer to left child
Definition: KDTree.h:139
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::Cut::Cut
Cut()
Definition: KDTree.h:79
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
KDTree.icc
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
int
ROOT::Math::KDTree
Definition: KDTree.h:45