/* $Id: pvector_t.hpp,v 1.18 2005/06/28 13:55:21 chfreund Exp $ */

#ifndef  POINTER_VECTOR_INCLUDED
#define  POINTER_VECTOR_INCLUDED

/***********************************************************
 *
 * pvector_t.hpp
 * Uwe Fabricius
 * Version 1.00.00                               21.02.2004
 *
 ***********************************************************/

#include <iostream>

/***********************************************************/

#ifndef  POINTER_VECTOR_GRANULARITY
#define  POINTER_VECTOR_GRANULARITY  10
#endif // POINTER_VECTOR_GRANULARITY
#if POINTER_VECTOR_GRANULARITY <= 0
#error "\nERROR: pvector.cpp: POINTER_VECTOR_GRANULARITY must not be <= 0\n"
#endif // POINTER_VECTOR_GRANULARITY <= 0

/**********************************************************/

// make shure that "DBG_LEVEL > 0" switches on "_DEBUG_"
#ifdef DBG_LEVEL
#if      DBG_LEVEL > 0
#ifndef    _DEBUG_
#define    _DEBUG_
#endif     // _DEBUG_
#endif   // DBG_LEVEL > 0
#endif // DBG_LEVEL

#ifdef  _DEBUG_
#ifndef  DEBUG_VERBOSITY
#define  DEBUG_VERBOSITY
#endif // DEBUG_VERBOSITY
#endif // _DEBUG_

// do not throw exceptions
#ifndef  NEW
#define  NEW  new(nothrow)
#endif

/**********************************************************/

// some macros for error messages
// coloring ?
#ifdef SUPPRESS_COLORED_OUTPUT
#define  PVEC_FN_ERR(fn)       fn << ":\n >> "
#define  PVEC_CALLED_FROM(fn)  "    called from " << fn << "\n"
#else
#define  PVEC_FN_ERR(fn)       "\033[31m" << fn << "\033[0m:\n >> "
#define  PVEC_CALLED_FROM(fn)  "    called from \033[36m" << fn << "\033[0m\n"
#endif
// makros, that do not depend directly on coloring
#define  PVEC_MEM_ERR(fn,n,s)  PVEC_FN_ERR(fn) << "could not get " \
                               << n << " bytes to " << s << endl

/***********************************************************/
using namespace std;
/***********************************************************/

//! dynamic vector for the collection of object pointers

/*! This class is a vector container specialized to contain pointers
 *  to objects of the template parameter type. The manipulating
 *  functions are designed partly to only modify the membership of
 *  the objects in the vector, partly to modify, e.g. destroy the
 *  objects itself. Assure to use the correct version. The following
 *  table should help you to use the appropriate function.
 *  <br><br>
 *
 *  <b>Adding Entries:</b>
 *  <br><br>
 *  You want to add the pointer <code>T *p</code> as new entry
 *  in the vector PointerVector<T> V:
 *   - (1) The position of the new entry in the vector matters and
 *     should be at index i -> (1.1)
 *     <br>
 *     The position of the new entry in the vector does not matter.
 *     The new entry should just be added -> PointerVector::append
 *   - (1.1) A possibly already present entry at [i] should be
 *     overwritten: -> (1.1.1)
 *     <br>
 *     The new entry should be inserted at [i] without removing
 *     previous entries -> (1.1.2)
 *   - (1.1.1) PointerVector::set, PointerVector::replace
 *   - (1.1.2) PointerVector::insert
 *  <br><br>
 *
 *  <b>Removing Entries:</b>
 *  <br><br>
 *  You want to remove an entry in the vector:
 *   - (1) The object, that was refered by the pointer at [i] should
 *     be deleted: -> (1.1)
 *     <br>
 *     The refered object should further exist. Only remove the pointer.
 *     -> (1.2)
 *   - (1.1) The ordering of the left entries does matter and should
 *     not be changed: PointerVector::remove
 *     <br>
 *     The ordering of the left entries does not matter:
 *     -> PointerVector::swap_unhook (delete the return value)
 *   - (1.2) The ordering of the left entries does matter and should
 *     not be changed: PointerVector::unhook
 *     <br>
 *     The ordering of the left entries does not matter:
 *     -> PointerVector::swap_unhook
 */
