#ifndef __PVS_H
#define __PVS_H

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

namespace GtpVisibilityPreprocessor {

class KdNode;
class BspNode;
class Ray;
class Intersectable;
class ViewCell;


template<typename T>
struct LtSample 
{
    bool operator()(const T a, const T b) const
    {
		return a < b;
	} 
};

/** Information stored with a PVS entry. Consists of the number
	the object was seen from the view cell.
*/
class PvsData {
public:
  // sum of probability density of visible sample rays
  float mSumPdf;

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

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


class MailablePvsData 
{
////////////////////////////
//  Mailing stuff
protected:
	int mMailbox;

public:
  // 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; }
//////////////////////////////////////////

  // 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!!!
  float GetVisibility() 
  { 
	  return mSumPdf; 
  }
};


/** 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 Pvs
{
public:
  Pvs(): /*mSamples(0), */mEntries() {}
  
  //virtual ~Pvs();
    
  /** Compresses PVS lossless or lossy.
  */
  int Compress() {return 0;}
  int GetSize() const {return (int)mEntries.size();}
  bool Empty() const {return mEntries.empty();}

  /** Normalize the visibility of entries in order to get comparable
	  results 
  */
  void NormalizeMaximum();
  
  /** Merges pvs of a into this pvs.
   */
  void Merge(const Pvs<T, S> &a);
  
  /** Difference of pvs to pvs b.
	  @returns number of different entries.
  */
  int Diff(const Pvs<T, S> &b);
  
  /** Finds sample in PVS.
	  @returns sample if found, NULL otherwise.
  */
  S *Find(T sample);

  bool GetSampleContribution(T sample, const float pdf, float &contribution);
  
