Module:Exponential search - Revision history

Uzume: strict

2023-02-10T20:10:53Z

strict

← Previous revision		Revision as of 20:10, 10 February 2023
Line 1:		Line 1:
	-- This module provides a generic exponential search algorithm.		-- This module provides a generic exponential search algorithm.
			require[[strict]]

	local checkType = require('libraryUtil').checkType		local checkType = require('libraryUtil').checkType

2019-10-08T16:14:11Z

Protected "Module:Exponential search": High-risk Lua module: used in Module:Highest archive number ([Edit=Require template editor access] (indefinite) [Move=Require template editor access] (indefinite))

← Previous revision	Revision as of 16:14, 8 October 2019
(No difference)

2019-09-29T20:59:01Z

Undid revision 918619241 by Pppery (talk)

← Previous revision		Revision as of 20:59, 29 September 2019
Line 39:		Line 39:
	init = init or 2		init = init or 2
	if not testFunc(1) then		if not testFunc(1) then
	return 0		return nil
	end		end
	return search(testFunc, init, 1, nil)		return search(testFunc, init, 1, nil)

2019-09-29T15:39:52Z

Return 0 instead of nil when testFunc returns false, per comments at Module talk:TableTools

← Previous revision		Revision as of 15:39, 29 September 2019
Line 39:		Line 39:
	init = init or 2		init = init or 2
	if not testFunc(1) then		if not testFunc(1) then
	return ~~nil~~		return 0
	end		end
	return search(testFunc, init, 1, nil)		return search(testFunc, init, 1, nil)

2015-02-27T13:37:05Z

fix error message tense

← Previous revision		Revision as of 13:37, 27 February 2015
Line 33:		Line 33:
	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 ~~values~~ must be a positive integer)",		"'Exponential search' (init value must be a positive integer)",
	tostring(init)		tostring(init)
	), 2)		), 2)

2015-02-27T11:59:45Z

do init checks at the start after all, so that we raise an error even for empty arrays

← Previous revision		Revision as of 11:59, 27 February 2015
Line 29:		Line 29:
	return function (testFunc, init)		return function (testFunc, init)
	checkType('Exponential search', 1, testFunc, 'function')		checkType('Exponential search', 1, testFunc, 'function')
⚫	if not testFunc(1) then
⚫	return nil
⚫	end
	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
Line 41:		Line 38:
	end		end
	init = init or 2		init = init or 2
		⚫	if not testFunc(1) then
		⚫	return nil
		⚫	end
	return search(testFunc, init, 1, nil)		return search(testFunc, init, 1, nil)
	end		end

2015-02-27T10:29:41Z

fix bad variable name

← Previous revision		Revision as of 10:29, 27 February 2015
Line 32:		Line 32:
	return nil		return nil
	end		end
	checkType('Exponential search', 2, ~~initNum~~, '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(

2015-02-26T13:12:13Z

move the init checkType a little later so that we don't execute it for empty arrays

← Previous revision		Revision as of 13:12, 26 February 2015
Line 29:		Line 29:
	return function (testFunc, init)		return function (testFunc, init)
	checkType('Exponential search', 1, testFunc, 'function')		checkType('Exponential search', 1, testFunc, 'function')
⚫	checkType('Exponential search', 2, initNum, 'number', true)
	if not testFunc(1) then		if not testFunc(1) then
	return nil		return nil
	end		end
		⚫	checkType('Exponential search', 2, initNum, '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(

2015-02-26T12:48:51Z

don't check testFunc(1) twice every time

← Previous revision		Revision as of 12:48, 26 February 2015
Line 30:		Line 30:
	checkType('Exponential search', 1, testFunc, 'function')		checkType('Exponential search', 1, testFunc, 'function')
	checkType('Exponential search', 2, initNum, 'number', true)		checkType('Exponential search', 2, initNum, 'number', true)
		⚫	if not testFunc(1) then
		⚫	return nil
		⚫	end
	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(
Line 37:		Line 40:
	), 2)		), 2)
	end		end
	init = init or 1		init = init or 2
		⚫	return search(testFunc, init, 1, nil)
⚫	if not testFunc(1) then
⚫	return nil
⚫	end
⚫	return search(testFunc, init, 0, nil)
	end		end

2015-02-25T13:36:58Z

specify a lower bound of 0 initially so that we don't have to do it on every recursion

← Previous revision		Revision as of 13:36, 25 February 2015
Line 22:		Line 22:
	else		else
	upper = i		upper = i
	lower = lower or 0
	i = midPoint(lower, upper)		i = midPoint(lower, upper)
	return search(testFunc, i, lower, upper)		return search(testFunc, i, lower, upper)
Line 42:		Line 41:
	return nil		return nil
	end		end
	return search(testFunc, init)		return search(testFunc, init, 0, nil)
	end		end