advf = {
    advf_biology = 1,
    advf_power = 1,
    advf_physics = 1,
    advf_construction = 1,
    advf_fields = 1,
    advf_chemistry = 1,
    advf_computers = 1,
    advf_sociology = 1
}

function make_branches(ff, keep_gray_boxes)
    local branches = {}
    local f2br = {}
    local starting_fields = rget_starting_fields()

    local map = { engineering = "advanced_engineering" }
    if keep_gray_boxes then
        map.chemistry = "advanced_metallurgy"
        map.nuclear_fission = "advanced_fusion"
        map.physics = "fusion_physics"
        map.electronics = "optronics"
    end
    for i,s in pairs(starting_fields) do
        if map[s] ~= nil then
            starting_fields[i] = map[s]
        end
    end

    for i,f in pairs(starting_fields) do
        local n = rawlen(branches) + 1
        local b = {
            branch_last_field = "advf_" .. i,
            branchnum = n,
            field = f,
        }
        table.insert(branches, b)
        ff[f].is_branch_root = 1
    end

    for i,b in ipairs(branches) do
        local fname = b.field
        local marks = {}
        local n = 1
        while advf[fname] == nil and ff[fname] ~= nil do
            local f = ff[fname]
            if marks[fname] ~= nil then
                error(tostring("detected tech loop ", marks))
            end
            marks[fname] = n
            n = n + 1
            f.branch = i
            f.techs = {}
            fname = f.next_field
        end
    end

    return branches
end

function ordered_fields_by_cost(ff)
    local fbycost = {}
    for i,f in pairs(ff) do
        if f.branch ~= nil and f.is_branch_root == nil then
            table.insert(fbycost, f)
        end
    end
    table.sort(fbycost, function(a,b) return a.cost < b.cost end)
    return fbycost
end

function ordered_techs_by_cost(tt, ff)
    local tbycost = {}
    for i,t in pairs(tt) do
        if t.field ~= "advanced_governments" then
            local f = ff[t.field]
            if f ~= nil and f.branch ~= nil then
                t.cost = f.cost
                table.insert(tbycost, t)
            end
        end
    end
    table.sort(tbycost, function(a,b) return a.cost < b.cost end)
    return tbycost
end

function random_pick(arr, i)
    if i > rawlen(arr) then i = rawlen(arr) end
    return table.remove(arr, random(i))
end

function rebuild_tree(ff, bb, fbc, tbc)
    local out_bb = {}
    local bb0 = {}
    for i,b in ipairs(bb) do
        out_bb[i] = {}
        bb0[i] = b
    end

    -- main loop
    local newbi = -1
    while rawlen(tbc) > 0 and rawlen(bb) > 0 do
        local bi
        if newbi > 0 then
            bi = newbi
            newbi = -1
        else
            bi = random(rawlen(bb))
        end
        local b = bb[bi]
        local f = ff[b.field]
        if f.name == "advanced_governments" then
            f.techs = {
                "federation",
                "confederation",
                "galactic_unification",
                "imperium"
            }
        else
            local pick_empty = false
            if rawlen(f.techs) > 0 then
                local nslots = rawlen(fbc) * 3
                for i,b in ipairs(bb) do
                    nslots = nslots + 4 - rawlen(ff[b.field].techs)
                end
                local ntechs = rawlen(tbc) - rawlen(fbc)
                if random(nslots) > ntechs then
                    pick_empty = true
                end
            end
            if pick_empty then
                table.insert(f.techs, "-")
            else
                local t = random_pick(tbc, 3)
                t.field = b.field
                table.insert(f.techs, t.name)
            end
        end

        -- field full
        if rawlen(f.techs) == 4 then
            table.insert(out_bb[b.branchnum], f)
            if rawlen(fbc) > 0 then
                local fn = random_pick(fbc, 1)
                b.field = fn.name
                newbi = bi
            else
                table.remove(bb, bi)
                newbi = -1
            end
        end
    end

    -- push current top fields
    for i,b in ipairs(bb) do
        local f = ff[b.field]
        table.insert(out_bb[b.branchnum], f)
    end

    -- push unused fields
    while rawlen(fbc) > 0 do
        f = table.remove(fbc, 1)
        table.insert(out_bb[random(8)], f)
    end

    -- push advanced fields
    for i,b in ipairs(bb0) do
        table.insert(out_bb[i], ff[b.branch_last_field])
    end

    -- link
    for i,o in ipairs(out_bb) do
        for j=1,rawlen(o) do
            if j > 1 then
                o[j-1].next_field = o[j].name
                o[j].prev_field = o[j-1].name
            end
        end
    end
    return out_bb
end

function set_id(t, tag)
    for i,v in pairs(t) do
        v[tag] = i
    end
end

function go()
    set_seed()
    local ff = rget_fields() set_id(ff, "name")
    local tt = rget_techs()  set_id(tt, "name")
    local bb = make_branches(ff, 1)
    local fbc = ordered_fields_by_cost(ff)
    local tbc = ordered_techs_by_cost(tt, ff)
    rebuild_tree(ff, bb, fbc, tbc)
    rset_fields(ff)
    rset_techs(tt)
end

go()
msgbox("Tech tree has been randomized")
