foldl = function(f, z, l)
  for i = 1, #l do z = f(z, l[i]) end
  return z
end

foldl1 = function(f, l)
  return foldl(f, table.remove(l, 1), l)
end

foldr = function(f, z, l)
  for i = #l, 1, -1 do z = f(l[i], z) end
  return z
end

foldr1 = function(f, l)
  return foldr(f, table.remove(l), l)
end

map = function(f, l)
  local z = table.sub(l)
  for k in pairs(l) do z[k] = f(rawget(l, k)) end
  return z
end

filter = function(pr, l)
  return foldl(function(c, v)
                 return pr(v) == true and table.insert(c, v) or c
               end, {}, l)
end

zipWith = function(f, a, b)
  local n = {}
  for i = 1, math.min(#a, #b) do n[i] = f(a[i], b[i]) end
  return n
end

elem = function(t, x)
  return foldl(function(c, v) return c or v == x end, false, t)
end

enum = function(i, j)
  local z = {}
  for k = i, j do z[#z + 1] = k end
  return z
end

table.join = function(a, b)
  return foldl(function(c, v)
                 table.insert(c, v); return c
               end, a, b)
end

table.sub = function(t, i, j)
  local n = {}
  i = i or 1
  j = j or #t
  table.move(t, i, j, 1, n)
  return n
end

table.rotate = function(t, k)
  local n = {}
  for i = 1, #t do
    n[i] = t[(i + k - 1) % #t + 1]
  end
  return n
end

tableStr = function(t, ind)
  ind = ind or 0
  local str = '{\n'
  local mLen = string.len(#t) + 1
  for k in pairs(t) do
    local kStr = k
    local xStr = rawget(t, k)
    if type(xStr) == "boolean" then
      xStr = xStr and "True" or "False"
    elseif type(xStr) == "string" then
      xStr = '"' .. xStr .. '"'
    elseif type(xStr) == "table" then
      xStr = tableStr(xStr, ind + 1)
    end
    str = str .. string.rep(' ', ind + mLen - string.len(kStr)) .. kStr .. ": " .. xStr .. '\n'
  end
  str = str .. string.rep(' ', ind) .. '}'
  if ind == 0 then str = str .. '\n' end
  return str
end

tableStr2 = function(t)
  local str = '{'
  for k in pairs(t) do
    local kStr = k
    local xStr = rawget(t, k)
    if type(xStr) == "boolean" then
      xStr = xStr and "True" or "False"
    elseif type(xStr) == "string" then
      xStr = '"' .. xStr .. '"'
    elseif type(xStr) == "table" then
      xStr = tableStr2(xStr)
    end
    str = str .. ' ' .. kStr .. ": " .. xStr .. ","
  end
  return str == '{' and "{ }" or string.sub(str, 1, string.len(str) - 1) .. " }"
end

cartProd = function(...)
  local _cartProd = function(a, b)
    local l = {}
    for _, v1 in pairs(a) do
      for _, v2 in pairs(b) do
        local _v1 = v1
        if type(_v1) ~= "table" then _v1 = {_v1} end
        if type(v2) ~= "table" then v2 = {v2} end
        l[#l + 1] = table.join(_v1, v2)
      end
    end
    return l
  end
  
  return foldr1(_cartProd, table.pack(...))
end

lexgt = function(a, b)
  for i = 1, #a do
    if b[i] == nil then return 1
    elseif a[i] > b[i] then return 1
    elseif a[i] < b[i] then return -1
    end
  end
  if #a < #b then return -1 end
  return 0
end

revlexgt = function(a, b)
  if #a > #b then return 1 end
  if #a < #b then return -1 end
  for i = #a, 1, -1 do
    if a[i] > b[i + #b - #a] then return 1
    elseif a[i] < b[i + #b - #a] then return -1
    end
  end
  return 0
end

--main

DESC = [[
Usage: lua chords.lua filename [option]
Options: 
  -u: use unicode characters
  -n: allow omitted extensions
 -nl: allow omitted chord tones
  -a: allow all avoid tones
  -f: allow all chords without checking
  -m: disallow all minor ninths
  -s: disallow suspended chords]]

-- command line argument flags
for i = 2, #arg do
  if arg[i] == "-u" then bUnicode = true
  elseif arg[i] == "-n" then bNoUpper = true
  elseif arg[i] == "-nl" then bNoLower = true
  elseif arg[i] == "-a" then bAllowAvoid = true
  elseif arg[i] == "-f" then bAllowAll = true
  elseif arg[i] == "-m" then bStrict = true
  elseif arg[i] == "-s" then bNoSus = true end
end

-- semitone offsets from chord root
local SEMITONES = {{0}
                  ,{ 4,  3,  5,  2}
                  ,{ 7,  6,  8}
                  ,{10,  9, 11}
                  ,{14, 13, 15}
                  ,{17, 16, 18}
                  ,{21, 20}}

-- chord factor strings
local CHORD_STR = {{"1"}
                  ,{"3" , "b3" , "4"  , "2"}
                  ,{"5" , "b5" , "#5"}
                  ,{"b7", "6"  , "M7"}
                  ,{"9" , "b9" , "#9"}
                  ,{"11", "b11", "#11"}
                  ,{"13", "b13"}}

if bNoUpper then for i = 5, 7 do table.insert(SEMITONES[i], -1) table.insert(CHORD_STR[i], "") end end
if bNoLower then for i = 2, 4 do table.insert(SEMITONES[i], -1) table.insert(CHORD_STR[i], "") end end
if bNoSus then
  table.remove(SEMITONES[2], 4)
  table.remove(SEMITONES[2], 3)
  table.remove(CHORD_STR[2], 4)
  table.remove(CHORD_STR[2], 3)
end

local chordStr = function(l)
  local sym = ""   -- chord symbol
  local scale = {} -- scale table
  local unalt = 4  -- extension index
  
  -- highest extension resulting from stacking thirds
  while (l[unalt] ~= -1 and unalt < 7) do unalt = unalt + 1 end
  -- highest unaltered extension in the chord
  while ((l[unalt] ~= SEMITONES[unalt][1] or l[unalt] == -1) and unalt > 4) do unalt = unalt - 1 end
  -- do not allow abbreviated extensions sixth chords
  if l[4] == 9 then unalt = 4 end
  
  -- chord symbol for the lower structure
  sym = (l[2] == 3 and "m" or "")
     .. (l[4] == 11 and "M" or "")
     .. (l[4] == 9 and "6" or l[4] ~= -1 and tostring(unalt * 2 - 1) or "")
     .. (l[3] == 6 and "b5" or l[3] == 8 and "#5" or "")
  if sym == "m6b5" then sym = "dim7" end
  
  -- append alterations
  for i = 5, 7 do
    if l[i] ~= -1 then
      local acc = l[i] - SEMITONES[i][1]
      if acc ~= 0 or i > unalt then
        -- add correct accidentals
        -- acc > 0 and string.rep('#', acc) or acc < 0 and string.rep('b', -acc) or '/'
        sym = sym .. (acc == 1 and '#' or acc == -1 and 'b' or '/')
                  .. tostring(i * 2 - 1)
      end
    end
  end
  
  -- special cases for the lower structure
  sym = sym .. (l[2] == 5 and "sus4" or l[2] == 2 and "sus2" or "")
            .. (l[2] == -1 and "no3" or "")
            .. (l[3] == -1 and "no5" or "")
  if sym == "" then sym = "M" end
  if sym == "mb5" then sym = "dim" end
  
  -- correctly label added chords
  sym = string.gsub(sym, "^/", "add")
  if foldl(function(a, b) return b ~= -1 or a end, false, table.sub(l, 5, 7)) then
    sym = string.gsub(sym, "^b", "addb")
    sym = string.gsub(sym, "^#", "add#")
  end
  if bUnicode then
    sym = string.gsub(string.gsub(sym, "b", "\u{266D}"), "#", "\u{266F}")
  end
  
  -- remove omitted notes from the chord table
  l = filter(function(x) return x ~= -1 end, l)
  -- reduce octaves from the chord tables
  scale = map(function(x) return x % 12 end, table.sub(l))
  -- sort the scale table
  table.sort(scale)
  
  -- replace chord table with spellings of chord factors
  local flatten = foldl(table.join, {}, CHORD_STR)
  for k, v in pairs(foldl(table.join, {}, SEMITONES)) do
    l = map(function(x)
              return x == v and flatten[k] or x
            end, l)
  end
  
  -- reorder the scale table to the largest inversion
  -- scale = foldl(function(l, k)
  --                 local n = table.rotate(l, k)
  --                 n = map(function(x) return (x - n[1]) % 12 end, n)
  --                 return revlexgt(l, n) == 1 and l or n
  --               end, scale, enum(1, #scale - 1))
  
  -- return a 2-tuple containing formatted string and scale table
  return {string.format("%-24s%-24s%s", table.concat(l, "-"), table.concat(scale, " "), sym), scale}
end

local validChord = function(l)
  if bAllowAll then return true end
  
  -- strict definition of avoid note:
  --  any chord tone forming a minor ninth above another chord tone
  --  but allow b9 unless M7 is present
  --  also allow b13 when both b3 and b7 are present
  --  but disallow minor seconds (e.g. #9 and b11, #5 and 6) and octaves (e.g. b3 and #9)
  local red = map(function(x) return x % 12 end, l)
  
  return (foldl1(function(a, b)
                   return a and b
                 end, zipWith(function(a, b)
                                return a == -1 or b == -1
                                    or b - a ~= 13
                                    or ((b == 13 and l[4] ~= 11)
                                     or (b == 20 and l[2] == 3 and l[4] == 10))
                                    and not bStrict
                              end
                             ,table.sub(l, 1, 3), table.sub(l, 5, 7)))
      and not (l[2] == 2 and l[5] == 15) -- special case
       or bAllowAvoid)
     and foldl1(function(a, b)
                  return a and b
                end, zipWith(function(a, b) return a == -1 or b == -1 or b - a > 1 end
                            ,table.sub(l, 1, 6), table.sub(l, 2, 7)))
     and foldl1(function(t, x)
                  return t and (l[x] == -1 or not elem(table.sub(red, 1, x - 1), red[x]))
                end, enum(1, 7))
end

local getChords = function()
  return map(chordStr, filter(validChord, cartProd(table.unpack(SEMITONES))))
end

if not arg[1] then
  print(DESC)
else
  local ALL_CHORDS = {}
  
  for i = 7, bAllowAll and 2 or 3, -1 do
    if SEMITONES[i][#SEMITONES[i]] == -1 then table.remove(SEMITONES[i]) end
    local chordTable = getChords()
    
    -- this sorts the chords by the reduced scale
    table.sort(chordTable, function(x, y) return lexgt(x[2], y[2]) == -1 end)
    
    file = io.open(arg[1] .. "_" .. tostring(i * 2 - 1) .. ".txt", "w")
    file:write(tableStr(map(function(x) return x[1] end, chordTable)))
    file:close()
    
    ALL_CHORDS = table.join(chordTable, ALL_CHORDS)
    SEMITONES[i] = {-1}
  end
  
  -- this sorts the chords by the reduced scale
  table.sort(ALL_CHORDS, function(x, y) if #x[2] > #y[2] then return false end if #y[2] > #x[2] then return true end return lexgt(x[2], y[2]) == -1 end)
  
  -- this sorts the chords by the chord name
  -- table.sort(ALL_CHORDS, function(x, y) return string.sub(x[1], 49) < string.sub(y[1], 49) end)
  
  file = io.open(arg[1] .. "_all.txt", "w")
  file:write(tableStr(map(function(x) return x[1] end, ALL_CHORDS)))
  file:close()
end