Module:Yesno and Module:Exponential search: Difference between pages

Revision as of 16:14, 8 October 2019

Documentation for this module may be created at Module:Exponential search/doc

-- This module provides a generic exponential search algorithm.

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

local function midPoint(lower, upper)
	return floor(lower + (upper - lower) / 2)
end

local function search(testFunc, i, lower, upper)
	if testFunc(i) then
		if i + 1 == upper then
			return i
		end
		lower = i
		if upper then
			i = midPoint(lower, upper)
		else
			i = i * 2
		end
		return search(testFunc, i, lower, upper)
	else
		upper = i
		i = midPoint(lower, upper)
		return search(testFunc, i, lower, upper)
	end
end

return function (testFunc, init)
	checkType('Exponential search', 1, testFunc, 'function')
	checkType('Exponential search', 2, init, 'number', true)
	if init and (init < 1 or init ~= floor(init) or init == math.huge) then
		error(string.format(
			"invalid init value '%s' detected in argument #2 to " ..
			"'Exponential search' (init value must be a positive integer)",
			tostring(init)
		), 2)
	end
	init = init or 2
	if not testFunc(1) then
		return nil
	end
	return search(testFunc, init, 1, nil)
end

@@ Line 1: / Line 1: @@
-local p = {}
+-- This module provides a generic exponential search algorithm.
-function p.yesno(frame)
+local checkType = require('libraryUtil').checkType
+local floor = math.floor
-    -- defaults
+local function midPoint(lower, upper)
-    local retvals = {
+	return floor(lower + (upper - lower) / 2)
-        yes   = "yes",
+end
-        no    = "",
-        ["¬"] = ""
-    }
-    -- Allow arguments to override defaults.
+local function search(testFunc, i, lower, upper)
-    local args;
+	if testFunc(i) then
-    if frame == mw.getCurrentFrame() then
+		if i + 1 == upper then
-        -- We're being called via #invoke. If the invoking template passed any args, use
+			return i
-        -- them. Otherwise, use the args that were passed into the template.
+		end
-        args = frame:getParent().args;
+		lower = i
-        for k, v in pairs(frame.args) do
+		if upper then
-            args = frame.args;
+			i = midPoint(lower, upper)
-            break
+		else
-        end
+			i = i * 2
-    else
+		end
-        -- We're being called from another module or from the debug console, so assume
+		return search(testFunc, i, lower, upper)
-        -- the args are passed in directly.
+	else
-        args = frame;
+		upper = i
-    end
+		i = midPoint(lower, upper)
+		return search(testFunc, i, lower, upper)
-    for k,v in pairs(args) do
+	end
-        retvals[k] = v
+end
-    end
-    val = args[1]
-    -- First deal with the case if val is nil, then deal with other cases.
-    if val == nil then
-        return retvals['¬']
-    end
-    val = val:lower()          -- Make lowercase.
+return function (testFunc, init)
-    val = val:match'^%s*(.*%S)' or ''  -- Trim whitespace.
+	checkType('Exponential search', 1, testFunc, 'function')
+	checkType('Exponential search', 2, init, 'number', true)
-    if val == '' then
+	if init and (init < 1 or init ~= floor(init) or init == math.huge) then
-        return retvals['blank'] or retvals['no']
+		error(string.format(
-    elseif val == 'n' or val == 'no'  or tonumber(val) == 0 then
+			"invalid init value '%s' detected in argument #2 to " ..
-        return retvals['no']
+			"'Exponential search' (init value must be a positive integer)",
-    elseif val == 'y' or val == 'yes' or tonumber(val) == 1 then
+			tostring(init)
-        return retvals['yes']
+		), 2)
-    elseif val == '¬' then
+	end
-        return retvals['¬']
+	init = init or 2
-    else
+	if not testFunc(1) then
-        return retvals['def'] or retvals['yes']
+		return nil
-    end
+	end
+	return search(testFunc, init, 1, nil)
 end
-return p