#ifndef __PVSBASE_H
#define __PVSBASE_H

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

namespace GtpVisibilityPreprocessor {

/** Information stored with a PVS entry. Consists of the number
	the object was seen from the view cell.
*/
struct PvsData 
{
public:
	PvsData() {}
	PvsData(const float sumPdf):
	mSumPdf(sumPdf) {}
	
	// $$JB in order to return meaningfull values
	// it assumes that the sum pdf has been normalized somehow!!!
	inline float GetVisibility() { return mSumPdf; }

	/// sum of probability density of visible sample rays
	float mSumPdf;
};


class MailablePvsData 
{
public:
	// sum of probability density of visible sample rays
	float mSumPdf;
	int mCounter;

	MailablePvsData() {}
	MailablePvsData(const float sumPdf):
	mSumPdf(sumPdf) {}

	// $$JB in order to return meaningfull values
	// it assumes that the sum pdf has been normalized somehow!!!
	inline float GetVisibility() { return mSumPdf; }


	///////////////
	//  Mailing stuff

	// last mail id -> warning not thread safe!
	// both mailId and mailbox should be unique for each thread!!!
	static int sMailId;
	static int sReservedMailboxes;

	static void NewMail(const int reserve = 1) 
	{
		sMailId += sReservedMailboxes;
		sReservedMailboxes = reserve;
	}

	void Mail() { mMailbox = sMailId; }
	bool Mailed() const { return mMailbox == sMailId; }

	void Mail(const int mailbox) { mMailbox = sMailId + mailbox; }
	bool Mailed(const int mailbox) const { return mMailbox == sMailId + mailbox; }

	int IncMail() { return ++ mMailbox - sMailId; }
	
	//////////////////////////////////////////

protected:

	int mMailbox;

};


/** Information stored with a PVS entry. Consists of the number
	the object was seen from the view cell.
*/
template<typename T, typename S>
struct PvsEntry 
{
public:

	PvsEntry(): mObject(NULL), mData(0) {}
	PvsEntry(T sample): mObject(sample), mData(0) {}
	PvsEntry(T sample, const S &data): mObject(sample), mData(data) {}

	T mObject;
	S mData;

  //template<typename T, typename S>
  friend int operator< (const PvsEntry<T, S> &a, const PvsEntry<T, S> &b);
  //template<typename T, typename S>
  friend int operator== (const PvsEntry<T, S> &a, const PvsEntry<T, S> &b);
};


template<typename T, typename S>
int operator< (const PvsEntry<T, S> &a, const PvsEntry<T, S> &b)
{
	return a.mObject < b.mObject;
} 

template<typename T, typename S>
int operator== (const PvsEntry<T, S> &a, const PvsEntry<T, S> &b)
{
	return a.mObject == b.mObject;
} 


template<typename T, typename S>
struct LtSample
{
    bool operator()(const PvsEntry<T, S> &a, const PvsEntry<T, S> &b) const
    {
		return a.mObject < b.mObject;
	} 
};

template<typename T, typename S>
int equalSample (const PvsEntry<T, S> &a, const PvsEntry<T, S> &b)
{
	return a.mObject == b.mObject;
} 


/** Iterator over the pvs.
*/
template<typename T, typename S>
class PvsIterator
{
public:
	PvsIterator<T, S>(){}
	PvsIterator<T, S>(const typename vector<PvsEntry<T, S> >::const_iterator &itCurrent,
					  const typename vector<PvsEntry<T, S> >::const_iterator &itEnd):
	mItCurrent(itCurrent), mItEnd(itEnd)
	{
	}
  
	inline bool HasMoreEntries() const { return (mItCurrent != mItEnd);	}

	inline T Next(S &pdf) {
		pdf = (*mItCurrent).mData;
		return (*(mItCurrent ++)).mObject;
	}

  
	inline T Next() { return (*(mItCurrent ++)).mObject; }

  inline T Current(S &pdf) {
	pdf = (*mItCurrent).mData;
	return (*(mItCurrent)).mObject;
  }

  //private:
	
  typename vector<PvsEntry<T, S> >::const_iterator mItCurrent;
  typename vector<PvsEntry<T, S> >::const_iterator mItEnd;
};




struct VerbosePvsStats
{
	VerbosePvsStats(): mDistanceWeightedTriangles(0), mDistanceWeightedPvs(0), mWeightedTriangles(0)
	{}

	float mDistanceWeightedTriangles;
	float mDistanceWeightedPvs;
	float mWeightedTriangles;
};


/** 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 VerbosePvs
{
  template<typename T1, typename S1> friend class PvsIterator;

public:

	VerbosePvs(): mSamples(0), mEntries(), mLastSorted(0), mQueriesSinceSort(0) 
	{}

	/** creates pvs and initializes it with the given entries. 
		Assumes that entries are sorted.
	*/
	VerbosePvs(const vector<PvsEntry<T, S> > &samples);
	virtual ~VerbosePvs() {};

