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