#include "quadtree.h"

Quadtree::Quadtree()
{
	_nwquad = NULL;
	_nequad = NULL;
	_sequad = NULL;
	_swquad = NULL;
}

Quadtree::Quadtree(Image::GrayImage& mask, unsigned int upleftx, unsigned int uplefty, unsigned int bottomrightx, unsigned int bottomrighty)
{
	upperleft(upleftx, uplefty);
	bottomright(bottomrightx, bottomrighty);
	//leaf(true); //checkSubdivide will set a flag
	_nwquad = NULL;
	_nequad = NULL;
	_sequad = NULL;
	_swquad = NULL;
	checkSubdivide(*this, mask);
}

Quadtree::~Quadtree()
{
	destroy_tree(this, 0);
}

void Quadtree::upperleftx(unsigned int upleftx)
{
	_upleftx = upleftx;
}

void Quadtree::upperlefty(unsigned int uplefty)
{
	_uplefty = uplefty;
}

void Quadtree::bottomrightx(unsigned int bottomrightx)
{
	_bottomrightx = bottomrightx;
}

void Quadtree::bottomrighty(unsigned int bottomrighty)
{
	_bottomrighty = bottomrighty;
}

void Quadtree::updateTree(Image::GrayImage& mask)
{
	destroy_tree(this, 0);
	upperleft(0, 0);
	bottomright(mask.width()-1, mask.height()-1);
	//leaf(true); //checkSubdivide will set a flag
	checkSubdivide(*this, mask);
}

void Quadtree::destroy_tree(Quadtree* currentQuad, int d)
{
	if(currentQuad->_nwquad != 0)
	{
		destroy_tree(currentQuad->_nwquad, d+1);
		currentQuad->_nwquad = 0;
	}

	if(currentQuad->_nequad != 0)
		{
			destroy_tree(currentQuad->_nequad, d+1);
			currentQuad->_nequad = 0;
		}

	if(currentQuad->_swquad != 0)
	{
		destroy_tree(currentQuad->_swquad, d+1);
		currentQuad->_swquad = 0;
	}

	if(currentQuad->_sequad != 0)
		{
			destroy_tree(currentQuad->_sequad, d+1);
			currentQuad->_sequad = 0;
		}

	if(d > 0)
		{
			delete currentQuad;
//			currentQuad = NULL;
		}
}

/*
void Quadtree::leaf(bool leaf)
{
	_leaf = leaf;
}
*/

bool Quadtree::leaf()
{
	return _coverage == COVERED || _coverage == UNCOVERED;
}

void Quadtree::upperleft(unsigned int upleftx, unsigned int uplefty)
{
	_upleftx = upleftx;
	_uplefty = uplefty;
}

void Quadtree::bottomright(unsigned int bottomrightx, unsigned int bottomrighty)
{
	_bottomrightx = bottomrightx;
	_bottomrighty = bottomrighty;
}

unsigned int Quadtree::width()
{
	return _bottomrightx - _upleftx + 1;
}

unsigned int Quadtree::height()
{
	return _bottomrighty - _uplefty + 1;
}


void Quadtree::subdivide(Quadtree& currentQuad, Image::GrayImage& mask)
{
	currentQuad._nwquad = new Quadtree(mask, currentQuad._upleftx, currentQuad._uplefty, currentQuad._upleftx + currentQuad.width()/2, currentQuad._uplefty + currentQuad.height()/2) ;
	
	currentQuad._nequad = new Quadtree(mask, currentQuad._upleftx + currentQuad.width()/2 /*+ 1*/, currentQuad._uplefty, currentQuad._bottomrightx, currentQuad._uplefty + currentQuad.height()/2);
	
	currentQuad._sequad = new Quadtree(mask, currentQuad._upleftx + currentQuad.width()/2 /*+ 1*/, currentQuad._uplefty + currentQuad.height()/2 /*+ 1*/, currentQuad._bottomrightx, currentQuad._bottomrighty);
	
	currentQuad._swquad = new Quadtree(mask, currentQuad._upleftx, currentQuad._uplefty + currentQuad.height()/2 /*+ 1*/, currentQuad._upleftx + currentQuad.width()/2, currentQuad._bottomrighty);
	
	//checkSubdivide on the newly created quads;
	//moved to constructor
}

void Quadtree::subdivide(Quadtree* currentQuad, Image::GrayImage& mask)
{
	currentQuad->_nwquad = new Quadtree(mask, currentQuad->_upleftx, currentQuad->_uplefty, currentQuad->_upleftx + currentQuad->width()/2, currentQuad->_uplefty + currentQuad->height()/2) ;
	
	currentQuad->_nequad = new Quadtree(mask, currentQuad->_upleftx + currentQuad->width()/2 /*+ 1*/, currentQuad->_uplefty, currentQuad->_bottomrightx, currentQuad->_uplefty + currentQuad->height()/2);
	
	currentQuad->_sequad = new Quadtree(mask, currentQuad->_upleftx + currentQuad->width()/2 /*+ 1*/, currentQuad->_uplefty + currentQuad->height()/2 /*+ 1*/, currentQuad->_bottomrightx, currentQuad->_bottomrighty);
	
	currentQuad->_swquad = new Quadtree(mask, currentQuad->_upleftx, currentQuad->_uplefty + currentQuad->height()/2 /*+ 1*/, currentQuad->_upleftx + currentQuad->width()/2, currentQuad->_bottomrighty);
	
	//checkSubdivide on the newly created quads;
	//moved to constructor
}

void Quadtree::checkSubdivide(Image::GrayImage& mask)
{
	checkSubdivide(*this, mask);
}

