
// 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 "../stdafx.h"
#include "PointerArray.h"
#include "../MessageQueue.h"

#define printError(message) MQ->InsertMessage(L#message);

int PointerArray::getLowerBound(void) {
	return 0;
}

int PointerArray::getUpperBound(void) {
	return Size - 1;
}

int PointerArray::getSize(void) {
	return Size;
}

void* PointerArray::getValue_warning(int index){
	if (Allocated == true) {
		if (index < 0) {
			printError ("Error in PointerArray::getValue_warning!\nBelow lower bound!");
			return 0;
		} else if (index > Size) {
			printError ("Error in PointerArray::getValue_warning!\nAbove upper bound!");
			return 0;
		} else {
			return TheContent[index];
		}
	} else {
		printError ("Error in PointerArray::getValue_warning! The array is not allocated!");
		return 0;
	}
}

void PointerArray::setValue_warning(int index, void* newValue) {
	if (Allocated == true) {
		if (index < 0) {
			printError ("Error in PointerArray::setValue_warning!\nBelow lower bound!");
		} else if (index > Size) {
			printError ("Error in PointerArray::setValue_warning!\nAbove upper bound!");
		} else {
			TheContent[index] = newValue;
		}
	} else {
		printError ("Error in PointerArray::setValue_warning!\nThe array is not allocated!");
	}
}

void* PointerArray::getValue_padded(int index, void* outsideValue) {
	if (Allocated == true) {
		if (index < 0 || index > Size) {
			return outsideValue;
		} else {
			return TheContent[index];
		}
	} else {
		printError ("Error in PointerArray::getValue_padded!\nThe array is not allocated!");
		return 0;
	}
}

void PointerArray::setValue_ignore(int index, void* newValue) {
	if (Allocated == true) {
		if (index < 0 || index > Size) {
			// Ignore out of bound
		} else {
			TheContent[index] = newValue;
		}
	} else {
		printError ("Error in PointerArray::setValue_ignore!\nThe array is not allocated!");
	}
}

float PointerArray::getSortValue_warning(int index){
	if (Allocated == true) {
		if (index < 0) {
			printError ("Error in PointerArray::getValue_warning!\nBelow lower bound!");
			return 0;
		} else if (index > Size) {
			printError ("Error in PointerArray::getValue_warning!\nAbove upper bound!");
			return 0;
		} else {
			return TheSortValues[index];
		}
	} else {
		printError ("Error in PointerArray::getValue_warning!\nThe array is not allocated!");
		return 0;
	}
}

void PointerArray::setSortValue_warning(int index, float newSortValue) {
	if (Allocated == true) {
		if (index < 0) {
			printError ("Error in PointerArray::setSortValue_warning!\nBelow lower bound!");
		} else if (index > Size) {
			printError ("Error in PointerArray::setSortValue_warning!\nAbove upper bound!");
		} else {
			TheSortValues[index] = newSortValue;
		}
	} else {
		printError ("Error in PointerArray::setSortValue_warning!\nThe array is not allocated!");
	}
}

float PointerArray::getSortValue_padded(int index, float outsideSortValue) {
	if (Allocated == true) {
		if (index < 0 || index > Size) {
			return outsideSortValue;
		} else {
			return TheSortValues[index];
		}
	} else {
		printError ("Error in PointerArray::getSortValue_padded!\nThe array is not allocated!");
		return 0;
	}
}

void PointerArray::setSortValue_ignore(int index, float newSortValue) {
	if (Allocated == true) {
		if (index < 0 || index > Size) {
			// Ignore out of bound
		} else {
			TheSortValues[index] = newSortValue;
		}
	} else {
		printError ("Error in PointerArray::setSortValue_ignore!\nThe array is not allocated!");
	}
}

void PointerArray::allocate(int newSize, void* initialValue) {
	int i;
	if (Allocated == false) {
		Size = newSize;
		TheContent = new void*[Size];
		TheSortValues = new float[Size];
		LoopForward(0, i, Size - 1) {
			TheContent[i] = initialValue;
			TheSortValues[i] = 0.0f;
		}
		Allocated = true;
	} else {
		printError ("Error in PointerArray::allocate!\nYou tried to allocate an array that already is allocated!\nUse redim_erase or redim_preserve if you want to reallocate.");
	}
}

void PointerArray::redim_erase(int newSize, void* initialValue) {
	int i;
	void** SwapArray;
	float* SwapArray2;
	int OldSize;
	if (Allocated == true) {
		OldSize = Size;
		Size = newSize;
		SwapArray = TheContent;
		SwapArray2 = TheSortValues;
		TheContent = new void*[Size];
		TheSortValues = new float[Size];
			// Erase
			LoopForward(0, i, Size - 1) {
				TheContent[i] = initialValue;
				TheSortValues[i] = 0;
			}
		SAFE_DELETE_ARRAY(SwapArray)
		SAFE_DELETE_ARRAY(SwapArray2)
		SwapArray = NULL;
	}
}

