
// zlib open source license
//
// Copyright (c) 2010 to 2013 David Forsgren Piuva
// 
// This software is provided 'as-is', without any express or implied
// warranty. In no event will the authors be held liable for any damages
// arising from the use of this software.
// 
// Permission is granted to anyone to use this software for any purpose,
// including commercial applications, and to alter it and redistribute it
// freely, subject to the following restrictions:
// 
//    1. The origin of this software must not be misrepresented; you must not
//    claim that you wrote the original software. If you use this software
//    in a product, an acknowledgment in the product documentation would be
//    appreciated but is not required.
// 
//    2. Altered source versions must be plainly marked as such, and must not be
//    misrepresented as being the original software.
// 
//    3. This notice may not be removed or altered from any source
//    distribution.

#include "QuadAllocator.h"
#include "../stdafx.h"

//SideEffect: Resets the quad heap
void QuadAllocator::Reset(void) {
	HeapCount[0] = 1;
	HeapArea[0][0] = MakeQARect(0.0f, 1.0f, 0.0f, 1.0f);
	int i;
	LoopForward(1,i,QASmallestSize) {
		HeapCount[i] = 0;
	}
	
}

//Pre: HeapCount[Size] > 0 and HeapCount[Size+1] = 0
//SideEffect: from Size to Size + 1
void QuadAllocator::Split(int Size) {
	QARect Uncut;
	Uncut = HeapArea[Size][HeapCount[Size] - 1];
	HeapCount[Size + 1] = 4;
	HeapArea[Size + 1][0] = MakeQARect(Uncut.MinU, (Uncut.MinU + Uncut.MaxU) / 2.0f, Uncut.MinV, (Uncut.MinV + Uncut.MaxV) / 2.0f);
	HeapArea[Size + 1][1] = MakeQARect((Uncut.MinU + Uncut.MaxU) / 2.0f, Uncut.MaxU, Uncut.MinV, (Uncut.MinV + Uncut.MaxV) / 2.0f);
	HeapArea[Size + 1][2] = MakeQARect(Uncut.MinU, (Uncut.MinU + Uncut.MaxU) / 2.0f, (Uncut.MinV + Uncut.MaxV) / 2.0f, Uncut.MaxV);
	HeapArea[Size + 1][3] = MakeQARect((Uncut.MinU + Uncut.MaxU) / 2.0f, Uncut.MaxU, (Uncut.MinV + Uncut.MaxV) / 2.0f, Uncut.MaxV);
	HeapCount[Size]--;
}

//Post: True iff something larger could be divided to Size
//SideEffect: HeapCount[Size] > 0 if true is returned
bool QuadAllocator::Divide(int Size) {
	if (Size < 0 || Size > QASmallestSize) {
		return false;
	} else if (HeapCount[Size] > 0) {
		Split(Size);
		return true;
	} else if (Divide(Size - 1)) {
		Split(Size);
		return true;
	} else {
		return false;
	}
}

//SideEffect: Split bigger squares if needed and store the new allocation in the camera if there is enough memory left.
QARect QuadAllocator::Allocate(int Size) {
	QARect RectResult;
	bool CanAllocate;
	if (HeapCount[Size] > 0) {
		// We have found something to allocate
		CanAllocate = true;
	} else {
		// We might be able to find something bigger to split
		CanAllocate = Divide(Size - 1);
	}
	if (CanAllocate == true) {
		// We could allocate something and return it
		RectResult = HeapArea[Size][HeapCount[Size] - 1];
		HeapCount[Size]--;
		return RectResult;
	} else {
		return MakeQARect(-1,-1,-1,-1);
	}
}
