#ifndef __PVS_H
#define __PVS_H

#include <map>

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;
	} 
};

//typedef std::map<T *, PvsData<T>, LtSample<T>> PvsMap<T>;

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

template<typename T>
class Pvs
{
public:
	Pvs(): mSamples(0), mEntries() {}

	int mSamples;

	int Compress() {return 0;}
	int GetSize() const {return (int)mEntries.size();}
	bool Empty() const {return mEntries.size() == 0;}
	/** 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);

	PvsData<T> *Find(T sample);
	int AddSample(T sample);

	void GetData(const int index, T &entry, PvsData<T> &data);
	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)
{
	int result;
	PvsData<T> *data = Find(sample);

	if (data) 
	{
		data->mVisibleSamples ++;
		result = 0;
	
	} 
	else 
	{
		mEntries[sample] = PvsData<T>(1);
		result = 1;
	}

	return  result;
}

/** 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<ViewCellKdNode *, PvsData<ViewCellKdNode *>, LtSample<ViewCellKdNode *> > ViewCellKdPvsMap;
typedef std::map<Intersectable *, PvsData<Intersectable *>, LtSample<Intersectable *> > ViewCellPvsMap;
typedef PvsData<Intersectable *> ViewCellPvsData;
typedef PvsData<KdNode *> KdPvsData;
typedef Pvs<ViewCellKdNode *> ViewCellKdPvs;
typedef Pvs<Intersectable *> ViewCellPvs;


#endif