#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_SEARCHING_ALGORITHMS_INTROSPECTIVE_SEARCH_POINTER
#define CA_UWATERLOO_ALUMNI_DWHARDER_SEARCHING_ALGORITHMS_INTROSPECTIVE_SEARCH_POINTER

#include "Binary_search_pointer.h"

namespace Searching_algorithms {
	namespace Introspective_search {
		int const POINTER_USE_BINARY = 500;

		class Pointer {
			public:
				template <typename Type>
				static
				bool search( Type const &obj, Type *array, int n ) {
					if ( obj < array[0] || array[n - 1] < obj ) {
						return false;
					}

					return search_iterative( obj, static_cast<double>( obj ), array, array + n - 1 );
				}

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

					return search_iterative( obj, static_cast<double>( obj ), array + a, array + b );
				}

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

					return search_iterative( obj, static_cast<double>( obj ), a, b );
				}

			private:
				template <typename Type>
				static
				bool search_iterative( Type const &obj, double d_obj, Type *a, Type *c ) {
					while ( a + POINTER_USE_BINARY <= c ) {
						if ( *a == *c ) {
							return *a == obj;
						}

						Type *b = a + static_cast<int>(
							static_cast<double>( c - a )*(d_obj - *a)/static_cast<double>(*c - *a)
						);

						if ( obj == *b ) {
							return true;
						}

						if ( obj < *b ) {
							c = b - 1;

							if ( *c < obj ) {
								return false;
							}
						} else {
							a = b + 1;

							if ( *a > obj ) {
								return false;
							}
						}

						b = a + (c - a)/2;

						if ( *b == obj ) {
							return true;
						} else if ( obj < *b ) {
							c = b - 1;
						} else {
							a = b + 1;
						}
					}

					return Searching_algorithms::Binary_search::Pointer::search( obj, a, c );
				}
		};
	}
}

#endif