STAT/TKDTree.h

   1 #ifndef ROOT_TKDTree
   2 #define ROOT_TKDTree
   3
   4 #ifndef ROOT_TObject
   5 #include "TObject.h"
   6 #endif
   7
   8 #include "TMath.h"
   9
  10 Int_t memory();
  11
  12
  13 template <typename Index, typename Value> class TKDTree : public TObject
  14 {
  15 public:
  16         enum{
  17                 kDimMax = 6
  18         };
  19
  20         TKDTree();
  21         TKDTree(Index npoints, Index ndim, UInt_t bsize, Value **data);
  22         ~TKDTree();
  23
  24         // getters
  25         inline  Index*  GetPointsIndexes(Int_t node) const {
  26                 if(node < fNnodes) return 0x0;
  27                 Int_t offset = (node >= fCrossNode) ? (node-fCrossNode)*fBucketSize : fOffset+(node-fNnodes)*fBucketSize;
  28                 return &fIndPoints[offset];
  29         }
  30         inline UChar_t GetNodeAxis(Int_t id) const {return (id < 0 || id >= fNnodes) ? 0 : fAxis[id];}
  31         inline Value   GetNodeValue(Int_t id) const {return (id < 0 || id >= fNnodes) ? 0 : fValue[id];}
  32         inline Int_t   GetNNodes() const {return fNnodes;}
  33         inline Int_t   GetNTNodes() const {return fNpoints/fBucketSize + ((fNpoints%fBucketSize)?1:0);}
  34         inline Value*  GetBoundaries();
  35         inline Value*  GetBoundary(const Int_t node);
  36         static  Int_t   GetIndex(Int_t row, Int_t collumn){return collumn+(1<<row);}
  37         static inline void GetCoord(Int_t index, Int_t &row, Int_t &collumn){for (row=0; index>=(16<<row);row+=4); for (; index>=(2<<row);row++);collumn= index-(1<<row);};
  38                 Bool_t  FindNearestNeighbors(const Value *point, const Int_t kNN, Index *&i, Value *&d);
  39                 Index   FindNode(const Value * point);
  40                 void    FindPoint(Value * point, Index &index, Int_t &iter);
  41                 void    FindInRangeA(Value * point, Value * delta, Index *res , Index &npoints,Index & iter, Int_t bnode);
  42                 void    FindInRangeB(Value * point, Value * delta, Index *res , Index &npoints,Index & iter, Int_t bnode);
  43         inline void    FindBNodeA(Value * point, Value * delta, Int_t &inode);
  44         inline Bool_t  IsTerminal(Index inode){return (inode>=fNnodes);}
  45         Value           KOrdStat(Index ntotal, Value *a, Index k, Index *index);
  46         void            MakeBoundaries(Value *range = 0x0);
  47         void            SetData(Index npoints, Index ndim, UInt_t bsize, Value **data);
  48         void            Spread(Index ntotal, Value *a, Index *index, Value &min, Value &max);
  49
  50 protected:
  51         void            Build();  // build tree
  52
  53 private:
  54         TKDTree(const TKDTree &); // not implemented
  55         TKDTree<Index, Value>& operator=(const TKDTree<Index, Value>&); // not implemented
  56         void            CookBoundaries(const Int_t node, Bool_t left);
  57
  58
  59 protected:
  60         Bool_t  kDataOwner;  //! Toggle ownership of the data
  61         Int_t   fNnodes;     // size of node array
  62         Index   fNDim;       // number of dimensions
  63         Index   fNDimm;      // dummy 2*fNDim
  64         Index   fNpoints;    // number of multidimensional points
  65         Index   fBucketSize; // limit statistic for nodes
  66         UChar_t *fAxis;      //[fNnodes] nodes cutting axis
  67         Value   *fValue;     //[fNnodes] nodes cutting value
  68         Value           *fRange;     //[fNDimm] range of data for each dimension
  69         Value   **fData;     //! data points
  70         Value           *fBoundaries;//! nodes boundaries - check class doc
  71
  72 // kNN related data
  73 protected:
  74         Int_t   fkNNdim;     //! current kNN arrays allocated dimension
  75         Index   *fkNN;       //! k nearest neighbors indexes
  76         Value   *fkNNdist;   //! k nearest neighbors distances
  77         Value   *fDistBuffer;//! working space for kNN
  78         Index   *fIndBuffer; //! working space for kNN
  79
  80 private:
  81         Index   *fIndPoints; //! array of points indexes
  82         Int_t   fRowT0;      //! smallest terminal row
  83         Int_t   fCrossNode;  //! cross node
  84         Int_t   fOffset;     //! offset in fIndPoints
  85
  86         ClassDef(TKDTree, 1)  // KD tree
  87 };
  88
  89
  90 typedef TKDTree<Int_t, Double_t> TKDTreeID;
  91 typedef TKDTree<Int_t, Float_t> TKDTreeIF;
  92
  93 //_________________________________________________________________
  94 template <typename  Index, typename Value>
  95 void TKDTree<Index, Value>::FindBNodeA(Value *point, Value *delta, Int_t &inode){
  96   //
  97   // find the smallest node covering the full range - start
  98   //
  99   inode =0;
 100   for (;inode<fNnodes;){
 101     if (TMath::Abs(point[fAxis[inode]] - fValue[inode])<delta[fAxis[inode]]) break;
 102     inode = (point[fAxis[inode]] < fValue[inode]) ? (inode*2)+1: (inode*2)+2;
 103   }
 104 }
 105
 106 //_________________________________________________________________
 107 template <typename  Index, typename Value>
 108 Value* TKDTree<Index, Value>::GetBoundaries()
 109 {
 110         if(!fBoundaries) MakeBoundaries();
 111         return fBoundaries;
 112 }
 113
 114 //_________________________________________________________________
 115 template <typename  Index, typename Value>
 116 Value* TKDTree<Index, Value>::GetBoundary(const Int_t node)
 117 {
 118         if(!fBoundaries) MakeBoundaries();
 119         return &fBoundaries[node*2*fNDim];
 120 }
 121
 122 #endif
 123