local math, pairs, ipairs, setmetatable, table_insert
    = math, pairs, ipairs, setmetatable, table.insert

local minetest, vector, nodecore
    = minetest, vector, nodecore

include("vector_extensions")
local region = include("region")

-- This is the object that is returned by this script.
local contraption = {}

-- Some constants. Should probably be removed.
local AIR = { name = "air" }
local PLANK = { name = "nc_woodwork:plank" }
local CONTRAPTION_WOOD = { name = "nc_contraptions:contraption_wood" }

-- Counts up to infinity as contraptions get created.
-- Each contraption gets assigned a unique id for its lifetime.
local id_counter = 0

-- Table containing the currently active contraptions keyed by their id.
local active_contraptions = {}

-- Inactive contraptions get stored in mod storage.
-- Currently only being used to save contraptions on shutdown.
local mod_storage = minetest.get_mod_storage()

-- TODO: Friction depending on ground.
-- TODO: Gravity.
-- TODO: Water physics!
-- TODO: Rotation.
-- TODO: Sound.
-- TODO: Discoveries.

-- TODO: Push items in a pyramid.
-- TODO: Damage players colliding with fast-moving contraption.
-- TODO: Damage players when squishing them into a wall.
-- TODO: Allow glueing separate contraptions together?

-- TODO: Add region type.
-- TODO: Unload and save contraptions when they're in unloaded chunks.
-- TODO: Use meta field `infotext` for displaying debug info about a contraption?
-- TODO: Use voxel manipulator for moving contraptions.

--------------------
-- EVENT HANDLING --
--------------------

function contraption.on_startup()
    local version = mod_storage:get_int("version")

    if version == 0 then
        -- Assume that no mod data has been saved yet.
        return
    elseif version ~= 1 then
        error("Unknown mod storage version " .. version)
        return
    end

    id_counter = mod_storage:get_int("id_counter")

    local contraptions_str = mod_storage:get("contraptions")
    local contraptions = minetest.deserialize(contraptions_str)

    for _, id in ipairs(contraptions) do
        local str = mod_storage:get("contraption_" .. id)
        contraption.load_from_string(id, str)
    end
end

function contraption.on_shutdown()
    -- TODO: Only modify mod storage where contraptions have changed / been destroyed.
    --       For now we're just going to wipe the storage and re-create it.
    mod_storage:from_table(nil)

    mod_storage:set_int("version", 1)
    mod_storage:set_int("id_counter", id_counter)

    local contraptions = {}

    for id, contrap in pairs(active_contraptions) do
        local str = contrap:save_to_string()
        mod_storage:set_string("contraption_" .. id, str)

        table_insert(contraptions, id)
    end

    mod_storage:set_string("contraptions", minetest.serialize(contraptions));
end

function contraption.on_global_step(delta_time)
    for _, contrap in pairs(active_contraptions) do
        contrap:update(delta_time)
    end
end

----------------------
-- PUBLIC FUNCTIONS --
----------------------

function contraption.find(pos)
    -- First check if the node at `pos` is a contraption block.
    for _, c in pairs(active_contraptions) do
        if c.region:contains(pos) then
            local rel_pos = c.region:to_relative(pos)
            if c.nodes[rel_pos:hash()] then return c end
        end
    end
    return nil
end

-- Returns if the specified node is pushable by a contraption, like items.
function contraption.is_pushable(node)
    local def = minetest.registered_nodes[node.name]
    if def and def.groups and def.groups.is_stack_only then return true end
    return false
end

-------------------------------------
-- CONTRAPTION TYPE IMPLEMENTATION --
-------------------------------------

local metatable = { __index = contraption }
contraption.metatable = metatable

