#ifndef __BITVECTORPVS_H
#define __BITVECTORPVS_H

#include <vector>
#include "common.h"
#include "PvsBase.h"


namespace GtpVisibilityPreprocessor {

// specialisation of vector<bool>
typedef vector<bool> bit_vector;


/** Iterator over a bitvector pvs.
*/
template<typename T, typename S>
class BitVectorPvsIterator
{
public:
	
	BitVectorPvsIterator<T, S>(const typename bit_vector::const_iterator &itBegin,
							   const typename bit_vector::const_iterator &itEnd
							   //,const int lastElement
							   ):
	mItCurrent(itBegin), mItEnd(itEnd), mDistance(0)//, mLastElement
	{
	}

	bool HasMoreEntries() const 
	{
		// find next element in bit vector
		// warning: has to do traversal each time
		typename bit_vector::const_iterator itNext = mItCurrent;

		for (;(itNext != mItEnd) && !(*itNext); ++ itNext);

		return (itNext != mItEnd);
	}

	T Next(S &pdf)
	{
		return Next();
	}
	
	T Next()
	{
		// hack: create new pvs entry
		for (; !(*mItCurrent); ++ mItCurrent, ++ mDistance);

		T sample = sObjects[mDistance];

		++ mDistance;
		++ mItCurrent;

		return sample;
	}

	
	// vector of objects corresponding to pvs entries
	static vector<T> sObjects;

private:

	typename bit_vector::const_iterator mItCurrent;
	//typename bit_vector::const_iterator mItNext;
	typename bit_vector::const_iterator mItEnd;
	
	// note: store distance explicitly because I 
	// don't know how efficient
	// std::distance is on specialisation of vector<bool>
	int mDistance;
};


/** Pvs implemented as bitvector
*/
template<typename T, typename S>
class BitVectorPvs//: public PvsBase<T>
{
  template<typename T1, typename S1> friend class BitVectorPvsIterator;

public:

	BitVectorPvs();
	//virtual ~HashPvs() {};

	int GetSize() const;
	bool Empty() const;

	/** Adds sample to PVS.
		@returns contribution of sample (0 or 1)
	*/
	float AddSample(T sample, const float pdf);

	/** Adds sample to PVS without checking for presence of the sample
		warning: pvs remains unsorted!
	*/
	void AddSampleDirty(T sample, const float pdf);

	/** Adds sample dirty (on the end of the vector) but
		first checks if sample is already in clean part of the pvs.
	*/
	bool AddSampleDirtyCheck(T sample, const float pdf);

	/** Sort pvs entries - this should always be called after a
		sequence of AddSampleDirty calls 
	*/
	void Sort();

	/** Clears the pvs.
	*/
	void Clear(const bool trim = true);

	bool IsDirty() const;

	bool RequiresResort() const;

	/** Finds sample in PVS.
	*/
	bool Find(T sample);

        BitVectorPvsIterator<T, S> GetIterator() const;

	/** Compute continuous PVS difference 
	*/
	float GetPvsHomogenity(BitVectorPvs<T, S> &pvs);

	static void Merge(BitVectorPvs<T, S> &mergedPvs, 
					  const BitVectorPvs<T, S> &a, 
					  const BitVectorPvs<T, S> &b);

	static int GetEntrySizeByte(); 
	static float GetEntrySize();

	bool GetSampleContribution(T sample,
        					   const float pdf,
							   float &contribution);

	int GetSamples() const
	{
		return mSamples;
	}

	void MergeInPlace(const BitVectorPvs<T, S> &a)
	{
	  std::cerr << "bitvector: merge in place not implemented yet"
		    << std::endl;
	}

	bool RequiresResortLog() const
	{
		return false;
	}

	void Reserve(const int n) 
	{ 
		mEntries.reserve(n);
	}

	/** Sort pvs entries assume that the pvs contains unique entries
	*/
	void SimpleSort()
	{
		// not necessary
	}

	int SubtractPvs(const BitVectorPvs<T, S> &pvs)
	{
	  std::cerr << "not yet implemented" << std::endl;
	  return 0;
	}

	/** Compute continuous PVS difference 
	*/
	void ComputeContinuousPvsDifference(BitVectorPvs<T, S> &pvs, 
										float &pvsReduction,
										float &pvsEnlargement)
	{
	  std::cerr << "not yet implemented" << std::endl;
	}


	static void SetPvsSize(const int pvsSize) { sPvsSize = pvsSize; };
	
protected:

