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 *
9 /// @file AliHLTIndexGrid.h
10 /// @author Matthias Richter
12 /// @brief Index grid for 3 dimensional coordinates
15 #include "AliHLTDataTypes.h"
20 template <typename T, typename V>
21 class AliHLTIndexGrid {
23 AliHLTIndexGrid(T maxX, T stepX,
26 int initialDataSize=-1)
39 , fDataDimension(initialDataSize)
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);
51 fCellDimension=fDimX*fDimY*fDimZ;
52 fCells=new AliHLTIndexGridCell[fCellDimension];
53 if (fDataDimension<0) fDataDimension=fgkDefaultDataSize;
54 fData=new V[fDataDimension];
59 virtual ~AliHLTIndexGrid() {
61 if (fData) delete [] fData;
62 if (fCells) delete [] fCells;
65 // for now array of spacepoint ids
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;
74 return (int)(x/fStepX);
76 int GetYIndex(T y) const {
77 if (y>fMaxY) return fDimY-1;
79 return (int)(y/fStepY);
81 int GetZIndex(T z) const {
82 if (z>fMaxZ) return fDimZ-1;
84 return (int)(z/fStepZ);
86 int Index(int xindex, int yindex, int zindex) {
87 return xindex*fDimY*fDimZ + yindex*fDimZ + zindex;
89 T GetLowerBoundX(int cell) const {
90 if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0;
91 int index=cell/(fDimY*fDimZ);
94 T GetCenterX(int cell) const {
95 if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0;
96 return GetLowerBoundX(cell)+fStepX/2;
98 T GetLowerBoundY(int cell) const {
99 if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0;
100 int index=cell%(fDimY*fDimZ); index/=fDimZ;
103 T GetCenterY(int cell) const {
104 if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0;
105 return GetLowerBoundY(cell)+fStepY/2;
107 T GetLowerBoundZ(int cell) const {
108 if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0;
109 int index=cell%(fDimY*fDimZ); index%=fDimZ;
112 T GetCenterZ(int cell) const {
113 if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0;
114 return GetLowerBoundZ(cell)+fStepZ/2;
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));
119 int GetNumberOfSpacePoints(int index=0, int endIndex=-1) const {
120 if (!fCells) return 0;
121 if (endIndex<0) endIndex=fCellDimension;
123 for (int cell=index; cell<endIndex && cell<fCellDimension && count<fCount; cell++) if (fCells[cell].fCount>0) count+=fCells[cell].fCount;
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++;
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;
147 fCells[cell].fFilled++;
152 void Clear(const char* /*option*/="") {
153 // clear internal data
154 if (fCells) memset(fCells, 0xff, fCellDimension*sizeof(AliHLTIndexGridCell));
155 if (fData) memset(fData, 0, fDataDimension*sizeof(V));
159 void Print(const char* /*option*/="") {
161 bool bPrintEmpty=false;
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;
169 for (int i=0; i<fCellDimension; i++) {
170 if (!bPrintEmpty && fCells[i].fCount<=0) continue;
171 cout << " " << setfill(' ') << setw(7) << fixed << setprecision(0) << i << " ("
172 << " " << setw(3) << GetLowerBoundX(i)
173 << " " << setw(3) << GetLowerBoundY(i)
174 << " " << setw(4) << GetLowerBoundZ(i)
176 cout << setw(3) << fCells[i].fCount << " entries, " << setw(3) << fCells[i].fFilled << " filled";
177 cout << " start index " << setw(5) << fCells[i].fStartIndex;
179 if (fCells[i].fCount>0) {
181 for (iterator id=begin(GetLowerBoundX(i), GetLowerBoundY(i), GetLowerBoundZ(i));
183 cout << " 0x" << hex << setw(8) << setfill('0') << id.Data();
189 cout.flags(coutflags); // restore the original flags
197 iterator(ValueType* pData)
199 iterator(const iterator& i)
201 iterator& operator=(const iterator& i)
202 { fData=i.fData; return *this;}
203 ~iterator() {fData=NULL;}
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);}
208 iterator& operator++() {fData++; return *this;}
209 iterator& operator--() {fData--; return *this;}
211 iterator operator++(int) {iterator i(*this); fData++; return i;}
212 iterator operator--(int) {iterator i(*this); fData--; return i;}
214 iterator& operator+=(int step) {fData+=step; return *this;}
216 const ValueType& Data() const {return *fData;}
217 ValueType& Data() {return *fData;}
221 ValueType* fData; //! data
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();
233 new (&fIterator) iterator(fData);
234 fIteratorEnd=fIterator;
235 fIteratorEnd+=fCount;
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;
245 if (!fData || startIndex>=fDataDimension) return fIterator;
247 // get the range end position
249 if (x<0) endCell=fCellDimension;
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
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;
258 // find the first cell with content in the range
259 for (; startIndex<0 && cell<endCell;) {
260 startIndex=fCells[++cell].fStartIndex;
262 if (startIndex<0) return fIterator;
264 new (&fIterator) iterator(fData+startIndex);
265 fIteratorEnd=fIterator;
266 fIteratorEnd+=GetNumberOfSpacePoints(cell, endCell);
270 // get loop end marker
275 iterator& find(ValueType v) {
276 for (iterator i=begin(); i!=end(); i++) {
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)
295 struct AliHLTIndexGridCell {
303 // standard constructor prohibited
305 // copy constructor prohibited
306 AliHLTIndexGrid(const AliHLTIndexGrid&);
307 // assignment operator prohibited
308 AliHLTIndexGrid& operator=(const AliHLTIndexGrid&);
311 // set the start index for data of every cell based on the counts
312 if (!fCells || fCellDimension<=0) return -ENOBUFS;
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;
322 if (offset>fDataDimension) {
323 // grow the data array
324 auto_ptr<V> newArray(new V[offset]);
325 if (newArray.get()) {
326 memcpy(newArray.get(), fData, fDataDimension);
327 memset(newArray.get()+fDataDimension, 0, (offset-fDataDimension)*sizeof(V));
329 fData=newArray.release();
330 fDataDimension=offset;
332 for (cell=0; cell<fCellDimension; cell++) {
333 fCells[cell].fStartIndex=-1;
352 AliHLTIndexGridCell* fCells; //! cell array
353 int fCellDimension; //! size of cell array
354 ValueType* fData; //! spacepoint data
355 int fDataDimension; //! size of spacepoint data
358 iterator fIterator; //! iterator
359 iterator fIteratorEnd; //! end marker iterator
361 static const int fgkDefaultDataSize=10000; //! the default data size
363 ClassDef(AliHLTIndexGrid, 0)