]>
Commit | Line | Data |
---|---|---|
4e1f33ca | 1 | //-*- Mode: C++ -*- |
2 | // $Id$ | |
3 | #ifndef ALIHLTINDEXGRID_H | |
4 | #define ALIHLTINDEXGRID_H | |
5 | //* This file is property of and copyright by the ALICE HLT Project * | |
6 | //* ALICE Experiment at CERN, All rights reserved. * | |
7 | //* See cxx source for full Copyright notice * | |
8 | ||
9 | /// @file AliHLTIndexGrid.h | |
10 | /// @author Matthias Richter | |
11 | /// @date 2011-08-14 | |
12 | /// @brief Index grid for 3 dimensional coordinates | |
13 | /// | |
14 | ||
15 | #include "AliHLTDataTypes.h" | |
16 | #include <iostream> | |
17 | #include <iomanip> | |
18 | #include <memory> | |
dc14c1f3 | 19 | #include <cerrno> |
5291de29 | 20 | #include <cmath> |
4e1f33ca | 21 | |
22 | template <typename T, typename V> | |
23 | class AliHLTIndexGrid { | |
24 | public: | |
25 | AliHLTIndexGrid(T maxX, T stepX, | |
26 | T maxY, T stepY, | |
27 | T maxZ, T stepZ, | |
28 | int initialDataSize=-1) | |
29 | : fMaxX(maxX) | |
30 | , fStepX(stepX) | |
31 | , fMaxY(maxY) | |
32 | , fStepY(stepY) | |
33 | , fMaxZ(maxZ) | |
34 | , fStepZ(stepZ) | |
35 | , fDimX(0) | |
36 | , fDimY(0) | |
37 | , fDimZ(0) | |
38 | , fCells(NULL) | |
39 | , fCellDimension(0) | |
40 | , fData(NULL) | |
41 | , fDataDimension(initialDataSize) | |
42 | , fCount(0) | |
43 | , fIterator() | |
44 | , fIteratorEnd() | |
45 | { | |
46 | // constructor | |
47 | if (fMaxX>0. && fMaxY>0. && fMaxZ>0 && | |
48 | fStepX>0. && fStepY>0. && fStepZ>0) { | |
49 | fDimX=(int)ceil(fMaxX/fStepX); | |
50 | fDimY=(int)ceil(fMaxY/fStepY); | |
51 | fDimZ=(int)ceil(fMaxZ/fStepZ); | |
52 | ||
53 | fCellDimension=fDimX*fDimY*fDimZ; | |
54 | fCells=new AliHLTIndexGridCell[fCellDimension]; | |
55 | if (fDataDimension<0) fDataDimension=fgkDefaultDataSize; | |
050a3338 | 56 | fData=new V[fDataDimension]; |
4e1f33ca | 57 | Clear(); |
58 | } | |
59 | } | |
60 | ||
61 | virtual ~AliHLTIndexGrid() { | |
62 | // destructor | |
63 | if (fData) delete [] fData; | |
64 | if (fCells) delete [] fCells; | |
65 | } | |
66 | ||
67 | // for now array of spacepoint ids | |
68 | typedef V ValueType; | |
69 | ||
70 | int GetDimensionX() const {return fDimX;} | |
71 | int GetDimensionY() const {return fDimY;} | |
72 | int GetDimensionZ() const {return fDimZ;} | |
73 | int GetXIndex(T x) const { | |
74 | if (x>fMaxX) return fDimX-1; | |
75 | if (x<0) return 0; | |
76 | return (int)(x/fStepX); | |
77 | } | |
78 | int GetYIndex(T y) const { | |
79 | if (y>fMaxY) return fDimY-1; | |
80 | if (y<0) return 0; | |
81 | return (int)(y/fStepY); | |
82 | } | |
83 | int GetZIndex(T z) const { | |
84 | if (z>fMaxZ) return fDimZ-1; | |
85 | if (z<0) return 0; | |
86 | return (int)(z/fStepZ); | |
87 | } | |
7131282c | 88 | int Index(int xindex, int yindex, int zindex) { |
89 | return xindex*fDimY*fDimZ + yindex*fDimZ + zindex; | |
90 | } | |
4e1f33ca | 91 | T GetLowerBoundX(int cell) const { |
b270a4e3 | 92 | if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0; |
4e1f33ca | 93 | int index=cell/(fDimY*fDimZ); |
94 | return index*fStepX; | |
95 | } | |
7131282c | 96 | T GetCenterX(int cell) const { |
b270a4e3 | 97 | if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0; |
7131282c | 98 | return GetLowerBoundX(cell)+fStepX/2; |
99 | } | |
4e1f33ca | 100 | T GetLowerBoundY(int cell) const { |
b270a4e3 | 101 | if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0; |
4e1f33ca | 102 | int index=cell%(fDimY*fDimZ); index/=fDimZ; |
103 | return index*fStepY; | |
104 | } | |
7131282c | 105 | T GetCenterY(int cell) const { |
b270a4e3 | 106 | if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0; |
7131282c | 107 | return GetLowerBoundY(cell)+fStepY/2; |
108 | } | |
4e1f33ca | 109 | T GetLowerBoundZ(int cell) const { |
b270a4e3 | 110 | if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0; |
4e1f33ca | 111 | int index=cell%(fDimY*fDimZ); index%=fDimZ; |
112 | return index*fStepZ; | |
113 | } | |
7131282c | 114 | T GetCenterZ(int cell) const { |
b270a4e3 | 115 | if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0; |
7131282c | 116 | return GetLowerBoundZ(cell)+fStepZ/2; |
117 | } | |
4e1f33ca | 118 | int GetCellIndex(T x, T y, T z) const { |
119 | return GetXIndex(x)*fDimY*fDimZ + (y<0?0:GetYIndex(y))*fDimZ + (z<0?0:GetZIndex(z)); | |
120 | } | |
7131282c | 121 | int GetNumberOfSpacePoints(int index=0, int endIndex=-1) const { |
4e1f33ca | 122 | if (!fCells) return 0; |
7131282c | 123 | if (endIndex<0) endIndex=fCellDimension; |
4e1f33ca | 124 | int count=0; |
125 | for (int cell=index; cell<endIndex && cell<fCellDimension && count<fCount; cell++) if (fCells[cell].fCount>0) count+=fCells[cell].fCount; | |
126 | return count; | |
127 | } | |
128 | ||
129 | // increment counter of the cell where the spacepoint is | |
130 | int CountSpacePoint(T x, T y, T z) { | |
131 | // increment counter of the cell where the spacepoint is | |
132 | int cell=GetCellIndex(x, y, z); | |
133 | if (cell<0 || !fCells || cell>=fCellDimension) return -EFAULT; | |
134 | if (fCells[cell].fCount<0) fCells[cell].fCount=1; | |
135 | else fCells[cell].fCount++; | |
136 | return 0; | |
137 | } | |
138 | ||
139 | ||
140 | // add spacepoint, all spacepoints must have been counted before | |
141 | int AddSpacePoint(ValueType t, T x, T y, T z) { | |
142 | // add spacepoint, all spacepoints must have been counted before | |
143 | int cell=GetCellIndex(x, y, z); | |
144 | if (cell<0 || !fCells || cell>=fCellDimension) return -EFAULT; | |
145 | if (fCells[cell].fFilled==fCells[cell].fCount) return -ENOSPC; | |
146 | if (fCells[cell].fStartIndex<0 && IndexCells()<0) return -EACCES; | |
147 | int offset=fCells[cell].fStartIndex+fCells[cell].fFilled; | |
148 | fData[offset]=t; | |
149 | fCells[cell].fFilled++; | |
150 | fCount++; | |
151 | return 0; | |
152 | } | |
153 | ||
154 | void Clear(const char* /*option*/="") { | |
155 | // clear internal data | |
156 | if (fCells) memset(fCells, 0xff, fCellDimension*sizeof(AliHLTIndexGridCell)); | |
050a3338 | 157 | if (fData) memset(fData, 0, fDataDimension*sizeof(V)); |
4e1f33ca | 158 | fCount=0; |
159 | } | |
160 | ||
161 | void Print(const char* /*option*/="") { | |
162 | // print info | |
163 | bool bPrintEmpty=false; | |
7131282c | 164 | ios::fmtflags coutflags=cout.flags(); // backup cout status flags |
165 | cout << "AliHLTIndexGrid: " << (fCells?fCellDimension:0) << " cells" << endl; | |
166 | cout << " x: " << fDimX << " [0," << fMaxX << "]" << endl; | |
167 | cout << " y: " << fDimY << " [0," << fMaxY << "]" << endl; | |
168 | cout << " z: " << fDimZ << " [0," << fMaxZ << "]" << endl; | |
169 | cout << " " << GetNumberOfSpacePoints(0, fCellDimension) << " point(s)" << endl; | |
4e1f33ca | 170 | if (fCells) { |
171 | for (int i=0; i<fCellDimension; i++) { | |
172 | if (!bPrintEmpty && fCells[i].fCount<=0) continue; | |
7131282c | 173 | cout << " " << setfill(' ') << setw(7) << fixed << setprecision(0) << i << " (" |
a7a49f77 | 174 | << " " << setw(3) << GetLowerBoundX(i) |
175 | << " " << setw(3) << GetLowerBoundY(i) | |
176 | << " " << setw(4) << GetLowerBoundZ(i) | |
177 | << "): "; | |
7131282c | 178 | cout << setw(3) << fCells[i].fCount << " entries, " << setw(3) << fCells[i].fFilled << " filled"; |
179 | cout << " start index " << setw(5) << fCells[i].fStartIndex; | |
180 | cout << endl; | |
4e1f33ca | 181 | if (fCells[i].fCount>0) { |
7131282c | 182 | cout << " "; |
4e1f33ca | 183 | for (iterator id=begin(GetLowerBoundX(i), GetLowerBoundY(i), GetLowerBoundZ(i)); |
184 | id!=end(); id++) { | |
7131282c | 185 | cout << " 0x" << hex << setw(8) << setfill('0') << id.Data(); |
4e1f33ca | 186 | } |
7131282c | 187 | cout << endl; |
4e1f33ca | 188 | } |
189 | } | |
190 | } | |
7131282c | 191 | cout.flags(coutflags); // restore the original flags |
4e1f33ca | 192 | } |
193 | ||
194 | ||
195 | class iterator { | |
196 | public: | |
197 | iterator() | |
198 | : fData(NULL) {} | |
a7a49f77 | 199 | iterator(ValueType* pData) |
4e1f33ca | 200 | : fData(pData) {} |
201 | iterator(const iterator& i) | |
202 | : fData(i.fData) {} | |
203 | iterator& operator=(const iterator& i) | |
a9877bd0 | 204 | { if (this!=&i) {fData=i.fData;} return *this;} |
4e1f33ca | 205 | ~iterator() {fData=NULL;} |
206 | ||
207 | bool operator==(const iterator& i) const {return (fData!=NULL) && (fData==i.fData);} | |
208 | bool operator!=(const iterator& i) const {return (fData!=NULL) && (fData!=i.fData);} | |
209 | // prefix operators | |
210 | iterator& operator++() {fData++; return *this;} | |
211 | iterator& operator--() {fData--; return *this;} | |
212 | // postfix operators | |
213 | iterator operator++(int) {iterator i(*this); fData++; return i;} | |
214 | iterator operator--(int) {iterator i(*this); fData--; return i;} | |
215 | ||
216 | iterator& operator+=(int step) {fData+=step; return *this;} | |
217 | ||
218 | const ValueType& Data() const {return *fData;} | |
a7a49f77 | 219 | ValueType& Data() {return *fData;} |
4e1f33ca | 220 | |
dc14c1f3 | 221 | ValueType operator*() {return *fData;} |
222 | ||
4e1f33ca | 223 | protected: |
224 | private: | |
a7a49f77 | 225 | ValueType* fData; //! data |
4e1f33ca | 226 | }; |
227 | ||
228 | // prepare iterator and end marker | |
229 | iterator& begin(T x=(T)-1, T y=(T)-1, T z=(T)-1) { | |
230 | fIterator.~iterator(); | |
231 | fIteratorEnd.~iterator(); | |
232 | ||
233 | int startIndex=0; | |
234 | if (x<0) { | |
235 | // get all data | |
236 | if (fData) { | |
237 | new (&fIterator) iterator(fData); | |
238 | fIteratorEnd=fIterator; | |
239 | fIteratorEnd+=fCount; | |
240 | } | |
241 | return fIterator; | |
242 | } | |
243 | ||
244 | // only search for the start index if specific x selected | |
245 | int cell=GetCellIndex(x, y, z); | |
246 | if (cell<0 || !fCells || cell>=fCellDimension) return fIterator; | |
247 | // get the index of the cell | |
248 | startIndex=fCells[cell].fStartIndex; | |
7131282c | 249 | if (!fData || startIndex>=fDataDimension) return fIterator; |
4e1f33ca | 250 | |
251 | // get the range end position | |
252 | int endCell=cell+1; | |
253 | if (x<0) endCell=fCellDimension; | |
b270a4e3 | 254 | else if (y<0) endCell=GetCellIndex(x+fStepX, (T)-1, (T)-1); // all entries for fixed x |
255 | else if (z<0) endCell=GetCellIndex(x, y+fStepY, (T)-1); // all entries for fixed x and y | |
4e1f33ca | 256 | if (endCell<=cell) { |
257 | // cell index returned is never outside the array | |
258 | // so this is a special case where we get to the bounds of the array | |
259 | endCell=fCellDimension; | |
260 | } | |
261 | ||
7131282c | 262 | // find the first cell with content in the range |
263 | for (; startIndex<0 && cell<endCell;) { | |
264 | startIndex=fCells[++cell].fStartIndex; | |
265 | } | |
266 | if (startIndex<0) return fIterator; | |
267 | ||
4e1f33ca | 268 | new (&fIterator) iterator(fData+startIndex); |
269 | fIteratorEnd=fIterator; | |
270 | fIteratorEnd+=GetNumberOfSpacePoints(cell, endCell); | |
271 | return fIterator; | |
272 | } | |
273 | ||
274 | // get loop end marker | |
275 | iterator& end() { | |
276 | return fIteratorEnd; | |
277 | } | |
278 | ||
7131282c | 279 | iterator& find(ValueType v) { |
280 | for (iterator i=begin(); i!=end(); i++) { | |
281 | if (i.Data()==v) { | |
282 | fIterator=i; | |
283 | return fIterator; | |
284 | } | |
285 | } | |
286 | return end(); | |
287 | } | |
288 | ||
289 | // find cell of entry | |
290 | int FindCell(ValueType v) const { | |
291 | if (!fCells) return -1; | |
292 | for (int cell=0; cell<fCellDimension; cell++) | |
293 | for (int count=0; count<fCells[cell].fCount; count++) | |
294 | if (fData[fCells[cell].fStartIndex+count]==v) | |
295 | return cell; | |
296 | return -1; | |
297 | } | |
298 | ||
4e1f33ca | 299 | struct AliHLTIndexGridCell { |
300 | int fCount; | |
301 | int fFilled; | |
302 | int fStartIndex; | |
303 | }; | |
304 | ||
305 | protected: | |
306 | private: | |
307 | // standard constructor prohibited | |
308 | AliHLTIndexGrid(); | |
309 | // copy constructor prohibited | |
310 | AliHLTIndexGrid(const AliHLTIndexGrid&); | |
311 | // assignment operator prohibited | |
312 | AliHLTIndexGrid& operator=(const AliHLTIndexGrid&); | |
313 | ||
314 | int IndexCells() { | |
315 | // set the start index for data of every cell based on the counts | |
316 | if (!fCells || fCellDimension<=0) return -ENOBUFS; | |
317 | int offset=0; | |
318 | int cell=0; | |
319 | for (; cell<fCellDimension; cell++) { | |
320 | if (fCells[cell].fCount<0) continue; | |
321 | fCells[cell].fStartIndex=offset; | |
322 | offset+=fCells[cell].fCount; | |
323 | fCells[cell].fFilled=0; | |
324 | } | |
325 | ||
326 | if (offset>fDataDimension) { | |
327 | // grow the data array | |
050a3338 | 328 | auto_ptr<V> newArray(new V[offset]); |
4e1f33ca | 329 | if (newArray.get()) { |
330 | memcpy(newArray.get(), fData, fDataDimension); | |
050a3338 | 331 | memset(newArray.get()+fDataDimension, 0, (offset-fDataDimension)*sizeof(V)); |
4e1f33ca | 332 | delete fData; |
333 | fData=newArray.release(); | |
334 | fDataDimension=offset; | |
335 | } else { | |
336 | for (cell=0; cell<fCellDimension; cell++) { | |
337 | fCells[cell].fStartIndex=-1; | |
338 | } | |
339 | } | |
340 | } | |
341 | return 0; | |
342 | } | |
343 | ||
344 | ||
345 | T fMaxX; | |
346 | T fStepX; | |
347 | T fMaxY; | |
348 | T fStepY; | |
349 | T fMaxZ; | |
350 | T fStepZ; | |
351 | ||
352 | int fDimX; | |
353 | int fDimY; | |
354 | int fDimZ; | |
355 | ||
356 | AliHLTIndexGridCell* fCells; //! cell array | |
357 | int fCellDimension; //! size of cell array | |
358 | ValueType* fData; //! spacepoint data | |
359 | int fDataDimension; //! size of spacepoint data | |
360 | int fCount; | |
361 | ||
362 | iterator fIterator; //! iterator | |
363 | iterator fIteratorEnd; //! end marker iterator | |
364 | ||
365 | static const int fgkDefaultDataSize=10000; //! the default data size | |
366 | ||
367 | ClassDef(AliHLTIndexGrid, 0) | |
368 | }; | |
369 | ||
370 | #endif |