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