function contraption.create(r)
    r = region.copy(r)

    local nodes = {}
    local num_nodes = 0
    for pos in r:iter_node_positions() do
        local node = minetest.get_node(pos)
        if nodecore.match(node, PLANK) then
            local offset = r:to_relative(pos)
            nodes[offset:hash()] = CONTRAPTION_WOOD
            num_nodes = num_nodes + 1
        end
    end

    -- Less than 4 nodes don't make a contraption.
    if num_nodes < 4 then return nil end

    -- TODO: Shrink region to the minimum required cuboid.
    --       In the above code we could just use pos as table key.

    -- TODO: Flood fill algorithm to make sure all nodes are connected.

    id_counter = id_counter + 1
    local result = setmetatable({
        id = id_counter,
        region = r,
        nodes = nodes,
        num_nodes = num_nodes,
    }, metatable)

    -- Change nodes from base nodes to their contraption version.
    for pos_hash, node in pairs(nodes) do
        local rel_pos = vector.from_hash(pos_hash)
        local abs_pos = r:to_absolute(rel_pos)
        minetest.set_node(abs_pos, node)
    end

    result:on_initialize()
    active_contraptions[result.id] = result
    return result
end

function contraption:on_initialize()
    local above_nodes = {}
    for orig_pos_hash, node in pairs(self.nodes) do
        local orig_pos = vector.from_hash(orig_pos_hash)

        -- Calculate the nodes above the contraption that it
        -- could potentially pull along with it as it moves.
        local above_pos = orig_pos:offset(0, 1, 0)
        if not self.nodes[above_pos:hash()] then
            -- Non-contraption block above this one. Move items here along.
            table_insert(above_nodes, above_pos)
        end
    end
    self.above_nodes = above_nodes
end

function contraption.load_from_string(id, str)
    local obj = minetest.deserialize(str)

    if obj.version ~= 1 then
        error("Unknown contraption version " .. obj.version)
        return nil
    end

    local result = setmetatable({
        id = id,

        region    = region.copy(obj.region),
        nodes     = obj.nodes,
        num_nodes = obj.num_nodes,

        motion  = obj.motion  and vector.copy(obj.motion ) or nil,
        partial = obj.partial and vector.copy(obj.partial) or nil,
    }, metatable)

    result:on_initialize()
    active_contraptions[id] = result
    return obj
end

function contraption:save_to_string()
    local to_save = {
        version = 1,

        region    = self.region,
        nodes     = self.nodes,
        num_nodes = self.num_nodes,

        motion  = self.motion,
        partial = self.partial,
    }
    return minetest.serialize(to_save)
end

function contraption:destroy()
    active_contraptions[self.id] = nil

    for pos_hash, node in pairs(self.nodes) do
        local rel_pos = vector.from_hash(pos_hash)
        local abs_pos = self.region:to_absolute(rel_pos)
        local def = minetest.registered_nodes[node.name]
        minetest.set_node(abs_pos, def.drop_in_place)
    end
end

function contraption:push(pusher, dir)
    -- See if the same player has already pushed this contraption recently.
    -- If so, do not apply the full amount of motion from the push.
    local pusher_name = pusher.get_player_name and pusher:get_player_name() or ""
    self.recent_pusher = self.recent_pusher or {}
    local delay = self.recent_pusher[pusher_name]
    if delay then dir = dir * (1 - math.min(1, delay)) end
    self.recent_pusher[pusher_name] = 1.0 -- seconds

    self.motion = self.motion or vector.zero()
    self.motion = self.motion + dir
end

