Logo ROOT   6.30.04
Reference Guide
 All Namespaces Files Pages
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 
48  class ComparePoints
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
103  BaseNode*& LeftChild() {return fLeftChild;}
104  const BaseNode* LeftChild() const {return fLeftChild;}
105  BaseNode*& Parent() {return fParent;}
106  const BaseNode* Parent() const {return fParent;}
107  BaseNode*& RightChild() {return fRightChild;}
108  const BaseNode* RightChild() const {return fRightChild;}
109 
110  //information about relative position of current node
111  BaseNode*& GetParentPointer();
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 
153  using BaseNode::GetParentPointer;
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
203  Double_t GetDensity() const {return GetBinContent()/GetVolume();}
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
258  TerminalNode(const TerminalNode& ) {}
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();}
270  BinNode* 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;}
275  void SetSplitOption(eSplitOption opt) {fSplitOption = opt;}
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) {}
300  ~iterator() {}
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();
341  Double_t GetBucketSize() const {return fBucketSize;}
342  void GetClosestPoints(const point_type& rRef,UInt_t nPoints,std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const;
343  Double_t GetEffectiveEntries() const;
344  KDTree<_DataPoint>* GetFrozenCopy();
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();
361  KDTree(const KDTree<point_type>& ) {}
362  KDTree<point_type>& operator=(const KDTree<point_type>& ) {return *this;}
363 
364  BaseNode* fHead;
365  Double_t fBucketSize;
366  Bool_t fIsFrozen;
367  };
368 
369 
370  }//namespace Math
371 }//namespace ROOT
372 
373 #include "Math/KDTree.icc"
374 
375 #endif // ROOT_Math_KDTree