#ifndef __HASHPVS_H
#define __HASHPVS_H

//#include <hash_set>
#include "common.h"
#include <math.h>
#include "PvsBase.h"
#include "google/dense_hash_set"
#include "google/dense_hash_map"


namespace GtpVisibilityPreprocessor {


/*template<typename T>
struct my_hash_compare
{
   enum
   {
      bucket_size = 1,
      min_buckets = 16
   };

   int operator()(int a) const
   {
	   return a;
   }


   bool operator()(T a, T b) const
   {
      return a < b;
   }
};*/


//#define HASH_SET google::dense_hash_set<T, my_hash_compare<T> >
#define HASH_SET google::dense_hash_map<int, T>//, hash_compare<int> >
//#define HASH_SET stdext::hash_set<T, my_hash_compare<T> >
#define HASH_ITERATOR HASH_SET::iterator
#define CONST_HASH_ITERATOR HASH_SET::const_iterator

/** Iterator over a hash pvs.
*/
template<typename T, typename S>
class HashPvsIterator
{
public:
	
	HashPvsIterator<T, S>() {}

	HashPvsIterator<T, S>(const typename CONST_HASH_ITERATOR &itCurrent,
						  const typename CONST_HASH_ITERATOR &itEnd):
	mItCurrent(itCurrent), mItEnd(itEnd)
	{
	}

	bool HasMoreEntries() const 
	{
		return (mItCurrent != mItEnd);
	}

	T Next(S &pdf)
	{
		T sample = (*mItCurrent).second;
		++ mItCurrent;

		return sample;
	}

	T Next()
	{
		T sample = (*mItCurrent).second;
		++ mItCurrent;

		return sample;
	}
	
private:
	typename CONST_HASH_ITERATOR mItCurrent;
	typename CONST_HASH_ITERATOR mItEnd;
};


/** Template class representing the Potentially Visible Set (PVS) 
	mainly from a view cell, but also e.g., from objects.
*/
template<typename T, typename S>
class HashPvs//: public PvsBase<T>
{
	template<typename T, typename S> friend class HashPvsIterator;

public:

	HashPvs()
	{
		 mEntries.set_deleted_key(-1);
		 mEntries.set_empty_key(-2);
	};

	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;

	inline bool RequiresResort() const;
	/** Finds sample in PVS.
		@param checkDirty if dirty part of the pvs should be checked for entry 
		(warning: linear runtime in dirty part)
		@returns iterator on the sample if found, else the place where 
		it would be added in the sorted vector.
	*/
	inline bool Find(T sample, typename HASH_ITERATOR &it);

	typename HashPvsIterator<T, S> GetIterator() const;
	/** Compute continuous PVS difference 
	*/
	float GetPvsHomogenity(HashPvs<T, S> &pvs);

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

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

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

	inline int GetSamples() const	{ return mSamples; }

	void MergeInPlace(const HashPvs<T, S> &a)
	{
		std::cerr << "hashpvs: mergeinplace not implemented yet" << std::endl;
	}

	inline bool RequiresResortLog() const {	return false; }

	void Reserve(const int n) 
	{ // not necessary 
	}

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

	int SubtractPvs(const HashPvs<T, S> &pvs)
	{
		cerr << "not yet implemented" << endl;
		return 0;
	}
	/** Compute continuous PVS difference 
	*/
	void ComputeContinuousPvsDifference(HashPvs<T, S> &pvs, 
										float &pvsReduction,
										float &pvsEnlargement)
	{
		cerr << "not yet implemented" << endl;
	}


protected:

	/// hash table of PVS entries
	HASH_SET mEntries; 

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


template <typename T, typename S>
bool HashPvs<T, S>::Find(T sample, typename HASH_ITERATOR &it)
{
	it = mEntries.find(sample->GetId());

	// already in map
	return (it != mEntries.end());
}


template <typename T, typename S>
int HashPvs<T, S>::GetSize() const
{
	return (int)mEntries.size();
}


template <typename T, typename S>
bool HashPvs<T, S>::Empty() const
{
	return mEntries.empty();
}


template <typename T, typename S>
float HashPvs<T, S>::AddSample(T sample, const float pdf)
{
	static HASH_ITERATOR it;

	if (Find(sample, it))
		return 0.0f;
	
	mEntries.insert(pair<int, T>(sample->GetId(), sample));
	return 1.0f;
}
	

template <typename T, typename S>
void HashPvs<T, S>::AddSampleDirty(T sample, const float pdf)
{
	static HASH_ITERATOR it;

	// not yet in map
	if (!Find(sample, it))
	{
		mEntries.insert(pair<int, T>(sample->GetId(), sample));
	}
}


template <typename T, typename S>
bool HashPvs<T, S>::AddSampleDirtyCheck(T sample, 
										const float pdf)
{
	static pair<HASH_ITERATOR, bool> result;
	result = mEntries.insert(pair<int, T>(sample->GetId(), sample));
	return result.second;

	/*
	static CONST_HASH_ITERATOR it;

	it = mEntries.find(sample->GetId());//, sample);

	// already in map
	const bool found = (it != mEntries.end());

	//return false;
	// already in map
	if (found)
	//if (Find(pair<int, T>(sample->GetId(), sample), it))
		return false;

	mEntries.insert(pair<int, T>(sample->GetId(), sample));
	
	return true;*/
}


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


template <typename T, typename S>
void HashPvs<T, S>::Clear(const bool trim = true)
{
	mEntries.clear();
}


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


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


template <typename T, typename S>
typename HashPvsIterator<T, S> HashPvs<T, S>::GetIterator() const
{
	HashPvsIterator<T, S> pit(mEntries.begin(), mEntries.end());

	return pit;
}


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


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


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

	ComputeContinuousPvsDifference(pvs,	pvsReduction, pvsEnlargement);

	return pvsReduction + pvsEnlargement;
}


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

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


template <typename T, typename S>
void HashPvs<T, S>::Merge(HashPvs<T, S> &mergedPvs, 
						  const HashPvs<T, S> &a, 
						  const HashPvs<T, S> &b)
{
	CONST_HASH_ITERATOR ait, ait_end = a.mEntries.end();

	for (ait = a.mEntries.begin(); ait != ait_end; ++ ait)
	{
		mergedPvs.AddSample((*ait).second, 1.0f);
	}

	CONST_HASH_ITERATOR bit, bit_end = b.mEntries.end();

	for (bit = b.mEntries.begin(); bit != bit_end; ++ bit)
	{
		mergedPvs.AddSample((*bit).second, 1.0f);
	}
}

}

#endif