function contraption:update(delta_time)
    if not self.motion then return end

    -- Partial motion that accumulates over time,
    -- since we can only move in increments of 1.
    self.partial = self.partial or vector.zero()
    self.partial = self.partial + self.motion * delta_time

    -- If partial motion has increased to more than 1 on
    -- one axis, find out which axis has the largest motion ..
    local which = 0
    do
        local max = 0
        for i = 1, 3 do
            local abs = math.abs(self.partial[i])
            if abs >= 1 and abs > max then
                max = abs
                which = i
            end
        end
    end

    -- .. and move it 1 step into that direction.
    if which ~= 0 then
        local step = vector.zero()
        step[which] = math.sign(self.partial[which])
        local moved_nodes = self:move(step)

        if moved_nodes then
            -- Reduce partial motion by the amount moved.
            self.partial = self.partial - step

            -- Push players around.
            local r = self.region:expand(2):extend_in_place(step)
            for _, player in ipairs(minetest.get_objects_in_area(r.min, r.max)) do
                if player:is_player() then
                    local extends = region.from_object(player)
                    extends:expand_in_place(0.5)
                    extends:extend_in_place(0, -0.5, 0)
                    extends:extend_in_place(-step)

                    for pos in extends:iter_node_positions() do
                        if moved_nodes[pos:hash()] then
                            -- TODO: Add velocity instead of teleporting.
                            player:set_pos(vector.add(player:get_pos(), step))
                            break
                        end
                    end
                end
            end
        else
            -- Reset motion into the direction that we bumped into.
            -- Allows for "sliding" along walls instead of stopping outright.
            self.motion[which] = 0
            self.partial[which] = 0
        end
    end

    -- Apply friction.
    local FRICTION = 0.25
    self.motion = self.motion * (1 - FRICTION * delta_time)

    -- If motion is small enough, unset it for performance.
    if self.motion:length() < 0.1 then
        self.motion = nil
        self.partial = nil
    end

    if self.recent_pusher then
        local has_pushers = false
        for pusher, delay in pairs(self.recent_pusher) do
            if delay > 0 then
                self.recent_pusher[pusher] = math.max(0, delay - delta_time)
                has_pushers = true
            end
        end
        -- If there are no active pushers, delete the `recent_pushers` table.
        if not has_pushers then self.recent_pusher = nil end
    end
end

