]>
Commit | Line | Data |
---|---|---|
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 | |
316a7f5a | 10 | |
f2040a8f | 11 | template <typename Index, typename Value> class TKDTree : public TObject |
12 | { | |
13 | public: | |
316a7f5a | 14 | |
42b4cfde | 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 | |
f2040a8f | 87 | }; |
88 | ||
89 | ||
90 | typedef TKDTree<Int_t, Double_t> TKDTreeID; | |
91 | typedef TKDTree<Int_t, Float_t> TKDTreeIF; | |
92 | ||
42b4cfde | 93 | // Test functions: |
94 | TKDTreeIF * TKDTreeTestBuild(); | |
95 | ||
96 | ||
97 | ||
f2040a8f | 98 | //_________________________________________________________________ |
316a7f5a | 99 | template <typename Index, typename Value> |
100 | void TKDTree<Index, Value>::FindBNodeA(Value *point, Value *delta, Int_t &inode){ | |
f2040a8f | 101 | // |
102 | // find the smallest node covering the full range - start | |
103 | // | |
104 | inode =0; | |
105 | for (;inode<fNnodes;){ | |
117c62ab | 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; | |
f2040a8f | 108 | } |
109 | } | |
110 | ||
316a7f5a | 111 | //_________________________________________________________________ |
112 | template <typename Index, typename Value> | |
113 | Value* TKDTree<Index, Value>::GetBoundaries() | |
114 | { | |
6460b5e8 | 115 | // Get the boundaries |
316a7f5a | 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 | { | |
6460b5e8 | 124 | // Get a boundary |
316a7f5a | 125 | if(!fBoundaries) MakeBoundaries(); |
126 | return &fBoundaries[node*2*fNDim]; | |
127 | } | |
128 | ||
f2040a8f | 129 | #endif |
130 |