[u/mrichter/AliRoot.git] / HLT / BASE / AliHLTIndexGrid.h

//-*- Mode: C++ -*-
// $Id$
#ifndef ALIHLTINDEXGRID_H
#define ALIHLTINDEXGRID_H
//* This file is property of and copyright by the ALICE HLT Project        * 
//* ALICE Experiment at CERN, All rights reserved.                         *
//* See cxx source for full Copyright notice                               *

/// @file   AliHLTIndexGrid.h
/// @author Matthias Richter
/// @date   2011-08-14
/// @brief  Index grid for 3 dimensional coordinates
///

#include "AliHLTDataTypes.h"
#include <iostream>
#include <iomanip>
#include <memory>

template <typename T, typename V>
class AliHLTIndexGrid {
 public:
  AliHLTIndexGrid(T maxX, T stepX,
		  T maxY, T stepY,
		  T maxZ, T stepZ,
		  int initialDataSize=-1)
    : fMaxX(maxX)
    , fStepX(stepX)
    , fMaxY(maxY)
    , fStepY(stepY)
    , fMaxZ(maxZ)
    , fStepZ(stepZ)
    , fDimX(0)
    , fDimY(0)
    , fDimZ(0)
    , fCells(NULL)
    , fCellDimension(0)
    , fData(NULL)
    , fDataDimension(initialDataSize)
    , fCount(0)
    , fIterator()
    , fIteratorEnd()
  {
    // constructor
    if (fMaxX>0. && fMaxY>0. && fMaxZ>0 &&
	fStepX>0. && fStepY>0. && fStepZ>0) {
      fDimX=(int)ceil(fMaxX/fStepX);
      fDimY=(int)ceil(fMaxY/fStepY);
      fDimZ=(int)ceil(fMaxZ/fStepZ);

      fCellDimension=fDimX*fDimY*fDimZ;
      fCells=new AliHLTIndexGridCell[fCellDimension];
      if (fDataDimension<0) fDataDimension=fgkDefaultDataSize;
      fData=new V[fDataDimension];
      Clear();
    }
  }

  virtual ~AliHLTIndexGrid() {
    // destructor
    if (fData) delete [] fData;
    if (fCells) delete [] fCells;
  }

  // for now array of spacepoint ids
  typedef V ValueType;

  int GetDimensionX() const {return fDimX;}
  int GetDimensionY() const {return fDimY;}
  int GetDimensionZ() const {return fDimZ;}
  int GetXIndex(T x) const {
    if (x>fMaxX) return fDimX-1;
    if (x<0) return 0;
    return (int)(x/fStepX);
  }
  int GetYIndex(T y) const {
    if (y>fMaxY) return fDimY-1;
    if (y<0) return 0;
    return (int)(y/fStepY);
  }
  int GetZIndex(T z) const {
    if (z>fMaxZ) return fDimZ-1;
    if (z<0) return 0;
    return (int)(z/fStepZ);
  }
  T GetLowerBoundX(int cell) const {
    if (fDimX==0 || fDimY==0 ||fDimZ==0) return 0.;
    int index=cell/(fDimY*fDimZ);
    return index*fStepX;
  }
  T GetLowerBoundY(int cell) const {
    if (fDimX==0 || fDimY==0 ||fDimZ==0) return 0.;
    int index=cell%(fDimY*fDimZ); index/=fDimZ;
    return index*fStepY;
  }
  T GetLowerBoundZ(int cell) const {
    if (fDimX==0 || fDimY==0 ||fDimZ==0) return 0.;
    int index=cell%(fDimY*fDimZ); index%=fDimZ;
    return index*fStepZ;
  }
  int GetCellIndex(T x, T y, T z) const {
    return GetXIndex(x)*fDimY*fDimZ + (y<0?0:GetYIndex(y))*fDimZ + (z<0?0:GetZIndex(z));
  }
  int GetNumberOfSpacePoints(int index, int endIndex) const {
    if (!fCells) return 0;
    int count=0;
    for (int cell=index; cell<endIndex && cell<fCellDimension && count<fCount; cell++) if (fCells[cell].fCount>0) count+=fCells[cell].fCount;
    return count;
  }

