-- converts an interval string into a note value
-- an interval string consists of any number of #'s and b's
-- followed by a non-negative scale degree
-- (string) -> (number)
local intvToNote = function (str)
	local a, b = str:match "^([#b]*)(%d+)$"
	local acc = 0
	a:gsub(".", function (c) acc = acc + (c == "#" and 1 or -1) end)
	b = tonumber(b)
	return acc * 7 + (b * 2 - 1) % 7 - 1
end
 
-- converts a note value into a MIDI pitch value between 0 and 11 inclusive
-- a note value is simply the number of perfect fifths from C
-- (number) -> (number)
local noteToMIDI = function (x)
	return x * 7 % 12
end
 
-- gets the number of sharps in a note value
-- (number) -> (number)
local noteGetAcc = function (x)
	return math.floor((x + 1) / 7)
end
 
-- converts a note value into a note name with proper accidentals
-- (number) -> (string)
local noteToStr; do
	local NAME = {[0] = 'C', 'D', 'E', 'F', 'G', 'A', 'B'}
noteToStr = function (x)
	local acc = noteGetAcc(x)
	return NAME[x * 4 % 7] .. ("#"):rep(acc) .. ("b"):rep(-acc)
end; end
 
-- converts a MIDI pitch value into a note name with sharp and octave name
-- (number) -> (string)
local MIDItoStr; do
	local NAME = {"C", "C#", "D", "D#", "E", "F", "F#", "G", "G#", "A", "A#", "B"}
MIDItoStr = function (x)
	return NAME[x % 12 + 1] .. math.floor(x / 12)
end; end
 
local LH_LOWEST = -.25 -- left-hand octave offset
local RH_CENTRE = 0 -- right-hand octave offset
LH_LOWEST = 41 + 12 * LH_LOWEST
RH_CENTRE = 60 + 12 * RH_CENTRE
-- converts a chord over a bass note into a MIDI voicing
-- a chord is a list of interval strings, basic order of chord tones is assumed:
--   root to highest extension, followed by added/suspended tones
--   members of lowest triad must use "0" as interval if omitted (or some other nil value)
-- the value corresponding to key 0 indicates an optional slash bass
-- a voicing consists of MIDI pitch values for the bass and four voices
-- ([string], number) -> (number, [number])
local voicing; do
	local map = function (f, t)
		local z = {}
		for k, v in next, t do z[k] = f(v) end
		return z
	end
voicing = function (chord, trsp)
	chord = map(function (x) return x end, chord) -- clone
	if chord[0] == "0" then chord[0] = nil end
	for i = #chord, 4, -1 do if chord[i] == "0" then table.remove(chord, i) end end
	assert(chord[1] and chord[1] ~= "0", "Missing bass note")
	local c = map(intvToNote, chord)
	local bass = (c[0] or c[1]) + trsp
 
	-- select notes
	local vo = {}
	local addVoice; do
		local selected = {}
		for i, v in pairs(chord) do if v == "0" then selected[i] = true end end
	addVoice = function (i, f)
		if #vo >= 4 then return end
		if not selected[i] and (not f or f(c[i])) then
			local n = noteToMIDI(c[i] + trsp)
			for _, v in ipairs(vo) do if n == v then return end end -- no duplicates
			selected[i] = true; table.insert(vo, n)
		end
	end; end
 
	local VOICES = #c
	-- 1st pass: suspended note
	addVoice(2, function (n) return n ~= intvToNote("3") and n ~= intvToNote("b3") end)
	-- 2nd pass: altered extensions
	for i = 5, VOICES do addVoice(i, function (n) return noteGetAcc(n) ~= 0 end) end
	-- 3rd pass: altered fifth
	addVoice(3, function (n) return n ~= intvToNote("5") end)
	-- 4th pass: other extensions
	for i = VOICES, 4, -1 do addVoice(i) end
	-- 5th pass: third, fifth
	for i = 2, 3 do addVoice(i) end
	-- 6th pass: slash bass (optional)
