/*----------------------------------------------------------------------------*-
					===================================
					Y Sever Includes - Binary Tree Core
					===================================
Description:
	Provides functions to generate balanced binary search trees for efficient
	searching of large arrays by value.  Left branch is less than, right branch
	is greater than or equal to for multiple matching values.
Legal:
	Copyright (C) 2007 Alex "Y_Less" Cole

	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.
Version:
	0.1.3
Changelog:
	12/08/07:
		Fixed a bug with empty trees.
	14/04/07:
		Updated header documentation with more than changelog.
	10/04/07:
		Added parents for easy deletion.
		Added node deletion code.
	08/04/07:
		Added Bintree_Add()
	24/03/07:
		First version.
Functions:
	Public:
		-
	Core:
		Bintree_QSort - Custom implementaion of QSort to keep pointers.
		Bintree_SortHalf - Itteratively balances halves of an array.
	Stock:
		Bintree_Generate - Generates a balanced binary tree from given input.
		Bintree_Reset - Resets a position in a tree.
		Bintree_FindValue - Finds the pointer for a value in the tree.
		Bintree_Add - Adds an item to a generated tree.
		Bintree_Delete - Removes an item from a tree.
		Bintree_UpdatePointers - Updates the pointers after a target change.
	Static:
		Bintree_Compress - Removes space from an altered tree.
		Bintree_FindMin - Finds the smallest value on a branch.
		Bintree_FindMax - Finds the largest value on a branch.
	Inline:
		Bintree_Sort - Entry point for Bintree_QSort.
		Bintree_Fill - Entry point for Bintree_SortHalf.
	API:
		-
Callbacks:
	-
Definitions:
	BINTREE_NO_BRANCH - Nowhere to go from the number in required direction.
	BINTREE_NOT_FOUND - Failure return.
Enums:
	E_BINTREE_TREE - Structure of a leaf of a binary tree.
	E_BINTREE_INPUT - Structure of an array of data to be added to a tree.
Macros:
	-
Tags:
	Bintree - Binary tree type.
Variables:
	Global:
		-
	Static:
		-
Commands:
	-
Compile options:
	-
Operators:
	-
-*----------------------------------------------------------------------------*/

#define BINTREE_NO_BRANCH -1
#define BINTREE_NOT_FOUND -1

enum E_BINTREE_TREE
{
	E_BINTREE_TREE_VALUE,
	E_BINTREE_TREE_LEFT,
	E_BINTREE_TREE_RIGHT,
	E_BINTREE_TREE_PARENT,
	E_BINTREE_TREE_POINTER
}

enum E_BINTREE_INPUT
{
	E_BINTREE_INPUT_VALUE,
	E_BINTREE_INPUT_POINTER
}

/*----------------------------------------------------------------------------*-
Function:
	Bintree_Sort
Params:
	input[][E_BINTREE_INPUT] - Data to sort.
	size - Size of data to sort.
Return:
	-
Notes:
	Entry point for Bintree_QSort.
-*----------------------------------------------------------------------------*/

#define Bintree_Sort(%1,%2) \
	Bintree_QSort((%1), 0, (%2) - 1)

/*----------------------------------------------------------------------------*-
Function:
	Bintree_Fill
Params:
	Bintree:output[][E_BINTREE_TREE] - Destination for balanced tree.
	data[][E_BINTREE_INPUT] - Source data.
	size - Size of data.
Return:
	Bintree_SortHalf.
Notes:
	Entry point for Bintree_SortHalf.
-*----------------------------------------------------------------------------*/

#define Bintree_Fill(%1,%2,%3) \
	Bintree_SortHalf((%1), (%2), 0, (%3), 0, BINTREE_NO_BRANCH)

/*----------------------------------------------------------------------------*-
Function:
	Bintree_Generate
Params:
	Bintree:output[][E_BINTREE_TREE] - Binary tree to store the data in.
	input[][E_BINTREE_INPUT] - Input data to get the data from.
	size - Number of items to sort.
Return:
	-
Notes:
	Just calls the sort and fill routines.
-*----------------------------------------------------------------------------*/