  // increment counter of the cell where the spacepoint is
  int CountSpacePoint(T x, T y, T z) {
    // increment counter of the cell where the spacepoint is
    int cell=GetCellIndex(x, y, z);
    if (cell<0 || !fCells || cell>=fCellDimension) return -EFAULT;
    if (fCells[cell].fCount<0) fCells[cell].fCount=1;
    else fCells[cell].fCount++;
    return 0;
  }


  // add spacepoint, all spacepoints must have been counted before
  int AddSpacePoint(ValueType t, T x, T y, T z) {
    // add spacepoint, all spacepoints must have been counted before
    int cell=GetCellIndex(x, y, z);
    if (cell<0 || !fCells || cell>=fCellDimension) return -EFAULT;
    if (fCells[cell].fFilled==fCells[cell].fCount) return -ENOSPC;
    if (fCells[cell].fStartIndex<0 && IndexCells()<0) return -EACCES;
    int offset=fCells[cell].fStartIndex+fCells[cell].fFilled;
    fData[offset]=t;
    fCells[cell].fFilled++;
    fCount++;
    return 0;
  }

  void Clear(const char* /*option*/="") {
    // clear internal data
    if (fCells) memset(fCells, 0xff, fCellDimension*sizeof(AliHLTIndexGridCell));
    if (fData) memset(fData, 0, fDataDimension*sizeof(V));
    fCount=0;
  }

  void Print(const char* /*option*/="") {
  // print info
  bool bPrintEmpty=false;
  std::streamsize precision=cout.precision();
  cout << "AliHLTIndexGrid: " << (fCells?fCellDimension:0) << " cells" << endl;
  cout << "   x: " << fDimX << " [0," << fMaxX << "]" << endl;
  cout << "   y: " << fDimY << " [0," << fMaxY << "]" << endl;
  cout << "   z: " << fDimZ << " [0," << fMaxZ << "]" << endl;
  cout << "   " << GetNumberOfSpacePoints(0, fCellDimension) << " point(s)" << endl;
  if (fCells) {
    for (int i=0; i<fCellDimension; i++) {
      if (!bPrintEmpty && fCells[i].fCount<=0) continue;
      cout << "     " << setfill(' ') << setw(7) << setprecision(0) << i << " (" 
	   << " " << setw(3) << GetLowerBoundX(i)
	   << " " << setw(3) << GetLowerBoundY(i)
	   << " " << setw(4) << GetLowerBoundZ(i)
	   << "): ";
      cout << setw(3) << fCells[i].fCount << " entries, " << setw(3) << fCells[i].fFilled << " filled";
      cout << "  start index " << setw(5) << fCells[i].fStartIndex;
      cout << endl;
      if (fCells[i].fCount>0) {
	cout << "          ";
	for (iterator id=begin(GetLowerBoundX(i), GetLowerBoundY(i), GetLowerBoundZ(i));
	     id!=end(); id++) {
	  cout << " 0x" << hex << setw(8) << setfill('0') << id.Data();
	}
	cout  << dec << endl;
      }
    }
  }
  cout << setprecision(precision);
}


  class iterator {
  public:
  iterator()
    : fData(NULL) {}
  iterator(const ValueType* pData)
    : fData(pData) {}
  iterator(const iterator& i)
    : fData(i.fData) {}
    iterator& operator=(const iterator& i)
      { fData=i.fData; return *this;}
    ~iterator() {fData=NULL;}

    bool operator==(const iterator& i) const  {return (fData!=NULL) && (fData==i.fData);}
    bool operator!=(const iterator& i) const  {return (fData!=NULL) && (fData!=i.fData);}
    // prefix operators
    iterator& operator++() {fData++; return *this;}
    iterator& operator--() {fData--; return *this;}
    // postfix operators
    iterator operator++(int) {iterator i(*this); fData++; return i;}
    iterator operator--(int) {iterator i(*this); fData--; return i;}

    iterator& operator+=(int step) {fData+=step; return *this;}

    const ValueType& Data() const {return *fData;}

  protected:
  private:
    const ValueType* fData; //! data
  };