	/// hash table of PVS entries
	bit_vector mEntries; 

	/// Number of samples used to create the PVS
	int mSamples;

public:
	static int sPvsSize;
};


template <typename T, typename S>
BitVectorPvs<T, S>::BitVectorPvs()
{
	// initialize bit vector
	mEntries.reserve(sPvsSize);
	mEntries.resize(sPvsSize);

	// set pvs entries to false
	Clear();
}


template <typename T, typename S>
bool BitVectorPvs<T, S>::Find(T sample)
{
	return mEntries[sample->GetId()];
}


template <typename T, typename S>
int BitVectorPvs<T, S>::GetSize() const
{
	int size = 0;
	bit_vector::const_iterator bit, bit_end = mEntries.end();

	for (bit = mEntries.begin(); bit != bit_end; ++ bit)
	{
		if (*bit) ++ size;
	}

	return size;
}


template <typename T, typename S>
bool BitVectorPvs<T, S>::Empty() const
{
	bit_vector::const_iterator bit, bit_end = mEntries.end();

	for (bit = mEntries.begin(); bit != bit_end; ++ bit)
	{
		if (*bit) return false;
	}

	return true;
}


template <typename T, typename S>
float BitVectorPvs<T, S>::AddSample(T sample, const float pdf)
{
	if (Find(sample))
		return 0.0f;
	
	mEntries[sample->GetId()] = true;

	return 1.0f;
}
	

template <typename T, typename S>
void BitVectorPvs<T, S>::AddSampleDirty(T sample, const float pdf)
{
	if (!Find(sample))
	{
		mEntries[sample->GetId()] = true;
	}
}


template <typename T, typename S>
bool BitVectorPvs<T, S>::AddSampleDirtyCheck(T sample, const float pdf)
{
	if (Find(sample))
		return false;
	
	mEntries[sample->GetId()] = true;
	return true;
}


template <typename T, typename S>
void BitVectorPvs<T, S>::Sort()
{
}


template <typename T, typename S>
void BitVectorPvs<T, S>::Clear(const bool trim)
{
	bit_vector::iterator bit, bit_end = mEntries.end();
	for (bit = mEntries.begin(); bit != bit_end; ++ bit)
	{
		(*bit) = false;
	}
}


template <typename T, typename S>
bool BitVectorPvs<T, S>::IsDirty() const
{
	return false;
}


template <typename T, typename S>
bool BitVectorPvs<T, S>::RequiresResort() const
{
	return false;
}


template <typename T, typename S>
BitVectorPvsIterator<T, S> BitVectorPvs<T, S>::GetIterator() const
{
  return BitVectorPvsIterator<T, S>(mEntries.begin(), mEntries.end());
}


template <typename T, typename S>
float BitVectorPvs<T, S>::GetEntrySize()
{
	return (float)(sizeof(bool)) / float(1024 * 1024);
}


template <typename T, typename S>
int BitVectorPvs<T, S>::GetEntrySizeByte()
{
	return sizeof(bool);
}


template <typename T, typename S>
float BitVectorPvs<T, S>::GetPvsHomogenity(BitVectorPvs<T, S> &pvs) 
{
	float pvsReduction, pvsEnlargement;

	ComputeContinuousPvsDifference(pvs,	pvsReduction, pvsEnlargement);

	return pvsReduction + pvsEnlargement;
}


template <typename T, typename S>
bool BitVectorPvs<T, S>::GetSampleContribution(T sample,
									  const float pdf,
									  float &contribution) 
{
	const bool entryFound = Find(sample);

	if (entryFound)  
	{
		contribution = 0.0f;
		return false;
	}
	else 
	{
		contribution = 1.0f;
		return true;
	}
}


template <typename T, typename S>
void BitVectorPvs<T, S>::Merge(BitVectorPvs<T, S> &mergedPvs, 
							   const BitVectorPvs<T, S> &a, 
							   const BitVectorPvs<T, S> &b)
{
	bit_vector::iterator bit, bit_end = mergedPvs.mEntries.end();
	bit_vector::const_iterator bitA =  a.mEntries.begin(), bitB = b.mEntries.begin();

	for (bit = mergedPvs.mEntries.begin(); bit != bit_end; ++ bit, ++ bitA, ++ bitB)
	{
        (*bit) = (*bitA) | (*bitB);
	}
}


template<typename T, typename S>
int BitVectorPvs<T, S>::sPvsSize = 0;

template<typename T, typename S>
vector<T> BitVectorPvsIterator<T, S>::sObjects;

}

#endif