// file:          BinarySearchtree.hpp
// description:   Special searchspace using a binary search tree.
//                Sak A16(7)(c), Sak A2.
// author:        Karlheinz Hug
// creation date: 2012-06-21
// last update:   2012-07-02

#ifndef BINARY_SEARCHTREE_HPP_
#define BINARY_SEARCHTREE_HPP_

#include <cassert>

#include "SearchspaceSpecial.hpp"
#include "OwnerOfTree.hpp"

	template <typename T>
	class BinarySearchtree : public SearchspaceSpecial<T>, protected OwnerOfTree<T>
		// Instantiation condition: T is a comparable type.
	{
			virtual void fill (unsigned int size, T minItem, T maxItem);

			virtual void for_all_act (void (*act) (T x));

		protected:
			virtual void inorder (typename OwnerOfTree<T>::Node * tree, void (*act) (T x));

			virtual bool is_empty ();

			virtual T item ();

			virtual void init (T x);

			virtual void reduce (T x);

			// Verification:
			virtual void loop_invariants (T x);
			virtual bool unequal_above (T x);
	}; // BinarySearchtree

	template <typename T>
	void BinarySearchtree<T>::fill (unsigned int size, T min_item, T max_item)
	{
		this->init_tree(size, min_item, max_item);
	}

	template <typename T>
	void BinarySearchtree<T>::for_all_act (void (*act) (T x))
	{
		inorder (this->root, act);
	}

	template <typename T>
	void BinarySearchtree<T>::inorder (typename OwnerOfTree<T>::Node * tree, void (*act) (T x))
	{
		if (tree)
		{
			inorder (tree->left, act);
			act(tree->item);
			inorder (tree->right, act);
		}
	}

	template <typename T>
	bool BinarySearchtree<T>::is_empty ()
	{
		return this->current == 0;
	}

	template <typename T>
	T BinarySearchtree<T>::item ()
	{
		assert(!is_empty()); // precondition
		return this->current->item;
	}

	template <typename T>
	void BinarySearchtree<T>::init (T x)
	{
		this->current = this->root;
	}

	template <typename T>
	void BinarySearchtree<T>::reduce (T x)
	{
		assert(!is_empty() && item() != x); // precondition
		if (x < this->current->item)
		{
			this->current = this->current->left;
		}
		else
		{
			this->current = this->current->right;
		}
	}

	// Verification:

	template <typename T>
	void BinarySearchtree<T>::loop_invariants (T x)
	{
		assert(unequal_above(x));
	}

	template <typename T>
	bool BinarySearchtree<T>::unequal_above (T x)
	{
		typename OwnerOfTree<T>::Node * pos = this->root;
		while (pos != this->current && pos->item != x)
		{
			if (x < pos->item)
			{
				pos = pos->left;
			}
			else
			{
				pos = pos->right;
			}
		}
		return pos == this->current;
	}

#endif // BINARY_SEARCHTREE_HPP_