ALIROOT-5600 - skip non-participating detector modules
[u/mrichter/AliRoot.git] / HLT / BASE / AliHLTIndexGrid.h
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     : 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;
56       fData=new V[fDataDimension];
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   }
88   int Index(int xindex, int yindex, int zindex) {
89     return xindex*fDimY*fDimZ + yindex*fDimZ + zindex;
90   }
91   T GetLowerBoundX(int cell) const {
92     if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0;
93     int index=cell/(fDimY*fDimZ);
94     return index*fStepX;
95   }
96   T GetCenterX(int cell) const {
97     if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0;
98     return GetLowerBoundX(cell)+fStepX/2;
99   }
100   T GetLowerBoundY(int cell) const {
101     if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0;
102     int index=cell%(fDimY*fDimZ); index/=fDimZ;
103     return index*fStepY;
104   }
105   T GetCenterY(int cell) const {
106     if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0;
107     return GetLowerBoundY(cell)+fStepY/2;
108   }
109   T GetLowerBoundZ(int cell) const {
110     if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0;
111     int index=cell%(fDimY*fDimZ); index%=fDimZ;
112     return index*fStepZ;
113   }
114   T GetCenterZ(int cell) const {
115     if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0;
116     return GetLowerBoundZ(cell)+fStepZ/2;
117   }
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   }
121   int GetNumberOfSpacePoints(int index=0, int endIndex=-1) const {
122     if (!fCells) return 0;
123     if (endIndex<0) endIndex=fCellDimension;
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));
157     if (fData) memset(fData, 0, fDataDimension*sizeof(V));
158     fCount=0;
159   }
160
161   void Print(const char* /*option*/="") {
162   // print info
163   bool bPrintEmpty=false;
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;
170   if (fCells) {
171     for (int i=0; i<fCellDimension; i++) {
172       if (!bPrintEmpty && fCells[i].fCount<=0) continue;
173       cout << "     " << setfill(' ') << setw(7) << fixed << setprecision(0) << i << " (" 
174           << " " << setw(3) << GetLowerBoundX(i)
175           << " " << setw(3) << GetLowerBoundY(i)
176           << " " << setw(4) << GetLowerBoundZ(i)
177           << "): ";
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;
181       if (fCells[i].fCount>0) {
182         cout << "          ";
183         for (iterator id=begin(GetLowerBoundX(i), GetLowerBoundY(i), GetLowerBoundZ(i));
184              id!=end(); id++) {
185           cout << " 0x" << hex << setw(8) << setfill('0') << id.Data();
186         }
187         cout  << endl;
188       }
189     }
190   }
191   cout.flags(coutflags); // restore the original flags
192 }
193
194
195   class iterator {
196   public:
197   iterator()
198     : fData(NULL) {}
199   iterator(ValueType* pData)
200     : fData(pData) {}
201   iterator(const iterator& i)
202     : fData(i.fData) {}
203     iterator& operator=(const iterator& i)
204       { if (this!=&i) {fData=i.fData;} return *this;}
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;}
219     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     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;
249     if (!fData || startIndex>=fDataDimension) return fIterator;
250
251     // get the range end position
252     int endCell=cell+1;
253     if (x<0) endCell=fCellDimension;
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
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
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
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
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
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
328       auto_ptr<V> newArray(new V[offset]);
329       if (newArray.get()) {
330         memcpy(newArray.get(), fData, fDataDimension);
331         memset(newArray.get()+fDataDimension, 0, (offset-fDataDimension)*sizeof(V));
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