// file:          SearchspaceSpecial.hpp
// description:   Special searchspace abstraction e.g. for simple linear and binary search.
//                Sak A16(1), Sak P39, PÜ 31.5(13)(a).
// author:        Karlheinz Hug
// creation date: 2012-06-14
// last update:   2012-07-02

#ifndef SEARCHSPACE_SPECIAL_HPP_
#define SEARCHSPACE_SPECIAL_HPP_

#include <cassert>

#include "SearchspaceGeneral.hpp"

	template <typename T>
	class SearchspaceSpecial : public virtual SearchspaceGeneral<T>
	{
		protected:
			virtual bool is_empty () = 0;

			virtual T item () = 0;
				// precondition: !is_empty()

			virtual bool done (T x);
				// Final! Normally, do not override!

			virtual bool found (T x);
				// Final! Normally, do not override!
	}; // SearchspaceSpecial

	template <typename T>
	bool SearchspaceSpecial<T>::done (T x)
	{
		return is_empty() || item() == x;
	}

	template <typename T>
	bool SearchspaceSpecial<T>::found (T x)
	{
		assert(done(x)); // precondition
		return !is_empty();
	}

#endif // SEARCHSPACE_SPECIAL_HPP_