Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 10:10:18 

0001 // @(#)root/mathcore:$Id$
0002 // Authors: C. Gumpert    09/2011
0003 /**********************************************************************
0004  *                                                                    *
0005  * Copyright (c) 2011 , LCG ROOT MathLib Team                         *
0006  *                                                                    *
0007  *                                                                    *
0008  **********************************************************************/
0009 //
0010 // Header file for KDTree class
0011 //
0012 
0013 
0014 #ifndef ROOT_Math_KDTree
0015 #define ROOT_Math_KDTree
0016 
0017 //STL header
0018 #include <cassert>
0019 #include <vector>
0020 #include <cmath>
0021 #include <utility>
0022 
0023 // ROOT include(s)
0024 #include "RtypesCore.h"
0025 
0026 namespace ROOT
0027 {
0028   namespace Math
0029   {
0030 
0031      //______________________________________________________________________________
0032      //Begin_Html
0033      //End_Html
0034      template<class _DataPoint>
0035      class KDTree
0036      {
0037      public:
0038 
0039         typedef _DataPoint                        point_type;
0040         typedef typename _DataPoint::value_type   value_type;
0041         static UInt_t Dimension() {return _DataPoint::Dimension();}
0042         enum eSplitOption {
0043            kEffective = 0,                         //split according to effective entries
0044            kBinContent                             //split according to bin content
0045         };
0046 
0047      private:
0048 
0049         class ComparePoints
0050         {
0051         public:
0052            Bool_t   operator()(const point_type* pFirst,const point_type* pSecond) const;
0053 
0054            UInt_t   GetAxis() const       {return fAxis;}
0055            void     SetAxis(UInt_t iAxis) {fAxis = iAxis;}
0056 
0057         private:
0058            UInt_t   fAxis; //axis at which the points are compared
0059         };
0060 
0061         class Cut
0062         {
0063         public:
0064            Cut():fAxis(0),fCutValue(0) {}
0065            Cut(UInt_t iAxis,Double_t fNewCutValue):fAxis(iAxis),fCutValue(fNewCutValue) {}
0066            ~Cut() {}
0067 
0068            UInt_t       GetAxis() const                   {return fAxis;}
0069            value_type   GetCutValue() const               {return fCutValue;}
0070            void         SetAxis(UInt_t iAxis)             {fAxis = iAxis;}
0071            void         SetCutValue(Double_t fNewCutValue) {fCutValue = fNewCutValue;}
0072 
0073            Bool_t       operator<(const point_type& rPoint) const;
0074            Bool_t       operator>(const point_type& rPoint) const;
0075 
0076         private:
0077            UInt_t    fAxis;       //axis at which the splitting is done
0078            Double_t  fCutValue;   //split value
0079         };
0080 
0081         //forward declarations
0082         class BaseNode;
0083         class HeadNode;
0084         class SplitNode;
0085         class BinNode;
0086         class TerminalNode;
0087 
0088         class BaseNode
0089         {
0090         public:
0091            //constructor and destructor
0092            BaseNode(BaseNode* pParent = 0);
0093            virtual ~BaseNode();
0094 
0095            //providing usual functionality of a tree
0096            virtual BaseNode*        Clone() = 0;
0097            virtual const BinNode*   FindNode(const point_type& rPoint) const = 0;
0098            virtual void             GetClosestPoints(const point_type& rRef,UInt_t nPoints,std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const = 0;
0099            virtual void             GetPointsWithinDist(const point_type& rRef,value_type fDist,std::vector<const point_type*>& vFoundPoints) const = 0;
0100            virtual Bool_t           Insert(const point_type& rPoint) = 0;
0101            virtual void             Print(int iRow = 0) const = 0;
0102 
0103            //navigating the tree
0104            BaseNode*&                LeftChild()        {return fLeftChild;}
0105            const BaseNode*           LeftChild() const  {return fLeftChild;}
0106            BaseNode*&                Parent()           {return fParent;}
0107            const BaseNode*           Parent() const     {return fParent;}
0108            BaseNode*&                RightChild()       {return fRightChild;}
0109            const BaseNode*           RightChild() const {return fRightChild;}
0110 
0111            //information about relative position of current node
0112            BaseNode*&                GetParentPointer();
0113            virtual Bool_t            IsHeadNode() const {return false;}
0114            Bool_t                    IsLeftChild() const;
0115 
0116         private:
0117            // node should never be copied or assigned
0118            BaseNode(const BaseNode& ) {}
0119            BaseNode& operator=(const BaseNode& ) {return *this;}
0120 
0121            //links to adjacent nodes
0122            BaseNode*                 fParent;     //!pointer to parent node
0123            BaseNode*                 fLeftChild;  //!pointer to left child
0124            BaseNode*                 fRightChild; //!pointer to right child
0125         };
0126 
0127         class HeadNode : public BaseNode
0128         {
0129         public:
0130            //constructor and destructor
0131            HeadNode(BaseNode& rNode):BaseNode(&rNode) {}
0132            virtual ~HeadNode() {delete Parent();}
0133 
0134            //delegate everything to the actual root node of the tree
0135            virtual const BinNode*   FindNode(const point_type& rPoint) const {return Parent()->FindNode(rPoint);}
0136            virtual void             GetClosestPoints(const point_type& rRef,UInt_t nPoints,std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const;
0137            virtual void             GetPointsWithinDist(const point_type& rRef,value_type fDist,std::vector<const _DataPoint*>& vFoundPoints) const;
0138            virtual Bool_t           Insert(const point_type& rPoint) {return Parent()->Insert(rPoint);}
0139            virtual void             Print(Int_t) const {Parent()->Print();}
0140 
0141         private:
0142            // node should never be copied
0143            HeadNode(const HeadNode& ) {}
0144            HeadNode& operator=(const HeadNode& ) {return *this;}
0145 
0146            virtual HeadNode*        Clone();
0147            virtual bool             IsHeadNode() const {return true;}
0148 
0149            // only delegate everything else is private and should not be used
0150            using BaseNode::Parent;
0151            using BaseNode::LeftChild;
0152            using BaseNode::RightChild;
0153 
0154            using BaseNode::GetParentPointer;
0155            using BaseNode::IsLeftChild;
0156         };
0157 
0158         class SplitNode : public BaseNode
0159         {
0160         public:
0161            // constructors and destructors
0162            SplitNode(UInt_t iAxis,Double_t fCutValue,BaseNode& rLeft,BaseNode& rRight,BaseNode* pParent = 0);
0163            virtual ~SplitNode();
0164 
0165            //accessing information about this split node
0166            const Cut*               GetCut() const {return fCut;}
0167            virtual void             Print(Int_t iRow = 0) const;
0168 
0169         private:
0170            // node should never be copied
0171            SplitNode(const SplitNode& ) {}
0172            SplitNode& operator=(const SplitNode& ) {return *this;}
0173 
0174            virtual SplitNode*       Clone();
0175            virtual const BinNode*   FindNode(const point_type& rPoint) const;
0176            virtual void             GetClosestPoints(const point_type& rRef,UInt_t nPoints,std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const;
0177            virtual void             GetPointsWithinDist(const point_type& rRef,value_type fDist,std::vector<const _DataPoint*>& vFoundPoints) const;
0178            virtual Bool_t           Insert(const point_type& rPoint);
0179 
0180            const Cut*               fCut;     //pointer to cut object owned by this node
0181         };
0182 
0183         class BinNode : public BaseNode
0184         {
0185         protected:
0186            //save some typing
0187            typedef std::pair<value_type,value_type> tBoundary;
0188         public:
0189            // constructors and destructors
0190            BinNode(BaseNode* pParent = 0);
0191            BinNode(const BinNode& copy);
0192            virtual ~BinNode() {}
0193 
0194            // usual bin operations
0195            virtual void                            EmptyBin();
0196            virtual const BinNode*                  FindNode(const point_type& rPoint) const;
0197            point_type                              GetBinCenter() const;
0198            Double_t                                GetBinContent() const {return GetSumw();}
0199 #ifndef _AIX
0200            virtual const std::vector<tBoundary>&   GetBoundaries() const {return fBoundaries;}
0201 #else
0202            virtual void GetBoundaries() const { }
0203 #endif
0204            Double_t                                GetDensity() const {return GetBinContent()/GetVolume();}
0205            Double_t                                GetEffectiveEntries() const {return (GetSumw2()) ? std::pow(GetSumw(),2)/GetSumw2() : 0;}
0206            UInt_t                                  GetEntries() const {return fEntries;}
0207            Double_t                                GetVolume() const;
0208            Double_t                                GetSumw() const {return fSumw;}
0209            Double_t                                GetSumw2() const {return fSumw2;}
0210            virtual Bool_t                          Insert(const point_type& rPoint);
0211            Bool_t                                  IsInBin(const point_type& rPoint) const;
0212            virtual void                            Print(int iRow = 0) const;
0213 
0214         protected:
0215            virtual BinNode*                        Clone();
0216 
0217            // intrinsic bin properties
0218            std::vector<tBoundary>                  fBoundaries;    ///< bin boundaries
0219            Double_t                                fSumw;          ///< sum of weights
0220            Double_t                                fSumw2;         ///< sum of weights^2
0221            UInt_t                                  fEntries;       ///< number of entries
0222 
0223         private:
0224            BinNode& operator=(const BinNode& rhs);
0225 
0226            // bin does not contain any point like information
0227            virtual void                    GetClosestPoints(const point_type&,UInt_t,std::vector<std::pair<const _DataPoint*,Double_t> >&) const {}
0228            virtual void                    GetPointsWithinDist(const point_type&,value_type,std::vector<const point_type*>&) const {}
0229 
0230            // a bin does not have children
0231            using BaseNode::LeftChild;
0232            using BaseNode::RightChild;
0233         };
0234 
0235         class TerminalNode : public BinNode
0236         {
0237            friend class KDTree<_DataPoint>;
0238            //save some typing
0239            typedef std::pair<value_type,value_type> tBoundary;
0240 
0241         public:
0242            //constructor and destructor
0243            TerminalNode(Double_t iBucketSize,BaseNode* pParent = 0);
0244            virtual ~TerminalNode();
0245 
0246            virtual void                            EmptyBin();
0247 #ifndef _AIX
0248            virtual const std::vector<tBoundary>&   GetBoundaries() const;
0249 #else
0250            virtual void GetBoundaries() const;
0251 #endif
0252            virtual void                            GetClosestPoints(const point_type& rRef,UInt_t nPoints,std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const;
0253            const std::vector<const point_type*>&   GetPoints() const {return fDataPoints;}
0254            virtual void                            GetPointsWithinDist(const point_type& rRef,value_type fDist,std::vector<const _DataPoint*>& vFoundPoints) const;
0255            virtual void                            Print(int iRow = 0) const;
0256 
0257         private:
0258            // node should never be copied
0259            TerminalNode(const TerminalNode& ) {}
0260            TerminalNode& operator=(const TerminalNode& ) {return *this;}
0261 
0262            // save some typing
0263            typedef typename std::vector<const point_type* >::iterator         data_it;
0264            typedef typename std::vector<const point_type* >::const_iterator   const_data_it;
0265 
0266            // creating new Terminal Node when splitting, copying elements in the given range
0267            TerminalNode(Double_t iBucketSize,UInt_t iSplitAxis,data_it first,data_it end);
0268 
0269            //tree operations
0270            virtual BinNode*                        Clone() {return ConvertToBinNode();}
0271            BinNode*                                ConvertToBinNode();
0272            virtual const BinNode*                  FindNode(const point_type&) const {return this;}
0273            virtual Bool_t                          Insert(const point_type& rPoint);
0274            void                                    Split();
0275            void                                    SetOwner(Bool_t bIsOwner = true) {fOwnData = bIsOwner;}
0276            void                                    SetSplitOption(eSplitOption opt) {fSplitOption = opt;}
0277            data_it                                 SplitEffectiveEntries();
0278            data_it                                 SplitBinContent();
0279            void                                    UpdateBoundaries();
0280 
0281            Bool_t                                  fOwnData;       ///< terminal node owns the data objects (default = false)
0282            eSplitOption                            fSplitOption;   ///< according to which figure of merit the node is split
0283            Double_t                                fBucketSize;    ///< target number of entries per bucket
0284            UInt_t                                  fSplitAxis;     ///< axis at which the next split will occur
0285            std::vector<const _DataPoint*>          fDataPoints;    ///< data points in this bucket
0286         };
0287 
0288      public:
0289         //////////////////////////////////////////////////////////////////////
0290         //
0291         // template<class _DataPoint> class KDTree<_DataPoint>::iterator
0292         //
0293         //////////////////////////////////////////////////////////////////////
0294         typedef BinNode Bin;
0295         class iterator
0296         {
0297            friend class KDTree<_DataPoint>;
0298         public:
0299            iterator(): fBin(0) {}
0300            iterator(const iterator& copy): fBin(copy.fBin) {}
0301            ~iterator() {}
0302 
0303            iterator&         operator++();
0304            const iterator&   operator++() const;
0305            iterator          operator++(int);
0306            const iterator    operator++(int) const;
0307            iterator&         operator--();
0308            const iterator&   operator--() const;
0309            iterator          operator--(int);
0310            const iterator    operator--(int) const;
0311            bool              operator==(const iterator& rIterator) const {return (fBin == rIterator.fBin);}
0312            bool              operator!=(const iterator& rIterator) const {return !(*this == rIterator);}
0313            iterator&         operator=(const iterator& rhs);
0314            Bin&              operator*() {return *fBin;}
0315            const Bin&        operator*() const {return *fBin;}
0316            Bin*              operator->() {return fBin;}
0317            const Bin*        operator->() const {return fBin;}
0318 
0319            TerminalNode*     TN() {assert(dynamic_cast<TerminalNode*>(fBin)); return (TerminalNode*)fBin;}
0320 
0321         private:
0322            iterator(BinNode* pNode): fBin(pNode) {}
0323 
0324            Bin*     Next() const;
0325            Bin*     Previous() const;
0326 
0327            mutable Bin* fBin;
0328         };
0329 
0330         //constructor and destructor
0331         KDTree(UInt_t iBucketSize);
0332         ~KDTree();
0333 
0334         //public member functions
0335         void            EmptyBins();
0336         iterator        End();
0337         const iterator  End() const;
0338         const Bin*      FindBin(const point_type& rPoint) const {return fHead->FindNode(rPoint);}
0339         iterator        First();
0340         const iterator  First() const;
0341         void            Freeze();
0342         Double_t        GetBucketSize() const {return fBucketSize;}
0343         void            GetClosestPoints(const point_type& rRef,UInt_t nPoints,std::vector<std::pair<const _DataPoint*,Double_t> >& vFoundPoints) const;
0344         Double_t         GetEffectiveEntries() const;
0345         KDTree<_DataPoint>* GetFrozenCopy();
0346         UInt_t          GetNBins() const;
0347         UInt_t          GetEntries() const;
0348         void            GetPointsWithinDist(const point_type& rRef,value_type fDist,std::vector<const point_type*>& vFoundPoints) const;
0349         Double_t        GetTotalSumw() const;
0350         Double_t        GetTotalSumw2() const;
0351         Bool_t          Insert(const point_type& rData) {return fHead->Parent()->Insert(rData);}
0352         Bool_t          IsFrozen() const {return fIsFrozen;}
0353         iterator        Last();
0354         const iterator  Last() const;
0355         void            Print() {fHead->Parent()->Print();}
0356         void            Reset();
0357         void            SetOwner(Bool_t bIsOwner = true);
0358         void            SetSplitOption(eSplitOption opt);
0359 
0360      private:
0361         KDTree();
0362         KDTree(const KDTree<point_type>& ) {}
0363         KDTree<point_type>& operator=(const KDTree<point_type>& ) {return *this;}
0364 
0365         BaseNode*  fHead;
0366         Double_t   fBucketSize;
0367         Bool_t     fIsFrozen;
0368      };
0369 
0370 
0371   }//namespace Math
0372 }//namespace ROOT
0373 
0374 #include "Math/KDTree.icc"
0375 
0376 #endif // ROOT_Math_KDTree
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!