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