/*    Zonic the Hog.  A silly Sonic-like game written for Speedhack 2007
 *    Copyright (c) 2007 Steven Wallace / Chedda Cheeze
 *    email: steven.t.wallace @ gmail. com
 *
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License along
 *    with this program; if not, write to the Free Software Foundation, Inc.,
 *    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */
 
 
#include "QuadMap.h"
#include "Object.h"

#include <list>
#include <typeinfo>

using namespace std;


// This is a quick helper function to concatenate two lists
void ListConcatenate(list<Object*> *src, list<Object*> *dest) {
	list<Object*>::const_iterator it;
	for(it = src->begin(); it != src->end(); it++) {
		dest->push_back(*it);
	}
}


// This is a quick helper function to determine if an object is in a list
// Returns true if the list contains the object
// Returns false otherwise
bool ListContains(list<Object*> *ol, Object *o) {
	list<Object*>::const_iterator it;
	for(it=ol->begin(); it!=ol->end(); it++) if(*it == o) return true;
	return false;
}



// This function will remove objects from a list if they are not in the specified coordinates
// TODO: Make it work!
void ListTrim(list<Object*> *obj, int x1, int y1, int x2, int y2) {
	printf("THIS FUNCTION DOES NOT WORK!\n");
	return;
	
	
	list<Object*>::iterator it;
	for(it=obj->begin(); it!=obj->end(); it++) {
		Object *o = *it;
		int x = (int)o->GetX();
		int y = (int)o->GetY();
		if(x < x1 || x > x2 || y < y1 || y > y2) obj->remove(o);
	}
}


QuadMap::QuadMap(int r, int b, int l, int t, int maxObjs) {
	q1 = q2 = 0;

	top = t;
	right = r;
	bottom = b;
	left = l;
	maxObjectsPerBin = maxObjs;

	width = right - left;
	height = bottom - top;
}

QuadMap::~QuadMap() {
	if(q1) delete q1;
	if(q2) delete q2;
}


bool QuadMap::Remove(Object *o) {
	if(!o) return false;
	size--;
	
	if(q1) {
		if(width > height) {
			if(o->GetX() > left + width/2) return q2->Remove(o);
			else return q1->Remove(o);
		}
		else {
			if(o->GetY() > top + height/2) return q2->Remove(o);
			else return q1->Remove(o);
		}
	}
	
	else {
		object.remove(o);
		
		// This is really poor.  We assume that we have removed an object.
		return true;
	}
}


void QuadMap::Clear() {
	if(object.size() == 0) {
		if(q1) q1->Clear();
		if(q2) q2->Clear();
	}
	else {
		object.clear();
	}
}


void QuadMap::Divide() {

	if(width > height) {
		// Divisions are left/right
		q1 = new QuadMap(left + width/2, bottom, left, top, maxObjectsPerBin);
		q2 = new QuadMap(right, bottom, left + width/2, top, maxObjectsPerBin);

		list<Object*>::const_iterator it;
		for(it=object.begin(); it!= object.end(); it++) {
			Object *obj = *it;
			if(obj->GetX() > left + width/2) q2->Insert(obj);
			else q1->Insert(obj);
		}
	}
	else {
		// Divisions are top/bottom
		q1 = new QuadMap(right, top + height/2, left, top, maxObjectsPerBin);
		q2 = new QuadMap(right, bottom, left, top + height/2, maxObjectsPerBin);

		list<Object*>::const_iterator it;
		for(it=object.begin(); it!=object.end(); it++) {
			Object *obj = *it;
			if(obj->GetY() > top + height/2) q2->Insert(obj);
			else q1->Insert(obj);
		}
	}
	
	
	// Finally, empty our bucket of objects, from now on the children
	// get to hold them.
	object.empty();
}


void QuadMap::Insert(Object *obj, bool checkPosition) {
	int x = (int)obj->GetX();
	int y = (int)obj->GetY();
	//printf("Inserting an object...\n");
	
	// Make sure that there's nothing in this spot already
	if(checkPosition) {
		list<Object*> ooo;
		GetObjects(&ooo, x-2, y-2, x+2, y+2);
		if(ooo.size() > 0) {
			// Check that none of the objects returned are in our location
			list<Object*>::const_iterator it;
			for(it=ooo.begin(); it!=ooo.end(); it++) {
				int xx = (int)(*it)->GetX();
				int yy = (int)(*it)->GetY();
				if(x-2 < xx && x+2 > xx && y-2 < yy && y+2 > yy) {
					printf("ERROR: Cannot insert object, there's already one in this spot.\n");
					return;
				}
			}
		}
	}
	
	
	if(x < left || y < top || x > right || y > bottom) {
		// Something very bad happened -- we tried inserting into an invalid area
		printf("Error: tried to insert object into a quadmap with insufficient bounds:\n");
		printf("(%d, %d) -> (%d, %d)-(%d, %d)\n", x, y, left, top, right, bottom);
		return;
	}
	
	// Increment counter
	size++;
	
	// If we aren't at the max capacity yet and we have no children, just pop the item in
	if(!q1 && (int)object.size() < maxObjectsPerBin) {
		object.push_back(obj);
		return;
	}
	
	// If we have no children but are at max capacity, divide
	else if(!q1) {
		Divide();
	}
	
	// Finally, now that we definitely have children at this line,
	// send the item down the chain
	if(width > height) {
		if(x > left + width/2) q2->Insert(obj);
		else q1->Insert(obj, false);
	}
	else {
		if(y > top + height/2) q2->Insert(obj);
		else q1->Insert(obj, false);
	}
	
	return;
}


void QuadMap::Serialize(FILE *f) {
	// Get a list of all the objects in the map
	list<Object*> obj;
	GetObjects(&obj, left, top, right, bottom);
	
	// Determine just how many there are
	int count = obj.size();
	
	// Store the nmber of objects
	fwrite(&count, sizeof(count), 1, f);
	
	// Then store all the objects themselves
	list<Object*>::const_iterator it;
	for(it=obj.begin(); it!=obj.end(); it++) {		
		// Serialize the object
		(*it)->Serialize(f);
	}
}


void QuadMap::Deserialize(FILE *f) {
	// Read the number of objects
	int i, numobjs;
	fread(&numobjs, sizeof(numobjs), 1, f);
	
	
	// Read all the data in
	for(i=0; i<numobjs; i++) {
		Object *o = new Object;		
		o->Deserialize(f);
		Insert(o);
	}
}

void QuadMap::SetBounds(int left, int top, int right, int bottom) {
	// TODO: make me rebuild the entire map if this happens!
	// TODO: only allow enlarging
	this->left = left;
	this->top = top;
	this->right = right;
	this->bottom = bottom;
}








// Returns all objects which are located in the given coordinates
void QuadMap::GetObjects(list<Object*> *obj, int left, int top, int right, int bottom) {
	//printf("I do%s have children.  I am returning objects in the range (%d, %d)-(%d, %d).\n", 
	//	q1?"":" not", left, top, right, bottom);
	// If we have children, traverse them
	if(q1) {
		if(width > height) {
			int middle = this->left + width/2;
			if(right > middle) q2->GetObjects(obj, middle, top, right, bottom);
			if(middle > left) q1->GetObjects(obj, left, top, middle, bottom);
		}
		else {
			int middle = this->top + height/2;
			if(bottom > middle) q2->GetObjects(obj, left, middle, right, bottom);
			if(middle > top) q1->GetObjects(obj, left, top, right, middle);
		}
	}
	
	// Otherwise, send the contents of our bucket
	else ListConcatenate(&object, obj);		
}