stock Bintree_Generate(Bintree:output[][E_BINTREE_TREE], input[][E_BINTREE_INPUT], size)
{
	if (!size)
	{
		output[0][E_BINTREE_TREE_PARENT] = BINTREE_NO_BRANCH;
		output[0][E_BINTREE_TREE_LEFT] = BINTREE_NO_BRANCH;
		output[0][E_BINTREE_TREE_RIGHT] = BINTREE_NO_BRANCH;
		return 0;
	}
	Bintree_Sort(input, size);
	Bintree_Fill(output, input, size);
	return 1;
}

/*----------------------------------------------------------------------------*-
Function:
	Bintree_Reset
Params:
	Bintree:tree[][E_BINTREE_TREE] - Array to reset.
	pointer - Position to reset.
Return:
	-
Notes:
	Initialises the array for use.
-*----------------------------------------------------------------------------*/

stock Bintree_Reset(Bintree:tree[][E_BINTREE_TREE], pointer = 0)
{
	tree[pointer][E_BINTREE_TREE_VALUE] = 0;
	tree[pointer][E_BINTREE_TREE_LEFT] = BINTREE_NO_BRANCH;
	tree[pointer][E_BINTREE_TREE_RIGHT] = BINTREE_NO_BRANCH;
	tree[pointer][E_BINTREE_TREE_PARENT] = BINTREE_NO_BRANCH;
	tree[pointer][E_BINTREE_TREE_POINTER] = BINTREE_NOT_FOUND;
}

/*----------------------------------------------------------------------------*-
Function:
	Bintree_FindValue
Params:
	Bintree:tree[][E_BINTREE_TREE] - Tree to find the data in.
	value - Value to search for.
	&cont - Start point.
	&old - The last real leaf.
Return:
	-
Notes:
	Itterates through the array following the various paths till it locates
	the value provided or reaches a dead end.  If the current value is greater
	than the search value, the search goes left, otherwise right.
	
	If cont is not -1 the search will start from the data pointed to by the
	data pointed to by conts' right path, this is to allow collisions to be
	passed over if you want a subsequent one.
-*----------------------------------------------------------------------------*/

stock Bintree_FindValue(Bintree:tree[][E_BINTREE_TREE], value, &cont = 0, &old = 0)
{
	new
		treeValue;
	while (cont != BINTREE_NO_BRANCH)
	{
		old = cont;
		treeValue = tree[old][E_BINTREE_TREE_VALUE];
		if (value < treeValue) cont = tree[old][E_BINTREE_TREE_LEFT];
		else
		{
			cont = tree[old][E_BINTREE_TREE_RIGHT];
			if (value == treeValue)
			{
				return tree[old][E_BINTREE_TREE_POINTER];
			}
		}
	}
	return BINTREE_NOT_FOUND;
}

/*----------------------------------------------------------------------------*-
Function:
	Bintree_QSort
Params:
	numbers[][E_BINTREE_INPUT] - Data to sort.
	left - Start index.
	right - End index.
Return:
	-
Notes:
	Custom version of QSort (see YSI_misc) allows for E_BINTREE_INPUT data
	types, preserving the relative pointers for the sorted data.
-*----------------------------------------------------------------------------*/

