Module:JI ratios

From Xenharmonic Wiki
Jump to navigation Jump to search

Documentation transcluded from /doc
Icon-Todo.png Todo: Documentation

local rat = require("Module:Rational")
local utils = require("Module:Utils")
local tip = require("Module:Template input parse")
local med = require("Module:Mediants")
local yesno = require("Module:Yesno")
p = {}

-- Template for handling multiple entry of JI ratios into a template, and for
-- searching for JI ratios if automatic entry is desired.
-- This is a successor/replacement for JI ratio finder.

-- JI ratios are searched by the following params in a hierarchy:
-- - Search by prime limit. Int limit is used to limit the num/den of ratios.
--   Prime limit takes precedence over subgroup.
-- - Search by subgroup. (Subgroup may contain nonprime numbers, but ratios are
--   currently not supported.) Int limit is used to limit the num/den of ratios.
-- - If neither prime limit or subgroup is present, search by int limit. This
--   is considered the absolute minimum requirement for ratio searching.
-- NOTES:
-- - Prime limits are infinite sets, so int limit is used to restrain the set
--   to a finite size. The same is true for subgroup.
-- - Tenney height is used for further filtering of ratios, and is considered
--   optional. If omitted, tenney height defaults to infinity.

local DEFAULT_FINE_SEARCH_ARGS = {
	["Int Limit"]        = 50,
	["Tenney Height"]    = 1/0,
	["Complements Only"] = false
}

--------------------------------------------------------------------------------
------------------------------ HELPER FUNCTIONS --------------------------------
--------------------------------------------------------------------------------

-- Does not return anything; entries in source are added to destination.
function p.merge_ratio_tables_without_duplicates(dest_table, source_table)
	for i = 1, #source_table do
		if not p.find_ratio_in_table(dest_table, source_table[i]) then
			table.insert(dest_table, source_table[i])
		end
	end
end

-- Checks whether a ratio was already in a table
function p.find_ratio_in_table(table_, ratio)
	local found = false
	for i = 1, #table_ do
		if rat.as_float(table_[i]) == rat.as_float(ratio) then
			found = true
			break
		end
	end
	return found
end

-- Preprocess fine-search args
function p.preprocess_fine_search_args(fine_search_args)
	local fine_search_args = fine_search_args or DEFAULT_FINE_SEARCH_ARGS
	local tenney_height = fine_search_args["Tenney Height"] or 1/0
	local comps_only    = fine_search_args["Complements Only"] or false
	local int_limit     = fine_search_args["Int Limit"] or DEFAULT_INT_LIMIT
	
	return {
		["Tenney Height"]    = tenney_height,
		["Complements Only"] = comps_only,
		["Int Limit"]        = int_limit
	}
end

--------------------------------------------------------------------------------
------------------------------- FILTER FUNCTIONS -------------------------------
--------------------------------------------------------------------------------

-- Remove ratios whose complements exceed the int limit and Tenney height.
-- If filtering based on Tenney height is not needed, then Tenney height is set
-- to infinity instead, which should be done by the calling function.
function p.filter_ratios_by_complements(ratios, equave, fine_search_args)
	if fine_search_args["Complements Only"] then
		local filtered_ratios = {}
		for i = 1, #ratios do
			local complement = rat.mul(rat.inv(ratios[i]), equave)
			if rat.int_limit(complement) <= fine_search_args["Int Limit"] and rat.tenney_height(complement) <= fine_search_args["Tenney Height"] then
				table.insert(filtered_ratios, ratios[i])
			end
		end
		return filtered_ratios
	else
		return ratios
	end
end

-- Remove ratios that exceed the Tenney height. This does nothing if the Tenney
-- height is infinity.
function p.filter_ratios_by_tenney_height(ratios, equave, fine_search_args)
	local filtered_ratios = {}
	for i = 1, #ratios do
		if rat.tenney_height(ratios[i]) <= fine_search_args["Tenney Height"] then
			table.insert(filtered_ratios, ratios[i])
		end
	end
	return filtered_ratios
