#ifndef __HASHPVS_H
#define __HASHPVS_H

//#include <hash_map>
#include <hash_set>
#include "common.h"
#include <math.h>
#include "PvsBase.h"


using namespace std;

namespace GtpVisibilityPreprocessor {


template<typename T>
struct my_hash_compare
{
   enum
   {
      bucket_size = 4,
      min_buckets = 80
   };

   size_t operator()(T a) const
   {
      size_t h = (size_t)(a->GetId());// % 2000;
      //for (; *s; ++s)
      //   h = 5 * h + *s;
      return h;
   }

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

/*
template<typename T>
struct gt
{
	bool operator() (T s1, T s2) const
	{
		return s1 > s2;
	}
};
*/
//#define HASH_SET stdext::hash_set<T, stdext::hash_compare<T, gt<T> > >
#define HASH_SET stdext::hash_set<T, my_hash_compare<T> >

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

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

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

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

	T Next()
	{
		// hack: create new pvs entry
		return *(mItCurrent) ++;
	}
	
private:
	typename HASH_SET::const_iterator mItCurrent;
	typename HASH_SET::const_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((Intersectable *)100) {};
	HashPvs() {};
	//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.
		@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.
	*/
	bool Find(T sample, typename HASH_SET::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);

	int GetSamples() const
	{
		return mSamples;
	}

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

	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_SET::iterator &it)
{
	it = mEntries.find(sample);

	// 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)
{
	HASH_SET::iterator it;

	if (Find(sample, it))
		return 0.0f;
	
	mEntries.insert(sample);
	return 1.0f;
}
	

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

	// not yet in map
	if (!Find(sample, it))
	{
		mEntries.insert(sample);	
	}
}


template <typename T, typename S>
bool HashPvs<T, S>::AddSampleDirtyCheck(T sample, 
										const float pdf)
{
	HASH_SET::iterator it;

	// already in map
	if (Find(sample, it))
		return false;
	
	mEntries.insert(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)
{
	HASH_SET::const_iterator ait, ait_end = a.mEntries.end();

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

	HASH_SET::const_iterator bit, bit_end = b.mEntries.end();

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

	//cerr << "not implemented" << endl; 
}

}

#endif