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

#ifndef FAST_BINARY_SEARCHARRAY_HPP_
#define FAST_BINARY_SEARCHARRAY_HPP_

#include <cassert>

#include "SearcharrayGeneral.hpp"
#include "ToolsetArrayComparableC.hpp"

	template <typename T>
	class FastBinarySearcharray : public SearcharrayGeneral<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 done (T x);

			virtual bool found (T x);

			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 greaterequal_from (T x);
	}; // FastBinarySearcharray

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

	template <typename T>
	bool FastBinarySearcharray<T>::done (T x)
	{
		return left >= right;
	}

	template <typename T>
	bool FastBinarySearcharray<T>::found (T x)
	{
		assert(done(x)); // precondition
		return left <= this->high && (this->array)[left] == x;
	}

	template <typename T>
	void FastBinarySearcharray<T>::init (T x)
	{
		left  = this->low;
		right = this->high + 1;
	}

	template <typename T>
	void FastBinarySearcharray<T>::reduce (T x)
	{
		assert(!done(x)); // precondition
		mid = (left + right) / 2;
		if (this->array[mid] < x)
		{
			left = mid + 1;
		}
		else
		{
			right = mid;
		}
	}

	template <typename T>
	int FastBinarySearcharray<T>::position (T x)
	{
		assert(done(x)); // precondition
		return found(x) ? left : this->not_found;
	}

	// Verification:

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

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

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

#endif // FAST_BINARY_SEARCHARRAY_HPP_