Bintree_QSort(numbers[][E_BINTREE_INPUT], left, right)
{
	new
		pivot = numbers[left][E_BINTREE_INPUT_VALUE],
		pointer = numbers[left][E_BINTREE_INPUT_POINTER],
		l_hold = left,
		r_hold = right;
	while (left < right)
	{
		while ((numbers[right][E_BINTREE_INPUT_VALUE] >= pivot) && (left < right)) right--;
		if (left != right)
		{
			numbers[left][E_BINTREE_INPUT_VALUE] = numbers[right][E_BINTREE_INPUT_VALUE];
			numbers[left][E_BINTREE_INPUT_POINTER] = numbers[right][E_BINTREE_INPUT_POINTER];
			left++;
		}
		while ((numbers[left][E_BINTREE_INPUT_VALUE] <= pivot) && (left < right)) left++;
		if (left != right)
		{
			numbers[right][E_BINTREE_INPUT_VALUE] = numbers[left][E_BINTREE_INPUT_VALUE];
			numbers[right][E_BINTREE_INPUT_POINTER] = numbers[left][E_BINTREE_INPUT_POINTER];
			right--;
		}
	}
	numbers[left][E_BINTREE_INPUT_VALUE] = pivot;
	numbers[left][E_BINTREE_INPUT_POINTER] = pointer;
	pivot = left;
	left = l_hold;
	right = r_hold;
	if (left < pivot) Bintree_QSort(numbers, left, pivot - 1);
	if (right > pivot) Bintree_QSort(numbers, pivot + 1, right);
}

/*----------------------------------------------------------------------------*-
Function:
	Bintree_SortHalf
Params:
	Bintree:output[][E_BINTREE_TREE] - Destination array.
	data[][E_BINTREE_INPUT] - Source array.
	index - Start index of the source for processing.
	upper - End index of the source for processing.
	offset - Current offset in the destination array for writing.
Return:
	Size of balanced tree.
Notes:
	Recursively calls itself.  Bisects the passed array and passed each half
	back to itself, with the middle value of each half being the left and
	right branches of the middle value of the passed array (which isn't
	included in either bisected half).  This is itterative so those are again
	split and again split.  If the passed array is only one or two elements
	big the behaviour is set and hardcoded.
	
	Equal values SHOULD branch right, the code is designed for this however
	the generation is not fully tested (it mostly branches right but adjacent
	after bisecting values haven't been tested).
	
	Based on code written for PHP by me.
-*----------------------------------------------------------------------------*/

Bintree_SortHalf(Bintree:output[][E_BINTREE_TREE], data[][E_BINTREE_INPUT], index, upper, offset, parent)
{
	new
		num = upper - index;
	if (!num) return offset;
	if (num == 1)
	{
		output[offset][E_BINTREE_TREE_VALUE] = data[index][E_BINTREE_INPUT_VALUE];
		output[offset][E_BINTREE_TREE_POINTER] = data[index][E_BINTREE_INPUT_POINTER];
		output[offset][E_BINTREE_TREE_PARENT] = parent;
		output[offset][E_BINTREE_TREE_LEFT] = BINTREE_NO_BRANCH;
		output[offset][E_BINTREE_TREE_RIGHT] = BINTREE_NO_BRANCH;
	}
	else if (num == 2)
	{
		output[offset][E_BINTREE_TREE_VALUE] = data[index][E_BINTREE_INPUT_VALUE];
		output[offset][E_BINTREE_TREE_POINTER] = data[index][E_BINTREE_INPUT_POINTER];
		output[offset][E_BINTREE_TREE_PARENT] = parent;
		output[offset][E_BINTREE_TREE_LEFT] = BINTREE_NO_BRANCH;
		output[offset][E_BINTREE_TREE_RIGHT] = ++offset;
		output[offset][E_BINTREE_TREE_VALUE] = data[++index][E_BINTREE_INPUT_VALUE];
		output[offset][E_BINTREE_TREE_POINTER] = data[index][E_BINTREE_INPUT_POINTER];
		output[offset][E_BINTREE_TREE_PARENT] = offset - 1;
		output[offset][E_BINTREE_TREE_LEFT] = BINTREE_NO_BRANCH;
		output[offset][E_BINTREE_TREE_RIGHT] = BINTREE_NO_BRANCH;
	}
	else
	{
		new
			half = num / 2,
			off = half + index,
			right;
		while (off && data[off][E_BINTREE_INPUT_VALUE] == data[off - 1][E_BINTREE_INPUT_VALUE]) off--;
		right = Bintree_SortHalf(output, data, index, off, offset + 1, offset);
		output[offset][E_BINTREE_TREE_VALUE] = data[off][E_BINTREE_INPUT_VALUE];
		output[offset][E_BINTREE_TREE_POINTER] = data[off][E_BINTREE_INPUT_POINTER];
		output[offset][E_BINTREE_TREE_PARENT] = parent;
		output[offset][E_BINTREE_TREE_LEFT] = offset + 1;
		output[offset][E_BINTREE_TREE_RIGHT] = right;
		return Bintree_SortHalf(output, data, off + 1, upper, right, offset);
	}
	return offset + 1;
}

