/*----------------------------------------------------------------------------*-
					===================================
					Y Sever Includes - Binary Tree Wrapper
					===================================
Description:
	Provides a simplified API to the binary tree system.
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.0
Changelog:
	29/06/08:
		First version.
Functions:
	Public:
		-
	Core:
		-
	Stock:
		Bintree_DelInternal - Internal deletion function.
		Bintree_FindInternal - Internal find function.
		Bintree_AddInternal - Internal addition function.
	Static:
		-
	Inline:
		Bintree_New - Declares a new binary tree.
		Bintree_AddPair - Adds a key/value pair to a tree.
		Bintree_Gen - Builds a sorted array from given input.
		Bintree_Del - Deletes a key/value pair from a tree.
		Bintree_Find - Finds a value in a tree from a key.
	API:
		-
Callbacks:
	-
Definitions:
	-
Enums:
	-
Macros:
	-
Tags:
	-
Variables:
	Global:
		-
	Static:
		-
Commands:
	-
Compile options:
	-
Operators:
	-
-*----------------------------------------------------------------------------*/

#define Bintree_New(%1,%2)                          \
	new                                             \
		Bintree:YSI_g%1Bintree[%2][E_BINTREE_TREE], \
		YSI_g%1Bindata[%2][E_BINTREE_INPUT],        \
		YSI_g%1Binsize

/*----------------------------------------------------------------------------*-
Function:
	Bintree_AddPair
Params:
	tree - Binary tree name.
	key - Key.
	value - Value.
Return:
	-
Notes:
	Adds a key/value pair to the binary tree.
-*----------------------------------------------------------------------------*/

#define Bintree_AddPair(%1,%2,%3) \
	Bintree_AddInternal(YSI_g%1Bintree, YSI_g%1Bindata, YSI_g%1Binsize, sizeof (YSI_g%1Bintree), %2, %3)

stock Bintree_AddInternal(Bintree:tree[][E_BINTREE_TREE], input[][E_BINTREE_INPUT], &count, size, key, value)
{
	if (count < 0)
	{
		new
			data[E_BINTREE_INPUT];
		data[E_BINTREE_INPUT_VALUE] = key;
		data[E_BINTREE_INPUT_POINTER] = value;
		Bintree_Add(tree, data, 0 - count, size);
		count--;
	}
	else
	{
		input[count][E_BINTREE_INPUT_VALUE] = key;
		input[count][E_BINTREE_INPUT_POINTER] = value;
		count++;
	}
}

/*----------------------------------------------------------------------------*-
Function:
	Bintree_Gen
Params:
	tree - Binary tree name.
Return:
	-
Notes:
	Builds a sorted tree from input data.
-*----------------------------------------------------------------------------*/

#define Bintree_Gen(%1) \
	Bintree_Generate(YSI_g%1Bintree, YSI_g%1Bindata, YSI_g%1Binsize); YSI_g%1Binsize = 0 - YSI_g%1Binsize

/*----------------------------------------------------------------------------*-
Function:
	Bintree_Find
Params:
	tree - Binary tree name.
	value - Value to find.
Return:
	-
Notes:
	Finds a value in a tree.
-*----------------------------------------------------------------------------*/

#define Bintree_Find(%1,%2) \
	Bintree_FindInternal(YSI_g%1Bintree, YSI_g%1Bindata, YSI_g%1Binsize, %2)

stock Bintree_FindInternal(Bintree:tree[][E_BINTREE_TREE], input[][E_BINTREE_INPUT], count, value)
{
	if (count < 0)
	{
		return Bintree_FindValue(tree, value);
	}
	else
	{
		for (new i = 0; i < count; i++)
		{
			if (input[i][E_BINTREE_INPUT_VALUE] == value)
			{
				return input[i][E_BINTREE_INPUT_POINTER];
			}
		}
	}
	return BINTREE_NOT_FOUND;
}

/*----------------------------------------------------------------------------*-
Function:
	Bintree_Del
Params:
	tree - Binary tree name.
	value - Value to delete.
Return:
	-
Notes:
	Deletes an entry from a binary tree.
-*----------------------------------------------------------------------------*/

#define Bintree_Del(%1,%2) \
	Bintree_DelInternal(YSI_g%1Bintree, YSI_g%1Bindata, YSI_g%1Binsize, %2)

stock Bintree_DelInternal(Bintree:tree[][E_BINTREE_TREE], input[][E_BINTREE_INPUT], &count, value)
{
	if (count < 0)
	{
		new
			pointer = Bintree_FindValue(tree, value);
		if (pointer != BINTREE_NOT_FOUND)
		{
			count = 0 - Bintree_Delete(tree, pointer, 0 - count);
		}
	}
	else
	{
		new
			i;
		while (i < count && input[i][E_BINTREE_INPUT_VALUE] != value)
		{
			i++;
		}
		if (i != count)
		{
			count--;
			while (i < count)
			{
				input[i][E_BINTREE_INPUT_VALUE] = input[i + 1][E_BINTREE_INPUT_VALUE];
				input[i][E_BINTREE_INPUT_POINTER] = input[i + 1][E_BINTREE_INPUT_POINTER];
				i++;
			}
		}
	}
}