function contraption:move(offset)
    -- Hash table of absolute positions before moved to nodes that have been moved by the
    -- contraption, either because they're part of it, or have been pushed as a result.
    local moved_nodes = {}
    -- TODO: Just have a function that returns the nodes-to-moved (if possible) and a separate one to actually do the moving?

    -- `to_clear` and `to_push` use a relative position hash
    -- as their key, since entries will need to be removed.
    local to_clear = {} -- Table of nodes to be cleared (to `AIR`).
    local to_push  = {} -- Table of nodes that want to be pushed.
    -- `to_set` is an append-only array with `{ pos, node, [meta] }` entries.
    local to_set   = {} -- Array of nodes that will be modified.

    -- Assume that every node this contraption occupies needs to be cleared.
    -- We'll remove entries from `to_clear` when we know a node is moved there.
    for pos_hash in pairs(self.nodes) do to_clear[pos_hash] = AIR end

    for _, rel_pos in ipairs(self.above_nodes) do
        local abs_pos = self.region:to_absolute(rel_pos)
        local node = minetest.get_node(abs_pos)
        if contraption.is_pushable(node) then
            to_push[rel_pos:hash()] = {
                node = node,
                meta = minetest.get_meta(abs_pos):to_table()
            }
        end
    end

    -- TODO: Redo this loop to work similar to the `to_push` loop below.
    for old_rel_pos_hash, node in pairs(self.nodes) do
        local old_rel_pos = vector.from_hash(old_rel_pos_hash)
        local old_abs_pos = self.region:to_absolute(old_rel_pos)

        local new_abs_pos = old_abs_pos + offset
        local new_rel_pos = old_rel_pos + offset
        local new_rel_pos_hash = new_rel_pos:hash()

        -- Node is being moved to this position, no need to clear here.
        to_clear[new_rel_pos_hash] = nil

        local self_overlap = self.nodes[new_rel_pos_hash]
        if self_overlap then
            moved_nodes[old_abs_pos:hash()] = { node = node }
            if not nodecore.match(node, self_overlap) then
                table_insert(to_set, { pos = new_abs_pos, node = node })
            end
        else
            local new_node = minetest.get_node(new_abs_pos)
            -- TODO: Could also just check `to_push` first instead of checking the node.
            if contraption.is_pushable(new_node) then
                new_node = { node = new_node, meta = minetest.get_meta(new_abs_pos):to_table() }
                moved_nodes[old_abs_pos:hash()] = new_node
                table_insert(to_set, { pos = new_abs_pos, node = node })

                while true do
                    old_abs_pos = new_abs_pos
                    old_rel_pos = new_rel_pos
                    new_abs_pos = new_abs_pos + offset
                    new_rel_pos = new_rel_pos + offset
                    new_rel_pos_hash = new_rel_pos:hash()

                    local pushable = to_push[new_rel_pos_hash]
                    if pushable then
                        -- The next node is a pushable node that was going to
                        -- get pushed by the contraption anyway, so continue.
                        moved_nodes[old_abs_pos:hash()] = new_node
                        table_insert(to_set, nodecore.underride({ pos = new_abs_pos }, new_node))
                        to_push[new_rel_pos_hash] = nil
                        new_node = pushable
                    elseif self.nodes[new_rel_pos_hash] then
                        -- The next node is part of the contraption.
                        -- If it can move, this pushable node can move.
                        moved_nodes[old_abs_pos:hash()] = new_node
                        table_insert(to_set, nodecore.underride({ pos = new_abs_pos }, new_node))
                        -- Do not clear this node by the contraption moving.
                        to_clear[new_rel_pos_hash] = nil
                        break
                    elseif nodecore.buildable_to(new_abs_pos) then
                        -- The next node is replaceable, so we can replace it.
                        moved_nodes[old_abs_pos:hash()] = new_node
                        table_insert(to_set, nodecore.underride({ pos = new_abs_pos }, new_node))
                        break
                    else
                        -- There's a node in the way, abort!
                        -- NOTE: Can't push a pushable node with another
                        --       one if already pushed by the contraption.
                        return nil
                    end
                end
            elseif nodecore.buildable_to(new_node) then
                moved_nodes[old_abs_pos:hash()] = { node = node }
                table_insert(to_set, { pos = new_abs_pos, node = node })
            else
                -- We bumped into a wall or something.
                return nil
            end
        end
    end

    -- The `to_push` table contains "lose" nodes that are not directly
    -- pushed by the contraption, and may or may not be pushed.
    for pos_hash, node in pairs(to_push) do
        local rel_pos = vector.from_hash(pos_hash)
        local forward_rel_pos = rel_pos + offset

        -- If there's a node to push ahead of this one, skip.
        -- The node ahead will take care of pulling the ones behind along with it.
        if to_push[forward_rel_pos:hash()] then goto continue end

        local forward_abs_pos = self.region:to_absolute(forward_rel_pos)

        if self.nodes[forward_rel_pos] then
            -- Do not clear this node by the contraption moving.
            to_clear[forward_rel_pos] = nil
        else
            -- If the node(s) can't be pushed, then just don't, but continue
            -- moving the rest of the contraption and other pushable nodes.
            if not nodecore.buildable_to(forward_abs_pos) then goto continue end
        end

        moved_nodes[self.region:to_absolute(rel_pos):hash()] = node
        table_insert(to_set, nodecore.underride({ pos = forward_abs_pos }, node))

        while true do
            local backward_rel_pos = rel_pos - offset
            local backward_rel_pos_hash = backward_rel_pos:hash()
            node = to_push[backward_rel_pos_hash]
            if not node then break end

            local abs_pos = self.region:to_absolute(rel_pos)
            moved_nodes[self.region:to_absolute(backward_rel_pos):hash()] = node
            table_insert(to_set, nodecore.underride({ pos = abs_pos }, node))
            rel_pos = backward_rel_pos
            pos_hash = backward_rel_pos_hash
        end

        to_clear[pos_hash] = AIR
        ::continue::
    end

    -- Set nodes that need to be changed.
    for _, e in ipairs(to_set) do
        minetest.set_node(e.pos, e.node)
        if e.meta then minetest.get_meta(e.pos):from_table(e.meta) end
    end

    -- Clear nodes that need to be cleared (to AIR).
    for pos_hash, node in pairs(to_clear) do
        local rel_pos = vector.from_hash(pos_hash)
        local abs_pos = self.region:to_absolute(rel_pos)
        minetest.set_node(abs_pos, node)
    end

    -- Move the contraption in the world.
    self.region.min = self.region.min + offset
    self.region.max = self.region.max + offset
    return moved_nodes
end

return contraption