Module:SB tree

Module documentation[view] [edit] [history] [purge]

This module should not be invoked directly; use its corresponding template instead: Template:SB tree.

This module is used to create a Stern–Brocot tree, given a pair of starting ratios and a depth.

Introspection summary for Module:SB tree
Functions provided (2) Line Function Params 6 sb_tree (depth, start_ratio, stop_ratio, edge_extend) 47 sb_table (invokable) (frame)	Lua modules required (1) Variable Module Functions used rat Module:Rational dependency not used

No function descriptions were provided. The Lua code may have further information.

---

local p = {}
local rat = require('Module:Rational')

-- Function that constructs a Stern-Brocot tree, given any start and end ratios and any depth
-- Transpiled from python to lua with aid of ChatGPT; may need testing to make sure code works
function p.sb_tree(depth, start_ratio, stop_ratio, edge_extend)
    -- Initial tree are the ratios 1/1 and 1/0
    local tree = {start_ratio, stop_ratio}

    for i = 1, depth do
        -- Make another tree that's empty
        local new_tree = {}

        -- Make a new tree that has entries in between existing ratios
        for j = 1, #tree - 1 do
            local ratio_1 = tree[j]
            local ratio_2 = tree[j+1]
            local new_ratio = {ratio_1[1] + ratio_2[1], ratio_1[2] + ratio_2[2]}

            table.insert(new_tree, ratio_1)
            table.insert(new_tree, new_ratio)
        end

        table.insert(new_tree, tree[#tree])
        tree = new_tree
    end

	-- TODO: for limit should be edge_extend, set as 3 for debugging
    for i = 1, 3 do
        local last_ratio_1 = tree[#tree - 1]     -- Second last ratio
        local last_ratio_2 = tree[#tree]         -- Last ratio
        local new_ratio_in_between = {last_ratio_2[1] + last_ratio_1[1], last_ratio_2[2] + last_ratio_1[2]}
        tree[#tree] = new_ratio_in_between
        table.insert(tree, last_ratio_2)

        local first_ratio_1 = tree[1]            -- First ratio
        local first_ratio_2 = tree[2]            -- Second first ratio
        local new_ratio_in_between_2 = {first_ratio_2[1] + first_ratio_1[1], first_ratio_2[2] + first_ratio_1[2]}
        tree[1] = new_ratio_in_between_2
        table.insert(tree, 1, first_ratio_1)
    end

    return tree
end

-- Test function that produces the SB tree as a one-column table
function p.sb_table(frame)
	result = '{| class="wikitable"\n'
	result = result .. '|-\n'
	result = result .. '!Ratio\n'
	
	local sb_tree_ratios = p.sb_tree(4, {1, 1}, {1, 0}, 0)
	
	for i = 1, #sb_tree_ratios
	do
		result = result .. '|-'
		result = result .. '|' .. sb_tree_ratios[i][1] .. '/' ..  sb_tree_ratios[i][2]
	end
	
	result = result .. '|}'
	
	return result
end

return p