// file:          OwnerOfTree.hpp
// description:   Container of a binary search tree with random initialization.
//                Usable as Mixin.
//                Sak A16(7)(c), Sak A2.
//                Caution: No destructor provided for OwnerOfTree and Node!
//                Dynamically created Node-objects on the heap are never deleted!
// author:        Karlheinz Hug
// creation date: 2012-06-21
// last update:   2012-07-02

#ifndef OWNER_OF_TREE_HPP_
#define OWNER_OF_TREE_HPP_

#include <cassert>

#include "ToolsetRandomC.hpp"

	template <typename T>
	class OwnerOfTree
		// Instantiation condition: T is a comparable type.
	{
		protected:
			struct Node
			{
				T      item;
				Node * left,
				     * right;
			};

			Node * root,
			     * current;

			virtual void init_tree (unsigned int size, T min_item, T max_item);

			virtual void put (Node ** tree, Node * node);
				// precondition: tree && node
				// Insert node into tree such that the order is kept.

			virtual ~OwnerOfTree();

			virtual void remove (Node * tree);
	}; // OwnerOfTree

	template <typename T>
	void OwnerOfTree<T>::init_tree (unsigned int size, T min_item, T max_item)
	{
		assert(min_item <= max_item); // precondition
		for (unsigned int index = 0; index < size; ++index)
		{
			current       = new Node();
			current->item = ToolsetRandom<T>::uniform (min_item, max_item);
			put (&root, current);
		}
	}

	template <typename T>
	void OwnerOfTree<T>::put (Node ** tree, Node * node)
	{
		assert(tree); // precondition;
		assert(node); // precondition;
		if (*tree == 0)
		{
			*tree = node;
		}
		else if (node->item < (*tree)->item)
		{
			put (&((*tree)->left), node);
		}
		else
		{
			put (&((*tree)->right), node);
		}
	}

	template <typename T>
	OwnerOfTree<T>::~OwnerOfTree ()
	{
		remove(root);
	}

	template <typename T>
	void OwnerOfTree<T>::remove (Node * tree)
	{
		if (tree)
		{
			remove(tree->left);
			remove(tree->right);
			delete tree;
		}
	}

#endif // OWNER_OF_TREE_HPP_