  // prepare iterator and end marker
  iterator& begin(T x=(T)-1, T y=(T)-1, T z=(T)-1) {
    fIterator.~iterator();
    fIteratorEnd.~iterator();

    int startIndex=0;
    if (x<0) {
      // get all data
      if (fData) {
	new (&fIterator) iterator(fData);
	fIteratorEnd=fIterator;
	fIteratorEnd+=fCount;
      }
      return fIterator;
    }

    // only search for the start index if specific x selected
    int cell=GetCellIndex(x, y, z);
    if (cell<0 || !fCells || cell>=fCellDimension) return fIterator;
    // get the index of the cell
    startIndex=fCells[cell].fStartIndex;
    if (startIndex<0 || !fData || startIndex>=fDataDimension) return fIterator;

    // get the range end position
    int endCell=cell+1;
    if (x<0) endCell=fCellDimension;
    else if (y<0) endCell=GetCellIndex(x+fStepX, -1., -1.); // all entries for fixed x
    else if (z<0) endCell=GetCellIndex(x, y+fStepY, -1.); // all entries for fixed x and y
    if (endCell<=cell) {
      // cell index returned is never outside the array
      // so this is a special case where we get to the bounds of the array
      endCell=fCellDimension;
    }

    new (&fIterator) iterator(fData+startIndex);
    fIteratorEnd=fIterator;
    fIteratorEnd+=GetNumberOfSpacePoints(cell, endCell);
    return fIterator;
  }

  // get loop end marker
  iterator& end() {
    return fIteratorEnd;
  }

  struct AliHLTIndexGridCell {
    int fCount;
    int fFilled;
    int fStartIndex;
  };

 protected:
 private:
  // standard constructor prohibited
  AliHLTIndexGrid();
  // copy constructor prohibited
  AliHLTIndexGrid(const AliHLTIndexGrid&);
  // assignment operator prohibited
  AliHLTIndexGrid& operator=(const AliHLTIndexGrid&);

  int IndexCells() {
    // set the start index for data of every cell based on the counts
    if (!fCells || fCellDimension<=0) return -ENOBUFS;
    int offset=0;
    int cell=0;
    for (; cell<fCellDimension; cell++) {
      if (fCells[cell].fCount<0) continue;
      fCells[cell].fStartIndex=offset;
      offset+=fCells[cell].fCount;
      fCells[cell].fFilled=0;
    }

    if (offset>fDataDimension) {
      // grow the data array
      auto_ptr<V> newArray(new V[offset]);
      if (newArray.get()) {
	memcpy(newArray.get(), fData, fDataDimension);
	memset(newArray.get()+fDataDimension, 0, (offset-fDataDimension)*sizeof(V));
	delete fData;
	fData=newArray.release();
	fDataDimension=offset;
      } else {
	for (cell=0; cell<fCellDimension; cell++) {
	  fCells[cell].fStartIndex=-1;
	}
      }
    }
    return 0;
  }


  T fMaxX;
  T fStepX;
  T fMaxY;
  T fStepY;
  T fMaxZ;
  T fStepZ;

  int fDimX;
  int fDimY;
  int fDimZ;

  AliHLTIndexGridCell* fCells; //! cell array
  int fCellDimension; //! size of cell array
  ValueType* fData; //! spacepoint data
  int fDataDimension; //! size of spacepoint data
  int fCount;

  iterator fIterator; //! iterator
  iterator fIteratorEnd; //! end marker iterator

  static const int fgkDefaultDataSize=10000; //! the default data size

  ClassDef(AliHLTIndexGrid, 0)
};

#endif
Commit	Line	Data
4e1f33ca	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=fDimXfDimYfDimZ;
	52	fCells=new AliHLTIndexGridCell[fCellDimension];
	53	if (fDataDimension<0) fDataDimension=fgkDefaultDataSize;
050a3338	54	fData=new V[fDataDimension];
4e1f33ca	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)fDimYfDimZ + (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));
050a3338	139	if (fData) memset(fData, 0, fDataDimension*sizeof(V));
4e1f33ca	140	fCount=0;
	141	}
	142
	143	void Print(const char* /option/="") {
	144	// print info
	145	bool bPrintEmpty=false;
aa8f91a4	146	std::streamsize precision=cout.precision();
4e1f33ca	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	}
aa8f91a4	173	cout << setprecision(precision);
4e1f33ca	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
050a3338	281	auto_ptr<V> newArray(new V[offset]);
4e1f33ca	282	if (newArray.get()) {
4e1f33ca	283	memcpy(newArray.get(), fData, fDataDimension);
050a3338	284	memset(newArray.get()+fDataDimension, 0, (offset-fDataDimension)*sizeof(V));
4e1f33ca	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