Preliminary files for CMake
[u/mrichter/AliRoot.git] / 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
11 template <typename Index, typename Value> class TKDTree : public TObject
12 {
13 public:
14         
15   TKDTree();
16   TKDTree(Index npoints, Index ndim, UInt_t bsize, Value **data);
17   ~TKDTree();
18   // Get indexes of left and right daughter nodes
19   Int_t GetLeft(Int_t inode)  const    {return inode*2+1;}
20   Int_t GetRight(Int_t inode) const    {return (inode+1)*2;}
21   Int_t GetParent(Int_t inode) const  {return inode/2;}
22   //  
23   // getters
24   Index*  GetPointsIndexes(Int_t node) const {
25     if(node < fNnodes) return 0x0;
26     Int_t offset = (node >= fCrossNode) ? (node-fCrossNode)*fBucketSize : fOffset+(node-fNnodes)*fBucketSize;
27     return &fIndPoints[offset];
28   }
29   UChar_t GetNodeAxis(Int_t id) const {return (id < 0 || id >= fNnodes) ? 0 : fAxis[id];}
30   Value   GetNodeValue(Int_t id) const {return (id < 0 || id >= fNnodes) ? 0 : fValue[id];}
31   Int_t   GetNNodes() const {return fNnodes;}
32   Value*  GetBoundaries();
33   Value*  GetBoundary(const Int_t node);
34   static  Int_t   GetIndex(Int_t row, Int_t collumn){return collumn+(1<<row);}
35   static 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);};
36   Bool_t  FindNearestNeighbors(const Value *point, const Int_t kNN, Index *&i, Value *&d);
37   Index   FindNode(const Value * point);
38   void    FindPoint(Value * point, Index &index, Int_t &iter);
39   void    FindInRangeA(Value * point, Value * delta, Index *res , Index &npoints,Index & iter, Int_t bnode);
40   void    FindInRangeB(Value * point, Value * delta, Index *res , Index &npoints,Index & iter, Int_t bnode);
41   void    FindBNodeA(Value * point, Value * delta, Int_t &inode);
42   Bool_t  IsTerminal(Index inode) const {return (inode>=fNnodes);}
43   Value   KOrdStat(Index ntotal, Value *a, Index k, Index *index) const;
44   void    MakeBoundaries(Value *range = 0x0);
45   void    SetData(Index npoints, Index ndim, UInt_t bsize, Value **data);
46   void    Spread(Index ntotal, Value *a, Index *index, Value &min, Value &max) const;
47   
48
49  protected:
50   void            Build();  // build tree
51   
52  private:
53   TKDTree(const TKDTree &); // not implemented
54   TKDTree<Index, Value>& operator=(const TKDTree<Index, Value>&); // not implemented
55   void            CookBoundaries(const Int_t node, Bool_t left);
56   
57   
58  protected:
59   Bool_t  fDataOwner;  //! Toggle ownership of the data
60   Int_t   fNnodes;     // size of node array
61   Index   fNDim;       // number of dimensions
62   Index   fNDimm;      // dummy 2*fNDim
63   Index   fNpoints;    // number of multidimensional points
64   Index   fBucketSize; // limit statistic for nodes 
65   UChar_t *fAxis;      //[fNnodes] nodes cutting axis
66   Value   *fValue;     //[fNnodes] nodes cutting value
67   //
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 // Test functions:
94 TKDTreeIF *  TKDTreeTestBuild();
95
96
97
98 //_________________________________________________________________
99 template <typename  Index, typename Value>
100 void TKDTree<Index, Value>::FindBNodeA(Value *point, Value *delta, Int_t &inode){
101   //
102   // find the smallest node covering the full range - start
103   //
104   inode =0; 
105   for (;inode<fNnodes;){
106     if (TMath::Abs(point[fAxis[inode]] - fValue[inode])<delta[fAxis[inode]]) break;
107     inode = (point[fAxis[inode]] < fValue[inode]) ? (inode*2)+1: (inode*2)+2;
108   }
109 }
110
111 //_________________________________________________________________
112 template <typename  Index, typename Value>
113 Value* TKDTree<Index, Value>::GetBoundaries()
114 {
115   // Get the boundaries
116         if(!fBoundaries) MakeBoundaries();
117         return fBoundaries;
118 }
119
120 //_________________________________________________________________
121 template <typename  Index, typename Value>
122 Value* TKDTree<Index, Value>::GetBoundary(const Int_t node)
123 {
124   // Get a boundary
125         if(!fBoundaries) MakeBoundaries();
126         return &fBoundaries[node*2*fNDim];
127 }
128
129 #endif
130