// @(#)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

//STL header
#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 HeadNode;
        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;}

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

        class HeadNode : public BaseNode
        {
        public:
           //constructor and destructor
           HeadNode(BaseNode& rNode):BaseNode(&rNode) {}
           virtual ~HeadNode() {delete Parent();}

           //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
           HeadNode(const HeadNode& ) {}
           HeadNode& operator=(const HeadNode& ) {return *this;}

           virtual HeadNode*        Clone();
           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();

           //accessing information about this split node
           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            Print() {fHead->Parent()->Print();}
        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;}

        BaseNode*  fHead;
        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