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 <sstream>
  18 #include <iomanip>
  19 #include <memory>
  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   T GetLowerBoundX(int cell) const {
  88     if (fDimX==0 || fDimY==0 ||fDimZ==0) return 0.;
  89     int index=cell/(fDimY*fDimZ);
  90     return index*fStepX;
  91   }
  92   T GetLowerBoundY(int cell) const {
  93     if (fDimX==0 || fDimY==0 ||fDimZ==0) return 0.;
  94     int index=cell%(fDimY*fDimZ); index/=fDimZ;
  95     return index*fStepY;
  96   }
  97   T GetLowerBoundZ(int cell) const {
  98     if (fDimX==0 || fDimY==0 ||fDimZ==0) return 0.;
  99     int index=cell%(fDimY*fDimZ); index%=fDimZ;
 100     return index*fStepZ;
 101   }
 102   int GetCellIndex(T x, T y, T z) const {
 103     return GetXIndex(x)*fDimY*fDimZ + (y<0?0:GetYIndex(y))*fDimZ + (z<0?0:GetZIndex(z));
 104   }
 105   int GetNumberOfSpacePoints(int index, int endIndex) const {
 106     if (!fCells) return 0;
 107     int count=0;
 108     for (int cell=index; cell<endIndex && cell<fCellDimension && count<fCount; cell++) if (fCells[cell].fCount>0) count+=fCells[cell].fCount;
 109     return count;
 110   }
 111
 112   // increment counter of the cell where the spacepoint is
 113   int CountSpacePoint(T x, T y, T z) {
 114     // increment counter of the cell where the spacepoint is
 115     int cell=GetCellIndex(x, y, z);
 116     if (cell<0 || !fCells || cell>=fCellDimension) return -EFAULT;
 117     if (fCells[cell].fCount<0) fCells[cell].fCount=1;
 118     else fCells[cell].fCount++;
 119     return 0;
 120   }
 121
 122
 123   // add spacepoint, all spacepoints must have been counted before
 124   int AddSpacePoint(ValueType t, T x, T y, T z) {
 125     // add spacepoint, all spacepoints must have been counted before
 126     int cell=GetCellIndex(x, y, z);
 127     if (cell<0 || !fCells || cell>=fCellDimension) return -EFAULT;
 128     if (fCells[cell].fFilled==fCells[cell].fCount) return -ENOSPC;
 129     if (fCells[cell].fStartIndex<0 && IndexCells()<0) return -EACCES;
 130     int offset=fCells[cell].fStartIndex+fCells[cell].fFilled;
 131     fData[offset]=t;
 132     fCells[cell].fFilled++;
 133     fCount++;
 134     return 0;
 135   }
 136
 137   void Clear(const char* /*option*/="") {
 138     // clear internal data
 139     if (fCells) memset(fCells, 0xff, fCellDimension*sizeof(AliHLTIndexGridCell));
 140     if (fData) memset(fData, 0, fDataDimension*sizeof(V));
 141     fCount=0;
 142   }
 143
 144   void Print(const char* /*option*/="") {
 145   // print info
 146   bool bPrintEmpty=false;
 147   std::stringstream str;
 148   str << "AliHLTIndexGrid: " << (fCells?fCellDimension:0) << " cells" << endl;
 149   str << "   x: " << fDimX << " [0," << fMaxX << "]" << endl;
 150   str << "   y: " << fDimY << " [0," << fMaxY << "]" << endl;
 151   str << "   z: " << fDimZ << " [0," << fMaxZ << "]" << endl;
 152   str << "   " << GetNumberOfSpacePoints(0, fCellDimension) << " point(s)" << endl;
 153   if (fCells) {
 154     for (int i=0; i<fCellDimension; i++) {
 155       if (!bPrintEmpty && fCells[i].fCount<=0) continue;
 156       str << "     " << setfill(' ') << setw(7) << setprecision(0) << i << " ("
 157           << " " << setw(3) << GetLowerBoundX(i)
 158           << " " << setw(3) << GetLowerBoundY(i)
 159           << " " << setw(4) << GetLowerBoundZ(i)
 160           << "): ";
 161       str << setw(3) << fCells[i].fCount << " entries, " << setw(3) << fCells[i].fFilled << " filled";
 162       str << "  start index " << setw(5) << fCells[i].fStartIndex;
 163       str << endl;
 164       if (fCells[i].fCount>0) {
 165         str << "          ";
 166         for (iterator id=begin(GetLowerBoundX(i), GetLowerBoundY(i), GetLowerBoundZ(i));
 167              id!=end(); id++) {
 168           str << " 0x" << hex << setw(8) << setfill('0') << id.Data();
 169         }
 170         str  << dec << endl;
 171       }
 172     }
 173   }
 174   cout << str;
 175 }
 176
 177
 178   class iterator {
 179   public:
 180   iterator()
 181     : fData(NULL) {}
 182   iterator(ValueType* pData)
 183     : fData(pData) {}
 184   iterator(const iterator& i)
 185     : fData(i.fData) {}
 186     iterator& operator=(const iterator& i)
 187       { fData=i.fData; return *this;}
 188     ~iterator() {fData=NULL;}
 189
 190     bool operator==(const iterator& i) const  {return (fData!=NULL) && (fData==i.fData);}
 191     bool operator!=(const iterator& i) const  {return (fData!=NULL) && (fData!=i.fData);}
 192     // prefix operators
 193     iterator& operator++() {fData++; return *this;}
 194     iterator& operator--() {fData--; return *this;}
 195     // postfix operators
 196     iterator operator++(int) {iterator i(*this); fData++; return i;}
 197     iterator operator--(int) {iterator i(*this); fData--; return i;}
 198
 199     iterator& operator+=(int step) {fData+=step; return *this;}
 200
 201     const ValueType& Data() const {return *fData;}
 202     ValueType& Data() {return *fData;}
 203
 204   protected:
 205   private:
 206     ValueType* fData; //! data
 207   };
 208
 209   // prepare iterator and end marker
 210   iterator& begin(T x=(T)-1, T y=(T)-1, T z=(T)-1) {
 211     fIterator.~iterator();
 212     fIteratorEnd.~iterator();
 213
 214     int startIndex=0;
 215     if (x<0) {
 216       // get all data
 217       if (fData) {
 218         new (&fIterator) iterator(fData);
 219         fIteratorEnd=fIterator;
 220         fIteratorEnd+=fCount;
 221       }
 222       return fIterator;
 223     }
 224
 225     // only search for the start index if specific x selected
 226     int cell=GetCellIndex(x, y, z);
 227     if (cell<0 || !fCells || cell>=fCellDimension) return fIterator;
 228     // get the index of the cell
 229     startIndex=fCells[cell].fStartIndex;
 230     if (startIndex<0 || !fData || startIndex>=fDataDimension) return fIterator;
 231
 232     // get the range end position
 233     int endCell=cell+1;
 234     if (x<0) endCell=fCellDimension;
 235     else if (y<0) endCell=GetCellIndex(x+fStepX, -1., -1.); // all entries for fixed x
 236     else if (z<0) endCell=GetCellIndex(x, y+fStepY, -1.); // all entries for fixed x and y
 237     if (endCell<=cell) {
 238       // cell index returned is never outside the array
 239       // so this is a special case where we get to the bounds of the array
 240       endCell=fCellDimension;
 241     }
 242
 243     new (&fIterator) iterator(fData+startIndex);
 244     fIteratorEnd=fIterator;
 245     fIteratorEnd+=GetNumberOfSpacePoints(cell, endCell);
 246     return fIterator;
 247   }
 248
 249   // get loop end marker
 250   iterator& end() {
 251     return fIteratorEnd;
 252   }
 253
 254   struct AliHLTIndexGridCell {
 255     int fCount;
 256     int fFilled;
 257     int fStartIndex;
 258   };
 259
 260  protected:
 261  private:
 262   // standard constructor prohibited
 263   AliHLTIndexGrid();
 264   // copy constructor prohibited
 265   AliHLTIndexGrid(const AliHLTIndexGrid&);
 266   // assignment operator prohibited
 267   AliHLTIndexGrid& operator=(const AliHLTIndexGrid&);
 268
 269   int IndexCells() {
 270     // set the start index for data of every cell based on the counts
 271     if (!fCells || fCellDimension<=0) return -ENOBUFS;
 272     int offset=0;
 273     int cell=0;
 274     for (; cell<fCellDimension; cell++) {
 275       if (fCells[cell].fCount<0) continue;
 276       fCells[cell].fStartIndex=offset;
 277       offset+=fCells[cell].fCount;
 278       fCells[cell].fFilled=0;
 279     }
 280
 281     if (offset>fDataDimension) {
 282       // grow the data array
 283       auto_ptr<V> newArray(new V[offset]);
 284       if (newArray.get()) {
 285         memcpy(newArray.get(), fData, fDataDimension);
 286         memset(newArray.get()+fDataDimension, 0, (offset-fDataDimension)*sizeof(V));
 287         delete fData;
 288         fData=newArray.release();
 289         fDataDimension=offset;
 290       } else {
 291         for (cell=0; cell<fCellDimension; cell++) {
 292           fCells[cell].fStartIndex=-1;
 293         }
 294       }
 295     }
 296     return 0;
 297   }
 298
 299
 300   T fMaxX;
 301   T fStepX;
 302   T fMaxY;
 303   T fStepY;
 304   T fMaxZ;
 305   T fStepZ;
 306
 307   int fDimX;
 308   int fDimY;
 309   int fDimZ;
 310
 311   AliHLTIndexGridCell* fCells; //! cell array
 312   int fCellDimension; //! size of cell array
 313   ValueType* fData; //! spacepoint data
 314   int fDataDimension; //! size of spacepoint data
 315   int fCount;
 316
 317   iterator fIterator; //! iterator
 318   iterator fIteratorEnd; //! end marker iterator
 319
 320   static const int fgkDefaultDataSize=10000; //! the default data size
 321
 322   ClassDef(AliHLTIndexGrid, 0)
 323 };
 324
 325 #endif