end

--------------------------------------------------------------------------------
----------------------- INT-LIMIT-BASED SEARCH FUNCTION ------------------------
--------------------------------------------------------------------------------

-- Int-limit-based search; finds ratios between 1/1 and an equave, within an int
-- limit.
function p.search_within_equave(equave, fine_search_args)
	local equave = equave or rat.new(2,1)			-- Defualt equave is 2/1.
	local fine_search_args = p.preprocess_fine_search_args(fine_search_args)
	
	local init_ratios = {{1,1}, {1,0}}
	local ratios = med.find_only_mediants_by_int_limit(init_ratios, fine_search_args["Int Limit"])
	
	-- Convert to ratios that Module:Rational can work with
	for i = 1, #ratios do
		ratios[i] = rat.new(ratios[i][1], ratios[i][2])
	end
	
	-- Remove ratios that exceed the equave.
	-- Note that mediant search returns sorted ratios, so remove them from the
	-- end until there's no more to remove.
	while rat.gt(ratios[#ratios], equave) do
		table.remove(ratios, #ratios)
	end
	
	-- Filter out ratios that exceed the int limit.
	-- Then filter out ratios if their equave complement would be filtered out.
	ratios = p.filter_ratios_by_tenney_height(ratios, equave, fine_search_args)
	ratios = p.filter_ratios_by_complements(ratios, equave, fine_search_args)
	
	return ratios
end

--------------------------------------------------------------------------------
------------------------ SUBGROUP-BASED SEARCH FUNCTION ------------------------
--------------------------------------------------------------------------------

function p.search_by_prime_limit(prime_limit, equave, fine_search_args)
	local prime_limit = prime_limit or 5
	local equave = equave or rat.new(2,1)
	local fine_search_args = p.preprocess_fine_search_args(fine_search_args)

	-- Find all primes up to the prime limit.
	local primes = {}
	for i = 2, prime_limit do
		local is_prime = true
		for j = 2, math.floor(math.sqrt(i)) do
			if i % j == 0 then
				is_prime = false
				break
			end
		end
		if is_prime then
			table.insert(primes, rat.new(i))
		end
	end
	
	-- Perform subgroup search on the primes found, as subgroup-search code can
	-- be reused for prime-limit search.
	return p.search_by_subgroup(primes, equave, fine_search_args)
end

-- WORK-IN-PROGRESS!!
function p.search_by_subgroup(subgroup, equave, fine_search_args)
	local subgroup = subgroup or {rat.new(2), rat.new(3), rat.new(7)}
	local equave = equave or rat.new(2,1)
	local fine_search_args = p.preprocess_fine_search_args(fine_search_args)
	
	-- Fine search params for ease of access
	local tenney_height = fine_search_args["Tenney Height"]
	local comps_only = fine_search_args["Complements Only"]
	local int_limit = fine_search_args["Int Limit"]
	
	-- Search for ratios within int limit within subgroup by multiplication.
	local products = p.multiply_ratios_using_bfs(rat.new(1), subgroup, int_limit)
	
	-- Use the products found to find all ratios between 1 and the equave.
	-- For each ratio found, have it be the denominator and have the numerator
	-- be all successive ratios after it. For each new ratio found this way, add
	-- it to the table of ratios, excluding ratios that exceed the equave or int
	-- limit, and excluding duplicates. This is way faster than performing BFS
	-- on each ratio and yields the same results.
	local ratios = {}
	for i = 1, #products do
		local new_ratios = {}
		for j = i, #products do
			local ratio = rat.div(products[j], products[i])	
			if rat.as_float(ratio) > rat.as_float(equave) then break end
			
			if not p.find_ratio_in_table(new_ratios, ratio) and rat.int_limit(ratio) <= int_limit then
				table.insert(new_ratios, ratio)
			end
		end
		p.merge_ratio_tables_without_duplicates(ratios, new_ratios)
	end
	
	-- Sort, then filter out ratios that exceed the int limit.
	-- Then filter out ratios if their equave complement would be filtered out.
	table.sort(ratios, rat.lt)
	ratios = p.filter_ratios_by_tenney_height(ratios, equave, fine_search_args)
	ratios = p.filter_ratios_by_complements(ratios, equave, fine_search_args)
	
	return ratios
end

-- Helper function for subgroup search; implementation of BFS
function p.multiply_ratios_using_bfs(init_ratio, subgroup, int_limit)
	local ratios = { init_ratio }
	local i = 1
	while i <= #ratios do
		local new_ratios = p.multiply_ratio_by_subgroup_elements(ratios[i], subgroup, int_limit)
		p.merge_ratio_tables_without_duplicates(ratios, new_ratios)
		i = i + 1
	end
	table.sort(ratios, rat.lt)
	return ratios
end

-- Helper function for BFS search; returns { ratio } X subgroup
function p.multiply_ratio_by_subgroup_elements(ratio, subgroup, int_limit)
	local ratios = {}
	for i = 1, #subgroup do
		local new_ratio = rat.mul(ratio, subgroup[i])
		if rat.int_limit(new_ratio) <= int_limit and not p.find_ratio_in_table(ratios, new_ratio) then
			table.insert(ratios, new_ratio)
		end
	end
	return ratios
end

--------------------------------------------------------------------------------
--------------------------- REVERSE-SEARCH FUNCTIONS ---------------------------
--------------------------------------------------------------------------------

function p.int_limit_of_ratios(ratios)
	
	
end

function p.prime_limit_of_ratios(ratios)
	
	
end

function p.subgroup_of_ratios(ratios, is_nonprime)
	
	
end

--------------------------------------------------------------------------------
-------------------------- ARG-BASED SEARCH FUNCTIONS --------------------------
--------------------------------------------------------------------------------

-- Search for ratios based on an array of args passed in. Certain params have
-- their own function calls.
function p.search_by_args_within_equave(equave, search_args)
	local equave = equave or rat.new(2,1)
	
	-- For each search method, check whether the corresponding search arg and
	-- int limit are both present and pass it and the equave to that function.
	-- All other search args are used as finer search args.
	-- Note that search by int limit alone just has the equave and search args
	-- passed in.
	local ratios = {}
	if search_args["Prime Limit"] ~= nil and search_args["Int Limit"] ~= nil then
		ratios = p.search_by_prime_limit(search_args["Prime Limit"], equave, search_args)
	elseif search_args["Subgroup"] ~= nil and search_args["Int Limit"] ~= nil then
		ratios = p.search_by_subgroup(search_args["Subgroup"], equave, search_args)
	elseif search_args["Int Limit"] ~= nil then
		ratios = p.search_within_equave(equave, search_args)
	end
	return ratios
end

-- Parse search args.
function p.parse_search_args(search_args)
	local parsed = tip.parse_kv_pairs(search_args)
	
	if parsed["Int Limit"] ~= nil then
		parsed["Int Limit"] = tonumber(parsed["Int Limit"])
	end
	
	if parsed["Tenney Height"] ~= nil then
		parsed["Tenney Height"] = tonumber(parsed["Tenney Height"])
	end
	
	if parsed["Prime Limit"] ~= nil then
		parsed["Prime Limit"] = tonumber(parsed["Prime Limit"])
	end
	
	if parsed["Subgroup"] ~= nil then
		local subgroup_elements = tip.parse_numeric_pairs(parsed["Subgroup"], ".", "/", true)
		for i = 1, #subgroup_elements do
			subgroup_elements[i] = rat.new(subgroup_elements[i][1], subgroup_elements[i][2])
		end
		parsed["Subgroup"] = subgroup_elements
	end
	
	if parsed["Complements Only"] ~= nil then
		parsed["Complements Only"] = yesno(parsed["Complements Only"])
	end
	
	return parsed
end

function p.search_footnotes(search_args)
	local result = "Other interpretations are possible."
	local autosearch_text = "Automatic search may be inexact."
	local search_text = ""
	
	if search_args["Prime Limit"] ~= nil then
		search_text = string.format("Ratios shown are within the %s-prime limit.", search_args["Prime Limit"])
			.. " " .. autosearch_text
	elseif search_args["Subgroup"] ~= nil then
		local subgroup_members = {}
		for i = 1, #search_args["Subgroup"] do
			local a, b = rat.as_pair(search_args["Subgroup"][i])
			table.insert(subgroup_members, (b == 1 and string.format("%s", a) or string.format("%s/%s", a, b)))
		end
		search_text = string.format("Ratios shown are within the %s subgroup.", table.concat(subgroup_members, "."))
			.. " " .. autosearch_text
	elseif search_args["Int Limit"] ~= nil then
		search_text = string.format("Ratios shown are within the %s-integer limit.", search_args["Int Limit"])
			.. " " .. autosearch_text
	end
	
	result = search_text .. " " .. result
	return result
end

--------------------------------------------------------------------------------
--------------------------- RATIO SORTING FUNCTIONS ----------------------------
--------------------------------------------------------------------------------

-- Sorts ratios by closeness to cent values.
function p.sort_by_closeness_to_cent_values(ratios, cent_values, tolerance)
	local tolerance = tolerance or 30
	
	local sorted_ratios = {}
	local curr_index = 1		-- Index of current_ratio
	for i = 1, #cent_values do
		local lower_bound = cent_values[i] - tolerance
		local upper_bound = cent_values[i] + tolerance
		local cents_within_range = true
		local curr_ratios = {}
		
		for j = curr_index, #ratios do
			local curr_ratio = ratios[j]
			local curr_cents = rat.cents(curr_ratio)
			
			if lower_bound < curr_cents and curr_cents < upper_bound then
				table.insert(curr_ratios, curr_ratio)
			--elseif curr_cents > upper_bound then
			--	curr_index = j
			--	break
			end
		end
		
		table.insert(sorted_ratios, curr_ratios)
	end
	
	return sorted_ratios
end

--------------------------------------------------------------------------------
------------------------ RATIO PARSING/INPUT FUNCTIONS -------------------------
--------------------------------------------------------------------------------

-- Parse a list of ratios from a string. String is formatted as follows:
-- "a/b; c/d; e/f; g/h"
function p.parse_ratios(unparsed)
	local parsed = tip.parse_numeric_pairs(unparsed)
	for i = 1, #parsed do
		parsed[i] = rat.new(parsed[i][1], parsed[i][2])
	end
	return parsed
end

--------------------------------------------------------------------------------
---------------------------- RATIO STRING FUNCTIONS ----------------------------
--------------------------------------------------------------------------------

-- Convert a table of ratios into a string, with options for links and delimiter
function p.ratios_as_string(ratios, add_links, delimiter)
	local add_links = add_links == true
	local delimiter = delimiter or ", "
	
	local text = ""
	if #ratios ~= 0 then
		text = add_links and string.format("[[%s]]", rat.as_ratio(ratios[1])) or rat.as_ratio(ratios[1])
		for i = 2, #ratios do
			text = text .. (add_links and string.format("%s[[%s]]", delimiter, rat.as_ratio(ratios[i])) or string.format("%s%s", delimiter, rat.as_ratio(ratios[i])))
		end
	end
	return text
end

-- Convert a jagged array of ratios into an array of strings
function p.ratios_as_strings(ratios, add_links, delimiter)
	local add_links = add_links == true
	local delimiter = delimiter or ", "
	
	local texts = {}
	for i = 1, #ratios do
		local text = p.ratios_as_string(ratios[i], add_links, delimiter)
		table.insert(texts, text)
	end
	return texts
end

function p.tester()

	local equave = rat.new(2,1)
	local fine_search_args = p.parse_search_args("Subgroup: 2.5.9/7.21; Int Limit: 50; Complements Only: 0; Tenney Height: 10")
	local subgroup = {rat.new(2), rat.new(3), rat.new(5), rat.new(7)}


	return p.ratios_as_string(p.search_by_args_within_equave(equave, fine_search_args))
end

return p