Logo ROOT   6.18/05
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
25namespace 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();}
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;}
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
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;
152
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
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
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
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;}
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;
295 {
296 friend class KDTree<_DataPoint>;
297 public:
298 iterator(): fBin(0) {}
299 iterator(const iterator& copy): fBin(copy.fBin) {}
301
303 const iterator& operator++() const;
304 iterator operator++(int);
305 const iterator operator++(int) const;
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);
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
int Int_t
Definition: RtypesCore.h:41
unsigned int UInt_t
Definition: RtypesCore.h:42
bool Bool_t
Definition: RtypesCore.h:59
double Double_t
Definition: RtypesCore.h:55
double pow(double, double)
BaseNode *& GetParentPointer()
Definition: KDTree.icc:520
BaseNode(const BaseNode &)
Definition: KDTree.h:117
const BaseNode * LeftChild() const
Definition: KDTree.h:104
virtual Bool_t Insert(const point_type &rPoint)=0
const BaseNode * Parent() const
Definition: KDTree.h:106
virtual const BinNode * FindNode(const point_type &rPoint) const =0
const BaseNode * RightChild() const
Definition: KDTree.h:108
BaseNode *& Parent()
Definition: KDTree.h:105
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:123
virtual Bool_t IsHeadNode() const
Definition: KDTree.h:112
BaseNode & operator=(const BaseNode &)
Definition: KDTree.h:118
BaseNode(BaseNode *pParent=0)
Definition: KDTree.icc:496
BaseNode *& LeftChild()
Definition: KDTree.h:103
virtual void Print(int iRow=0) const =0
virtual BaseNode * Clone()=0
BaseNode *& RightChild()
Definition: KDTree.h:107
BaseNode * fLeftChild
pointer to parent node
Definition: KDTree.h:122
virtual void GetPointsWithinDist(const point_type &, value_type, std::vector< const point_type * > &) const
Definition: KDTree.h:227
virtual const std::vector< tBoundary > & GetBoundaries() const
Definition: KDTree.h:199
virtual void EmptyBin()
Definition: KDTree.icc:788
std::vector< tBoundary > fBoundaries
Definition: KDTree.h:217
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:208
virtual void GetClosestPoints(const point_type &, UInt_t, std::vector< std::pair< const _DataPoint *, Double_t > > &) const
Definition: KDTree.h:226
virtual Bool_t Insert(const point_type &rPoint)
Definition: KDTree.icc:860
Double_t GetSumw() const
Definition: KDTree.h:207
std::pair< value_type, value_type > tBoundary
Definition: KDTree.h:186
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:205
Double_t GetDensity() const
Definition: KDTree.h:203
Double_t GetEffectiveEntries() const
Definition: KDTree.h:204
Double_t GetBinContent() const
Definition: KDTree.h:197
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:54
value_type GetCutValue() const
Definition: KDTree.h:68
Cut(UInt_t iAxis, Double_t fNewCutValue)
Definition: KDTree.h:64
UInt_t GetAxis() const
Definition: KDTree.h:67
Bool_t operator>(const point_type &rPoint) const
Definition: KDTree.icc:476
void SetAxis(UInt_t iAxis)
Definition: KDTree.h:69
void SetCutValue(Double_t fNewCutValue)
Definition: KDTree.h:70
Double_t fCutValue
Definition: KDTree.h:77
Bool_t operator<(const point_type &rPoint) const
Definition: KDTree.icc:456
virtual bool IsHeadNode() const
Definition: KDTree.h:146
virtual Bool_t Insert(const point_type &rPoint)
Definition: KDTree.h:137
HeadNode & operator=(const HeadNode &)
Definition: KDTree.h:143
HeadNode(BaseNode &rNode)
Definition: KDTree.h:130
HeadNode(const HeadNode &)
Definition: KDTree.h:142
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:105
virtual void Print(Int_t) const
Definition: KDTree.h:138
virtual HeadNode * Clone()
Definition: KDTree.icc:556
virtual const BinNode * FindNode(const point_type &rPoint) const
Definition: KDTree.h:134
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:165
virtual const BinNode * FindNode(const point_type &rPoint) const
Definition: KDTree.icc:638
SplitNode & operator=(const SplitNode &)
Definition: KDTree.h:171
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:170
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:262
void SetOwner(Bool_t bIsOwner=true)
Definition: KDTree.h:274
void SetSplitOption(eSplitOption opt)
Definition: KDTree.h:275
virtual const BinNode * FindNode(const point_type &) const
Definition: KDTree.h:271
std::pair< value_type, value_type > tBoundary
Definition: KDTree.h:238
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:263
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:259
TerminalNode(const TerminalNode &)
Definition: KDTree.h:258
virtual BinNode * Clone()
Definition: KDTree.h:269
std::vector< const _DataPoint * > fDataPoints
Definition: KDTree.h:284
const std::vector< const point_type * > & GetPoints() const
Definition: KDTree.h:252
bool operator==(const iterator &rIterator) const
Definition: KDTree.h:310
TerminalNode * TN()
Definition: KDTree.h:318
const Bin & operator*() const
Definition: KDTree.h:314
bool operator!=(const iterator &rIterator) const
Definition: KDTree.h:311
iterator(BinNode *pNode)
Definition: KDTree.h:321
iterator(const iterator &copy)
Definition: KDTree.h:299
iterator & operator=(const iterator &rhs)
Definition: KDTree.icc:1479
const Bin * operator->() const
Definition: KDTree.h:316
Bool_t IsFrozen() const
Definition: KDTree.h:351
Double_t GetTotalSumw2() const
Definition: KDTree.icc:321
Bool_t Insert(const point_type &rData)
Definition: KDTree.h:350
Bool_t fIsFrozen
Definition: KDTree.h:366
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:38
void EmptyBins()
Definition: KDTree.icc:85
_DataPoint::value_type value_type
Definition: KDTree.h:39
const Bin * FindBin(const point_type &rPoint) const
Definition: KDTree.h:337
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:365
Double_t GetBucketSize() const
Definition: KDTree.h:341
Double_t GetEffectiveEntries() const
Definition: KDTree.icc:224
KDTree< point_type > & operator=(const KDTree< point_type > &)
Definition: KDTree.h:362
BaseNode * fHead
Definition: KDTree.h:364
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:361
iterator End()
Definition: KDTree.icc:103
static UInt_t Dimension()
Definition: KDTree.h:40
Namespace for new Math classes and functions.
Namespace for new ROOT classes and functions.
Definition: StringConv.hxx:21
Definition: first.py:1