#ifndef __PVS_H
#define __PVS_H

#include <map>
#include <vector>

class KdNode;
class BspNode;
class Ray;
class Intersectable;
class ViewCellKdNode;

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.
*/

template<typename T> 
struct PvsData {
  int mVisibleSamples;
  PvsData<T>() {}
  PvsData<T>(const int samples): mVisibleSamples(samples) {}
};

/** Template class representing the Potentially Visible Set (PVS) 
	mainly from a view cell, but also e.g., from objects.
*/
template<typename T>
class Pvs
{
public:
  Pvs(): /*mSamples(0), */mEntries() {}
  
  //int mSamples;
  
  /** Compresses PVS lossless or lossy.
  */
  int Compress() {return 0;}
  int GetSize() const {return (int)mEntries.size();}
  bool Empty() const {return mEntries.empty();}
  
  /** Merges pvs of a and pvs of b into this pvs.
   */
  void Merge(const Pvs<T> &a, const Pvs<T> &b);
  
  /** Difference of pvs to pvs b.
	  @returns number of different entries.
  */
  int Diff(const Pvs<T> &b);
  
  /** Finds sample in PVS.
	  @returns sample if found, NULL otherwise.
  */
  PvsData<T> *Find(T sample);
  
  /** Adds sample to PVS. 
	  @contribution contribution of sample (0 or 1)
	  @returns true if sample was not already in PVS.
  */
  bool AddSample(T sample, float &contribution);

  /** Adds sample to PVS.
	  @returns contribution of sample (0 or 1)
  */
  int AddSample(T sample);

  /** Adds one pvs to another one.
	  @returns new pvs size
  */
  int AddPvs(const Pvs<T> &pvs);
  /** Subtracts one pvs from another one.
	  @returns new pvs size
  */
  int SubtractPvs(const Pvs<T> &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, PvsData<T> &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 visibleSampels number of references to be removed
  */
  bool RemoveSample(T sample, const int visibleSamples);

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

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

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

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

	return dif;
}

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

	// todo: copy all elements instead of inserting
	for (it = a.mEntries.begin(); it != a.mEntries.end(); ++ it)
		mEntries.insert(*it);
	
	for (it = b.mEntries.begin(); it != b.mEntries.end(); ++ it)
	{
		PvsData<T> *data = Find((*it).first);
		
		if (data)
			data->mVisibleSamples += (*it).second.mVisibleSamples;
		else
			mEntries.insert(*it);
	}
}

template <typename T>
PvsData<T> *Pvs<T>::Find(T sample)
{
  std::map<T, PvsData<T>, LtSample<T> >::iterator i = mEntries.find(sample);
  if (i != mEntries.end()) {
    return &(*i).second;
  } else
    return NULL;
}

template <typename T>
void Pvs<T>::GetData(const int index,
					 T &entry,
					 PvsData<T> &data)
{
  std::map<T, PvsData<T>, 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>
int Pvs<T>::AddSample(T sample)
{
  float dummy;
  return AddSample(sample, dummy) ? 1 : 0;
}

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

template <typename T>
bool Pvs<T>::RemoveSample(T sample, const int visibleSamples)
{
	std::map<T, PvsData<T>, LtSample<T> >::
		iterator it = mEntries.find(sample);

	if (it == mEntries.end())
		return false;

	PvsData<T> *data = &(*it).second;
  
	data->mVisibleSamples -= visibleSamples;
	if (data->mVisibleSamples <= 0)
		mEntries.erase(it);

	return true;
}

template <typename T>
int Pvs<T>::AddPvs(const Pvs<T> &pvs)
{
	std::map<T, PvsData<T>, 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, contri);

	return GetSize();
}
 
template <typename T>
int Pvs<T>::SubtractPvs(const Pvs<T> &pvs)
{
	std::map<T, PvsData<T>, 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.mVisibleSamples);

	return GetSize();
}

template <typename T>
void Pvs<T>::CollectEntries(std::vector<T> &entries)
{
	std::map<T, PvsData<T>, 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);
}

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

typedef std::map<KdNode *, PvsData<KdNode *>, LtSample<KdNode *> > KdPvsMap;
typedef std::map<Intersectable *, PvsData<Intersectable *>, LtSample<Intersectable *> > ObjectPvsMap;
typedef PvsData<Intersectable *> ObjectPvsData;
typedef PvsData<KdNode *> KdPvsData;

typedef Pvs<Intersectable *> ObjectPvs;


#endif