#ifndef __VERBOSEPVS_H
#define __VERBOSEPVS_H

#include <vector>
#include "common.h"
#include <math.h>
//#include "PvsBB.h"
#include "PvsBase.h"
#include "ObjectPvs.h"


namespace GtpVisibilityPreprocessor {

inline int operator< (PvsEntry<Intersectable*, PvsData> const &a,
                      PvsEntry<Intersectable*, PvsData> const &b)
{
  return a.mObject < b.mObject;
} 

template <typename T, typename S>
VerbosePvs<T, S>::VerbosePvs(const vector<PvsEntry<T, S> > &samples): 
mLastSorted(0)
{
	mEntries.reserve(samples.size());
	mEntries = samples;
	mSamples = samples.size();
}


template <typename T, typename S>
void VerbosePvs<T, S>::Sort()
{
	typename vector<PvsEntry<T, S> >::iterator it = mEntries.begin() + mLastSorted;
	typename vector<PvsEntry<T, S> >::iterator it_end = mEntries.end();

	// throw out double entries
	typename std::vector<PvsEntry<T, S> >::iterator newEnd = unique(it, it_end);
	sort(it, newEnd);
	
	// now merge sorted ranges
	ObjectPvs newPvs;
	Merge(newPvs, 
		  mEntries.begin(),
		  it, 
		  it,
		  newEnd, 
		  mSamples,
		  0);
	
	mEntries = newPvs.mEntries;
	mLastSorted = (int)mEntries.size();
	mQueriesSinceSort = 0;
}

template <typename T, typename S>
void VerbosePvs<T, S>::SimpleSort()
{
  //  sort(mEntries.begin(), mEntries.end());
  typename vector<PvsEntry<T, S> >::iterator it = mEntries.begin() + mLastSorted;
  
  sort(it, mEntries.end());
  inplace_merge(mEntries.begin(), it, mEntries.end());
  
  mLastSorted = (int)mEntries.size();
  mQueriesSinceSort = 0;
}


/**
   Compute continuous PVS difference of 'b' with respect to the base PVS (*this).
   Provides separatelly PVS reduction from PVS enlargement.

*/
template <typename T, typename S>
void
VerbosePvs<T, S>::ComputeContinuousPvsDifference(VerbosePvs<T, S> &b,
										  float &pvsReduction,
										  float &pvsEnlargement)
{
	pvsReduction = 0.0f;
	pvsEnlargement = 0.0f;

	// Uses sum of log differences, which corresponds to entropy
	typename vector<PvsEntry<T, S> >::iterator it;

	for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it) 
	{
		float bSumPdf = (*it).mData.mSumPdf;
		float aSumPdf = 0.0f;

		typename vector<PvsEntry<T, S> >::iterator oit;
		const bool entryFound = Find((*it).mObject, oit);		

		if (entryFound)
		{
			aSumPdf = (*it).mData.mSumPdf;

			// mark this entry as processed to avoid double counting
			(*it).mData.mSumPdf = -aSumPdf;
		}

#if 0
		const float diff = bSumPdf - aSumPdf;

		if (diff > 0.0f) 
		{
			pvsEnlargement += diff;
		} 
		else 
		{
			pvsReduction += -diff;
		}
#else
		if (!entryFound)
		{
			pvsEnlargement += 1.0f;
		}
#endif
	}

	for (it = mEntries.begin(); it != mEntries.end(); ++ it) 
	{
		float aSumPdf = (*it).mData.mSumPdf;
		float bSumPdf = 0.0f;
		if (aSumPdf < 0.0f) 
		{
			// this entry was already accounted for!
			// just revert it back
			(*it).mData.mSumPdf = -aSumPdf;
		} 
		else 
		{
		        typename vector<PvsEntry<T, S> >::iterator oit;
		
			const bool entryFound = b.Find((*it).mObject, oit);
						
			if (entryFound) {
				bSumPdf = (*oit).mData.mSumPdf;
			}
#if 0
			const float diff = bSumPdf - aSumPdf;

			if (diff > 0.0f) {
				pvsEnlargement += diff;
			} else {
				pvsReduction += -diff;
			}

#else
			if (!entryFound) 
				pvsReduction += 1.0f;
#endif
		}
	}
}


template <typename T, typename S>
int VerbosePvs<T, S>::Diff(const VerbosePvs<T, S> &b)
{
	int dif = 0;

	typename std::vector<PvsEntry<T, S> >::const_iterator it;

	for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
	{
	        typename vector<PvsEntry<T, S> >::iterator bit;
		const bool entryFound = Find((*it).first, bit);

		if (!entryFound) ++ dif;
	}

	return dif;
}


