/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 *
 *   This file is part of
 *       _______   ______________  ______     _____
 *      / ____/ | / /  _/ ____/  |/  /   |   |__  /
 *     / __/ /  |/ // // / __/ /|_/ / /| |    /_ <
 *    / /___/ /|  // // /_/ / /  / / ___ |  ___/ /
 *   /_____/_/ |_/___/\____/_/  /_/_/  |_| /____/.
 *
 *   Copyright © 2003-2010 Brain Control, all rights reserved.
 *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

#include "system.hpp"

eBinTree::eBinTree() : m_root(eNULL) { }

eBinTree::~eBinTree()
{
	if (m_root)
		_clear(m_root);
}

void eBinTree::addNode(eU32 key, ePtr data)
{
	if (m_root)
		_addNode(m_root, key, data);
	else
	{
		m_root = new Node(key, data);
	}

	m_size++;
}

ePtr eBinTree::findNode(eU32 key)
{
	if (!m_root)
		return eNULL;

	return _findNode(m_root, key);
}

eU32 eBinTree::getSize()
{
	return m_size;
}

void eBinTree::_addNode(Node *root, eU32 key, ePtr data)
{
	if (key > root->key)
	{
		if (!root->higher)
			root->higher = new Node(key, data);
		else
			_addNode(root->higher, key, data);
	}
	else
	{
		if (!root->lower)
			root->lower = new Node(key, data);
		else
			_addNode(root->lower, key, data);
	}
}

ePtr eBinTree::_findNode(Node *root, eU32 key)
{
	if (root->key == key)
		return root->data;
	else
	{
		if (root->key < key)
		{
			if (root->higher)
				return _findNode(root->higher, key);
			else
				return eNULL;
		}
		else
		{
			if (root->lower)
				return _findNode(root->lower, key);
			else
				return eNULL;
		}
	}
}

void eBinTree::_clear(Node *root)
{
	if (root->lower)
		_clear(root->lower);

	if (root->higher)
		_clear(root->higher);

	delete root;
}