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