kNN algorithm improved. IO Defined
[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"
316a7f5a 9
10template <typename Index, typename Value>
11struct TKDNode{
12 Char_t fAxis;
13 Value fValue;
14
15 ClassDef(TKDNode, 1) // TKDTree node structure
16};
17
f2040a8f 18template <typename Index, typename Value> class TKDTree : public TObject
19{
20public:
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
316a7f5a 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);
f2040a8f 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);};
316a7f5a 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);
f2040a8f 54
55protected:
316a7f5a 56 void Build(); // build tree
f2040a8f 57
58private:
316a7f5a 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);
a9c20b1f 62
f2040a8f 63
64protected:
316a7f5a 65 Bool_t kDataOwner; //! Toggle ownership of the data
f2040a8f 66 Int_t fNnodes; // size of node array
316a7f5a 67 Index fNDim; // number of dimensions
68 Index fNDimm; // dummy 2*fNDim
f2040a8f 69 Index fNpoints; // number of multidimensional points
70 Index fBucketSize; // limit statistic for nodes
316a7f5a 71 TKDNode<Index, Value> *fNodes; //[fNnodes] nodes descriptors array
72 Value *fRange; //[fNDimm] range of data for each dimension
73 Value **fData; //! data points
f2040a8f 74 Value *fBoundaries;//! nodes boundaries - check class doc
f2040a8f 75
316a7f5a 76// kNN related data
77protected:
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
f2040a8f 84private:
85 Index *fIndPoints; //! array of points indexes
316a7f5a 86 Int_t fRowT0; //! smallest terminal row
87 Int_t fCrossNode; //! cross node
88 Int_t fOffset; //! offset in fIndPoints
f2040a8f 89
90 ClassDef(TKDTree, 1) // KD tree
91};
92
93
94typedef TKDTree<Int_t, Double_t> TKDTreeID;
95typedef TKDTree<Int_t, Float_t> TKDTreeIF;
96
97//_________________________________________________________________
316a7f5a 98template <typename Index, typename Value>
99void TKDTree<Index, Value>::FindBNodeA(Value *point, Value *delta, Int_t &inode){
f2040a8f 100 //
101 // find the smallest node covering the full range - start
102 //
103 inode =0;
104 for (;inode<fNnodes;){
316a7f5a 105 TKDNode<Index, Value> & node = fNodes[inode];
f2040a8f 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
316a7f5a 111//_________________________________________________________________
112template <typename Index, typename Value>
113Value* TKDTree<Index, Value>::GetBoundaries()
114{
115 if(!fBoundaries) MakeBoundaries();
116 return fBoundaries;
117}
118
119//_________________________________________________________________
120template <typename Index, typename Value>
121Value* TKDTree<Index, Value>::GetBoundary(const Int_t node)
122{
123 if(!fBoundaries) MakeBoundaries();
124 return &fBoundaries[node*2*fNDim];
125}
126
f2040a8f 127#endif
128