using Plots
runge = x->1/(1+x^2)
f = x->1/(1+25x^2)
#P2D to macierz Nx2 o wierszach [x y]
# współczynniki ilorazów dla interp. Newtona
function _diff(P2D)
    b, n = Array(P2D[:, 2]), length(P2D[:, 1])
    for  i = 2:n
        for j = n:-1:i
            b[j] = (b[j] - b[j-1])/(P2D[j, 1] - P2D[j-i+1, 1])
        end
    end
    return b
end

# Zwraca wartość ilorazu.
function diff(P2D)
    last(_diff(P2D))
end

function interp_newton(P2D)
    return function(x)
        b, n = _diff(P2D), length(P2D[:, 1])-1
        sum, p = b[1], 1
        for i in 1:n
            p *= (x - P2D[i, 1])
            sum += b[i+1]*p
            end # nie chce mi się robić Hornera
        sum
    end
end;

err = f_interp->x->abs(f(x)-f_interp(x))
maxerr = f_interp->reduce(max, map(x->err(f_interp)(x), range(-1,stop=1,length=1000)))
w9_eq = interp_newton(reduce(vcat, map(x->[x f(x)], collect(range(-1,stop=1, length=10)))))             # w równoodległych
w9_T10_zeros = interp_newton(reduce(vcat, map(x->[x f(x)], map(j->cos(pi*((2*j-1)/(2*10))), [1:10;])))) # w zerach Czebyszewa
w9_T9_extremums = interp_newton(reduce(vcat, map(x->[x f(x)], map(j->cos(j*pi/9), [0:9;])))) # w extremach Czebyszewa

equal_plot = begin
    plot(f, -1, 1, line=(color=:blue), label="f", title="equal")
    plot!(w9_eq, line=(color=:green), label="equal")
    plot!(err(w9_eq), line=(color=:red),fill=(0, 0.1, :red), label="EQ error")
    annotate!(-1, 2, text(string("max error: ", maxerr(w9_eq)), 10, :left, :top, :crimson))
end
Chebyshev_zeros_plot = begin
    plot(f, -1, 1, line=(color=:blue), label="f", title="Chebyshev's zeros")
    plot!(w9_T10_zeros, line=(color=:green), label="Ch. zeros")
    plot!(err(w9_T10_zeros), line=(color=:red),fill=(0, 0.1, :red), label="CH. zeros error")
    annotate!(-1, 2, text(string("max error: ", maxerr(w9_T10_zeros)), 10, :left, :top, :crimson))
end
row1_plot = plot(equal_plot, Chebyshev_zeros_plot, layout=(1,2), ylims=(-0.3, 2))

Chebyshev_extremums_plot = begin
    plot(f, -1, 1, line=(color=:blue), label="f", title="Chebyshev's extremums")
    plot!(w9_T9_extremums, line=(color=:green), label="Ch. extremums")
    plot!(err(w9_T9_extremums), line=(color=:red), fill=(0, 0.1, :red), label="CH. extremums error")
    annotate!(-1, 1, text(string("max error: ", maxerr(w9_T9_extremums)), 10, :left, :top, :crimson))
end
plot(row1_plot, Chebyshev_extremums_plot, layout=(2,1), size=(900, 600), fmt=:png)