Line data Source code
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 : #include <cerrno>
20 : #include <cmath>
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 0 : : fMaxX(maxX)
30 0 : , fStepX(stepX)
31 0 : , fMaxY(maxY)
32 0 : , fStepY(stepY)
33 0 : , fMaxZ(maxZ)
34 0 : , fStepZ(stepZ)
35 0 : , fDimX(0)
36 0 : , fDimY(0)
37 0 : , fDimZ(0)
38 0 : , fCells(NULL)
39 0 : , fCellDimension(0)
40 0 : , fData(NULL)
41 0 : , fDataDimension(initialDataSize)
42 0 : , fCount(0)
43 0 : , fIterator()
44 0 : , fIteratorEnd()
45 0 : {
46 : // constructor
47 0 : if (fMaxX>0. && fMaxY>0. && fMaxZ>0 &&
48 0 : fStepX>0. && fStepY>0. && fStepZ>0) {
49 0 : fDimX=(int)ceil(fMaxX/fStepX);
50 0 : fDimY=(int)ceil(fMaxY/fStepY);
51 0 : fDimZ=(int)ceil(fMaxZ/fStepZ);
52 :
53 0 : fCellDimension=fDimX*fDimY*fDimZ;
54 0 : fCells=new AliHLTIndexGridCell[fCellDimension];
55 0 : if (fDataDimension<0) fDataDimension=fgkDefaultDataSize;
56 0 : fData=new V[fDataDimension];
57 0 : Clear();
58 0 : }
59 0 : }
60 :
61 0 : virtual ~AliHLTIndexGrid() {
62 : // destructor
63 0 : if (fData) delete [] fData;
64 0 : if (fCells) delete [] fCells;
65 0 : }
66 :
67 : // for now array of spacepoint ids
68 : typedef V ValueType;
69 :
70 0 : int GetDimensionX() const {return fDimX;}
71 0 : int GetDimensionY() const {return fDimY;}
72 0 : int GetDimensionZ() const {return fDimZ;}
73 : int GetXIndex(T x) const {
74 0 : if (x>fMaxX) return fDimX-1;
75 0 : if (x<0) return 0;
76 0 : return (int)(x/fStepX);
77 0 : }
78 : int GetYIndex(T y) const {
79 0 : if (y>fMaxY) return fDimY-1;
80 0 : if (y<0) return 0;
81 0 : return (int)(y/fStepY);
82 0 : }
83 : int GetZIndex(T z) const {
84 0 : if (z>fMaxZ) return fDimZ-1;
85 0 : if (z<0) return 0;
86 0 : return (int)(z/fStepZ);
87 0 : }
88 : int Index(int xindex, int yindex, int zindex) {
89 0 : return xindex*fDimY*fDimZ + yindex*fDimZ + zindex;
90 : }
91 : T GetLowerBoundX(int cell) const {
92 0 : if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0;
93 0 : int index=cell/(fDimY*fDimZ);
94 0 : return index*fStepX;
95 0 : }
96 : T GetCenterX(int cell) const {
97 0 : if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0;
98 0 : return GetLowerBoundX(cell)+fStepX/2;
99 0 : }
100 : T GetLowerBoundY(int cell) const {
101 0 : if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0;
102 0 : int index=cell%(fDimY*fDimZ); index/=fDimZ;
103 0 : return index*fStepY;
104 0 : }
105 : T GetCenterY(int cell) const {
106 0 : if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0;
107 0 : return GetLowerBoundY(cell)+fStepY/2;
108 0 : }
109 : T GetLowerBoundZ(int cell) const {
110 0 : if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0;
111 0 : int index=cell%(fDimY*fDimZ); index%=fDimZ;
112 0 : return index*fStepZ;
113 0 : }
114 : T GetCenterZ(int cell) const {
115 0 : if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0;
116 0 : return GetLowerBoundZ(cell)+fStepZ/2;
117 0 : }
118 : int GetCellIndex(T x, T y, T z) const {
119 0 : return GetXIndex(x)*fDimY*fDimZ + (y<0?0:GetYIndex(y))*fDimZ + (z<0?0:GetZIndex(z));
120 : }
121 : int GetNumberOfSpacePoints(int index=0, int endIndex=-1) const {
122 0 : if (!fCells) return 0;
123 0 : if (endIndex<0) endIndex=fCellDimension;
124 : int count=0;
125 0 : for (int cell=index; cell<endIndex && cell<fCellDimension && count<fCount; cell++) if (fCells[cell].fCount>0) count+=fCells[cell].fCount;
126 : return count;
127 0 : }
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 0 : int cell=GetCellIndex(x, y, z);
133 0 : if (cell<0 || !fCells || cell>=fCellDimension) return -EFAULT;
134 0 : if (fCells[cell].fCount<0) fCells[cell].fCount=1;
135 0 : else fCells[cell].fCount++;
136 0 : return 0;
137 0 : }
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 0 : int cell=GetCellIndex(x, y, z);
144 0 : if (cell<0 || !fCells || cell>=fCellDimension) return -EFAULT;
145 0 : if (fCells[cell].fFilled==fCells[cell].fCount) return -ENOSPC;
146 0 : if (fCells[cell].fStartIndex<0 && IndexCells()<0) return -EACCES;
147 0 : int offset=fCells[cell].fStartIndex+fCells[cell].fFilled;
148 0 : fData[offset]=t;
149 0 : fCells[cell].fFilled++;
150 0 : fCount++;
151 : return 0;
152 0 : }
153 :
154 : void Clear(const char* /*option*/="") {
155 : // clear internal data
156 0 : if (fCells) memset(fCells, 0xff, fCellDimension*sizeof(AliHLTIndexGridCell));
157 0 : if (fData) memset(fData, 0, fDataDimension*sizeof(V));
158 0 : fCount=0;
159 0 : }
160 :
161 : void Print(const char* /*option*/="") {
162 : // print info
163 : bool bPrintEmpty=false;
164 0 : ios::fmtflags coutflags=cout.flags(); // backup cout status flags
165 0 : cout << "AliHLTIndexGrid: " << (fCells?fCellDimension:0) << " cells" << endl;
166 0 : cout << " x: " << fDimX << " [0," << fMaxX << "]" << endl;
167 0 : cout << " y: " << fDimY << " [0," << fMaxY << "]" << endl;
168 0 : cout << " z: " << fDimZ << " [0," << fMaxZ << "]" << endl;
169 0 : cout << " " << GetNumberOfSpacePoints(0, fCellDimension) << " point(s)" << endl;
170 0 : if (fCells) {
171 0 : for (int i=0; i<fCellDimension; i++) {
172 0 : if (!bPrintEmpty && fCells[i].fCount<=0) continue;
173 0 : cout << " " << setfill(' ') << setw(7) << fixed << setprecision(0) << i << " ("
174 0 : << " " << setw(3) << GetLowerBoundX(i)
175 0 : << " " << setw(3) << GetLowerBoundY(i)
176 0 : << " " << setw(4) << GetLowerBoundZ(i)
177 0 : << "): ";
178 0 : cout << setw(3) << fCells[i].fCount << " entries, " << setw(3) << fCells[i].fFilled << " filled";
179 0 : cout << " start index " << setw(5) << fCells[i].fStartIndex;
180 0 : cout << endl;
181 0 : if (fCells[i].fCount>0) {
182 0 : cout << " ";
183 0 : for (iterator id=begin(GetLowerBoundX(i), GetLowerBoundY(i), GetLowerBoundZ(i));
184 0 : id!=end(); id++) {
185 0 : cout << " 0x" << hex << setw(8) << setfill('0') << id.Data();
186 : }
187 0 : cout << endl;
188 0 : }
189 : }
190 0 : }
191 0 : cout.flags(coutflags); // restore the original flags
192 0 : }
193 :
194 :
195 : class iterator {
196 : public:
197 : iterator()
198 0 : : fData(NULL) {}
199 : iterator(ValueType* pData)
200 0 : : fData(pData) {}
201 : iterator(const iterator& i)
202 0 : : fData(i.fData) {}
203 : iterator& operator=(const iterator& i)
204 0 : { if (this!=&i) {fData=i.fData;} return *this;}
205 0 : ~iterator() {fData=NULL;}
206 :
207 : bool operator==(const iterator& i) const {return (fData!=NULL) && (fData==i.fData);}
208 0 : 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 0 : iterator operator++(int) {iterator i(*this); fData++; return i;}
214 : iterator operator--(int) {iterator i(*this); fData--; return i;}
215 :
216 0 : iterator& operator+=(int step) {fData+=step; return *this;}
217 :
218 : const ValueType& Data() const {return *fData;}
219 0 : ValueType& Data() {return *fData;}
220 :
221 : ValueType operator*() {return *fData;}
222 :
223 : protected:
224 : private:
225 : ValueType* fData; //! data
226 : };
227 :
228 : // prepare iterator and end marker
229 : iterator& begin(T x=(T)-1, T y=(T)-1, T z=(T)-1) {
230 0 : fIterator.~iterator();
231 0 : fIteratorEnd.~iterator();
232 :
233 : int startIndex=0;
234 0 : if (x<0) {
235 : // get all data
236 0 : if (fData) {
237 0 : new (&fIterator) iterator(fData);
238 0 : fIteratorEnd=fIterator;
239 0 : fIteratorEnd+=fCount;
240 0 : }
241 0 : return fIterator;
242 : }
243 :
244 : // only search for the start index if specific x selected
245 0 : int cell=GetCellIndex(x, y, z);
246 0 : if (cell<0 || !fCells || cell>=fCellDimension) return fIterator;
247 : // get the index of the cell
248 0 : startIndex=fCells[cell].fStartIndex;
249 0 : if (!fData || startIndex>=fDataDimension) return fIterator;
250 :
251 : // get the range end position
252 0 : int endCell=cell+1;
253 0 : if (x<0) endCell=fCellDimension;
254 0 : else if (y<0) endCell=GetCellIndex(x+fStepX, (T)-1, (T)-1); // all entries for fixed x
255 0 : else if (z<0) endCell=GetCellIndex(x, y+fStepY, (T)-1); // all entries for fixed x and y
256 0 : 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 0 : endCell=fCellDimension;
260 0 : }
261 :
262 : // find the first cell with content in the range
263 0 : for (; startIndex<0 && cell<endCell;) {
264 0 : startIndex=fCells[++cell].fStartIndex;
265 : }
266 0 : if (startIndex<0) return fIterator;
267 :
268 0 : new (&fIterator) iterator(fData+startIndex);
269 0 : fIteratorEnd=fIterator;
270 0 : fIteratorEnd+=GetNumberOfSpacePoints(cell, endCell);
271 0 : return fIterator;
272 0 : }
273 :
274 : // get loop end marker
275 : iterator& end() {
276 0 : return fIteratorEnd;
277 : }
278 :
279 : iterator& find(ValueType v) {
280 0 : for (iterator i=begin(); i!=end(); i++) {
281 0 : if (i.Data()==v) {
282 0 : fIterator=i;
283 0 : return fIterator;
284 : }
285 : }
286 0 : return end();
287 0 : }
288 :
289 : // find cell of entry
290 : int FindCell(ValueType v) const {
291 0 : if (!fCells) return -1;
292 0 : for (int cell=0; cell<fCellDimension; cell++)
293 0 : for (int count=0; count<fCells[cell].fCount; count++)
294 0 : if (fData[fCells[cell].fStartIndex+count]==v)
295 0 : return cell;
296 0 : return -1;
297 0 : }
298 :
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 0 : if (!fCells || fCellDimension<=0) return -ENOBUFS;
317 : int offset=0;
318 : int cell=0;
319 0 : for (; cell<fCellDimension; cell++) {
320 0 : if (fCells[cell].fCount<0) continue;
321 0 : fCells[cell].fStartIndex=offset;
322 0 : offset+=fCells[cell].fCount;
323 0 : fCells[cell].fFilled=0;
324 0 : }
325 :
326 0 : if (offset>fDataDimension) {
327 : // grow the data array
328 0 : auto_ptr<V> newArray(new V[offset]);
329 0 : if (newArray.get()) {
330 0 : memcpy(newArray.get(), fData, fDataDimension);
331 0 : memset(newArray.get()+fDataDimension, 0, (offset-fDataDimension)*sizeof(V));
332 0 : delete fData;
333 0 : fData=newArray.release();
334 0 : fDataDimension=offset;
335 0 : } else {
336 0 : for (cell=0; cell<fCellDimension; cell++) {
337 0 : fCells[cell].fStartIndex=-1;
338 : }
339 : }
340 0 : }
341 : return 0;
342 0 : }
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 378 : ClassDef(AliHLTIndexGrid, 0)
368 : };
369 :
370 : #endif
|
