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