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       { 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