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