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

#ifndef SEARCHSPACE_GENERAL_HPP_
#define SEARCHSPACE_GENERAL_HPP_

	template <typename T>
	class SearchspaceGeneral
	{
		public:
			virtual void fill (unsigned int size, T min_item, T max_item) = 0;
				// Add 'size' items of range 'min_item .. max_item' to searchspace.
				// precondition: min_item <= max_item

			virtual bool has (T x);
				// Is 'x' found in searchspace?
				// Template method using services of protected part.
				// Final! Normally, do not override!

			virtual void for_all_act (void (*act) (T x)) = 0;
				// Traverse searchspace and apply 'act' to each item.
				// PÜ 31.5(5).

		protected:
			virtual bool done (T x) = 0;

			virtual bool found (T x) = 0;
				// precondition: done(x)

			virtual void init (T x) = 0;
				// 'x' is needed in FastLinearSearcharray (linear search with sentinel).

			virtual void reduce (T x) = 0;
				// precondition: !done(x)

			// Verification:
			// Sak A16(2), PÜ 31.5(13)(b).
			virtual void loop_invariants (T x) = 0;
	}; // SearchspaceGeneral

	template <typename T>
	bool SearchspaceGeneral<T>::has (T x)
	{
		init(x);
		loop_invariants(x);
		while (!done(x))
		{
			reduce(x);
			loop_invariants(x);
		};
		return found(x);
	}

#endif // SEARCHSPACE_GENERAL_HPP_