template <typename T, typename S> 
void VerbosePvs<T, S>::MergeInPlace(const VerbosePvs<T, S> &a)
{
	// early exit
	if (a.Empty())
	{
		return;
	}
	else if (Empty())
	{
		mEntries.reserve(a.GetSize());
		mEntries = a.mEntries;
		mSamples = a.mSamples;
		return;
	}

	ObjectPvs interPvs;
	
	Merge(interPvs, *this, a);
	
	mEntries.reserve(interPvs.GetSize());
	mEntries = interPvs.mEntries;
	mSamples = interPvs.mSamples;
}


template <typename T, typename S>
void VerbosePvs<T, S>::Merge(VerbosePvs<T, S> &mergedPvs, 
							 const VerbosePvs<T, S> &a, 
							 const VerbosePvs<T, S> &b)
{
        typename std::vector<PvsEntry<T, S> >::const_iterator ait = 
		a.mEntries.begin(), ait_end = a.mEntries.end();
	typename std::vector<PvsEntry<T, S> >::const_iterator bit = 
		b.mEntries.begin(), bit_end = b.mEntries.end();
	
	Merge(mergedPvs, 
		  ait, ait_end,
		  bit, bit_end,
		  a.mSamples,
		  b.mSamples);
}


template <typename T, typename S>
void VerbosePvs<T, S>::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)
{
        typename std::vector<PvsEntry<T, S> >::const_iterator ait = aBegin;
	typename std::vector<PvsEntry<T, S> >::const_iterator bit = bBegin;
	
	for (; (ait != aEnd); ++ ait)
	{
		Intersectable *aObj = (*ait).mObject;
		Intersectable *bObj = NULL;
		//Intersectable *bObjOld = NULL;
	
		const PvsEntry<T, S> &aEntry = (*ait);

		for (; (bit != bEnd) && ((*bit).mObject <= (*ait).mObject); ++ bit)
		{
			bObj = (*bit).mObject;

			// object found => add up probabilities
			if (bObj == aEntry.mObject)
			{
				PvsData newData(aEntry.mData.mSumPdf + (*bit).mData.mSumPdf);
				PvsEntry<T, S> entry(bObj, newData);
				mergedPvs.mEntries.push_back(entry);
			}
			else
			{
				mergedPvs.mEntries.push_back(*bit);
			}
		}

		// only push back if objects different 
		// (equal case is handled by second loop)
		if (aObj != bObj)
		{
			mergedPvs.mEntries.push_back(*ait);
		}
	}

	// add the rest
	for (; (bit != bEnd); ++ bit)
	{
		mergedPvs.mEntries.push_back(*bit);
	}

	mergedPvs.mSamples = aSamples + bSamples;
}


template <typename T, typename S> void VerbosePvs<T, S>::Clear(const bool trim)
{
	mEntries.clear();
	mSamples = 0;
	mLastSorted = 0;

	if (trim)
	{
		vector<PvsEntry<T,S> >().swap(mEntries);
	}
}


template <typename T, typename S> void VerbosePvs<T, S>::Trim()
{
	vector<PvsEntry<T,S> >(mEntries).swap(mEntries);
}


template <typename T, typename S> 
bool VerbosePvs<T, S>::Find(T sample,
			    typename vector<PvsEntry<T, S> >::iterator &it,
			    const bool checkDirty)
{
	bool found = false;
	
	PvsEntry<T, S> dummy(sample, PvsData());

	// only check clean part
	typename vector<PvsEntry<T, S> >::iterator sorted_end = mEntries.begin() + mLastSorted;
	mQueriesSinceSort++;

	// binary search
	it = lower_bound(mEntries.begin(), sorted_end, dummy);

	if ((it != mEntries.end()) && ((*it).mObject == sample))
		found = true;

	// sample not found yet => search further in the unsorted part
	if (!found && checkDirty) 
	{
	    typename vector<PvsEntry<T, S> >::iterator dit, dit_end = mEntries.end();

        for (dit = sorted_end; (dit != dit_end) && ((*dit).mObject != sample); ++ dit);
	
		if (dit != dit_end)
		{
			found = true;
			it = dit;
		}
	}

	return found;
}


template <typename T, typename S>
void VerbosePvs<T, S>::GetData(const int index, T &entry, S &data)
{
        typename std::vector<PvsEntry<T, S> >::iterator i = mEntries.begin();
	for (int k = 0; k != index && i != mEntries.end(); ++ i, ++ k);

	entry = (*i).first;
	data = (*i).second;
}


