```// @(#)root/mathcore:\$Id\$
// Authors: C. Gumpert    09/2011
/**********************************************************************
*                                                                    *
* Copyright (c) 2011 , LCG ROOT MathLib Team                         *
*                                                                    *
*                                                                    *
**********************************************************************/
//
// Header file for KDTree class
//

#ifndef ROOT_Math_KDTree
#define ROOT_Math_KDTree

#include <assert.h>
#include <vector>
#include <cmath>

// ROOT include(s)
#include "Rtypes.h"

namespace ROOT
{
namespace Math
{

//______________________________________________________________________________
//Begin_Html
//End_Html
template<class _DataPoint>
class KDTree
{
public:

typedef _DataPoint                        point_type;
typedef typename _DataPoint::value_type   value_type;
static UInt_t Dimension() {return _DataPoint::Dimension();}
enum eSplitOption {
kEffective = 0,                         //split according to effective entries
kBinContent                             //split according to bin content
};

private:

class ComparePoints
{
public:
Bool_t   operator()(const point_type* pFirst,const point_type* pSecond) const;

UInt_t   GetAxis() const       {return fAxis;}
void     SetAxis(UInt_t iAxis) {fAxis = iAxis;}

private:
UInt_t   fAxis; //axis at which the points are compared
};

class Cut
{
public:
Cut():fAxis(0),fCutValue(0) {}
Cut(UInt_t iAxis,Double_t fNewCutValue):fAxis(iAxis),fCutValue(fNewCutValue) {}
~Cut() {}

UInt_t       GetAxis() const                   {return fAxis;}
value_type   GetCutValue() const               {return fCutValue;}
void         SetAxis(UInt_t iAxis)             {fAxis = iAxis;}
void         SetCutValue(Double_t fNewCutValue) {fCutValue = fNewCutValue;}

Bool_t       operator<(const point_type& rPoint) const;
Bool_t       operator>(const point_type& rPoint) const;

private:
UInt_t    fAxis;       //axis at which the splitting is done
Double_t  fCutValue;   //split value
};

//forward declarations
class BaseNode;
class SplitNode;
class BinNode;
class TerminalNode;

class BaseNode
{
public:
//constructor and destructor
BaseNode(BaseNode* pParent = 0);
virtual ~BaseNode();

//providing usual functionality of a tree
virtual BaseNode*        Clone() = 0;
virtual const BinNode*   FindNode(const point_type& rPoint) const = 0;
virtual void             GetClosestPoints(const point_type& rRef,UInt_t nPoints,std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const = 0;
virtual void             GetPointsWithinDist(const point_type& rRef,value_type fDist,std::vector<const point_type*>& vFoundPoints) const = 0;
virtual Bool_t           Insert(const point_type& rPoint) = 0;
virtual void             Print(int iRow = 0) const = 0;

//navigating the tree
BaseNode*&                LeftChild()        {return fLeftChild;}
const BaseNode*           LeftChild() const  {return fLeftChild;}
BaseNode*&                Parent()           {return fParent;}
const BaseNode*           Parent() const     {return fParent;}
BaseNode*&                RightChild()       {return fRightChild;}
const BaseNode*           RightChild() const {return fRightChild;}

//information about relative position of current node
BaseNode*&                GetParentPointer();
virtual Bool_t            IsHeadNode() const {return false;}
Bool_t                    IsLeftChild() const;

private:
// node should never be copied or assigned
BaseNode(const BaseNode& ) {}
BaseNode& operator=(const BaseNode& ) {return *this;}

BaseNode*                 fParent;     //!pointer to parent node
BaseNode*                 fLeftChild;  //!pointer to left child
BaseNode*                 fRightChild; //!pointer to right child
};

{
public:
//constructor and destructor

//delegate everything to the actual root node of the tree
virtual const BinNode*   FindNode(const point_type& rPoint) const {return Parent()->FindNode(rPoint);}
virtual void             GetClosestPoints(const point_type& rRef,UInt_t nPoints,std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const;
virtual void             GetPointsWithinDist(const point_type& rRef,value_type fDist,std::vector<const _DataPoint*>& vFoundPoints) const;
virtual Bool_t           Insert(const point_type& rPoint) {return Parent()->Insert(rPoint);}
virtual void             Print(Int_t) const {Parent()->Print();}

private:
// node should never be copied

virtual bool             IsHeadNode() const {return true;}

// only delegate everything else is private and should not be used
using BaseNode::Parent;
using BaseNode::LeftChild;
using BaseNode::RightChild;

using BaseNode::GetParentPointer;
using BaseNode::IsLeftChild;
};

class SplitNode : public BaseNode
{
public:
// constructors and destructors
SplitNode(UInt_t iAxis,Double_t fCutValue,BaseNode& rLeft,BaseNode& rRight,BaseNode* pParent = 0);
virtual ~SplitNode();

const Cut*               GetCut() const {return fCut;}
virtual void             Print(Int_t iRow = 0) const;

private:
// node should never be copied
SplitNode(const SplitNode& ) {}
SplitNode& operator=(const SplitNode& ) {return *this;}

virtual SplitNode*       Clone();
virtual const BinNode*   FindNode(const point_type& rPoint) const;
virtual void             GetClosestPoints(const point_type& rRef,UInt_t nPoints,std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const;
virtual void             GetPointsWithinDist(const point_type& rRef,value_type fDist,std::vector<const _DataPoint*>& vFoundPoints) const;
virtual Bool_t           Insert(const point_type& rPoint);

const Cut*               fCut;     //pointer to cut object owned by this node
};

class BinNode : public BaseNode
{
protected:
//save some typing
typedef std::pair<value_type,value_type> tBoundary;
public:
// constructors and destructors
BinNode(BaseNode* pParent = 0);
BinNode(const BinNode& copy);
virtual ~BinNode() {}

// usual bin operations
virtual void                            EmptyBin();
virtual const BinNode*                  FindNode(const point_type& rPoint) const;
point_type                              GetBinCenter() const;
Double_t                                GetBinContent() const {return GetSumw();}
#ifndef _AIX
virtual const std::vector<tBoundary>&   GetBoundaries() const {return fBoundaries;}
#else
virtual void GetBoundaries() const { }
#endif
Double_t                                GetDensity() const {return GetBinContent()/GetVolume();}
Double_t                                GetEffectiveEntries() const {return (GetSumw2()) ? std::pow(GetSumw(),2)/GetSumw2() : 0;}
UInt_t                                  GetEntries() const {return fEntries;}
Double_t                                GetVolume() const;
Double_t                                GetSumw() const {return fSumw;}
Double_t                                GetSumw2() const {return fSumw2;}
virtual Bool_t                          Insert(const point_type& rPoint);
Bool_t                                  IsInBin(const point_type& rPoint) const;
virtual void                            Print(int iRow = 0) const;

protected:
virtual BinNode*                        Clone();

// intrinsic bin properties
std::vector<tBoundary>                  fBoundaries;    //bin boundaries
Double_t                                fSumw;          //sum of weights
Double_t                                fSumw2;         //sum of weights^2
UInt_t                                  fEntries;       //number of entries

private:
BinNode& operator=(const BinNode& rhs);

// bin does not contain any point like information
virtual void                    GetClosestPoints(const point_type&,UInt_t,std::vector<std::pair<const _DataPoint*,Double_t> >&) const {}
virtual void                    GetPointsWithinDist(const point_type&,value_type,std::vector<const point_type*>&) const {}

// a bin does not have children
using BaseNode::LeftChild;
using BaseNode::RightChild;
};

class TerminalNode : public BinNode
{
friend class KDTree<_DataPoint>;
//save some typing
typedef std::pair<value_type,value_type> tBoundary;

public:
//constructor and desctructor
TerminalNode(Double_t iBucketSize,BaseNode* pParent = 0);
virtual ~TerminalNode();

virtual void                            EmptyBin();
#ifndef _AIX
virtual const std::vector<tBoundary>&   GetBoundaries() const;
#else
virtual void GetBoundaries() const;
#endif
virtual void                            GetClosestPoints(const point_type& rRef,UInt_t nPoints,std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const;
const std::vector<const point_type*>&   GetPoints() const {return fDataPoints;}
virtual void                            GetPointsWithinDist(const point_type& rRef,value_type fDist,std::vector<const _DataPoint*>& vFoundPoints) const;
virtual void                            Print(int iRow = 0) const;

private:
// node should never be copied
TerminalNode(const TerminalNode& ) {}
TerminalNode& operator=(const TerminalNode& ) {return *this;}

// save some typing
typedef typename std::vector<const point_type* >::iterator         data_it;
typedef typename std::vector<const point_type* >::const_iterator   const_data_it;

// creating new Terminal Node when splitting, copying elements in the given range
TerminalNode(Double_t iBucketSize,UInt_t iSplitAxis,data_it first,data_it end);

//tree operations
virtual BinNode*                        Clone() {return ConvertToBinNode();}
BinNode*                                ConvertToBinNode();
virtual const BinNode*                  FindNode(const point_type&) const {return this;}
virtual Bool_t                          Insert(const point_type& rPoint);
void                                    Split();
void                                    SetOwner(Bool_t bIsOwner = true) {fOwnData = bIsOwner;}
void                                    SetSplitOption(eSplitOption opt) {fSplitOption = opt;}
data_it                                 SplitEffectiveEntries();
data_it                                 SplitBinContent();
void                                    UpdateBoundaries();

Bool_t                                  fOwnData;       // terminal node owns the data objects (default = false)
eSplitOption                            fSplitOption;   // according to which figure of merit the node is splitted
Double_t                                fBucketSize;    // target number of entries per bucket
UInt_t                                  fSplitAxis;     // axis at which the next split will occur
std::vector<const _DataPoint*>          fDataPoints;    // data points in this bucket
};

public:
//////////////////////////////////////////////////////////////////////
//
// template<class _DataPoint> class KDTree<_DataPoint>::iterator
//
//////////////////////////////////////////////////////////////////////
typedef BinNode Bin;
class iterator
{
friend class KDTree<_DataPoint>;
public:
iterator(): fBin(0) {}
iterator(const iterator& copy): fBin(copy.fBin) {}
~iterator() {}

iterator&         operator++();
const iterator&   operator++() const;
iterator          operator++(int);
const iterator    operator++(int) const;
iterator&         operator--();
const iterator&   operator--() const;
iterator          operator--(int);
const iterator    operator--(int) const;
bool              operator==(const iterator& rIterator) const {return (fBin == rIterator.fBin);}
bool              operator!=(const iterator& rIterator) const {return !(*this == rIterator);}
iterator&         operator=(const iterator& rhs);
Bin&              operator*() {return *fBin;}
const Bin&        operator*() const {return *fBin;}
Bin*              operator->() {return fBin;}
const Bin*        operator->() const {return fBin;}

TerminalNode*     TN() {assert(dynamic_cast<TerminalNode*>(fBin)); return (TerminalNode*)fBin;}

private:
iterator(BinNode* pNode): fBin(pNode) {}

Bin*     Next() const;
Bin*     Previous() const;

mutable Bin* fBin;
};

//constructor and destructor
KDTree(UInt_t iBucketSize);
~KDTree();

//public member functions
void            EmptyBins();
iterator        End();
const iterator  End() const;
const Bin*      FindBin(const point_type& rPoint) const {return fHead->FindNode(rPoint);}
iterator        First();
const iterator  First() const;
void            Freeze();
Double_t        GetBucketSize() const {return fBucketSize;}
void            GetClosestPoints(const point_type& rRef,UInt_t nPoints,std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const;
Double_t         GetEffectiveEntries() const;
KDTree<_DataPoint>* GetFrozenCopy();
UInt_t          GetNBins() const;
UInt_t          GetEntries() const;
void            GetPointsWithinDist(const point_type& rRef,value_type fDist,std::vector<const point_type*>& vFoundPoints) const;
Double_t        GetTotalSumw() const;
Double_t        GetTotalSumw2() const;
Bool_t          Insert(const point_type& rData) {return fHead->Parent()->Insert(rData);}
Bool_t          IsFrozen() const {return fIsFrozen;}
iterator        Last();
const iterator  Last() const;
void            Reset();
void            SetOwner(Bool_t bIsOwner = true);
void            SetSplitOption(eSplitOption opt);

private:
KDTree();
KDTree(const KDTree<point_type>& ) {}
KDTree<point_type>& operator=(const KDTree<point_type>& ) {return *this;}

Double_t   fBucketSize;
Bool_t     fIsFrozen;
};

}//namespace Math
}//namespace ROOT

#include "Math/KDTree.icc"

#endif // ROOT_Math_KDTree
```
KDTree.h:1
KDTree.h:2
KDTree.h:3
KDTree.h:4
KDTree.h:5
KDTree.h:6
KDTree.h:7
KDTree.h:8
KDTree.h:9
KDTree.h:10
KDTree.h:11
KDTree.h:12
KDTree.h:13
KDTree.h:14
KDTree.h:15
KDTree.h:16
KDTree.h:17
KDTree.h:18
KDTree.h:19
KDTree.h:20
KDTree.h:21
KDTree.h:22
KDTree.h:23
KDTree.h:24
KDTree.h:25
KDTree.h:26
KDTree.h:27
KDTree.h:28
KDTree.h:29
KDTree.h:30
KDTree.h:31
KDTree.h:32
KDTree.h:33
KDTree.h:34
KDTree.h:35
KDTree.h:36
KDTree.h:37
KDTree.h:38
KDTree.h:39
KDTree.h:40
KDTree.h:41
KDTree.h:42
KDTree.h:43
KDTree.h:44
KDTree.h:45
KDTree.h:46
KDTree.h:47
KDTree.h:48
KDTree.h:49
KDTree.h:50
KDTree.h:51
KDTree.h:52
KDTree.h:53
KDTree.h:54
KDTree.h:55
KDTree.h:56
KDTree.h:57
KDTree.h:58
KDTree.h:59
KDTree.h:60
KDTree.h:61
KDTree.h:62
KDTree.h:63
KDTree.h:64
KDTree.h:65
KDTree.h:66
KDTree.h:67
KDTree.h:68
KDTree.h:69
KDTree.h:70
KDTree.h:71
KDTree.h:72
KDTree.h:73
KDTree.h:74
KDTree.h:75
KDTree.h:76
KDTree.h:77
KDTree.h:78
KDTree.h:79
KDTree.h:80
KDTree.h:81
KDTree.h:82
KDTree.h:83
KDTree.h:84
KDTree.h:85
KDTree.h:86
KDTree.h:87
KDTree.h:88
KDTree.h:89
KDTree.h:90
KDTree.h:91
KDTree.h:92
KDTree.h:93
KDTree.h:94
KDTree.h:95
KDTree.h:96
KDTree.h:97
KDTree.h:98
KDTree.h:99
KDTree.h:100
KDTree.h:101
KDTree.h:102
KDTree.h:103
KDTree.h:104
KDTree.h:105
KDTree.h:106
KDTree.h:107
KDTree.h:108
KDTree.h:109
KDTree.h:110
KDTree.h:111
KDTree.h:112
KDTree.h:113
KDTree.h:114
KDTree.h:115
KDTree.h:116
KDTree.h:117
KDTree.h:118
KDTree.h:119
KDTree.h:120
KDTree.h:121
KDTree.h:122
KDTree.h:123
KDTree.h:124
KDTree.h:125
KDTree.h:126
KDTree.h:127
KDTree.h:128
KDTree.h:129
KDTree.h:130
KDTree.h:131
KDTree.h:132
KDTree.h:133
KDTree.h:134
KDTree.h:135
KDTree.h:136
KDTree.h:137
KDTree.h:138
KDTree.h:139
KDTree.h:140
KDTree.h:141
KDTree.h:142
KDTree.h:143
KDTree.h:144
KDTree.h:145
KDTree.h:146
KDTree.h:147
KDTree.h:148
KDTree.h:149
KDTree.h:150
KDTree.h:151
KDTree.h:152
KDTree.h:153
KDTree.h:154
KDTree.h:155
KDTree.h:156
KDTree.h:157
KDTree.h:158
KDTree.h:159
KDTree.h:160
KDTree.h:161
KDTree.h:162
KDTree.h:163
KDTree.h:164
KDTree.h:165
KDTree.h:166
KDTree.h:167
KDTree.h:168
KDTree.h:169
KDTree.h:170
KDTree.h:171
KDTree.h:172
KDTree.h:173
KDTree.h:174
KDTree.h:175
KDTree.h:176
KDTree.h:177
KDTree.h:178
KDTree.h:179
KDTree.h:180
KDTree.h:181
KDTree.h:182
KDTree.h:183
KDTree.h:184
KDTree.h:185
KDTree.h:186
KDTree.h:187
KDTree.h:188
KDTree.h:189
KDTree.h:190
KDTree.h:191
KDTree.h:192
KDTree.h:193
KDTree.h:194
KDTree.h:195
KDTree.h:196
KDTree.h:197
KDTree.h:198
KDTree.h:199
KDTree.h:200
KDTree.h:201
KDTree.h:202
KDTree.h:203
KDTree.h:204
KDTree.h:205
KDTree.h:206
KDTree.h:207
KDTree.h:208
KDTree.h:209
KDTree.h:210
KDTree.h:211
KDTree.h:212
KDTree.h:213
KDTree.h:214
KDTree.h:215
KDTree.h:216
KDTree.h:217
KDTree.h:218
KDTree.h:219
KDTree.h:220
KDTree.h:221
KDTree.h:222
KDTree.h:223
KDTree.h:224
KDTree.h:225
KDTree.h:226
KDTree.h:227
KDTree.h:228
KDTree.h:229
KDTree.h:230
KDTree.h:231
KDTree.h:232
KDTree.h:233
KDTree.h:234
KDTree.h:235
KDTree.h:236
KDTree.h:237
KDTree.h:238
KDTree.h:239
KDTree.h:240
KDTree.h:241
KDTree.h:242
KDTree.h:243
KDTree.h:244
KDTree.h:245
KDTree.h:246
KDTree.h:247
KDTree.h:248
KDTree.h:249
KDTree.h:250
KDTree.h:251
KDTree.h:252
KDTree.h:253
KDTree.h:254
KDTree.h:255
KDTree.h:256
KDTree.h:257
KDTree.h:258
KDTree.h:259
KDTree.h:260
KDTree.h:261
KDTree.h:262
KDTree.h:263
KDTree.h:264
KDTree.h:265
KDTree.h:266
KDTree.h:267
KDTree.h:268
KDTree.h:269
KDTree.h:270
KDTree.h:271
KDTree.h:272
KDTree.h:273
KDTree.h:274
KDTree.h:275
KDTree.h:276
KDTree.h:277
KDTree.h:278
KDTree.h:279
KDTree.h:280
KDTree.h:281
KDTree.h:282
KDTree.h:283
KDTree.h:284
KDTree.h:285
KDTree.h:286
KDTree.h:287
KDTree.h:288
KDTree.h:289
KDTree.h:290
KDTree.h:291
KDTree.h:292
KDTree.h:293
KDTree.h:294
KDTree.h:295
KDTree.h:296
KDTree.h:297
KDTree.h:298
KDTree.h:299
KDTree.h:300
KDTree.h:301
KDTree.h:302
KDTree.h:303
KDTree.h:304
KDTree.h:305
KDTree.h:306
KDTree.h:307
KDTree.h:308
KDTree.h:309
KDTree.h:310
KDTree.h:311
KDTree.h:312
KDTree.h:313
KDTree.h:314
KDTree.h:315
KDTree.h:316
KDTree.h:317
KDTree.h:318
KDTree.h:319
KDTree.h:320
KDTree.h:321
KDTree.h:322
KDTree.h:323
KDTree.h:324
KDTree.h:325
KDTree.h:326
KDTree.h:327
KDTree.h:328
KDTree.h:329
KDTree.h:330
KDTree.h:331
KDTree.h:332
KDTree.h:333
KDTree.h:334
KDTree.h:335
KDTree.h:336
KDTree.h:337
KDTree.h:338
KDTree.h:339
KDTree.h:340
KDTree.h:341
KDTree.h:342
KDTree.h:343
KDTree.h:344
KDTree.h:345
KDTree.h:346
KDTree.h:347
KDTree.h:348
KDTree.h:349
KDTree.h:350
KDTree.h:351
KDTree.h:352
KDTree.h:353
KDTree.h:354
KDTree.h:355
KDTree.h:356
KDTree.h:357
KDTree.h:358
KDTree.h:359
KDTree.h:360
KDTree.h:361
KDTree.h:362
KDTree.h:363
KDTree.h:364
KDTree.h:365
KDTree.h:366
KDTree.h:367
KDTree.h:368
KDTree.h:369
KDTree.h:370
KDTree.h:371
KDTree.h:372
KDTree.h:373
KDTree.h:374
KDTree.h:375