Diff: Module:Exponential search

-- This module provides a generic exponential search algorithm.

-- This module provides a generic exponential search algorithm.

local checkType = require('libraryUtil').checkType

local checkType = require('libraryUtil').checkType

local floor = math.floor

local floor = math.floor

local function midPoint(lower, upper)

local function midPoint(lower, upper)

	return floor(lower + (upper - lower) / 2)

	return floor(lower + (upper - lower) / 2)

end

end

local function search(testFunc, i, lower, upper)

local function search(testFunc, i, lower, upper)

	if testFunc(i) then

	if testFunc(i) then

		if i + 1 == upper then

		if i + 1 == upper then

			return i

			return i

		end

		end

		lower = i

		lower = i

		if upper then

		if upper then

			i = midPoint(lower, upper)

			i = midPoint(lower, upper)

		else

		else

			i = i * 2

			i = i * 2

		end

		end

		return search(testFunc, i, lower, upper)

		return search(testFunc, i, lower, upper)

	else

	else

		upper = i

		upper = i

		i = midPoint(lower, upper)

		i = midPoint(lower, upper)

		return search(testFunc, i, lower, upper)

		return search(testFunc, i, lower, upper)

	end

	end

end

end

return function (testFunc, init)

return function (testFunc, init)

	checkType('Exponential search', 1, testFunc, 'function')

	checkType('Exponential search', 1, testFunc, 'function')

	checkType('Exponential search', 2, init, 'number', true)

	checkType('Exponential search', 2, init, 'number', true)

	if init and (init < 1 or init ~= floor(init) or init == math.huge) then

	if init and (init < 1 or init ~= floor(init) or init == math.huge) then

		error(string.format(

		error(string.format(

			"invalid init value '%s' detected in argument #2 to " ..

			"invalid init value '%s' detected in argument #2 to " ..

			"'Exponential search' (init value must be a positive integer)",

			"'Exponential search' (init value must be a positive integer)",

			tostring(init)

			tostring(init)

		), 2)

		), 2)

	end

	end

	init = init or 2

	init = init or 2

	if not testFunc(1) then

	if not testFunc(1) then

		return nil

		return nil

	end

	end

	return search(testFunc, init, 1, nil)

	return search(testFunc, init, 1, nil)

end

end