Module:Array length

This module finds the length of an array, or of a quasi-array with keys such as "data1", "data2", etc. It uses a binary search algorithm to find the length, so as to use as few table lookups as possible.

This algorithm is useful for arrays that use metatables (e.g. frame.args) and for quasi-arrays. For normal arrays, just use the # operator, as it is implemented in C and will be quicker.

Also, if you need to access every item in the array, it will be more efficient to load all of the data into a normal array and either use a counter variable or the # operator to find the length. This algorithm only makes sense when you only need to access a small subset of the array values.

Finally, this algorithm should only be used on arrays containing around 10 or more items, as otherwise it will perform more table lookups than there are items in the array.

Usage

First, load the module. It returns a function, arrayLength, although you may choose a different name.

local arrayLength = require('Module:Array length')

The arrayLength function takes the following parameters:

arrayLength(t, prefix)

• t is the array or quasi-array to find the length of. (table, required)
• prefix is the prefix for quasi-arrays. For example, a quasi-array with keys such as "data1", "data2", etc. would have the prefix "data". (string, optional)

It always returns a number. That number is either a positive integer or zero.

---

-- This module finds the length of an array, or of a quasi-array with keys such
-- as "data1", "data2", etc., using a binary search algorithm.

local checkType = require('libraryUtil').checkType

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

local function makeKey(prefix, i)
	if prefix then
		return prefix .. tostring(i)
	else
		return i
	end
end

local function findLength(t, prefix, i, lower, upper)
	local key = makeKey(prefix, i)
	if t[key] ~= nil then
		if i + 1 == upper then
			return i
		else
			lower = i
			if upper then
				i = midPoint(lower, upper)
				return findLength(t, prefix, i, lower, upper)
			else
				i = i * 2
				return findLength(t, prefix, i, lower, upper)
			end
		end
	else
		upper = i
		i = midPoint(lower, upper)
		return findLength(t, prefix, i, lower, upper)
	end
end

return function (t, prefix)
	checkType('Array length', 1, t, 'table')
	checkType('Array length', 2, prefix, 'string', true)
	local key = makeKey(prefix, 1)
	if t[key] == nil then
		return 0
	end
	return findLength(t, prefix, 2, 1, nil)
end

This module "Array length" is from Wikipedia if otherwise notified