Module:SB tree

---

Documentation transcluded from /doc
Note: Do not invoke this module directly; use the corresponding template instead: Template:SB tree.

Todo: Documentation

---

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, so depth 4 is 5 layers
-- 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
-- Transpiled from python code to lua with aid of ChatGPT
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 initial ratios are 1 for lua programming purposes
    local tree = {1, 1}

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

		-- Depths of the first and mediant of first and second ratio are added in pairs
		-- The last ratio is added after the for loop itself
        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
    -- When edge-extending, the first and last depths must always be 1
    for i = 1, edge_extend do
        -- Extend at end
        tree[#tree] = tree[#tree - 1] + 1
        table.insert(tree, 1)

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

    return tree
end

-- Helper function that parses ratios entered as "p/q", returning it as an array { p, q }
function p.parse_ratio(ratio_unparsed)
	local ratio = {}
	for number in string.gmatch(ratio_unparsed, '([^/]+)') do
		table.insert(ratio, number)
	end
	return ratio
end

-- Test function that produces the ratios of the SB tree as a multi-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 = frame.args["Depth"] or 4
	local edge_extend = frame.args["Edge Extend"] or 2
	local start_ratio_unparsed = frame.args["Start Ratio"] or "1/1"
	local stop_ratio_unparsed = frame.args["Stop Ratio"] or "1/0"
	local stagger_ratios = (frame.args["Stagger Ratios"] and string.lower(frame.args["Stagger Ratios"])) == "true" and true or false
	
	-- Parse ratios
	local start_ratio = p.parse_ratio(start_ratio_unparsed)
	local stop_ratio = p.parse_ratio(stop_ratio_unparsed)
	
	-- Get the ratios and depths
	local sb_tree_depths = p.sb_tree_depths(depth, edge_extend)
	local sb_tree_ratios = p.sb_tree_ratios(depth, start_ratio, stop_ratio, edge_extend)
	
	-- Create the table
	result = "{| class=\"wikitable\"\n"
		.. "! "
	-- Create the header cell
	if stagger_ratios then
		result = result .. "colspan=\"" .. depth + edge_extend + 1 .. "\" | "
	end
	result = result .. "Ratios\n"
	
	-- Create the individual rows
	for i = 1, #sb_tree_ratios
	do
		result = result .. "|-\n"
		
		-- Create the cells for each row
		if stagger_ratios then
			-- Stagger ratios
			for j = 1, depth + edge_extend + 1 do
				result = result .. "| "
				if j == sb_tree_depths[i] then
					result = result .. sb_tree_ratios[i][1] .. "/" ..  sb_tree_ratios[i][2]
				end
				result = result .. "\n"
			end
		else
			-- Don't stagger ratios
			result = result .. "| " .. sb_tree_ratios[i][1] .. "/" .. sb_tree_ratios[i][2] .. "\n"
		end
	end
	
	result = result .. "|}"
	return result
end

return p