// file:          BinarySearcharray.hpp
// description:   Special searchspace using an array and simple binary search.
//                Sak A16(1), Sak P29, PÜ 31.5(13)(a).
// author:        Karlheinz Hug
// creation date: 2012-06-15
// last update:   2012-07-02

#ifndef BINARY_SEARCHARRAY_HPP_
#define BINARY_SEARCHARRAY_HPP_

#include <cassert>

#include "SearcharraySpecial.hpp"
#include "ToolsetArrayComparableC.hpp"

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

		protected:
			int	left,
				mid,
				right;

			virtual bool is_empty ();

			virtual T item ();

			virtual void init (T x);

			virtual void reduce (T x);

			virtual int position (T x);

			// Verification:
			virtual void loop_invariants (T x);
			virtual bool less_before (T x);
			virtual bool greater_after (T x);
	}; // BinarySearcharray

	template <typename T>
	void BinarySearcharray<T>::fill (unsigned int size, T min_item, T max_item)
	{
		SearcharraySpecial<T>::fill(size, min_item, max_item);
		ToolsetArrayComparable<T>::sort(this->array);
	}

	template <typename T>
	bool BinarySearcharray<T>::is_empty ()
	{
		return left > right;
	}

	template <typename T>
	T BinarySearcharray<T>::item ()
	{
		assert(!is_empty()); // precondition
		return this->array[mid];
	}

	template <typename T>
	void BinarySearcharray<T>::init (T x)
	{
		left  = this->low;
		right = this->high,
		mid   = (left + right) / 2;
	}

	template <typename T>
	void BinarySearcharray<T>::reduce (T x)
	{
		assert(!is_empty() && item() != x); // precondition
		if (item() < x)
		{
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}
		mid = (left + right) / 2;
	}

	template <typename T>
	int BinarySearcharray<T>::position (T x)
	{
		assert(done(x)); // precondition
		return is_empty() ? this->not_found : mid;
	}

	// Verification:

	template <typename T>
	void BinarySearcharray<T>::loop_invariants (T x)
	{
		assert(this->low <= left);
		assert(left <= right + 1);
		assert(right <= this->high);
		assert(less_before(x));
		assert(greater_after(x));
	}

	template <typename T>
	bool BinarySearcharray<T>::less_before (T x)
	{
		assert(left <= right + 1); // precondition
		int i = this->low;
		while (i < left && this->array[i] < x)
		{
			++i;
		}
		return i >= left;
	}

	template <typename T>
	bool BinarySearcharray<T>::greater_after (T x)
	{
		assert(-1 <= right); // precondition
		int i = this->high;
		while (right < i && x < this->array[i])
		{
			--i;
		}
		return right >= i;
	}

#endif // BINARY_SEARCHARRAY_HPP_