template <class T>
class PointerVector
{
	public:

/***********************************************************/

//! creates an empty vector of the passed size

/*! Creates a vector of the passed size. All pointers are initialized
 *  to NULL.
 *  \param size size of the vector. If < 0 (default), an empty vector
 *         object is created.
 */
PointerVector( const int size = -1 )
: m_Size(0),
  m_BufferSize(0),
  m_Data(NULL)
{
	if( size > 0 ) {
#ifdef  DEBUG_VERBOSITY
		if( false == resize(size) ) {
			cerr << PVEC_CALLED_FROM("PointerVector::PointerVector("<<size<<")");
		}
#else
		resize( size );
#endif
	}	
}

/***********************************************************/

//! destructor
~PointerVector()
{
	reset();
}

/***********************************************************/

//! access operator

/*! Returns the address of the pointer at position [i]. That means that
 *  the pointer in the vector itself can be modified using this operator.
 *  This operator also exists for constant objects, but returns a copy
 *  of the pointer in this case. <br>
 *  Note that a boundary check is only done in debug mode.
 */
T*& operator [] ( const int i )
{
#ifdef _DEBUG_
	if( i < 0 || i >= m_Size ) {
		cerr << PVEC_FN_ERR("PointerVector::operator []")
		     << "access of element[" << i << "], which is out "
		        "of range [0," << (m_Size-1) << "]\n"
		        "    expect a crash\n";
		return m_Data[0];
	}
#endif

	return m_Data[i];
}

/***********************************************************/

//! access operator

/*! Returns the pointer at position [i]. In contrary to the non-constant
 *  version of the operator, which offers direct access to the vector
 *  data, this one returns a copy of the pointer at position [i].
 */
T* operator [] ( const int i ) const
{
#ifdef _DEBUG_
	if( i < 0 || i >= m_Size ) {
		cerr << PVEC_FN_ERR("PointerVector::operator []")
		     << "access of element[" << i << "], which is out "
		        "of range [0," << (m_Size-1) << "]\n"
		        "    expect a crash\n";
		return NULL;
	}
#endif

	return m_Data[i];
}

/**********************************************************/

//! returns the size of the vector
int getSize() const { return m_Size; }
//! returns the current buffer size
int getBufferSize() const { return m_BufferSize; }
//! returns a pointer to the data buffer
T*  getDataPointer() const { return m_Data; }

/**********************************************************/

//! returns the index of a passed pointer

/*! Takes a pointer and searches this pointer in the pointer vector.
 *  If it can be found the function returns the index of this
 *  pointer entry in the vector, otherwise -1.
 */
int getIndex( const T *const item )
{
	for( int i = 0; i < m_Size; i++ ) {
		if( item == m_Data[i] )  return i;
	}
	return -1;
}

/**********************************************************/

//! sets the pointer at position [i]

/*! Sets the vector value at position [i]. If this position already
 *  contains the address of an existing object, this object is deleted!
 *  To prevent the deletion of the present object, this function offers
 *  an address to a pointer of type T as optional parameter to "return"
 *  the previous pointer at position [i], which is written at "*oldptr"
 *  if that parameter is passed as != NULL. The size of the vector
 *  is not changed.
 *  <br>
 *  Note that a boundary check for parameter i is done only in debug
 *  mode.
 *  \param i index of the value to be set
 *  \param newptr pointer that should be set as value at index [i]
 *  \param oldptr (optional) address of a pointer variable. If passed
 *         as != NULL, the previous content of index [i] is saved at
 *         this address.
 *  \return true, if the set was successfull
 */
bool set( const int i,
          const T*  newptr,
                T** oldptr = NULL  )
{
#ifdef _DEBUG_
	if( i < 0 || i >= m_Size ) {
		cerr << PVEC_FN_ERR("PointerVector::set("<<i<<",..)")
		     << i << " is out of range [0," << (m_Size-1) << "]\n"
		        "    expect a crash\n";
		return false;
	}
#endif

	if( oldptr ) *oldptr = m_Data[i];
	else         delete m_Data[i];
	m_Data[i] = (T*)newptr;

	return true;
}

/***********************************************************/

//! replaces the value at index [i]

/*! Sets the value at position [i] to the passed pointer and returns
 *  the previous value. In particular this includes that the object
 *  belonging to a previous non-zero pointer is not deleted.
 */
T* replace( const int i, const T* newptr )
{
	T* oldptr;
#ifdef _DEBUG_
	if( false == set(i, newptr, &oldptr) ) {
		cerr << PVEC_CALLED_FROM("PointerVector::replace");
		return NULL;
	} else {
		return oldptr;
	}
#endif

	set( i, newptr, &oldptr );
	return oldptr;
}

/***********************************************************/

//! resets the vector to an empty vector of size 0.

/*! Resets the vector to an empty vector of size 0. All objects, pointed
 *  at in the vector are deleted.
 */
void reset()
{
	// delete data array
	if( m_Data ) {
		for( int i = 0; i < m_Size; i++ )  delete m_Data[i];
	}
	delete [] m_Data;
	m_Data = NULL;

	m_Size       = 0;
	m_BufferSize = 0;
}

/***********************************************************/

//! returns the index of the NULL pointer with lowest index

/*! Starts at the passed position startposition to search the next
 *  vector entry containing a NULL pointer and returns its index.
 *  \param startindex the index, at that the vector should start to
 *         seek the next NULL pointer.
 */
int getNextFree( const int startindex = 0 ) const
{
	for( int i = startindex<0 ? 0 : startindex; i < m_Size; i++ ) {
		if( m_Data[i] == NULL )  return i;
	}
	return m_Size;
}

/***********************************************************/

//! resizes the vector while keeping the old content as far as possible.

/*! Resizes the vector to the passed size while keeping the old content
 *  of the lower indices. If the new vector is smaller that the old one,
 *  all objects, pointed at in the overlap, are deleted. If the new size
 *  exceeds the old one, the new overlap is initialized with NULL.
 *  \param newSize the new size of the vector
 *  \param true, if the resize was successfull
 */ 
bool resize( const int newSize )
{
	if( newSize <= 0 ) { reset(); return true; }

	// if the vector gets smaller, ...
	if( newSize < m_Size ) {
		// ... delete all elements in the overlap
		for( int i = newSize; i < m_Size; i++ ) {
			delete m_Data[i];
			m_Data[i] = NULL;
		}
	}
	
	int newBufferSize = getBufferSizeFromVSize( newSize );
	// if buffer cannot be reused, ...
	if( newBufferSize != m_BufferSize ) {
		// ... try to get some new and ...
		T **newData = NEW T* [newBufferSize];
		if( newData ) {
			int copySize = newSize < m_Size ? newSize : m_Size;
			// copy old data and initialise overlap
			memcpy( newData, m_Data, copySize*sizeof(T*) );
			for( int i = copySize; i < newBufferSize; i++ ) {
				newData[i] = NULL;
			}
			delete [] m_Data;
			m_Data       = newData;
			m_Size       = newSize;
			m_BufferSize = newBufferSize;
		} else {
#ifdef  DEBUG_VERBOSITY
			cerr << PVEC_MEM_ERR("PointerVector::resize("<<newSize<<")",
				                 newSize*sizeof(T), "to resize array");
#endif
			return false;
		}
	} else {
		m_Size = newSize;
	}

	return true;
}	

/***********************************************************/

//! inserts a pointer at position [pos]

/*! Inserts the passed pointer at position [pos]. This means, that the
 *  new pointer is really inserted, whereby none of the present pointers
 *  is overwritten. The vector's size increases by one in this function
 *  call. All previous entries with indices greater that [pos] are
 *  shifted upwards by one. If [pos] exceeds the current vector size,
 *  the vector is enlarged in order to assure to fullfill the specified
 *  position. The pointers in between are filled up with NULL. If you want
 *  to make sure, that no "NULL-holes" are created by this mechanism, the
 *  additional parameter "compact" can be passed as true.
 *  \param item pointer, that should be inserted
 *  \param pos index position, at which the new value should be inserted
 *  \param compact if false (default) a value of parameter pos greater
 *         than the current vector size will cause a fill in of NULL
 *         pointers to ensure the correct position. If true, the value
 *         will simply be appended, if pos is greater than the current
 *         vector size.
 *  \return true, if the insertion was successfull
 */
bool insert( const T* const item,
             const int      pos,
             const bool     compact = false )
{
#ifdef _DEBUG_
#ifdef DBG_LEVEL
	if( DBG_LEVEL >= 3 )
#endif
	{
		for( int i = 0; i < m_Size; i++ ) {
			if( NULL != item && item == m_Data[i] ) {
				cerr << PVEC_FN_ERR("WARNING: PointerVector::insert")
				     << "pointer already present at ["<<i<<"]\n";
			}
		}
	}
#endif // _DEBUG_

	int newPosition = pos < 0 ? 0 : pos;
	// adapt the position, if holes are not wanted
	if( newPosition > m_Size && compact )  newPosition = m_Size;
	// resize the array
	if( false == resize(newPosition <= m_Size ? m_Size+1 : newPosition) ) {
		cerr << PVEC_CALLED_FROM("PointerVector::insert(..,"<<pos<<",..)");
		return false;
	}
	// move the pointers in the area above i
	for( int i = m_Size-1; i > newPosition; i-- ) {
		m_Data[i] = m_Data[i-1];
	}
	m_Data[newPosition] = (T*)item;

	return true;
}

/***********************************************************/

//! inserts another vector as subvector of this one

/*! Enlarges the vector in order to insert the full passed vector
 *  at the specified position. It works analoguously to the function
 *  insert, that inserts a single pointer.
 *  \param vector vector, that should be inserted
 *  \param pos index position, at which the new value should be inserted
 *  \param compact if false (default) a value of parameter pos greater
 *         than the current vector size will cause a fill in of NULL
 *         pointers to ensure the correct position. If true, the value
 *         will simply be appended, if pos is greater than the current
 *         vector size.
 *  \return true, if the insertion was successfull
 */
bool insert(       PointerVector<T>& vector,
             const int               pos,
             const bool              compact  = true )
{
	if( vector.getSize() == 0 )  return true;

	int newPosition = pos < 0 ? 0 : pos;
	// adapt the position, if holes are not wanted
	if( newPosition > m_Size && compact )  newPosition = m_Size;
	// resize the array
	if( false == resize(newPosition <= m_Size              ?
	                    m_Size      + vector.getSize()     :
	                    newPosition + vector.getSize() - 1  ) ) {
		cerr << PVEC_CALLED_FROM("PointerVector::insert");
		return false;
	}
	// move the pointers in the area above i
	for( int i = m_Size-1; i > newPosition; i-- ) {
		m_Data[i] = m_Data[i-1];
	}
	// insert the pointers from the passes vector
	for( int i = 0; i < vector.getSize(); i++ ) {
#ifdef _DEBUG_
		T* pT = vector.unhook( i );
		if( compact && pT == NULL ) {
			cerr << PVEC_FN_ERR("WARNING: PointerVector::insert")
			     << "    inserting a NULL pointer in a compact vector\n";
		}
		m_Data[newPosition + i] = pT;
#else
		m_Data[newPosition + i] = vector.unhook( i );
#endif
	}
	// reset the passed vector
	vector.reset();
	
	return true;
}

/***********************************************************/

//! appends an entry

/*! Appends a new entry in the vector. The vector is enlarged in any
 *  case.
 *  \param item pointer, that should be appended
 *  \return true, if successfull
 */
bool append( const T* const item )
{
#ifdef _DEBUG_
	if( false == insert(item, m_Size) ) {
		cerr << PVEC_CALLED_FROM("PointerVector::append");
		return false;
	}
	return true;
#endif

	return insert( item, m_Size );
}

/***********************************************************/

//! appends a vector
bool append( PointerVector<T>& vector )
{
#ifdef _DEBUG_
	if( false == insert(vector, m_Size) ) {
		cerr << PVEC_CALLED_FROM("PointerVector::append");
		return false;
	}
	return true;
#endif

	return insert( vector, m_Size );
}

/***********************************************************/

bool append( const T* const item, int num_items )
{
#ifdef _DEBUG_
	if( num_items < 0 ) {
		cerr << PVEC_FN_ERR("PointerVector::append")
		     << "attempt to append pointers to "<<num_items
		     << " items\n -> vector stays unchanged, but this "
		        "is fixed only in debug mode\n";
		num_items = 0;
	}
#endif

	const int firstNewPosition = getSize();
	// resize the vector
	if( ! resize(getSize() + num_items) ) {
		cerr << PVEC_CALLED_FROM("PointerVector::append");
		return false;
	}
	// append the pointers
	for( int i = 0; i < num_items; i++ ) {
		m_Data[firstNewPosition + i] = item[i];
	}

	return true;
}

/***********************************************************/

//! removes pointer at index [i] from the vector

/*! Removes pointer entry at index [i] from the vector <b>and</b>
 *  deletes the refered object. If parameter compact is specified as
 *  true, all following entries are moved by one index down in order
 *  to remove the resulting "NULL pointer hole". If compact is passed
 *  as false (default), the resulting memory is not closed. If
 *  index parameter i is out of the vectors index range, the vector
 *  stays unchanged and false is returned.
 *  \param i index of the entry, that should be removed
 *  \result true, if successfull
 */
bool remove( const int i, const bool compact = false )
{
#ifdef _DEBUG_
	if( i >= 0 && i < m_Size ) {
		// close hole
		if( compact ) {
			for( int j = i; j < m_Size-1; j++ )  m_Data[j] = m_Data[j+1];
			m_Data[m_Size-1] = NULL; // added by Tom
			if( false == resize(m_Size-1) ) {
				cerr << PVEC_CALLED_FROM("PointerVector::unhook("
				     << i << ",true)") << "    -> could not compact "
				        "the vector after deleting item\n";
			}			
		} else {
			delete m_Data[i];
			m_Data[i] = NULL;
		}
		return true;
	} else {
		cerr << PVEC_FN_ERR("PointerVector::unhook:")
		     << i << " is out of range [0," << m_Size-1 << "]\n";
		return false;
	}
#else // _DEBUG_
	delete unhook( i, compact );
	return true;
#endif // _DEBUG_
}

/***********************************************************/

//! removes entry [i] from the vector without deletion of the referenced object

/*! Removes the entry at index [i] of the vector. In contrary to function
 *  remove the refered object is not deleted, and the removed pointer
 *  is returned. For the function of paramter compact se the method
 *  PointerVector::remove.
 */
T* unhook( const int i, const bool compact = false )
{
	if( i >= 0 && i < m_Size ) {
		T* item = m_Data[i];
		// close hole
		if( compact ) {
			for( int j = i; j < m_Size-1; j++ )  m_Data[j] = m_Data[j+1];
			m_Data[m_Size-1] = NULL; // added by Tom
			if( false == resize(m_Size-1) ) {
#ifdef DEBUG_VERBOSITY
				cerr << PVEC_CALLED_FROM("PointerVector::unhook("
				     << i << ",true)");
#endif
			}			
		} else {
			m_Data[i] = NULL;
		}
		return item;
	} else {
#ifdef DEBUG_VERBOSITY
		cerr << PVEC_FN_ERR("PointerVector::unhook:")
		     << i << " is out of range [0," << m_Size-1 << "]\n";
#endif
		return NULL;
	}
}

/***********************************************************/

//! removes an entry from the vector and closes the resulting hole

/*! PointerVector::swap_unhook works similarly to PointerVector::unhook.
 *  In particular it always closes the resulting hole by moving the
 *  previously last entry to the now empty entry. This is faster, than
 *  moving all following entries on index down, but the ordering of the
 *  entries is changed.
 *  \param item the entry "item" with lowest is searched in the vector
 *         and removed, if it could be found.
 *  \return the removed pointer is returned. If it could not be found
 *          in the vector, NULL is returned.
 */
T* swap_unhook( const T* const item )
{
	for( int i = 0; i < m_Size; i++ ) {
		if( m_Data[i] == item ) {
			m_Data[i] = m_Data[m_Size-1];
			m_Data[m_Size-1] = NULL;
			resize( m_Size-1 );
			return (T*)item;
		}
	}
	return NULL;
}
	

/***********************************************************/

//! removes entry [i] and fills the resulting hole with the last entry

/*! Works just like PointerVector::swap_unhook( const T* const item ),
 *  but here the index is specified, not the pointer.
 */
T* swap_unhook( const int i )
{
	if( i >= 0 && i < m_Size ) {
		T* item = m_Data[i];
		// close hole
		m_Data[i] = m_Data[m_Size-1];
		m_Data[m_Size-1] = NULL;
		resize( getSize()-1 );
		return item;
	}
	return NULL;
}

/***********************************************************/

	protected:

/***********************************************************/

int getBufferSizeFromVSize( const int vsize ) const
{
#if POINTER_VECTOR_GRANULARITY > 1
	return  POINTER_VECTOR_GRANULARITY *
	       ((int)((vsize) / POINTER_VECTOR_GRANULARITY) +
		   ((vsize) % POINTER_VECTOR_GRANULARITY  ? 1 : 0));
#else
	return  vsize;
#endif
}	

/***********************************************************/

		int   m_Size,
		      m_BufferSize;
		T   **m_Data;
};

/***********************************************************/

#endif // POINTER_VECTOR_INCLUDED