void PointerArray::redim_preserve(int newSize, void* initialValue) {
	int i;
	void** SwapArray;
	float* SwapArray2;
	int OldSize;
	if (Allocated == true) {
		OldSize = Size;
		Size = newSize;
		SwapArray = TheContent;
		SwapArray2 = TheSortValues;
		TheContent = new void*[Size];
		TheSortValues = new float[Size];
			// Preserve
			LoopForward(0, i, Size - 1) {
				if (i < OldSize) {
					TheContent[i] = SwapArray[i];
					TheSortValues[i] = SwapArray2[i];
				} else {
					TheContent[i] = initialValue;
					TheSortValues[i] = 0;
				}
			}
		SAFE_DELETE_ARRAY(SwapArray)
		SAFE_DELETE_ARRAY(SwapArray2)
		SwapArray = NULL;
	}
}

void PointerArray::deallocate(void) {
	if (Allocated == true) {
		Size = 0;
		SAFE_DELETE_ARRAY(TheContent)
		SAFE_DELETE_ARRAY(TheSortValues)
		Allocated = false;
	} else {
		printError ("Error in PointerArray::deallocate!\nYou tried to deallocate an array that is not allocated!");
	}
}

void PointerArray::swapElements_Unsafe(int A, int B) {
	void* swapInt; float swapFloat;
	swapInt = TheContent[A];
	swapFloat = TheSortValues[A];
	TheContent[A] = TheContent[B];
	TheSortValues[A] = TheSortValues[B];
	TheContent[B] = swapInt;
	TheSortValues[B] = swapFloat;
}

void PointerArray::swapElements_Warning(int A, int B) {
	if (A < 0 || A > Size - 1) {
		printError ("Error in PointerArray::swapElements!\nReference A is out of bound!");
		return;
	}
	if (B < 0 || B > Size - 1) {
		printError ("Error in PointerArray::swapElements!\nReference B is out of bound!");
		return;
	}
	swapElements_Unsafe(A, B);
}

// Postcondition:
//		The array will be sorted so that elements with lower sort values have a lower index than the elements with higher sort values.
//		All(x){ All(y){ (x < y) -> (Array(x).SortValue < Array(y).SortValue) } }
// Worst case complexity:
//		O(n^2) for decreasing array.
// Best case complexity:
//		O(n) for already increasing array.
// Main purpose:
//		Switch back to this simple method if you suspect that there is a bug in one of the advanced sorting methods.
void PointerArray::safeSort(int usedSize) {
	int i;
	LastUsedSize = usedSize;
	if (LastUsedSize > 1) {
		// i and i+1 will travel over the array and swap when the pair is decreasing
		i = 0;
		while ( i < LastUsedSize - 1) {
			if ( TheSortValues[i] > TheSortValues[i+1] ) {
				// Swap to allowed order and go back if possible
				swapElements_Unsafe(i, i+1);
				if ( i > -1 ) {
					i--;
				} else {
					i++;
				}
			} else {
				// Continue
				i++;
			}
		}
	}
}

int PointerArray::heapParent(int x) {
	if ( x % 2 == 0 ) {
		return x / 2;
	} else {
		return (x - 1) / 2;
	}
}

int PointerArray::heapLeft(int x) {
	return x * 2;
}

int PointerArray::heapRight(int x) {
	return (x * 2) + 1;
}

void PointerArray::maxHeapify(int i) {
	int l; int r; int largest;
	l = heapLeft(i); r = heapRight(i);
	if (l <= Heapsize && TheSortValues[l-1] > TheSortValues[i-1]) {
		largest = l;
	} else {
		largest = i;
	}
	if (r <= Heapsize && TheSortValues[r-1] > TheSortValues[largest-1]) {
		largest = r;
	}
	if (largest != i) {
		swapElements_Unsafe(i-1, largest-1);
		maxHeapify(largest);
	}
}

void PointerArray::buildMaxHeap(void) {
	int i; Heapsize = LastUsedSize;
	for(i = heapParent(LastUsedSize); i >= 1; i--) {
		maxHeapify(i);
	}
}

// Postcondition:
//		The array will be sorted so that elements with lower sort values have a lower index than the elements with higher sort values.
//		All(x){ All(y){ (x < y) -> (Array(x).SortValue < Array(y).SortValue) } }
// Complexity:
//		O(n lg n)
void PointerArray::heapSort(int usedSize) {
	int i;
	LastUsedSize = usedSize;
	if (LastUsedSize > 1) {
		buildMaxHeap();
		for(i = LastUsedSize; i >= 2; i--) {
			swapElements_Unsafe(0, i-1);
			Heapsize--;
			maxHeapify(1);
		}
	}
}