	/** Compresses PVS lossless or lossy.
	*/
	int Compress() { return 0; }
	
	inline int GetSize() const { return (int)mEntries.size(); }
	
	inline bool Empty() const { return mEntries.empty(); }

	inline void Reserve(const int n) { mEntries.reserve(n); }
	/** Normalize the visibility of entries in order to get 
		comparable results.
	*/
	void NormalizeMaximum();
	/** Merges pvs of a into this pvs.
		Warning: very slow!
	*/
	void MergeInPlace(const VerbosePvs<T, S> &a);
	/** Difference of pvs to pvs b.
	@returns number of different entries.
	*/
	int Diff(const VerbosePvs<T, S> &b);
	/** 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 vector<PvsEntry<T, S> >::iterator &it,
			  const bool checkDirty = true);

	bool GetSampleContribution(T sample, const float pdf, float &contribution);
	/** 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();
	/** Sort pvs entries assume that the pvs contains unique entries
	*/
	void SimpleSort();
	/** Adds sample to PVS.
		@returns PvsData
	*/
	typename std::vector<PvsEntry<T, S> >::iterator 
		AddSample2(T sample, const float pdf);
	/** Subtracts one pvs from another one.
		WARNING: could contains bugs
		@returns new pvs size
	*/
	int SubtractPvs(const VerbosePvs<T, S> &pvs);

	/** Returns PVS data, i.e., how often it was seen from the view cell, 
		and the object itsef.
	*/
	void GetData(const int index, T &entry, S &data);

	/** Collects the PVS entries and returns them in the vector.
	*/
	void CollectEntries(std::vector<T> &entries);

	/** Removes sample from PVS if reference count is zero.
	@param visibleSamples number of references to be removed
	*/
  bool RemoveSample(T sample, const float pdf);

  void Remove(typename vector<PvsEntry<T, S> >::iterator &it);

	/** Compute continuous PVS difference 
	*/
	void ComputeContinuousPvsDifference(VerbosePvs<T, S> &pvs, 
										float &pvsReduction,
										float &pvsEnlargement);

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

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

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

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

	inline int GetSamples() const {	return mSamples; }

	/** If there is an unsorted part in the pvs.
	*/
	bool IsDirty() const { return mLastSorted < mEntries.size(); }

	/** If this pvs requires a resort to stay efficient.
	*/
	bool RequiresResort() const
	{
		// the last part should not be more than log of the sorted part. this
		// way we can achieve logarithmic behaviour for insertion and find
		const int n = (int)mEntries.size();
		const int dirtySize = n - mLastSorted;

		const double LOG2E = 1.442695040f;

		const float logN = log((float) Max(1, n))/ (float)LOG2E;
		const float logS = log((float) Max(1, mLastSorted))/ (float)LOG2E;
		const float logD = log((float) Max(1, dirtySize))/ (float)LOG2E;

		if (8*(n + 2*dirtySize*logD) <
			mQueriesSinceSort*((mLastSorted*logS + dirtySize*dirtySize/2)/n - logN)) 
		{
			// cout<<"Q="<<mQueriesSinceSort<<" N="<<n<<" D="<<dirtySize<<endl;
			return true;
		}
		
		return false;
	}

	/** If this pvs requires a resort to stay efficient.
	*/
	bool RequiresResortLog() const
	{
		// the last part should not be more than log of the sorted part. this
		// way we can achieve logarithmic behaviour for insertion and find
		const int dirtySize = (int)mEntries.size() - mLastSorted;
		return dirtySize > 4 * (int)(log((double)mEntries.size()) / log(2.0));
	}

	inline int GetLastSorted() const { return mLastSorted; }

  PvsIterator<T, S> GetIterator() const;

	VerbosePvsStats mStats;

  //protected:

	/** Merge pvs 1 from begin iterator to end iterator with
		pvs 2 from begin iterator to end iterator.
	*/
	static void Merge(VerbosePvs<T, S> &mergedPvs, 
					  const typename std::vector<PvsEntry<T, S> >::const_iterator &aBegin,
					  const typename std::vector<PvsEntry<T, S> >::const_iterator &aEnd,
					  const typename std::vector<PvsEntry<T, S> >::const_iterator &bBegin,
					  const typename std::vector<PvsEntry<T, S> >::const_iterator &bEnd,
					  const int aSamples, 
					  const int bSamples);


	//////////////////////////////

	/// vector of PVS entries
	vector<PvsEntry<T, S> > mEntries; 

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

	/// Last sorted entry in the pvs (important for find and merge)
	int mLastSorted;

	int mQueriesSinceSort;
};


}

#endif