/*----------------------------------------------------------------------------*-
Function:
	Bintree_Add
Params:
	Bintree:data[][E_BINTREE_TREE] - Array to add to.
	input[][E_BINTREE_INPUT] - Data to add.
	offset - Location in the array to store the data.
	maxsize - Size of data.
Return:
	Next free location
Notes:
	-
-*----------------------------------------------------------------------------*/

stock Bintree_Add(Bintree:data[][E_BINTREE_TREE], input[E_BINTREE_INPUT], offset, maxsize = sizeof (data))
{
	if (offset >= maxsize) return BINTREE_NOT_FOUND;
	if (offset)
	{
		new
			leaf,
			old,
			value = input[E_BINTREE_INPUT_VALUE];
		while (Bintree_FindValue(data, value, leaf, old) != BINTREE_NOT_FOUND) continue;
		Bintree_Reset(data, offset);
		if (value < data[old][E_BINTREE_TREE_VALUE]) data[old][E_BINTREE_TREE_LEFT] = offset;
		else data[old][E_BINTREE_TREE_RIGHT] = offset;
		data[offset][E_BINTREE_TREE_PARENT] = old;
		data[offset][E_BINTREE_TREE_VALUE] = value;
		data[offset][E_BINTREE_TREE_POINTER] = input[E_BINTREE_INPUT_POINTER];
		return offset + 1;
	}
	else
	{
		data[0][E_BINTREE_TREE_PARENT] = BINTREE_NO_BRANCH;
		data[0][E_BINTREE_TREE_LEFT] = BINTREE_NO_BRANCH;
		data[0][E_BINTREE_TREE_RIGHT] = BINTREE_NO_BRANCH;
		data[0][E_BINTREE_TREE_VALUE] = input[E_BINTREE_INPUT_VALUE];
		data[0][E_BINTREE_TREE_POINTER] = input[E_BINTREE_INPUT_POINTER];
		return 1;
	}
}

/*----------------------------------------------------------------------------*-
Function:
	Bintree_Delete
Params:
	Bintree:tree[][E_BINTREE_TREE] - Data.
	index - Index to remove.
	count - Number of binary tree items.
Return:
	-
Notes:
	The left branch is usually larger due to the division
	method used so we start there.  Even though right is
	>= and left is only < in even sized arrays the greater
	chunk (unless there's only 2 items) goes left.
	
	Called itteratively to ensure branches are maintained.
-*----------------------------------------------------------------------------*/

stock Bintree_Delete(Bintree:source[][E_BINTREE_TREE], index, count)
{
	new
		branch,
		old = index;
	while (TRUE)
	{
		if ((branch = source[old][E_BINTREE_TREE_LEFT]) != BINTREE_NO_BRANCH) branch = Bintree_FindMax(source, branch);
		else if ((branch = source[old][E_BINTREE_TREE_RIGHT]) != BINTREE_NO_BRANCH) branch = Bintree_FindMin(source, branch);
		else
		{
			if ((branch = source[old][E_BINTREE_TREE_PARENT]) != BINTREE_NO_BRANCH)
			{
				if (source[branch][E_BINTREE_TREE_LEFT] == old) source[branch][E_BINTREE_TREE_LEFT] = BINTREE_NO_BRANCH;
				else source[branch][E_BINTREE_TREE_RIGHT] = BINTREE_NO_BRANCH;
			}
			return Bintree_Compress(source, old, count);
		}
		new
			value = source[old][E_BINTREE_TREE_VALUE],
			pointer = source[old][E_BINTREE_TREE_POINTER];
		source[old][E_BINTREE_TREE_VALUE] = source[branch][E_BINTREE_TREE_VALUE];
		source[old][E_BINTREE_TREE_POINTER] = source[branch][E_BINTREE_TREE_POINTER];
		source[branch][E_BINTREE_TREE_VALUE] = value;
		source[branch][E_BINTREE_TREE_POINTER] = pointer;
		old = branch;
	}
	return BINTREE_NO_BRANCH;
}