template <typename T, typename S>
float VerbosePvs<T, S>::AddSample(T sample, const float pdf)
{
	++ mSamples;
	
	typename vector<PvsEntry<T, S> >::iterator it;
	const bool entryFound = Find(sample, it);		

	if (entryFound)
	{	
		S &data = (*it).mData;
		data.mSumPdf += pdf;
		return data.mSumPdf;
	}
	else 
	{
		PvsEntry<T, S> entry(sample, pdf);
		mEntries.insert(it, entry);
		++ mLastSorted;
		return pdf;
	}
}


template <typename T, typename S>
void VerbosePvs<T, S>::AddSampleDirty(T sample, const float pdf)
{
	++ mSamples;
	mEntries.push_back(PvsEntry<T, S>(sample, pdf));
}
					 

template <typename T, typename S>
typename vector< PvsEntry<T, S> >::iterator 
VerbosePvs<T, S>::AddSample2(T sample, const float pdf)
{
	++ mSamples;
	
	typename vector<PvsEntry<T, S> >::iterator it;
	const bool entryFound = Find(sample, it);

	if (entryFound)
	{
		S &data = (*it).second;
		data->mSumPdf += pdf;
	}
	else 
	{
		PvsEntry<T, S> entry(sample, pdf);
		mEntries.insert(it, entry);
		++ mLastSorted;
	}

	return it;
}


template <typename T, typename S> 
bool VerbosePvs<T, S>::AddSampleDirtyCheck(T sample, const float pdf)
{
	++ mSamples;

	typename vector<PvsEntry<T, S> >::iterator it;
	const bool entryFound = Find(sample, it);

	if (entryFound) 
	{
		S &data = (*it).mData;
	  
		data.mSumPdf += pdf;
        return false;
	}
	else 
	{
		AddSampleDirty(sample, pdf);
		return true;
	}
}


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

	if (entryFound)  
	{
		S &data = (*it).mData;
		contribution = pdf / (data.mSumPdf + pdf);
		return false;
	}
	else 
	{
		contribution = 1.0f;
		return true;
	}
}

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

  mEntries.erase(it);
  -- mLastSorted; // wrong if sample was in tail!!
  // $$JB decrement only if the sample found
  -- mSamples;
  
}

template <typename T, typename S>
bool VerbosePvs<T, S>::RemoveSample(T sample, const float pdf)
{
	
	typename vector<PvsEntry<T, S> >::iterator it;
	const bool entryFound = Find(sample, it);

	if (!entryFound)
		return false;

	// $$JB decrement only if the sample found
	-- mSamples;

	S &data = (*it).mData;

	data.mSumPdf -= pdf;

	if (data.mSumPdf <= 0.0f)
	{
		mEntries.erase(it);
		-- mLastSorted; // wrong if sample was in tail!!
	}

	return true;
}


template <typename T, typename S>
int VerbosePvs<T, S>::SubtractPvs(const VerbosePvs<T, S> &pvs)
{
	const int samples = mSamples - pvs.mSamples;

	typename std::vector<PvsEntry<T, S> >::
	  const_iterator it, it_end = pvs.mEntries.end();

	// output PVS of view cell
	for (it = pvs.mEntries.begin(); it != it_end; ++ it) 
		RemoveSample((*it).mObject, (*it).mData.mSumPdf);

	mSamples = samples;

	return GetSize();
}


template <typename T, typename S>
void VerbosePvs<T, S>::CollectEntries(std::vector<T> &entries)
{
        typename std::vector<PvsEntry<T, S> >::
	   const_iterator it, it_end = mEntries.end();

	// output PVS of view cell
	for (it = mEntries.begin(); it != it_end; ++ it) 
		entries.push_back((*it)->first);
}


template <typename T, typename S>
void VerbosePvs<T, S>::NormalizeMaximum()
{
	typename std::vector<PvsEntry<T, S> >::
		const_iterator it, it_end = mEntries.end();

	float maxPdfSum = -1.0f;

	// output PVS of view cell
	for (it = mEntries.begin(); it != it_end; ++ it) {
		float sum = (*it)->second.sumPdf;
		if (sum > maxPdfSum)
			maxPdfSum = sum;
	}

	maxPdfSum = 1.0f / maxPdfSum;

	for (it = mEntries.begin(); it != it_end; ++ it) {
		(*it)->second.sumPdf *= maxPdfSum;
	}
}


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


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


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

	ComputeContinuousPvsDifference(pvs,	pvsReduction, pvsEnlargement);
	return pvsReduction + pvsEnlargement;
}


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

}

#endif