--	if chord[0] then addVoice(0); c[0] = nil end
	-- 7th pass: root
	addVoice(1)
	table.sort(vo)
 
	-- raise bass note to left-hand range
	bass = noteToMIDI(bass)
	while bass < LH_LOWEST do bass = bass + 12 end
 
	-- use average pitch value for voicing
	local avg = 0
	for _, v in ipairs(vo) do avg = avg + v end
	local COUNT = #vo
	while avg < (RH_CENTRE - 12) * COUNT do
		avg = avg + 12 * COUNT -- raise notes just below right-hand octave
		for i, v in ipairs(vo) do vo[i] = v + 12 end
	end
	while avg < RH_CENTRE * COUNT do
		avg = avg + 12 -- invert voicing until average pitch above right-hand octave
		table.insert(vo, table.remove(vo, 1) + 12)
	end
	-- swap end notes for slightly open voicing
	vo[1], vo[math.min(COUNT + 1, 4)] = vo[COUNT] - 12, vo[1] + 12
--	if COUNT == 4 then
--		vo[1], vo[4] = vo[4] - 12, vo[1] + 12
--	else -- double one note
--		local top = avg + vo[1] + 12
--		local down = avg + vo[COUNT] - 12
--		local centre = RH_CENTRE * COUNT
--		if math.abs(down - centre) <= math.abs(top - centre) then
--			table.insert(vo, 1, vo[COUNT] - 12)
--		else
--			table.insert(vo, vo[1] + 12)
--		end
--	end
 
	return bass, vo
end; end
 
local test = function (chord, name)
	-- for i, v in ipairs(chord) do print(i, intvToNote(v), noteToStr(intvToNote(v))) end
	for i = -7, 7 do
		local lh, rh = voicing(chord, i)
		io.write(("%14s"):format(noteToStr(i) .. name ..
			(chord[0] and "/" .. noteToStr(i + intvToNote(chord[0])) or "")))
		io.write "\t\t\t"
		for _, v in ipairs(chord) do if v ~= "0" then
			io.write((" %3s"):format(noteToStr(intvToNote(v) + i)))
		end end
		if chord[0] and chord[0] ~= "0" then
			io.write((" / %3s"):format(noteToStr(intvToNote(chord[0]) + i)))
		end
		io.write "\t\t\t"
		io.write((" %3s"):format(MIDItoStr(lh)))
		for _, v in ipairs(rh) do io.write((" %3s"):format(MIDItoStr(v))) end
		io.write '\n'
	end
	io.write '\n'
end
 
test({"1", "3", "#5"}, "+")
test({"1", "b3", "5", [0] = "2"}, "m")
test({"1", "3", "5", [0] = "5"}, "")
test({"1", "4", "5", "b7", "9"}, "9sus")
test({"1", "3", "5", "b7", "b9", "13"}, "7(b9,13)")
test({"1", "0", "5"}, "5")
test({"1", "4", "5", "2"}, "sus42")
 

