Parallel Prefix Sum

using GeometryBasics
import Base: getindex, setindex!, length, size
import Base.+

using AbstractPlotting


function prefix_sum(y, func)
    l = length(y)
    k = ceil(Int, log2(l))
    for j=1:k, i=2^j:2^j:min(l, 2^k)
        y[i] = func(y[i-2^(j-1)], y[i])
    end
    for j=(k-1):-1:1, i=3*2^(j-1):2^j:min(l, 2^k)
        y[i] = func(y[i-2^(j-1)], y[i])
    end
    y
end

mutable struct AccessArray <: AbstractArray{Nothing, 1}
    length::Int
    read::Vector
    history::Vector
end

function AccessArray(length, read = [], history = [])
    AccessArray(length, read, history)
end

length(A::AccessArray) = A.length
size(A::AccessArray) = (A.length,)

function getindex(A::AccessArray, i)
    push!(A.read, i)
    return
end

function setindex!(A::AccessArray, x, i)
    push!(A.history, (A.read, [i]))
    A.read = []
end

+(a::Nothing, b::Nothing)=a
A = prefix_sum(AccessArray(8), +)

function render(A::AccessArray)
    olast = depth = 0
    for y in A.history
        (any(y[1] .≤ olast)) && (depth += 1)
        olast = maximum(y[2])
    end
    maxdepth = depth
    olast = depth = 0
    C = []
    for y in A.history
        (any(y[1] .≤ olast)) && (depth += 1)
        push!(C, ((y...,), A.length, maxdepth, depth))
        olast = maximum(y[2])
    end
    msize = 0.1
    outsize = 0.15
    x1 = Point2f0.(first.(first.(first.(C))), last.(C) .+ outsize .+ 0.05)
    x2 = Point2f0.(last.(first.(first.(C))), last.(C) .+ outsize .+ 0.05)
    x3 = Point2f0.(first.(last.(first.(C))), last.(C) .+ 1)
    connections = Point2f0[]

    yoff = Point2f0(0, msize / 2)
    ooff = Point2f0(0, outsize / 2 + 0.05)
    for i = 1:length(x3)
        push!(connections, x3[i] .- ooff, x1[i] .+ yoff, x3[i] .- ooff, x2[i] .+ yoff)
    end
    node_theme = Theme(
        markersize = msize, strokewidth = 3,
        strokecolor = :black, color = (:white, 0.0),
        axis = (
            ticks = (ranges = (1:8, 1:5),),
            names = (axisnames = ("Array Index", "Depth"),),
            frame = (axis_position = :none,)
        )
    )
    s = scatter(node_theme, x1)
    scatter!(node_theme, x2)
    scatter!(x3, color = :white, markersize = 0.2, strokewidth = 4, strokecolor = :black)
    scatter!(x3, color = :red, marker = '+', markersize = outsize)
    linesegments!(connections, color = :red)
    s
end
render(A)