// file:          LinearSearchlist.hpp
// description:   Special searchspace using a simply linked list and linear search.
//                Sak A16(7)(b), Sak A1.
// author:        Karlheinz Hug
// creation date: 2012-06-20
// last update:   2012-07-03

#ifndef LINEAR_SEARCHLIST_HPP_
#define LINEAR_SEARCHLIST_HPP_

#include <cassert>

#include "SearchspaceSpecial.hpp"
#include "SearchlistGeneral.hpp"

	template <typename T>
	class LinearSearchlist : public SearchspaceSpecial<T>, 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 is_empty ();

			virtual T item ();

			virtual void init (T x);

			virtual void reduce (T x);

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

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

	template <typename T>
	bool LinearSearchlist<T>::is_empty ()
	{
		return this->current == 0;
	}

	template <typename T>
	T LinearSearchlist<T>::item ()
	{
		assert(!is_empty()); // precondition
		return this->current->item;
	}

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

	template <typename T>
	void LinearSearchlist<T>::reduce (T x)
	{
		assert(!is_empty() && item() != x); // precondition
		this->current = this->current->next;
	}

	// Verification:

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

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

#endif // LINEAR_SEARCHLIST_HPP_