db1b182ab92356d5f2a04ab54fd18014380c4c23
[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
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;
54       fData=new V[fDataDimension];
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   }
86   int Index(int xindex, int yindex, int zindex) {
87     return xindex*fDimY*fDimZ + yindex*fDimZ + zindex;
88   }
89   T GetLowerBoundX(int cell) const {
90     if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0;
91     int index=cell/(fDimY*fDimZ);
92     return index*fStepX;
93   }
94   T GetCenterX(int cell) const {
95     if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0;
96     return GetLowerBoundX(cell)+fStepX/2;
97   }
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;
101     return index*fStepY;
102   }
103   T GetCenterY(int cell) const {
104     if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0;
105     return GetLowerBoundY(cell)+fStepY/2;
106   }
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;
110     return index*fStepZ;
111   }
112   T GetCenterZ(int cell) const {
113     if (fDimX==0 || fDimY==0 ||fDimZ==0) return (T)0;
114     return GetLowerBoundZ(cell)+fStepZ/2;
115   }
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   }
119   int GetNumberOfSpacePoints(int index=0, int endIndex=-1) const {
120     if (!fCells) return 0;
121     if (endIndex<0) endIndex=fCellDimension;
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));
155     if (fData) memset(fData, 0, fDataDimension*sizeof(V));
156     fCount=0;
157   }
158
159   void Print(const char* /*option*/="") {
160   // print info
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;
168   if (fCells) {
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)
175           << "): ";
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;
179       if (fCells[i].fCount>0) {
180         cout << "          ";
181         for (iterator id=begin(GetLowerBoundX(i), GetLowerBoundY(i), GetLowerBoundZ(i));
182              id!=end(); id++) {
183           cout << " 0x" << hex << setw(8) << setfill('0') << id.Data();
184         }
185         cout  << endl;
186       }
187     }
188   }
189   cout.flags(coutflags); // restore the original flags
190 }
191
192
193   class iterator {
194   public:
195   iterator()
196     : fData(NULL) {}
197   iterator(ValueType* pData)
198     : fData(pData) {}
199   iterator(const iterator& i)
200     : fData(i.fData) {}
201     iterator& operator=(const iterator& i)
202       { if (this!=&i) {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;}
217     ValueType& Data() {return *fData;}
218
219   protected:
220   private:
221     ValueType* fData; //! data
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;
245     if (!fData || startIndex>=fDataDimension) return fIterator;
246
247     // get the range end position
248     int endCell=cell+1;
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
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
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
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
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
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
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));
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