  /** Adds sample to PVS. 
	  @contribution contribution of sample (0 or 1)
	  @returns true if sample was not already in PVS.
  */
  bool AddSample(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.
	  @returns PvsData
  */
  S *AddSample2(T sample, const float pdf);

  /** Adds one pvs to another one.
	  @returns new pvs size
  */
  int AddPvs(const Pvs<T, S> &pvs);

  /** Subtracts one pvs from another one.
  WARNING: could contains bugs
	  @returns new pvs size
  */
  int SubtractPvs(const Pvs<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);

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

  /** Clears the pvs.
  */
  void Clear();

  /** Compute continuous PVS difference */
  float GetPvsHomogenity(Pvs<T, S> &pvs) {
	float 
	  pvsReduction,
	  pvsEnlargement;
	
	ComputeContinuousPvsDifference(pvs,
								   pvsReduction,
								   pvsEnlargement);
	
	return pvsReduction + pvsEnlargement;
  }

					  
					  
  /// Map of PVS entries
  std::map<T, S, LtSample<T> > mEntries;
};



/**
   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
Pvs<T, S>::ComputeContinuousPvsDifference(Pvs<T, S> &b,
									   float &pvsReduction,
									   float &pvsEnlargement)
{
	pvsReduction = 0.0f;
	pvsEnlargement = 0.0f;
  // Uses sum of log differences, which corresponds to entropy
  std::map<T, S, LtSample<T> >::iterator it;
  
  for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it) 
  {
	float bSumPdf = (*it).second.mSumPdf;
	float aSumPdf = 0.0f;
	S *data = Find((*it).first);		
	
	if (data) 
	{
		aSumPdf = data->mSumPdf;
		// mark this entry as processed to avoid double counting
		data->mSumPdf = -aSumPdf;
	}

#if 0
	float diff = bSumPdf - aSumPdf;
	
	if (diff > 0.0f) {
	  pvsEnlargement += diff;
	} else {
	  pvsReduction += -diff;
	}
#else
	if (!data)
	  pvsEnlargement += 1.0f;
#endif
  }
  
  for (it = mEntries.begin(); it != mEntries.end(); ++ it) {
	float aSumPdf = (*it).second.mSumPdf;
	float bSumPdf = 0.0f;
	if (aSumPdf < 0.0f) {
	  // this entry was already accounted for!
	  // just revert it back
	  (*it).second.mSumPdf = -aSumPdf;
	} else {
	  S *data = b.Find((*it).first);
	  if (data) {
		bSumPdf = data->mSumPdf;
	  }
#if 0
	  float diff = bSumPdf - aSumPdf;
	  
	  if (diff > 0.0f) {
		pvsEnlargement += diff;
	  } else {
		pvsReduction += -diff;
	  }

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

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

	std::map<T, S, LtSample<T> >::const_iterator it;

	for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
	{
		S data = Find((*it).first);		
		if (!data) ++ dif;
	}

	return dif;
}

template <typename T, typename S> void Pvs<T, S>::Merge(const Pvs<T, S> &a)
{
	std::map<T, S, LtSample<T> >::const_iterator it;

	for (it = a.mEntries.begin(); it != a.mEntries.end(); ++ it)
	{
		AddSample((*it).first, (*it).second.mSumPdf);
	}
}


template <typename T, typename S> void Pvs<T, S>::Clear()
{
	mEntries.clear();
}


template <typename T, typename S> 
S *Pvs<T, S>::Find(T sample)
{
  std::map<T, S, LtSample<T> >::iterator i = mEntries.find(sample);

  if (i != mEntries.end()) 
  {
	  return &(*i).second;
  } 
  else
  {
	  return NULL;
  }
}

template <typename T, typename S>
void Pvs<T, S>::GetData(const int index,
					 T &entry,
					 S &data)
{
  std::map<T, S, LtSample<T> >::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
Pvs<T, S>::AddSample(T sample, const float pdf)
{
	S *data = Find(sample);
  
	if (data)  
	{
		data->mSumPdf += pdf;
		return data->mSumPdf;
	}
	else 
	{
		mEntries[sample] = S(pdf);
		return pdf;
	}
}


template <typename T, typename S>
S * Pvs<T, S>::AddSample2(T sample, const float pdf)
{
	S *data = Find(sample);
  
	if (data)  
	{
		data->mSumPdf += pdf;
	}
	else 
	{
		mEntries[sample] = S(pdf);
		data = Find(sample);
	}

	return data;
}

template <typename T, typename S> 
bool Pvs<T, S>::AddSample(T sample,
				  const float pdf,
				  float &contribution)
{
  S *data = Find(sample);
  
  if (data)  
  {
	data->mSumPdf += pdf;
	contribution = pdf / data->mSumPdf;
	return false;
  }
  else {
	mEntries[sample] = S(pdf);
	contribution = 1.0f;
	return true;
  }
}

template <typename T, typename S>
bool
Pvs<T, S>::GetSampleContribution(T sample,
								 const float pdf,
								 float &contribution) 
{
  S *data = Find(sample);
  
  if (data)  {
	contribution = pdf / (data->mSumPdf + pdf);
	return false;
  }
  else {
	contribution = 1.0f;
	return true;
  }
}

template <typename T, typename S>
bool Pvs<T, S>::RemoveSample(T sample,
						  const float pdf)
{
  std::map<T, S, LtSample<T> >::
	iterator it = mEntries.find(sample);
  
  if (it == mEntries.end())
	return false;
  
  S *data = &(*it).second;
  
  data->mSumPdf -= pdf;

  if (data->mSumPdf <= 0.0f)
  {
	  mEntries.erase(it);
  }

  return true;
}

template <typename T, typename S>
int Pvs<T, S>::AddPvs(const Pvs<T, S> &pvs)
{
  std::map<T, S, LtSample<T> >::
	const_iterator it, it_end = pvs.mEntries.end();
  
  float contri;
  // output PVS of view cell
  for (it = pvs.mEntries.begin(); it != it_end; ++ it)
  {	
	  AddSample((*it).first, (*it).second.mSumPdf, contri);
  }
  
  return GetSize();
}
 
template <typename T, typename S>
int Pvs<T, S>::SubtractPvs(const Pvs<T, S> &pvs)
{
  std::map<T, S, LtSample<T> >::
	const_iterator it, it_end = pvs.mEntries.end();
  
  // output PVS of view cell
  for (it = pvs.mEntries.begin(); it != it_end; ++ it) 
	RemoveSample((*it).first, (*it).second.mSumPdf);
  
  return GetSize();
}

template <typename T, typename S>
void Pvs<T, S>::CollectEntries(std::vector<T> &entries)
{
	std::map<T, S, LtSample<T> >::
		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 Pvs<T, S>::NormalizeMaximum()
{
  std::map<T, S, LtSample<T> >::
	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 > maxSum)
	  maxSum = sum;
  }

  maxSum = 1.0f / maxSum;

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


/** Class instantiating the Pvs template for kd tree nodes.
*/
class KdPvs: public Pvs<KdNode *, PvsData>
{
public:
	int Compress();
};


class ObjectPvs: public Pvs<Intersectable *, PvsData>
{
public:
	/** Counts object int the pvs. Different to method "GetSize", not
		only the raw container size is returned,
		but the individual contributions of the entries are summed up.
	*/
	int CountObjectsInPvs() const;
};


////////////
//-- typedefs

typedef std::map<KdNode *, PvsData, LtSample<KdNode *> > KdPvsMap;
typedef std::map<Intersectable *, PvsData, LtSample<Intersectable *> > ObjectPvsMap;
typedef std::map<ViewCell *, MailablePvsData, LtSample<ViewCell *> > ViewCellPvsMap;


typedef Pvs<ViewCell *, MailablePvsData> ViewCellPvs;

}

#endif