------------------------------------------------------------------------
-- Biome generation.
------------------------------------------------------------------------

-- Number of quart positions per MapBlock.
local N = 4

local function index (x, y, z, dx, dy, dz)
	return (x + 1) * (dy + 2) * (dz + 2)
		+ (y + 1) * (dz + 2)
		+ (z + 1) + 1
end
mcl_levelgen.biome_table_index = index

local id_to_name_map = mcl_levelgen.biome_id_to_name_map

if not core or core.save_gen_notify then -- Mapgen environment.

-- Return biomes in the table BIOMES for each position in the region
-- from X, Y, Z to X1, Y1, Z1, and a margin of one QuartPos around the
-- same, in PRESET, which must be Minecraft block positions divided by
-- 4.  The index of each position so divided in this table is produced
-- from the difference between each such position and the supplied
-- origin in X-major, Z-minor order.

function mcl_levelgen.generate_biomes (preset, biomes, x, y, z, x1, y1, z1)
	local dx = x1 - x + 3
	local dy = y1 - y + 3
	local dz = z1 - z + 3
	preset:index_biomes_begin (dx, dz, x - 1, z - 1)

	for xpos = x - 1, x1 + 1 do
		for ypos = y - 1, y1 + 1 do
			for zpos = z - 1, z1 + 1 do
				local biome
					= preset:index_biomes_cached (xpos, ypos, zpos)
				local idx = index (xpos - x, ypos - y, zpos - z,
						   dx - 2, dy - 2, dz - 2)
				biomes[idx] = biome
			end
		end
	end
end

-- Likewise, but for a column of Luanti MapBlocks of dimensions W
-- and H at X, Y, Z (i.e., Minecraft X, Y, -Z - (W - 1) - 1).

function mcl_levelgen.generate_biomes_at_block (preset, biomes, x, y, z, w, h)
	local qx, qy, qz = x * N, y * N, z * N
	local qw, qh = w * N, h * N
	local qx2, qy2, qz2 = qx + qw - 1, qy + qh - 1, qz + qw - 1
	mcl_levelgen.generate_biomes (preset, biomes, qx, qy, -qz2 - 1,
				      qx2, qy2, -qz - 1)
end

local char = string.char
local name_to_id_map = mcl_levelgen.biome_name_to_id_map

local function encode_biome_list (encoded)
	local str = ""
	for i = 1, #encoded, 2 do
		str = str .. char (encoded[i])
		str = str .. char (name_to_id_map[encoded[i + 1]])
	end
	return str
end

-- Generate a run-length encoding indexed by MapBlock of a table of
-- biomes TABLE generated by mcl_levelgen.generate_biomes_at_block for
-- a column of MapBlocks W in width and H in height, between Y0 and Y0
-- + YH - 1, and assuming that TABLE's coordinates have been
-- translated into Minecraft's coordinate system.  Return a table of
-- node metadata values indexed by suitably inverted MapBlock
-- positions relative to 0, Y0, 0.

local insert = table.insert
local mathmin = math.min
local mathmax = math.max

