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
26namespace 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();}
43 kEffective = 0, //split according to effective entries
44 kBinContent //split according to bin content
45 };
46
47 private:
48
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;}
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
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
105 const BaseNode* LeftChild() const {return fLeftChild;}
106 BaseNode*& Parent() {return fParent;}
107 const BaseNode* Parent() const {return fParent;}
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
150 using BaseNode::Parent;
153
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
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
205 Double_t GetEffectiveEntries() const {return (GetSumw2()) ? std::pow(GetSumw(),2)/GetSumw2() : 0;}
206 UInt_t GetEntries() const {return fEntries;}
207 Double_t GetVolume() const;
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
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
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;}
279 void UpdateBoundaries();
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;
296 {
297 friend class KDTree<_DataPoint>;
298 public:
299 iterator(): fBin(0) {}
300 iterator(const iterator& copy): fBin(copy.fBin) {}
302
304 const iterator& operator++() const;
305 iterator operator++(int);
306 const iterator operator++(int) const;
308 const iterator& operator--() const;
309 iterator operator--(int);
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);
332 ~KDTree();
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;}
353 iterator Last();
354 const iterator Last() const;
355 void Print() {fHead->Parent()->Print();}
356 void Reset();
357 void SetOwner(Bool_t bIsOwner = true);
359
360 private:
361 KDTree();
364
368 };
369
370
371 }//namespace Math
372}//namespace ROOT
373
374#include "Math/KDTree.icc"
375
376#endif // ROOT_Math_KDTree
int Int_t
Definition: RtypesCore.h:45
unsigned int UInt_t
Definition: RtypesCore.h:46
bool Bool_t
Definition: RtypesCore.h:63
double Double_t
Definition: RtypesCore.h:59
BaseNode *& GetParentPointer()
Definition: KDTree.icc:520
BaseNode(const BaseNode &)
Definition: KDTree.h:118
const BaseNode * LeftChild() const
Definition: KDTree.h:105
virtual Bool_t Insert(const point_type &rPoint)=0
const BaseNode * Parent() const
Definition: KDTree.h:107
virtual const BinNode * FindNode(const point_type &rPoint) const =0
const BaseNode * RightChild() const
Definition: KDTree.h:109
BaseNode *& Parent()
Definition: KDTree.h:106
virtual void GetPointsWithinDist(const point_type &rRef, value_type fDist, std::vector< const point_type * > &vFoundPoints) const =0
virtual void GetClosestPoints(const point_type &rRef, UInt_t nPoints, std::vector< std::pair< const _DataPoint *, Double_t > > &vFoundPoints) const =0
Bool_t IsLeftChild() const
Definition: KDTree.icc:542
BaseNode * fRightChild
pointer to left child
Definition: KDTree.h:124
virtual Bool_t IsHeadNode() const
Definition: KDTree.h:113
BaseNode & operator=(const BaseNode &)
Definition: KDTree.h:119
BaseNode(BaseNode *pParent=0)
Definition: KDTree.icc:496
BaseNode *& LeftChild()
Definition: KDTree.h:104
virtual void Print(int iRow=0) const =0
virtual BaseNode * Clone()=0
BaseNode *& RightChild()
Definition: KDTree.h:108
BaseNode * fLeftChild
pointer to parent node
Definition: KDTree.h:123
virtual void GetPointsWithinDist(const point_type &, value_type, std::vector< const point_type * > &) const
Definition: KDTree.h:228
virtual const std::vector< tBoundary > & GetBoundaries() const
Definition: KDTree.h:200
virtual void EmptyBin()
Definition: KDTree.icc:788
std::vector< tBoundary > fBoundaries
Definition: KDTree.h:218
virtual const BinNode * FindNode(const point_type &rPoint) const
Definition: KDTree.icc:814
BinNode(BaseNode *pParent=0)
Definition: KDTree.icc:748
virtual BinNode * Clone()
Definition: KDTree.icc:779
point_type GetBinCenter() const
Definition: KDTree.icc:826
Double_t GetSumw2() const
Definition: KDTree.h:209
virtual void GetClosestPoints(const point_type &, UInt_t, std::vector< std::pair< const _DataPoint *, Double_t > > &) const
Definition: KDTree.h:227
virtual Bool_t Insert(const point_type &rPoint)
Definition: KDTree.icc:860
Double_t GetSumw() const
Definition: KDTree.h:208
std::pair< value_type, value_type > tBoundary
Definition: KDTree.h:187
Bool_t IsInBin(const point_type &rPoint) const
Definition: KDTree.icc:878
BinNode & operator=(const BinNode &rhs)
Definition: KDTree.icc:798
virtual void Print(int iRow=0) const
Definition: KDTree.icc:891
UInt_t GetEntries() const
Definition: KDTree.h:206
Double_t GetDensity() const
Definition: KDTree.h:204
Double_t GetEffectiveEntries() const
Definition: KDTree.h:205
Double_t GetBinContent() const
Definition: KDTree.h:198
Double_t GetVolume() const
Definition: KDTree.icc:843
Bool_t operator()(const point_type *pFirst, const point_type *pSecond) const
Definition: KDTree.icc:433
void SetAxis(UInt_t iAxis)
Definition: KDTree.h:55
value_type GetCutValue() const
Definition: KDTree.h:69
Cut(UInt_t iAxis, Double_t fNewCutValue)
Definition: KDTree.h:65
UInt_t GetAxis() const
Definition: KDTree.h:68
Bool_t operator>(const point_type &rPoint) const
Definition: KDTree.icc:476
void SetAxis(UInt_t iAxis)
Definition: KDTree.h:70
void SetCutValue(Double_t fNewCutValue)
Definition: KDTree.h:71
Double_t fCutValue
Definition: KDTree.h:78
Bool_t operator<(const point_type &rPoint) const
Definition: KDTree.icc:456
virtual bool IsHeadNode() const
Definition: KDTree.h:147
virtual Bool_t Insert(const point_type &rPoint)
Definition: KDTree.h:138
HeadNode & operator=(const HeadNode &)
Definition: KDTree.h:144
HeadNode(BaseNode &rNode)
Definition: KDTree.h:131
HeadNode(const HeadNode &)
Definition: KDTree.h:143
virtual void GetPointsWithinDist(const point_type &rRef, value_type fDist, std::vector< const _DataPoint * > &vFoundPoints) const
Definition: KDTree.icc:580
BaseNode *& Parent()
Definition: KDTree.h:106
virtual void Print(Int_t) const
Definition: KDTree.h:139
virtual HeadNode * Clone()
Definition: KDTree.icc:556
virtual const BinNode * FindNode(const point_type &rPoint) const
Definition: KDTree.h:135
virtual void GetClosestPoints(const point_type &rRef, UInt_t nPoints, std::vector< std::pair< const _DataPoint *, Double_t > > &vFoundPoints) const
Definition: KDTree.icc:572
SplitNode(UInt_t iAxis, Double_t fCutValue, BaseNode &rLeft, BaseNode &rRight, BaseNode *pParent=0)
Definition: KDTree.icc:588
virtual void GetClosestPoints(const point_type &rRef, UInt_t nPoints, std::vector< std::pair< const _DataPoint *, Double_t > > &vFoundPoints) const
Definition: KDTree.icc:652
virtual void GetPointsWithinDist(const point_type &rRef, value_type fDist, std::vector< const _DataPoint * > &vFoundPoints) const
Definition: KDTree.icc:689
const Cut * GetCut() const
Definition: KDTree.h:166
virtual const BinNode * FindNode(const point_type &rPoint) const
Definition: KDTree.icc:638
SplitNode & operator=(const SplitNode &)
Definition: KDTree.h:172
virtual SplitNode * Clone()
Definition: KDTree.icc:619
virtual void Print(Int_t iRow=0) const
Definition: KDTree.icc:735
SplitNode(const SplitNode &)
Definition: KDTree.h:171
virtual Bool_t Insert(const point_type &rPoint)
Definition: KDTree.icc:721
virtual const std::vector< tBoundary > & GetBoundaries() const
Definition: KDTree.icc:1018
std::vector< constpoint_type * >::iterator data_it
Definition: KDTree.h:263
void SetOwner(Bool_t bIsOwner=true)
Definition: KDTree.h:275
void SetSplitOption(eSplitOption opt)
Definition: KDTree.h:276
virtual const BinNode * FindNode(const point_type &) const
Definition: KDTree.h:272
std::pair< value_type, value_type > tBoundary
Definition: KDTree.h:239
virtual void GetPointsWithinDist(const point_type &rRef, value_type fDist, std::vector< const _DataPoint * > &vFoundPoints) const
Definition: KDTree.icc:1085
virtual void Print(int iRow=0) const
Definition: KDTree.icc:1140
TerminalNode(Double_t iBucketSize, BaseNode *pParent=0)
Definition: KDTree.icc:915
virtual Bool_t Insert(const point_type &rPoint)
Definition: KDTree.icc:1106
std::vector< constpoint_type * >::const_iterator const_data_it
Definition: KDTree.h:264
virtual void GetClosestPoints(const point_type &rRef, UInt_t nPoints, std::vector< std::pair< const _DataPoint *, Double_t > > &vFoundPoints) const
Definition: KDTree.icc:1040
TerminalNode & operator=(const TerminalNode &)
Definition: KDTree.h:260
TerminalNode(const TerminalNode &)
Definition: KDTree.h:259
virtual BinNode * Clone()
Definition: KDTree.h:270
std::vector< const _DataPoint * > fDataPoints
Definition: KDTree.h:285
const std::vector< const point_type * > & GetPoints() const
Definition: KDTree.h:253
bool operator==(const iterator &rIterator) const
Definition: KDTree.h:311
TerminalNode * TN()
Definition: KDTree.h:319
const Bin & operator*() const
Definition: KDTree.h:315
bool operator!=(const iterator &rIterator) const
Definition: KDTree.h:312
iterator(BinNode *pNode)
Definition: KDTree.h:322
iterator(const iterator &copy)
Definition: KDTree.h:300
iterator & operator=(const iterator &rhs)
Definition: KDTree.icc:1479
const Bin * operator->() const
Definition: KDTree.h:317
Bool_t IsFrozen() const
Definition: KDTree.h:352
Double_t GetTotalSumw2() const
Definition: KDTree.icc:321
Bool_t Insert(const point_type &rData)
Definition: KDTree.h:351
Bool_t fIsFrozen
Definition: KDTree.h:367
void SetOwner(Bool_t bIsOwner=true)
Definition: KDTree.icc:391
KDTree< _DataPoint > * GetFrozenCopy()
Definition: KDTree.icc:256
Double_t GetTotalSumw() const
Definition: KDTree.icc:308
_DataPoint point_type
Definition: KDTree.h:39
void EmptyBins()
Definition: KDTree.icc:85
_DataPoint::value_type value_type
Definition: KDTree.h:40
const Bin * FindBin(const point_type &rPoint) const
Definition: KDTree.h:338
UInt_t GetEntries() const
Definition: KDTree.icc:243
void GetPointsWithinDist(const point_type &rRef, value_type fDist, std::vector< const point_type * > &vFoundPoints) const
Definition: KDTree.icc:286
iterator First()
Definition: KDTree.icc:131
UInt_t GetNBins() const
Definition: KDTree.icc:273
iterator Last()
Definition: KDTree.icc:334
Double_t fBucketSize
Definition: KDTree.h:366
Double_t GetBucketSize() const
Definition: KDTree.h:342
Double_t GetEffectiveEntries() const
Definition: KDTree.icc:224
KDTree< point_type > & operator=(const KDTree< point_type > &)
Definition: KDTree.h:363
BaseNode * fHead
Definition: KDTree.h:365
void SetSplitOption(eSplitOption opt)
Definition: KDTree.icc:410
void GetClosestPoints(const point_type &rRef, UInt_t nPoints, std::vector< std::pair< const _DataPoint *, Double_t > > &vFoundPoints) const
Definition: KDTree.icc:200
KDTree(const KDTree< point_type > &)
Definition: KDTree.h:362
iterator End()
Definition: KDTree.icc:103
static UInt_t Dimension()
Definition: KDTree.h:41
Namespace for new Math classes and functions.
tbb::task_arena is an alias of tbb::interface7::task_arena, which doesn't allow to forward declare tb...
Definition: first.py:1