#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_SEARCHING_ALGORITHMS_JUMP_SEARCH_POINTER
#define CA_UWATERLOO_ALUMNI_DWHARDER_SEARCHING_ALGORITHMS_JUMP_SEARCH_POINTER

#include <cmath>
#include "Linear_search_pointer.h"

namespace Searching_algorithms {
	namespace Jump_search {
		class Pointer {
			public:
				template <typename Type>
				static
				bool search( Type const &obj, Type *const array, int const n ) {
					return search( obj, array, array + n - 1 );
				}

				template <typename Type>
				static
				bool search( Type const &obj, Type *const array, int const a, int const b ) {
					return search( obj, array + a, array + b );
				}

				template <typename Type>
				static
				bool search( Type const &obj, Type *a, Type *const b ) {
					if ( a > b || obj < *a || obj > *b ) {
						return false;
					}

					int jump = static_cast<int>( std::sqrt( b - a ) );
					a += jump;

					for ( ; a < b && *a < obj; a += jump ) {
						// do nothing
					}


					if ( a > b ) {
						return Searching_algorithms::Linear_search::Pointer::search( obj, a - jump, b );
					} else {
						return Searching_algorithms::Linear_search::Pointer::search( obj, a - jump, a );
					}
				}
		};
	}
}

#endif