LS0gY29udmVydHMgYW4gaW50ZXJ2YWwgc3RyaW5nIGludG8gYSBub3RlIHZhbHVlCi0tIGFuIGludGVydmFsIHN0cmluZyBjb25zaXN0cyBvZiBhbnkgbnVtYmVyIG9mICMncyBhbmQgYidzCi0tIGZvbGxvd2VkIGJ5IGEgbm9uLW5lZ2F0aXZlIHNjYWxlIGRlZ3JlZQotLSAoc3RyaW5nKSAtPiAobnVtYmVyKQpsb2NhbCBpbnR2VG9Ob3RlID0gZnVuY3Rpb24gKHN0cikKCWxvY2FsIGEsIGIgPSBzdHI6bWF0Y2ggIl4oWyNiXSopKCVkKykkIgoJbG9jYWwgYWNjID0gMAoJYTpnc3ViKCIuIiwgZnVuY3Rpb24gKGMpIGFjYyA9IGFjYyArIChjID09ICIjIiBhbmQgMSBvciAtMSkgZW5kKQoJYiA9IHRvbnVtYmVyKGIpCglyZXR1cm4gYWNjICogNyArIChiICogMiAtIDEpICUgNyAtIDEKZW5kCgotLSBjb252ZXJ0cyBhIG5vdGUgdmFsdWUgaW50byBhIE1JREkgcGl0Y2ggdmFsdWUgYmV0d2VlbiAwIGFuZCAxMSBpbmNsdXNpdmUKLS0gYSBub3RlIHZhbHVlIGlzIHNpbXBseSB0aGUgbnVtYmVyIG9mIHBlcmZlY3QgZmlmdGhzIGZyb20gQwotLSAobnVtYmVyKSAtPiAobnVtYmVyKQpsb2NhbCBub3RlVG9NSURJID0gZnVuY3Rpb24gKHgpCglyZXR1cm4geCAqIDcgJSAxMgplbmQKCi0tIGdldHMgdGhlIG51bWJlciBvZiBzaGFycHMgaW4gYSBub3RlIHZhbHVlCi0tIChudW1iZXIpIC0+IChudW1iZXIpCmxvY2FsIG5vdGVHZXRBY2MgPSBmdW5jdGlvbiAoeCkKCXJldHVybiBtYXRoLmZsb29yKCh4ICsgMSkgLyA3KQplbmQKCi0tIGNvbnZlcnRzIGEgbm90ZSB2YWx1ZSBpbnRvIGEgbm90ZSBuYW1lIHdpdGggcHJvcGVyIGFjY2lkZW50YWxzCi0tIChudW1iZXIpIC0+IChzdHJpbmcpCmxvY2FsIG5vdGVUb1N0cjsgZG8KCWxvY2FsIE5BTUUgPSB7WzBdID0gJ0MnLCAnRCcsICdFJywgJ0YnLCAnRycsICdBJywgJ0InfQpub3RlVG9TdHIgPSBmdW5jdGlvbiAoeCkKCWxvY2FsIGFjYyA9IG5vdGVHZXRBY2MoeCkKCXJldHVybiBOQU1FW3ggKiA0ICUgN10gLi4gKCIjIik6cmVwKGFjYykgLi4gKCJiIik6cmVwKC1hY2MpCmVuZDsgZW5kCgotLSBjb252ZXJ0cyBhIE1JREkgcGl0Y2ggdmFsdWUgaW50byBhIG5vdGUgbmFtZSB3aXRoIHNoYXJwIGFuZCBvY3RhdmUgbmFtZQotLSAobnVtYmVyKSAtPiAoc3RyaW5nKQpsb2NhbCBNSURJdG9TdHI7IGRvCglsb2NhbCBOQU1FID0geyJDIiwgIkMjIiwgIkQiLCAiRCMiLCAiRSIsICJGIiwgIkYjIiwgIkciLCAiRyMiLCAiQSIsICJBIyIsICJCIn0KTUlESXRvU3RyID0gZnVuY3Rpb24gKHgpCglyZXR1cm4gTkFNRVt4ICUgMTIgKyAxXSAuLiBtYXRoLmZsb29yKHggLyAxMikKZW5kOyBlbmQKCmxvY2FsIExIX0xPV0VTVCA9IC0uMjUgLS0gbGVmdC1oYW5kIG9jdGF2ZSBvZmZzZXQKbG9jYWwgUkhfQ0VOVFJFID0gMCAtLSByaWdodC1oYW5kIG9jdGF2ZSBvZmZzZXQKTEhfTE9XRVNUID0gNDEgKyAxMiAqIExIX0xPV0VTVApSSF9DRU5UUkUgPSA2MCArIDEyICogUkhfQ0VOVFJFCi0tIGNvbnZlcnRzIGEgY2hvcmQgb3ZlciBhIGJhc3Mgbm90ZSBpbnRvIGEgTUlESSB2b2ljaW5nCi0tIGEgY2hvcmQgaXMgYSBsaXN0IG9mIGludGVydmFsIHN0cmluZ3MsIGJhc2ljIG9yZGVyIG9mIGNob3JkIHRvbmVzIGlzIGFzc3VtZWQ6Ci0tICAgcm9vdCB0byBoaWdoZXN0IGV4dGVuc2lvbiwgZm9sbG93ZWQgYnkgYWRkZWQvc3VzcGVuZGVkIHRvbmVzCi0tICAgbWVtYmVycyBvZiBsb3dlc3QgdHJpYWQgbXVzdCB1c2UgIjAiIGFzIGludGVydmFsIGlmIG9taXR0ZWQgKG9yIHNvbWUgb3RoZXIgbmlsIHZhbHVlKQotLSB0aGUgdmFsdWUgY29ycmVzcG9uZGluZyB0byBrZXkgMCBpbmRpY2F0ZXMgYW4gb3B0aW9uYWwgc2xhc2ggYmFzcwotLSBhIHZvaWNpbmcgY29uc2lzdHMgb2YgTUlESSBwaXRjaCB2YWx1ZXMgZm9yIHRoZSBiYXNzIGFuZCBmb3VyIHZvaWNlcwotLSAoW3N0cmluZ10sIG51bWJlcikgLT4gKG51bWJlciwgW251bWJlcl0pCmxvY2FsIHZvaWNpbmc7IGRvCglsb2NhbCBtYXAgPSBmdW5jdGlvbiAoZiwgdCkKCQlsb2NhbCB6ID0ge30KCQlmb3IgaywgdiBpbiBuZXh0LCB0IGRvIHpba10gPSBmKHYpIGVuZAoJCXJldHVybiB6CgllbmQKdm9pY2luZyA9IGZ1bmN0aW9uIChjaG9yZCwgdHJzcCkKCWNob3JkID0gbWFwKGZ1bmN0aW9uICh4KSByZXR1cm4geCBlbmQsIGNob3JkKSAtLSBjbG9uZQoJaWYgY2hvcmRbMF0gPT0gIjAiIHRoZW4gY2hvcmRbMF0gPSBuaWwgZW5kCglmb3IgaSA9ICNjaG9yZCwgNCwgLTEgZG8gaWYgY2hvcmRbaV0gPT0gIjAiIHRoZW4gdGFibGUucmVtb3ZlKGNob3JkLCBpKSBlbmQgZW5kCglhc3NlcnQoY2hvcmRbMV0gYW5kIGNob3JkWzFdIH49ICIwIiwgIk1pc3NpbmcgYmFzcyBub3RlIikKCWxvY2FsIGMgPSBtYXAoaW50dlRvTm90ZSwgY2hvcmQpCglsb2NhbCBiYXNzID0gKGNbMF0gb3IgY1sxXSkgKyB0cnNwCgoJLS0gc2VsZWN0IG5vdGVzCglsb2NhbCB2byA9IHt9Cglsb2NhbCBhZGRWb2ljZTsgZG8KCQlsb2NhbCBzZWxlY3RlZCA9IHt9CgkJZm9yIGksIHYgaW4gcGFpcnMoY2hvcmQpIGRvIGlmIHYgPT0gIjAiIHRoZW4gc2VsZWN0ZWRbaV0gPSB0cnVlIGVuZCBlbmQKCWFkZFZvaWNlID0gZnVuY3Rpb24gKGksIGYpCgkJaWYgI3ZvID49IDQgdGhlbiByZXR1cm4gZW5kCgkJaWYgbm90IHNlbGVjdGVkW2ldIGFuZCAobm90IGYgb3IgZihjW2ldKSkgdGhlbgoJCQlsb2NhbCBuID0gbm90ZVRvTUlESShjW2ldICsgdHJzcCkKCQkJZm9yIF8sIHYgaW4gaXBhaXJzKHZvKSBkbyBpZiBuID09IHYgdGhlbiByZXR1cm4gZW5kIGVuZCAtLSBubyBkdXBsaWNhdGVzCgkJCXNlbGVjdGVkW2ldID0gdHJ1ZTsgdGFibGUuaW5zZXJ0KHZvLCBuKQoJCWVuZAoJZW5kOyBlbmQKCglsb2NhbCBWT0lDRVMgPSAjYwoJLS0gMXN0IHBhc3M6IHN1c3BlbmRlZCBub3RlCglhZGRWb2ljZSgyLCBmdW5jdGlvbiAobikgcmV0dXJuIG4gfj0gaW50dlRvTm90ZSgiMyIpIGFuZCBuIH49IGludHZUb05vdGUoImIzIikgZW5kKQoJLS0gMm5kIHBhc3M6IGFsdGVyZWQgZXh0ZW5zaW9ucwoJZm9yIGkgPSA1LCBWT0lDRVMgZG8gYWRkVm9pY2UoaSwgZnVuY3Rpb24gKG4pIHJldHVybiBub3RlR2V0QWNjKG4pIH49IDAgZW5kKSBlbmQKCS0tIDNyZCBwYXNzOiBhbHRlcmVkIGZpZnRoCglhZGRWb2ljZSgzLCBmdW5jdGlvbiAobikgcmV0dXJuIG4gfj0gaW50dlRvTm90ZSgiNSIpIGVuZCkKCS0tIDR0aCBwYXNzOiBvdGhlciBleHRlbnNpb25zCglmb3IgaSA9IFZPSUNFUywgNCwgLTEgZG8gYWRkVm9pY2UoaSkgZW5kCgktLSA1dGggcGFzczogdGhpcmQsIGZpZnRoCglmb3IgaSA9IDIsIDMgZG8gYWRkVm9pY2UoaSkgZW5kCgktLSA2dGggcGFzczogc2xhc2ggYmFzcyAob3B0aW9uYWwpCi0tCWlmIGNob3JkWzBdIHRoZW4gYWRkVm9pY2UoMCk7IGNbMF0gPSBuaWwgZW5kCgktLSA3dGggcGFzczogcm9vdAoJYWRkVm9pY2UoMSkKCXRhYmxlLnNvcnQodm8pCgoJLS0gcmFpc2UgYmFzcyBub3RlIHRvIGxlZnQtaGFuZCByYW5nZQoJYmFzcyA9IG5vdGVUb01JREkoYmFzcykKCXdoaWxlIGJhc3MgPCBMSF9MT1dFU1QgZG8gYmFzcyA9IGJhc3MgKyAxMiBlbmQKCgktLSB1c2UgYXZlcmFnZSBwaXRjaCB2YWx1ZSBmb3Igdm9pY2luZwoJbG9jYWwgYXZnID0gMAoJZm9yIF8sIHYgaW4gaXBhaXJzKHZvKSBkbyBhdmcgPSBhdmcgKyB2IGVuZAoJbG9jYWwgQ09VTlQgPSAjdm8KCXdoaWxlIGF2ZyA8IChSSF9DRU5UUkUgLSAxMikgKiBDT1VOVCBkbwoJCWF2ZyA9IGF2ZyArIDEyICogQ09VTlQgLS0gcmFpc2Ugbm90ZXMganVzdCBiZWxvdyByaWdodC1oYW5kIG9jdGF2ZQoJCWZvciBpLCB2IGluIGlwYWlycyh2bykgZG8gdm9baV0gPSB2ICsgMTIgZW5kCgllbmQKCXdoaWxlIGF2ZyA8IFJIX0NFTlRSRSAqIENPVU5UIGRvCgkJYXZnID0gYXZnICsgMTIgLS0gaW52ZXJ0IHZvaWNpbmcgdW50aWwgYXZlcmFnZSBwaXRjaCBhYm92ZSByaWdodC1oYW5kIG9jdGF2ZQoJCXRhYmxlLmluc2VydCh2bywgdGFibGUucmVtb3ZlKHZvLCAxKSArIDEyKQoJZW5kCgktLSBzd2FwIGVuZCBub3RlcyBmb3Igc2xpZ2h0bHkgb3BlbiB2b2ljaW5nCgl2b1sxXSwgdm9bbWF0aC5taW4oQ09VTlQgKyAxLCA0KV0gPSB2b1tDT1VOVF0gLSAxMiwgdm9bMV0gKyAxMgotLQlpZiBDT1VOVCA9PSA0IHRoZW4KLS0JCXZvWzFdLCB2b1s0XSA9IHZvWzRdIC0gMTIsIHZvWzFdICsgMTIKLS0JZWxzZSAtLSBkb3VibGUgb25lIG5vdGUKLS0JCWxvY2FsIHRvcCA9IGF2ZyArIHZvWzFdICsgMTIKLS0JCWxvY2FsIGRvd24gPSBhdmcgKyB2b1tDT1VOVF0gLSAxMgotLQkJbG9jYWwgY2VudHJlID0gUkhfQ0VOVFJFICogQ09VTlQKLS0JCWlmIG1hdGguYWJzKGRvd24gLSBjZW50cmUpIDw9IG1hdGguYWJzKHRvcCAtIGNlbnRyZSkgdGhlbgotLQkJCXRhYmxlLmluc2VydCh2bywgMSwgdm9bQ09VTlRdIC0gMTIpCi0tCQllbHNlCi0tCQkJdGFibGUuaW5zZXJ0KHZvLCB2b1sxXSArIDEyKQotLQkJZW5kCi0tCWVuZAoKCXJldHVybiBiYXNzLCB2bwplbmQ7IGVuZAoKbG9jYWwgdGVzdCA9IGZ1bmN0aW9uIChjaG9yZCwgbmFtZSkKCS0tIGZvciBpLCB2IGluIGlwYWlycyhjaG9yZCkgZG8gcHJpbnQoaSwgaW50dlRvTm90ZSh2KSwgbm90ZVRvU3RyKGludHZUb05vdGUodikpKSBlbmQKCWZvciBpID0gLTcsIDcgZG8KCQlsb2NhbCBsaCwgcmggPSB2b2ljaW5nKGNob3JkLCBpKQoJCWlvLndyaXRlKCgiJTE0cyIpOmZvcm1hdChub3RlVG9TdHIoaSkgLi4gbmFtZSAuLgoJCQkoY2hvcmRbMF0gYW5kICIvIiAuLiBub3RlVG9TdHIoaSArIGludHZUb05vdGUoY2hvcmRbMF0pKSBvciAiIikpKQoJCWlvLndyaXRlICJcdFx0XHQiCgkJZm9yIF8sIHYgaW4gaXBhaXJzKGNob3JkKSBkbyBpZiB2IH49ICIwIiB0aGVuCgkJCWlvLndyaXRlKCgiICUzcyIpOmZvcm1hdChub3RlVG9TdHIoaW50dlRvTm90ZSh2KSArIGkpKSkKCQllbmQgZW5kCgkJaWYgY2hvcmRbMF0gYW5kIGNob3JkWzBdIH49ICIwIiB0aGVuCgkJCWlvLndyaXRlKCgiIC8gJTNzIik6Zm9ybWF0KG5vdGVUb1N0cihpbnR2VG9Ob3RlKGNob3JkWzBdKSArIGkpKSkKCQllbmQKCQlpby53cml0ZSAiXHRcdFx0IgoJCWlvLndyaXRlKCgiICUzcyIpOmZvcm1hdChNSURJdG9TdHIobGgpKSkKCQlmb3IgXywgdiBpbiBpcGFpcnMocmgpIGRvIGlvLndyaXRlKCgiICUzcyIpOmZvcm1hdChNSURJdG9TdHIodikpKSBlbmQKCQlpby53cml0ZSAnXG4nCgllbmQKCWlvLndyaXRlICdcbicKZW5kCgp0ZXN0KHsiMSIsICIzIiwgIiM1In0sICIrIikKdGVzdCh7IjEiLCAiYjMiLCAiNSIsIFswXSA9ICIyIn0sICJtIikKdGVzdCh7IjEiLCAiMyIsICI1IiwgWzBdID0gIjUifSwgIiIpCnRlc3QoeyIxIiwgIjQiLCAiNSIsICJiNyIsICI5In0sICI5c3VzIikKdGVzdCh7IjEiLCAiMyIsICI1IiwgImI3IiwgImI5IiwgIjEzIn0sICI3KGI5LDEzKSIpCnRlc3QoeyIxIiwgIjAiLCAiNSJ9LCAiNSIpCnRlc3QoeyIxIiwgIjQiLCAiNSIsICIyIn0sICJzdXM0MiIpCg==