void Quadtree::checkSubdivide(Quadtree& currentQuad, Image::GrayImage& mask)
{
	/*
	if(mask.getPixel(currentQuad._upleftx, currentQuad._uplefty) == 0)
		currentQuad._coverage = COVERED;
	else currentQuad._coverage = UNCOVERED;
	bool stop = false;
	for(unsigned int y=currentQuad._uplefty; y<=currentQuad._bottomrighty && !stop; y++)
		for(unsigned int x=currentQuad._upleftx; x<=currentQuad._bottomrightx && !stop; x++) {
			//if ((mask.getPixelAlpha(x,y) != 0 && currentQuad._coverage == COVERED) || (mask.getPixelAlpha(x,y) != 255 && currentQuad._coverage == UNCOVERED)) {
			if ((mask.getPixel(x,y) != 0 && currentQuad._coverage == COVERED) || (mask.getPixel(x,y) != 255 && currentQuad._coverage == UNCOVERED)) {
				currentQuad._coverage = MIXED;
				stop = true;
			}
		}
	if (stop && currentQuad.width() >= 4 && currentQuad.height() >= 4)
		subdivide(currentQuad, mask);
	*/
	_pixelvote = 0;

	if(mask.getPixel(currentQuad._upleftx, currentQuad._uplefty))
		currentQuad._coverage = UNCOVERED;
	else 
		currentQuad._coverage = COVERED;
	
	if(currentQuad.width() > MIN_QUAD_SIZE && currentQuad.height() > MIN_QUAD_SIZE)
	{
		for(unsigned int y=currentQuad._uplefty; y<=currentQuad._bottomrighty ; y++)
			for(unsigned int x=currentQuad._upleftx; x<=currentQuad._bottomrightx ; x++) {
				if ((mask.getPixel(x,y) != 0 && currentQuad._coverage == COVERED) || (mask.getPixel(x,y) != 255 && currentQuad._coverage == UNCOVERED)) {
					currentQuad._coverage = MIXED;
					x = currentQuad._bottomrightx;	//ensure the loops terminate after return from subdivide
					y = currentQuad._bottomrighty;
					subdivide(currentQuad, mask);
				}
			}
	}
	else
	{
		for(unsigned int y=currentQuad._uplefty; y<=currentQuad._bottomrighty ; y++)
		{
			for(unsigned int x=currentQuad._upleftx; x<=currentQuad._bottomrightx ; x++) 
			{
				if(mask.getPixel(x,y))
					_pixelvote++;
				if(_pixelvote >= currentQuad.width()*currentQuad.height()/3)
				{
					y=currentQuad._uplefty;
					x=currentQuad._upleftx;
					for(y=currentQuad._uplefty; y<=currentQuad._bottomrighty ; y++)
						for(x=currentQuad._upleftx; x<=currentQuad._bottomrightx ; x++) 
							mask.setPixel(x, y, 255);
					currentQuad._coverage = UNCOVERED;
					y=currentQuad._bottomrighty;
					x=currentQuad._bottomrightx;
				}
			}
		}
		if(_pixelvote < currentQuad.width()*currentQuad.height()/3)
		{
			currentQuad._coverage = COVERED;
			for(unsigned int y=currentQuad._uplefty; y<=currentQuad._bottomrighty ; y++)
				for(unsigned int x=currentQuad._upleftx; x<=currentQuad._bottomrightx ; x++) 
					mask.setPixel(x, y, 0);
		}
	}
}

void Quadtree::checkSubdivide(Quadtree* currentQuad, Image::GrayImage& mask)
{
	_pixelvote = 0;

	if(mask.getPixel(currentQuad->_upleftx, currentQuad->_uplefty))
		currentQuad->_coverage = UNCOVERED;
	else 
		currentQuad->_coverage = COVERED;
	
	if(currentQuad->width() > MIN_QUAD_SIZE && currentQuad->height() > MIN_QUAD_SIZE)
	{
		for(unsigned int y=currentQuad->_uplefty; y<=currentQuad->_bottomrighty ; y++)
			for(unsigned int x=currentQuad->_upleftx; x<=currentQuad->_bottomrightx ; x++) {
				if ((mask.getPixel(x,y) != 0 && currentQuad->_coverage == COVERED) || (mask.getPixel(x,y) != 255 && currentQuad->_coverage == UNCOVERED)) {
					currentQuad->_coverage = MIXED;
					x = currentQuad->_bottomrightx;	//ensure the loops terminate after return from subdivide
					y = currentQuad->_bottomrighty;
					subdivide(currentQuad, mask);
				}
			}
	}
	else
	{
		for(unsigned int y=currentQuad->_uplefty; y<=currentQuad->_bottomrighty ; y++)
		{
			for(unsigned int x=currentQuad->_upleftx; x<=currentQuad->_bottomrightx ; x++) 
			{
				if(mask.getPixel(x,y))
					_pixelvote++;
				if(_pixelvote >= currentQuad->width()*currentQuad->height()/3)
				{
					y=currentQuad->_uplefty;
					x=currentQuad->_upleftx;
					for(y=currentQuad->_uplefty; y<=currentQuad->_bottomrighty ; y++)
						for(x=currentQuad->_upleftx; x<=currentQuad->_bottomrightx ; x++) 
							mask.setPixel(x, y, 255);
					currentQuad->_coverage = UNCOVERED;
					y=currentQuad->_bottomrighty;
					x=currentQuad->_bottomrightx;
				}
			}
		}
		if(_pixelvote < currentQuad->width()*currentQuad->height()/3)
		{
			currentQuad->_coverage = COVERED;
			for(unsigned int y=currentQuad->_uplefty; y<=currentQuad->_bottomrighty ; y++)
				for(unsigned int x=currentQuad->_upleftx; x<=currentQuad->_bottomrightx ; x++) 
					mask.setPixel(x, y, 0);
		}
	}
}