/*----------------------------------------------------------------------------*-
Function:
	Bintree_Compress
Params:
	Bintree:tree[][E_BINTREE_TREE] - Array to compress.
	index - Point to start at.
	count - Number of items total.
Return:
	-
Notes:
	-
-*----------------------------------------------------------------------------*/

static stock Bintree_Compress(Bintree:data[][E_BINTREE_TREE], index, count)
{
	new
		index2 = index + 1;
	while (index < count)
	{
		new
			left = (data[index][E_BINTREE_TREE_LEFT] = data[index2][E_BINTREE_TREE_LEFT]),
			right = (data[index][E_BINTREE_TREE_RIGHT] = data[index2][E_BINTREE_TREE_RIGHT]),
			parent = (data[index][E_BINTREE_TREE_PARENT] = data[index2][E_BINTREE_TREE_PARENT]);
		data[index][E_BINTREE_TREE_VALUE] = data[index2][E_BINTREE_TREE_VALUE];
		data[index][E_BINTREE_TREE_POINTER] = data[index2][E_BINTREE_TREE_POINTER];
		if (left != BINTREE_NO_BRANCH) data[left][E_BINTREE_TREE_PARENT] = index;
		if (right != BINTREE_NO_BRANCH) data[right][E_BINTREE_TREE_PARENT] = index;
		if (parent != BINTREE_NO_BRANCH)
		{
			if (data[parent][E_BINTREE_TREE_LEFT] == index2) data[parent][E_BINTREE_TREE_LEFT] = index;
			else if (data[parent][E_BINTREE_TREE_RIGHT] == index2) data[parent][E_BINTREE_TREE_RIGHT] = index;
		}
		index++;
		index2++;
	}
	return count - 1;
}

/*----------------------------------------------------------------------------*-
Function:
	Bintree_FindMin
Params:
	Bintree:data[][E_BINTREE_TREE] - Array to search.
	offset - Start of branch to search.
Return:
	-
Notes:
	Finds the smallest value on a branch
-*----------------------------------------------------------------------------*/

static stock Bintree_FindMin(Bintree:data[][E_BINTREE_TREE], offset)
{
	new
		branch;
	while ((branch = data[offset][E_BINTREE_TREE_LEFT]) != BINTREE_NO_BRANCH) offset = branch;
	return offset;
}

/*----------------------------------------------------------------------------*-
Function:
	Bintree_FindMax
Params:
	Bintree:data[][E_BINTREE_TREE] - Array to search.
	offset - Start of branch to search.
Return:
	-
Notes:
	Finds the largest value on a branch
-*----------------------------------------------------------------------------*/

static stock Bintree_FindMax(Bintree:data[][E_BINTREE_TREE], offset)
{
	new
		branch;
	while ((branch = data[offset][E_BINTREE_TREE_RIGHT]) != BINTREE_NO_BRANCH) offset = branch;
	return offset;
}

/*----------------------------------------------------------------------------*-
Function:
	Bintree_UpdatePointers
Params:
	Bintree:data[][E_BINTREE_TREE] - Data to modify.
	offset - Pointer to modify values after.
	mod - Value to modify by.
Return:
	-
Notes:
	Used for updating pointers when the target data has been modifed (i.e. a
	value has been removed from the array and the array shifted).
-*----------------------------------------------------------------------------*/

stock Bintree_UpdatePointers(Bintree:data[][E_BINTREE_TREE], offset, size, mod = -1)
{
	for (new i = 0; i < size; i++)
	{
		if (data[i][E_BINTREE_TREE_POINTER] > offset) data[i][E_BINTREE_TREE_POINTER] += mod;
	}
}