// file:          FastLinearSearchlist.hpp
// description:   General searchspace using a simply linked list with a sentinel and linear search.
//                Sak A16(7)(b), Sak A1.
// author:        Karlheinz Hug
// creation date: 2012-06-21
// last update:   2012-07-02

#ifndef FAST_LINEAR_SEARCHLIST_HPP_
#define FAST_LINEAR_SEARCHLIST_HPP_

#include <cassert>

#include "SearchlistGeneral.hpp"

	template <typename T>
	class FastLinearSearchlist : public SearchlistGeneral<T>
		// Instantiation condition: T is a comparable type.
	{
		public:
			virtual void fill (unsigned int size, T min_item, T max_item);

		protected:
			virtual bool done (T x);

			virtual bool found (T x);

			virtual void init (T x);

			virtual void reduce (T x);

			// Verification:
			virtual void loop_invariants (T x);
			virtual bool unequal_before (T x);
	}; // FastLinearSearchlist

	template <typename T>
	void FastLinearSearchlist<T>::fill (unsigned int size, T min_item, T max_item)
	{
		init_list(size, min_item, max_item, true);
	}

	template <typename T>
	bool FastLinearSearchlist<T>::done (T x)
	{
		return this->current->item == x;
	}

	template <typename T>
	bool FastLinearSearchlist<T>::found (T x)
	{
		assert(done(x)); // precondition
		return this->current != this->last;
	}

	template <typename T>
	void FastLinearSearchlist<T>::init (T x)
	{
		this->last->item = x;
		this->current    = this->first;
	}

	template <typename T>
	void FastLinearSearchlist<T>::reduce (T x)
	{
		assert(!done(x)); // precondition
		this->current = this->current->next;
	}

	// Verification:

	template <typename T>
	void FastLinearSearchlist<T>::loop_invariants (T x)
	{
		assert(unequal_before(x));
	}

	template <typename T>
	bool FastLinearSearchlist<T>::unequal_before (T x)
	{
		typename OwnerOfList<T>::Node * pos = this->first;
		while (pos != this->current && pos->item != x)
		{
			pos = pos->next;
		}
		return pos == this->current;
	}

#endif // FAST_LINEAR_SEARCHLIST_HPP_