local gtable = require "gears.table"

-- port of https://github.com/WebKit/WebKit/blob/da934454c84ac2dcbf9fca9e5f4ac2644ef25d72/Source/WebCore/platform/graphics/UnitBezier.h

local bezier = {}

function bezier:sample_x(t)
    -- `ax t^3 + bx t^2 + cx t' expanded using Horner's rule.
    return ((self.ax * t + self.bx) * t + self.cx) * t
end

function bezier:sample_y(t)
    return ((self.ay * t + self.by) * t + self.cy) * t
end

function bezier:sample_derivative_x(t)
    return (3.0 * self.ax * t + 2.0 * self.bx) * t + self.cx
end

function bezier:solve_x(x, epsilon)
    local x2, d2
    local t2 = x

    -- First try a few iterations of Newton's method -- normally very fast.
    for _ = 1, 8 do
        x2 = self:sample_x(t2) - x
        if math.abs(x2) < epsilon then
            return t2
        end
        d2 = self:sample_derivative_x(t2)
        if math.abs(d2) < 1e-6 then
            break
        end
        t2 = t2 - x2 / d2
    end

    -- Fall back to the bisection method for reliability.
    local t0 = 0
    local t1 = 1
    t2 = x

    if t2 < t0 then
        return t0
    end
    if t2 > t1 then
        return t1
    end

    while t0 < t1 do
        x2 = self:sample_x(t2)
        if math.abs(x2 - x) < epsilon then
            return t2
        end
        if x > x2 then
            t0 = t2
        else
            t1 = t2
        end
        t2 = (t1 - t0) * 0.5 + t0
    end

    -- Failure.
    return t2
end

function bezier:solve(x, epsilon)
    return self:sample_y(self:solve_x(x, epsilon))
end

local function new(x1, y1, x2, y2)
    local obj = gtable.crush({}, bezier)

    -- Calculate the polynomial coefficients, implicit first and last control points are (0,0) and (1,1).
    obj.cx = 3.0 * x1
    obj.bx = 3.0 * (x2 - x1) - obj.cx
    obj.ax = 1.0 - obj.cx - obj.bx

    obj.cy = 3.0 * y1
    obj.by = 3.0 * (y2 - y1) - obj.cy
    obj.ay = 1.0 - obj.cy - obj.by

    return obj
end

return setmetatable(bezier, {
    __call = function(_, ...)
        return new(...)
    end,
})