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