function mcl_levelgen.encode_biomes (biomes, y0, yh, w, h, hash_for_testing)
	local qw = w * N
	local qh = h * N
	-- local max_index = index (qw, qh, qw, qw, qh, qw)
	-- This assertion is no longer applicable as the biome list
	-- may grow after a vertically larger dimension has been
	-- generated.
	-- assert (#biomes == max_index)
	local x_stride = (qw + 2) * (qh + 2)
	local y_stride = (qw + 2)
	local compressed = {}
	local min = mathmax (0, -y0)
	local max = mathmin (yh - 1, h - y0 - 1)

	if max < 0 then
		return {}
	end

	for x = 0, w - 1 do
		for y = min, max do
			for z = 0, w - 1 do
				local qx, qy, qz = x * N, (y0 + y) * N, (w - z) * N
				local base = index (qx, qy, qz, qw, qh, qw)
				local list = {}
				local n, biome = 0, nil

				for ix = 0, N - 1 do
					local ybase = base
					for iy = 0, N - 1 do
						for iz = 1, N do
							local b = biomes[ybase - iz]
							if b == biome or not biome then
								n = n + 1
							else
								insert (list, n)
								insert (list, biome)
								n = 1
							end
							biome = b
						end
						ybase = ybase + y_stride
					end
					base = base + x_stride
				end
				if biome ~= nil then
					insert (list, n)
					insert (list, biome)
				end
				if not hash_for_testing then
					compressed[{ x = x, y = y, z = z, }]
						= encode_biome_list (list)
				else
					compressed[x * h * w + y * w + z + 1]
						= encode_biome_list (list)
				end
			end
		end
	end
	return compressed
end

end

local byte = string.byte

function mcl_levelgen.index_biome_list (list, qx, qy, qz)
	assert (qx < N and qy < N and qz < N)
	local i, idx = 1, qx * N * N + qy * N + qz + 1
	local biome
	repeat
		idx = idx - byte (list, i)
		biome = byte (list, i + 1)
		i = i + 2
	until idx <= 0
	return id_to_name_map[biome]
end

local insert = table.insert

function mcl_levelgen.expand_biome_list (list, dest, seen)
	local i, n = 1, #list
	while i <= n do
		local biome = byte (list, i + 1)
		if not seen[biome] then
			seen[biome] = true
			local name = id_to_name_map[biome]
			if name then
				insert (dest, name)
			end
		end
		i = i + 2
	end
end

function mcl_levelgen.debug_biome_list (list)
	local i, n = 1, #list
	local biomes = {}
	while i <= n do
		local nbiomes = byte (list, i)
		local biome = byte (list, i + 1)
		for k = 1, nbiomes do
			insert (biomes, id_to_name_map[biome])
		end
		i = i + 2
	end
	print (#biomes .. " biome entries")
	for y = N - 1, 0, -1 do
		for x = 0, N - 1 do
			local idx = x * N * N + y * N
			print (string.format (" (%d): %-24s %-24s %-24s %-24s",
					      y, biomes[idx + 1], biomes[idx + 2],
					      biomes[idx + 3], biomes[idx + 4]))
		end
	end
end

------------------------------------------------------------------------
-- Biome data storage.
------------------------------------------------------------------------

if core and core.get_meta then -- Mod environment.

local band = bit.band
local arshift = bit.arshift
local floor = math.floor
local mod_storage = core.get_mod_storage ()
local v = vector.zero ()
local conv_pos_raw, seed, is_emerged
local munge_biome_coords = mcl_levelgen.munge_biome_coords

core.register_on_mods_loaded (function ()
	seed = mcl_levelgen.biome_seed
	conv_pos_raw = mcl_levelgen.conv_pos_raw
	is_emerged = mcl_levelgen.is_emerged
end)

local function sample_biome (dim, qx, qy, qz)
	return dim.preset:index_biomes (qx, qy, qz)
end

local index_biome_list = mcl_levelgen.index_biome_list
local lshift = bit.lshift
local concat = table.concat

function mcl_levelgen.get_biome (pos, allow_sample, always_sample)
	v.x = floor (pos.x + 0.5)
	v.y = floor (pos.y + 0.5)
	v.z = floor (pos.z + 0.5)
	local mc_pos_x, mc_pos_y, mc_pos_z, dim = conv_pos_raw (v)
	if not mc_pos_x then
		return nil
	end
	local qx, qy, qz = munge_biome_coords (seed,
					       mc_pos_x,
					       mc_pos_y,
					       mc_pos_z)
	if always_sample then
		return sample_biome (dim, qx, qy, qz)
	end
	qz = -qz - 1
	qy = qy - dim.y_offset / 4

	local bx = arshift (qx, 2)
	local by = arshift (qy, 2)
	local bz = arshift (qz, 2)
	local str = ""

	-- Don't attempt to load metadata for a MapBlock that is yet
	-- to be emerged.
	if is_emerged (dim, bx, by - dim.y_global_block, bz) then
		v.x = lshift (bx, 4)
		v.y = lshift (by, 4)
		v.z = lshift (bz, 4)

		local meta = core.get_meta (v)
		str = meta:get_string ("mcl_levelgen:biome_index")
		if str == "" then
			-- Biome index was overwritten; load it from
			-- mod storage.
			str = mod_storage:get_string (concat ({
				tostring (bx), ",",
				tostring (by), ",",
				tostring (bz),
			}))
			if str ~= "" then
				meta:set_string ("mcl_levelgen:biome_index", str)
			end
		end
	end

	if str == "" then
		-- The caller absolutely requires a biome, so sample.
		if allow_sample then
			return sample_biome (dim, qx, qy, -qz - 1)
		else
			return nil
		end
	end

	local qx = band (qx, 3)
	local qy = band (qy, 3)
	local qz = band (qz, 3)
	return index_biome_list (str, qx, qy, qz)
end

function mcl_levelgen.get_biome_meta (bx, by, bz)
	v.x = bx * 16
	v.y = by * 16
	v.z = bz * 16
	local meta = core.get_meta (v)
	local str = meta:get_string ("mcl_levelgen:biome_index")
	if not str or str == "" then
		-- Biome index was overwritten; load it from mod
		-- storage.
		str = mod_storage:get_string (table.concat ({
			tostring (bx), ",",
			tostring (by), ",",
			tostring (bz),
		}))

		if not str or str == "" then
			return nil
		end
		meta:set_string ("mcl_levelgen:biome_index", str)
	end
	return str
end

local function save_biome_index (pos, bx, by, bz, index)
	-- Saving biome data into an unloaded mapblock's metadata
	-- within a register_on_generated callback triggers a Luanti
	-- bug where the mapchunk is liable to be generated twice if
	-- it has been unloaded since generation.
	if core.compare_block_status (pos, "loaded") then
		local meta = core.get_meta (pos)
		meta:set_string ("mcl_levelgen:biome_index", index)
	else
		core.log ("info", "save_biome_index: Averted possible regeneration of "
			  .. bx .. "," .. by .. "," .. bz)
	end

	mod_storage:set_string (table.concat ({
		tostring (bx), ",",
		tostring (by), ",",
		tostring (bz),
	}), index)
end

core.set_gen_notify ({ custom = true, }, nil, {
	"mcl_levelgen:biome_data",
	"mcl_levelgen:level_height_map",
	"mcl_levelgen:structure_mask",
	"mcl_levelgen:structure_pieces",
	"mcl_levelgen:gen_notifies",
})

core.register_on_generated (function (minp, maxp, blockseed)
	local custom = core.get_mapgen_object ("gennotify").custom
	if not custom then
		return
	end
	local data = custom["mcl_levelgen:biome_data"]
	if not data then
		return
	end
	local x, y, z = minp.x, minp.y, minp.z
	local bx, by, bz = x / 16, y / 16, z / 16
	for pos, index in pairs (data) do
		local ix, iy, iz = pos.x, pos.y, pos.z
		pos.x = pos.x * 16 + x
		pos.y = pos.y * 16 + y
		pos.z = pos.z * 16 + z
		save_biome_index (pos, bx + ix, by + iy, bz + iz, index)
	end
end)

end
