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