#ifndef PHOTONKDTREE
 #define PHOTONKDTREE
 
 #include "Photon.hxx"
 #include "PhotonHeap.hxx"
 #include <fcntl.h>
 #include <sys/mman.h>
 
 // A helper class to compare photon positions according to the given dimension
 class PhotonCompare
 {
 	// Dimension in which 'less' is tested
 	int dimension;
 
 public:
 	PhotonCompare(int dimension)
 		: dimension(dimension)
 	{};
 
 	bool operator()(const Photon *less, const Photon *greater) const
 	{
 		// Special case: If the same point is hit twice , the addresses are compared
 		// (Otherwise there could be maldefined split locations!)
 		if (less->point[dimension] == greater->point[dimension])
 			return (less < greater);
 
 		return (less->point[dimension] < greater->point[dimension]);
 	};
 };
 
 // A helper class to compare photon positions against a given reference point, according to the distance
 class PhotonDistanceCompare
 {
 	Vec3f point;
 public:
 	PhotonDistanceCompare(Vec3f point)
 		: point(point)
 	{};
 
 	bool operator()(const Photon *less, const Photon *greater) const
 	{
 		Vec3f lconn = less->point - point,
 		      gconn = greater->point - point;
 		float ldist = Dot(lconn, lconn),
 		      gdist = Dot(gconn, gconn);
 		
 		// Special case: If the same point is hit twice , the addresses are compared
 		// (Otherwise there could be maldefined split locations!)
 		if (ldist == gdist)
 			return (less < greater);
 
 		return (ldist < gdist);
 	};
 };
 
 // The tree itself
 class PhotonKDTree
 {
 public:
 	Photon       *resident;
 	PhotonKDTree *less,
 	             *more;
 	int          count,
 	             dimension;
 
 	PhotonKDTree()
 		: resident(NULL), less(NULL), more(NULL), count(0), dimension(0)
 	{};
 
 	PhotonKDTree(Photon *newone)
 		: resident(newone), less(NULL), more(NULL), count(1), dimension(0)
 	{};
 
 	PhotonKDTree(vector<Photon*> &list, int from = 0, int to = -1)
 		: resident(NULL), less(NULL), more(NULL), count(0), dimension(0)
 	{
 		// -1 makes the method detect the to automatically
 		if (to == -1)
 			to = list.size() - 1;
 
 		count = to - from + 1;
 
 		Vec3f minimum = Vec3f( Infinity),
 		      maximum = Vec3f(-Infinity);
 
 		// Get the split dimension
 		for (int i = from; i <= to; ++i)
 		{
 			minimum = Min(minimum, list[i]->point);
 			maximum = Max(maximum, list[i]->point);
 		}
 
 		float distance    = 0.0f,
 		      newdistance;
 		for (int i = 0; i < 3; ++i)
 		{
 			newdistance = maximum[i] - minimum[i]; 
 			if (newdistance > distance)
 			{
 				distance  = newdistance;
 				dimension = i;
 			}
 		}
 
 		// Sort the list partially (into two halfs)
 		int middle = (to + from) / 2;
 		nth_element(&list[from], &list[middle], &list[to], PhotonCompare(dimension));
 
 		// And split it recursively into two subtrees
 		resident = list[middle];
 
 		if (middle - 1 >= from)
 			less = new PhotonKDTree(list, from, middle - 1);
 
 		if (middle + 1 <= to)
 			more = new PhotonKDTree(list, middle + 1, to);
 	};
 
 	// Loads a KD tree from a file
 	PhotonKDTree(string filename)
 		: resident(NULL), less(NULL), more(NULL), count(0), dimension(0)
 	{
 		int fd = open(filename.c_str(), O_RDONLY, (mode_t)0600);
 		if (fd == -1)
 		{
 			cerr << "Could not open PhotonMap file [pass 1]!" << endl;
 			exit(0);
 		}
 
 		char photonword[10] = "         ";
 		read(fd, photonword, 9);
 
 		if (strcmp(photonword, "PHOTONMAP"))
 		{
 			cerr << "Wrong file format!" << endl;
 			exit(0);
 		}
 
 		int count;
 		read(fd, &count, sizeof(int));
 		close(fd);
 
 		// Be aware of wild pointer arithmetics! ;-)
 		void *map;
 		int  photonsize = 3 * sizeof(Vec3f);
 		int  filesize   = 9                                        // The word "PHOTONMAP"
 		                + count * (3 * sizeof(int) + photonsize);  // Node entries
 
 		fd = open(filename.c_str(), O_RDONLY, (mode_t)0600);
 		if (fd == -1)
 		{
 			cerr << "Could not open PhotonMap file [pass 2]!" << endl;
 			exit(0);
 		}
 
 		// Map the file into virtual memory
 		map = mmap(0, filesize, PROT_READ, MAP_SHARED, fd, 0);
 		if (map == MAP_FAILED)
 		{
 			close(fd);
 			cerr << "Could not mmap PhotonMap file!" << endl;
 			exit(0);
 		}
 
 		BuildTree(reinterpret_cast<char*>(map) + 9, photonsize);
 
 		// Unmap the file again
 		if (munmap(map, filesize) == -1)
 			cerr << "Could not munmap PhotonMap file!" << endl;
 
 		close(fd);
 
 	};
 
 	// Deserializer, building the corresponding tree
 	PhotonKDTree(char *pointer, int photonsize)
 		: resident(NULL), less(NULL), more(NULL), count(0), dimension(0)
 	{
 		BuildTree(pointer, photonsize);
 	};
 
 	virtual ~PhotonKDTree(){};
 
 	virtual void BuildTree(char *pointer, int photonsize)
 	{
 		int lcount;
 		memmove(&count,     pointer                  , sizeof(int));
 		memmove(&dimension, pointer +     sizeof(int), sizeof(int));
 		memmove(&lcount,    pointer + 2 * sizeof(int), sizeof(int));
 
 		resident = new Photon(pointer + 3 * sizeof(int));
 
 		int offset = 3 * sizeof(int) + photonsize;
 		
 		if (lcount > 0)
 			less = new PhotonKDTree(pointer + offset, photonsize);
 
 		if (count - lcount > 1)
 			more = new PhotonKDTree(pointer + offset * (1 + lcount), photonsize);
 	};
 
 	// Serializes this current part of the tree into a virtual memory range
 	virtual void Serialize(char *pointer, int photonsize)
 	{
 		int lcount = (less) ? less->count : 0;
 
 		memmove(pointer                  , &count,     sizeof(int));
 		memmove(pointer +     sizeof(int), &dimension, sizeof(int));
 		memmove(pointer + 2 * sizeof(int), &lcount,    sizeof(int));
 
 		resident->Serialize(pointer + 3 * sizeof(int));
 
 		int offset = 3 * sizeof(int) + photonsize;
 
 		if (less)
 			less->Serialize(pointer + offset, photonsize);
 
 		if (more)
 			more->Serialize(pointer + offset * (1 + lcount), photonsize);
 	}
 
 	// Stores the KD tree to a file
 	virtual void Save(string filename)
 	{
 		// Be aware of wild pointer arithmetics! ;-)
 		cout << "INFO: The tree contains " << count << " photons that will now be stored..." << endl;
 
 		void *map;
 		int  photonsize = 3 * sizeof(Vec3f);
 		int  filesize   = 9                                        // The word "PHOTONMAP"
 		                + count * (3 * sizeof(int) + photonsize);  // Node entries
 
 		int fd = open(filename.c_str(), O_RDWR | O_CREAT | O_TRUNC, (mode_t)0600);
 		if (fd == -1)
 		{
 			cerr << "Could not open PhotonMap file!" << endl;
 			exit(0);
 		}
 
 		// Resize the file to required needs
 		int result = lseek(fd, filesize - 1, SEEK_SET);
 		if (result == -1)
 		{
 			close(fd);
 			cerr << "Could not resize PhotonMap file [seek]!" << endl;
 			exit(0);
 		}
 
 		result = write(fd, "", 1);
 		if (result != 1)
 		{
 			close(fd);
 			cerr << "Could not resize PhotonMap file [write]!" << endl;
 			exit(0);
 		}
 
 		// Map the file into virtual memory
 		map = mmap(0, filesize, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
 		if (map == MAP_FAILED)
 		{
 			close(fd);
 			cerr << "Could not mmap PhotonMap file!" << endl;
 			exit(0);
 		}
 
 		char photonword[10] = "PHOTONMAP";
 		memmove(map, photonword, 9);
 		Serialize(reinterpret_cast<char*>(map) + 9, photonsize);
 
 		// Unmap the file again
 		if (munmap(map, filesize) == -1)
 			cerr << "Could not munmap PhotonMap file!" << endl
 			     << "The file may be corrupted..." << endl;
 
 		close(fd);
 	};
 
 	// Get the neighborhood (to calculate the radiance estimate)
 	virtual void GetNextPhotons(PhotonHeap &heap)
 	{
 		float distance = resident->point[dimension] - heap.reference[dimension];
 
 		if (less && distance >= 0)
 		{
 			less->GetNextPhotons(heap);
 
 			if (more && distance < heap.maxdist)
 				more->GetNextPhotons(heap);
 		}
 		else if (more && distance <= 0)
 		{
 			more->GetNextPhotons(heap);
 
 			if (less && -distance < heap.maxdist)
 				less->GetNextPhotons(heap);
 		}
 
 		// Insert the photon if it is close enough
 		DistantPhoton *dphoton = new DistantPhoton(resident, heap.reference);
 
 		if (dphoton->distance < heap.maxdist2)
 			heap.Insert(dphoton);
 		else
 			delete dphoton;
 	};
 
 };
 
 #endif