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 (3) Line Function Params 11 sb_tree_ratios (depth, start_ratio, stop_ratio, edge_extend) 67 sb_tree_depths (depth, edge_extend) 109 sb_table (invokable) (frame)	Lua modules required (0) Variable Module Functions used

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

---

local p = {}

-- Function that constructs a sequence of ratios according to the Stern-Brocot tree
-- Ratios are entered as arrays, such as {1, 1} for the ratio 1/1 and {1, 0} for the ratio 1/0
-- Mediants are found between adjacent ratios iteratively
-- Start and stop ratio may be any two ratios, but the default values are 1/1 and 1/0
-- Depth may be specified to be any value, but the default is 4; this is how many generations
-- after the initial ratios to produce successive layers of the tree
-- Edge extend iteratively finds the mediants of the first two and last two ratios; default is 0
-- Transpiled from python code to lua with aid of ChatGPT
function p.sb_tree_ratios(depth, start_ratio, stop_ratio, edge_extend)
	-- Default parameter values
	depth = depth or 4
	start_ratio = start_ratio or {1, 1}
	stop_ratio = stop_ratio or {1, 0}
	edge_extend = edge_extend or 0
	
    -- Initial tree are the ratios 1/1 and 1/0, if default params are used
    local tree = {start_ratio, stop_ratio}

	-- Iteratively find the mediants of every adjacent pair of ratios
    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 (the mediants)
        -- For loop needs to make one fewer iteration since the current ratio and its mediant with the next
        -- are added as a pair; the last ratio in the array is added separately after the loop
        for j = 1, #tree - 1 do
            local ratio_1 = tree[j]
            local ratio_2 = tree[j+1]
            local mediant = {ratio_1[1] + ratio_2[1], ratio_1[2] + ratio_2[2]}

			-- Add to new tree
            table.insert(new_tree, ratio_1)
            table.insert(new_tree, mediant)
        end

		-- Add last ratio, then replace tree with new tree with mediants
        table.insert(new_tree, tree[#tree])
        tree = new_tree
    end

	-- Edge-extend code
	-- Mediants of the last two ratios are added, as are the mediants of the first two ratios
    for i = 1, edge_extend do
        local last_ratio_1 = tree[#tree - 1]     -- Second last ratio
        local last_ratio_2 = tree[#tree]         -- Last ratio
        local mediant_last = {last_ratio_2[1] + last_ratio_1[1], last_ratio_2[2] + last_ratio_1[2]}
        tree[#tree] = mediant_last
        table.insert(tree, last_ratio_2)

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

    return tree
end

-- Function that calculates the depths of each ratio in the Stern-Brocot tree
-- This is nearly identical to the sb_tree_ratios function, except only the depth
-- and edge extend are needed
-- Depths start at 1 rather than 0, for lua code purposes
function p.sb_tree_depths(depth, edge_extend)
	-- Default parameter values
	depths = depths or 4
	edge_extend = edge_extend or 0
	
    -- Initial depths of the nodes are 0
    local tree = {1, 1}

	-- Calculate depths for successive layers in the tree
    for i = 1, depth do
        local new_tree = {}

        for j = 1, #tree - 1 do
            local depth_1 = tree[j]
            local depth_new = i + 1

            table.insert(new_tree, depth_1)
            table.insert(new_tree, depth_new)
        end

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

    -- For extending the edges of the tree
    for i = 1, edge_extend do
        -- Extend at end
        tree[#tree] = tree[#tree - 1] + 1
        table.insert(tree, 0)

        -- Extend at front
        tree[1] = tree[2] + 1
        table.insert(tree, 1, 0)
    end

    return tree
end

-- TODO: Add depths to create the staggered look of the SB tree, typical of nearly all scale tree pages
-- Test function that produces the ratios of the SB tree as a one-column table, using different arguments
-- To try this out, add the following text (not as a lua comment):
-- {{#invoke:SB_tree|sb_table}}
function p.sb_table(frame)
	-- Call the sb function
	-- Start/stop ratios are the same, depth is deeper, and edge-extend is allowed
	local depth = 4
	local edge_extend = 3
	local sb_tree_depths = p.sb_tree_depths(depth, edge_extend)
	local sb_tree_ratios = p.sb_tree_ratios(depth, {1, 1}, {1, 0}, edge_extend)
	
	-- Create the table
	result = '{| class="wikitable"\n'
	result = result .. "|+\n"
	result = result .. "|-\n"
	
	-- Create the multi-column header cell
	result = result .. '! colspan="' .. depth + 1 .. " | Ratio\n"
	
	-- Create the individual rows
	for i = 1, #sb_tree_ratios
	do
		result = result .. "|-\n"
		
		-- Create the cells for each row, staggering the ratios
		-- One ratio per row
		for j = 1, depth + 1 do
			if j == depth[i] then
				result = result .. "|" .. sb_tree_ratios[i][1] .. "/" ..  sb_tree_ratios[i][2] .. "\n"
			else
				result = result .. "|\n"
			end
		end
	end
	
	result = result .. "|}"
	
	return result
end

return p