text:
# Rohan McLure 2019 (C), Australian National University, licensed under MIT.

# Serialisation / Deserialisation of InPlaceArrays will involve a deep copy to a preallocated buffer
mutable struct InPlaceArray{T,N} <: DenseArray{T,N}
    src :: Array{T,N} # Reference to array, never overwritten.
    rrid :: RRID
    buf_no :: Int64

    function InPlaceArray{T,N}(A::Array{T,N}, id::RRID, buf_no::Int64=0) where {T,N}
        ipa = new(A, id, buf_no)::InPlaceArray{T,N}
        if buf_no == 0
            places[id] = A
        else
            scratches[buf_no][id] = A
        end
        return ipa
    end
end

# Required to show InPlaceArray objects
function show(S::IO, A::InPlaceArray)
	invoke(show, Tuple{IO, DenseArray}, S, A.src::Array)
end

function show(S::IO, mime::MIME"text/plain", A::InPlaceArray)
    invoke(show, Tuple{IO, MIME"text/plain", DenseArray}, S, MIME"text/plain"(), A.src)
end

function getindex(I::InPlaceArray, keys...)
    getindex(I.src, keys...)
end

function setindex!(I::InPlaceArray, v, keys...)
    setindex!(I.src, v, keys...)
end

function size(A::InPlaceArray)
    size(A.src)
end

function serialize(S::AbstractSerializer, A::InPlaceArray)
    writetag(S.io, OBJECT_TAG)
    serialize(S, typeof(A))
    serialize(S, A.rrid)
    serialize(S, A.buf_no)
    serialize(S, A.src)
end

function deserialize(S::AbstractSerializer, t::Type{<:InPlaceArray{T,N}}) where {T,N}
    # Remote reference which references this 'array' uniquely
    id = deserialize(S)     :: RRID
    buf_no = deserialize(S) :: Int64

    # Read the object tag for the array. Forces following lines to deserialise components of array,
    # rather than full array. We need this for granular control.
    read(S.io, UInt8)::UInt8

    local A
    if buf_no == 0
        A = places[id]
    else
        A = scratches[buf_no][id]
    end

    return deserialize_helper(id, buf_no, S, A)
end

function deserialize_helper(id::RRID, buf_no::Int64, S::AbstractSerializer, A::Array{T,N}) where {T,N}
    # Deserialise an array but pop it in place
    slot = S.counter; S.counter += 1
    d1 = deserialize(S)
    if isa(d1, Type)
        elty = d1
        d1 = deserialize(S)
    else
        elty = UInt8
    end
    if isa(d1, Integer)
        if elty !== Bool && isbitstype(elty)
            S.table[slot] = A
            return InPlaceArray(read!(S.io, A), id, buf_no)
        end
        dims = (Int(d1),)
    else
        dims = convert(Dims, d1)::Dims
    end
    if isbitstype(elty)
        n = prod(dims)::Int
        if elty === Bool && n > 0
            # A = Array{Bool, length(dims)}(undef, dims)
            i = 1
            while i <= n
                b = read(S.io, UInt8)::UInt8
                v = (b >> 7) != 0
                count = b & 0x7f
                nxt = i + count
                while i < nxt
                    A[i] = v
                    i += 1
                end
            end
        else
            read!(S.io, A)
        end
        S.table[slot] = A
    else
        S.table[slot] = A
        # sizehint!(S.table, S.counter + div(length(A),4)) # I reckon not necessary
        deserialize_fillarray!(A, S)
    end
    return InPlaceArray(A::Array{T,N}, id, buf_no)
end

InPlaceArray(A::Array{T,N}, id::RRID) where {T,N} = InPlaceArray{T,N}(A, id)
InPlaceArray(A::Array{T,N}, id::RRID, buf_no::Int64) where {T,N} = InPlaceArray{T,N}(A, id, buf_no)

global places = Dict{RRID, Array}()
global scratches = [Dict{RRID, Array}(), Dict{RRID, Array}()]


text:
using Voting
using Base.Test

## Low-level tests

# Construction
@test vote(3, 1, 2) == Vote([3, 1, 2], 1)
@test 2 * vote(3, 1, 2) == Vote([3, 1, 2], 2)
@test 1 * vote(3, 1, 2) == vote(3, 1, 2)
@test 2 * vote(3, 1, 2) == 2 * vote(3, 1, 2)
@test hash(vote(3, 1, 2)) == hash(vote(3, 1, 2))
@test hash(2 * vote(3, 1, 2)) != hash(vote(3, 1, 2))
ballot = [:A, :B, :C]
@test_throws ArgumentError Votes(ballot, vote(1, 2, 3, 4))
@test_throws ArgumentError Votes(ballot, vote(1, 2))
@test_throws ArgumentError Votes(ballot, vote(1, 2, 4))
@test_throws ArgumentError Votes(ballot, vote(1, 2, 2))

# Iteration
@test 3 == length(vote(3, 1, 2))
@test [3, 1, 2] == [c for c in 4 * vote(3, 1, 2)]
@test [3, 1, 2] == collect(vote(3, 1, 2))

votes = Votes([:A, :B, :C],
        [1 2 3;
        1 3 2;
        1 3 2;
        3 2 1;
        3 2 1])
@test 5 == length(votes)
@test 5 == length([c for c in votes])
@test 5 == length(collect(votes))
@test [ vote(1, 2, 3),
        vote(1, 3, 2),
        vote(1, 3, 2),
        vote(3, 2, 1),
        vote(3, 2, 1) ] == collect(votes)
@test [:A] == plurality(votes)
@test [:A, :C] == borda(votes)

votes = Votes([32, 64, 12],
    10 * vote(3, 1, 2),
    3 * vote(1, 2, 3),
    3 * vote(1, 3, 2))
@test 3 == length(votes)
@test [12] == plurality(votes)

votes1 = Votes([:A, :B], [vote(1, 2), vote(2, 1)])
votes2 = Votes([:A, :B], vote(1, 2), vote(2, 1))
@test votes1 == votes2
@test hash(votes1) == hash(votes2)
@test hash(votes1) != hash(votes)

@test "2× [:A,:B]\n1× [:B,:A]\n" ==
    string(Votes([:A, :B], 2*vote(1, 2), vote(2, 1)))

## Examples taken from Coursera "Game Theory II: Advanced Applications" course
## from Stanford/UBC.

unit12 = Votes([:A, :B, :C, :D],
       [2 3 1 4;
       2 4 3 1;
       4 3 1 2;
       1 4 2 3;
       1 4 3 2])
@test [] == condorcet(unit12)
@test [:A, :B] == sort(plurality(unit12))
@test [:D] == borda(unit12)

paradox = Votes([:A, :B, :C],
        499 * vote(1, 2, 3),
        3 * vote(2, 3, 1),
        498 * vote(3, 2, 1))
@test [:B] == condorcet(paradox)
@test [:A] == plurality(paradox)
@test [:C] == plurality_with_elimination(paradox)

iia_paradox = Votes([:A, :B, :C],
        35 * vote(1, 3, 2),
        33 * vote(2, 1, 3),
        32 * vote(3, 2, 1))
@test [:A] == plurality(iia_paradox)
@test [:A] == borda(iia_paradox)

iia_paradox_without_c = Voting.delete(iia_paradox, 3)
@test [:B] == plurality(iia_paradox_without_c)
@test [:B] == borda(iia_paradox_without_c)

@test [:C] == pairwise_elimination(iia_paradox, [:A, :B, :C])
@test [:B] == pairwise_elimination(iia_paradox, [:A, :C, :B])
@test [:A] == pairwise_elimination(iia_paradox, [:B, :C, :A])

pe_paradox = Votes([:A, :B, :C, :D],
        [2 4 3 1;
        1 2 4 3;
        3 1 2 4])
@test [:D] == pairwise_elimination(pe_paradox, [:A, :B, :C, :D])
# :B Pareto-dominates :D
@test pareto_dominates(pe_paradox, :B, :D)

unit13 = Votes([:A, :B, :C, :D],
        [2 3 1 4;
        2 4 3 1;
        4 3 1 2;
        1 4 2 3;
        1 4 3 2])
@test [:D] == pairwise_elimination(unit13, [:A, :B, :C, :D])
@test [:A] == pairwise_elimination(unit13, [:D, :C, :B, :A])
ballot = unit13.ballot
for first in ballot, other in ballot
    @test !pareto_dominates(unit13, first, other)
end

unit16first = Votes([:a, :b, :c],
    3 * vote(1, 2, 3),
    2 * vote(2, 3, 1),
    2 * vote(3, 2, 1))
@test [:a] == plurality(unit16first)
unit16second = Votes([:a, :b, :c],
    3 * vote(1, 2, 3),
    2 * vote(2, 3, 1),
    2 * vote(2, 1, 3))
@test [:b] == plurality(unit16second)

ext: jl


text:
# Different dispatch for cases where VF alter is a Vector and Array
## Case for Vector:
"""
Function calculates single iteration of Value Function search.
Updates VF::__`Matrix`__ and VFalter::(either __`Matrix`__ or __`Vector`__ object - depending on alternate state (discrete choice) being a single vector(one value for each status)  )
or an array(single value for each state and status)

# Arguments
- `mdl::Model`: Model
- `vectorORmatrix::Union{Vector{<:Real},Matrix{<:Real}}=mdl.VFalter`: used just to determine which version of algorithm will be used: One for Vector or one for Matrix. Supplied automatically.
# Examples
```julia-repl
julia> dr_CPU(my_mdl) # where my_mdl is Struct Model.
julia> dr_CPU(my_mdl,mymdl.VFalter)
```
"""
function dr_CPU(mdl::Model,vectorORmatrix::Vector{<:Real}=mdl.VFalter)

    #initialize etc
    value = view(mdl.VF, :, :)
    decission = view(mdl.DR, :,:)
    υ = view( mdl.VFalter, : )
    l_dim = Int64( floor( length( mdl.GridDef.Grids ) / 2 ) )
    n_dim = tuple( length.( mdl.GridDef.Grids[1: l_dim ] )... )

    # for each status
    for status = mdl.GridDef.Grids[end]

        # initialize value in next period
        # TODO: actually, check if it is correct (seems to be)
        v_tomorrow = value * mdl.λ[status,:]

        @Threads.threads for idx = vec(LinearIndices( n_dim ))

            #get cartesian index equivalent 4 linear index idx
            idxC = CartesianIndices( n_dim )[ idx ]

            #get CIs for Utils selection: today's stays the same, future can be any.
            cis = [ CartesianIndex( idxC, future_ci) for future_ci = CartesianIndices( n_dim ) ]

            # This seems extremely unoptimal. But works so is left for now.
            cis_today = vec( LinearIndices( tuple(repeat([ n_dim... ], 2)...) )[ cis ] )
            u_today = mdl.Utils.f.( CartesianIndex.(cis_today), [status], [mdl] )

            #v get potential VF for given index of state variables
            v_tmp = u_today + mdl.β * v_tomorrow
            #find max
            v,i_d = findmax(v_tmp)

            #update for discrete choice
            # shouldn't it be done AFTER VFalter is updated? For consideration.
            v,i_d = υ[status] > v ? (υ[status], 0) : (v, i_d)

            #update view
            value[idx, status], decission[idx, status] = ( v, i_d )

        end

    end

    #Update VF alter (view) for updated VF → needs to be here because of (1)
    υ[:] = mdl.HAconstraint_Alt(mdl)

    #initialize parameters for VFalter search
    iter = 0
    condition = true

    #Search for VFalter for new Model.VF
    while condition

        test_υ = copy(υ) # (1)
        υ[:] = mdl.HAconstraint_Alt(mdl)

        #Inrease precission in the future?
        sum(abs.(υ - test_υ)) < 10^(-6) && (iter += 1)
        condition = iter <= 7

    end

end

## Case for Array:

function dr_CPU(mdl::Model,vectorORmatrix::Matrix{<:Real}=mdl.VFalter)

    #initialize etc
    value = view(mdl.VF, :, :)
    decission = view(mdl.DR, :,:)
    υ = view( mdl.VFalter, :, :)
    l_dim = Int64( floor( length( mdl.GridDef.Grids ) / 2 ) )
    n_dim = tuple( length.( mdl.GridDef.Grids[1: l_dim ] )... )

    # for each status
    for status = mdl.GridDef.Grids[end]

        # initialize value in next period
        # TODO: actually, check if it is correct
        v_tomorrow = value * mdl.λ[status,:]

        @Threads.threads for idx = vec(LinearIndices( n_dim ))

            idxC = CartesianIndices( n_dim )[ idx ]

            cis = [ CartesianIndex( idxC, future_ci) for future_ci = CartesianIndices( n_dim ) ]
            cis_today = vec( LinearIndices( tuple(repeat([ n_dim... ], 2)...) )[ cis ] )
            u_today = mdl.Utils.f.( CartesianIndex.(cis_today), [status], [mdl] )
            v_tmp = u_today + mdl.β * v_tomorrow
            v,i_d = findmax(v_tmp)

            #TODO: MAS - multi alternate state
            v,i_d = υ[idx,status] > v ? (υ[idx,status], 0) : (v, i_d)

            value[idx, status], decission[idx, status] = ( v, i_d )

        end

    end

    #TODO: MAS - multi alternate state
    υ[:,:] = mdl.HAconstraint_Alt(mdl)

    iter = 0
    condition = true

    while condition

        test_υ = copy(υ)
        #TODO: MAS - multi alternate state
        υ[:,:] = mdl.HAconstraint_Alt(mdl)

        sum(abs.(υ - test_υ)) < 10^(-6) && (iter += 1)
        condition = iter <= 7

    end

end

"""
Function pre-calculates VF and VFalter. For VF it assumes that agents do not switch either state or status. Thus for low-endowment statuses it will be too low and vice versa for high-endowment.
State switching was not included to simplify (and speed up) calculations.
"""
function precomputeVF(mdl::Model)

    # initialize stuff
    vf = view(mdl.VF,:,:)
    ndim = length.(mdl.GridDef.Grids[1:(end-1)] )
    statuses = mdl.GridDef.Grids[end]
    cis = CartesianIndices( tuple( ndim[1:(length(ndim)÷2)]... ) )
    cis = CartesianIndex.(cis,cis)

    ## not sure if multithreading here helps:
    # most operations are basic algebra so they are multithreaded anyway.
    # In the future might test for MT and ST here.
    @Threads.threads for status = statuses

        u = mdl.Utils.qb[status][cis]
        vf_i = copy(u)

        iter = 0
        condition = true
        while condition

            test_vf = copy(vf_i)
            vf_i *= mdl.β
            vf_i += u
            # array bool is necessary to calculate convergeance criterion for when Inf/-Inf and others are present
            array_bool = vf_i .!= Inf
            array_bool .*= vf_i .!= -Inf
            array_bool .*= .!isnan.(vf_i)
            vf_check = abs.(vf_i - test_vf)
            sum( vf_check .* array_bool) < 10^(-6) && (iter += 1)
            condition = iter <= 7

        end

        # vectorize and write
        vf[:,status] = vec(vf_i)

    end

    # Compute VFalter for precomputed VF
    mdl.VFalter = mdl.HAconstraint_Alt(mdl)
    υ = view( mdl.VFalter, :,: )

    iter = 0
    # condition = true
    while iter <= 7

        test_υ = copy(υ)
        υ[:,:] = mdl.HAconstraint_Alt(mdl)

        sum(abs.(υ - test_υ)) < 10^(-6) && (iter += 1)
        # condition = iter <= 7

    end

    # change strange values into some more reasonable

    if (isa(mdl.VFalter, Vector))

        @Threads.threads for status in statuses

            array_bool = vf[:,status] .!= Inf
            array_bool .*= vf[:,status] .!= -Inf
            array_bool .*= .!isnan.(vf[:,status])
            array_bool .*= vf[:,status] .< υ[status]
            vf[:,status][.!array_bool] .= υ[status]

        end

    elseif (isa(mdl.VFalter, Matrix))

        @Threads.threads for status in statuses

            array_bool = vf[:,status] .!= Inf
            array_bool .*= vf[:,status] .!= -Inf
            array_bool .*= .!isnan.(vf[:,status])
            array_bool .*= vf[:,status] .≥ υ[:,status]
            vf[:,status][.!array_bool] .= υ[:,status][.!array_bool]

        end

    else

        error("Precalculation of VF failed")

    end

end


text:
@testset "tree.jl" begin

    @testset "root insertion test" begin
        t = AVLTree{Int64,Int64}()
        insert!(t, 1, 2)
        @test !isnothing(t.root)
        @test t.root.bf == 0
        @test isnothing(t.root.right) && isnothing(t.root.left)
        @test t.root.key == 1 && t.root.data == 2
        @test size(t) == 1
        insert!(t, 1, 10)
        delete!(t, 999)
        @test t.root.data == 10
        @test size(t) == 1
    end

    @testset "left rotation test" begin
        t = AVLTree{Int64,Int64}()
        insert!(t, 1, 2)
        insert!(t, 2, 2)
        insert!(t, 3, 2)
        @test t.root.bf == 0 && t.root.left.bf == 0 && t.root.right.bf == 0
        @test t.root.key == 2 && t.root.left.key == 1 && t.root.right.key == 3
        @test size(t) == 3
    end

    @testset "right rotation test" begin
        t = AVLTree{Int64,Int64}()
        insert!(t, 3, 2)
        insert!(t, 2, 2)
        insert!(t, 1, 2)
        @test t.root.bf == 0 && t.root.left.bf == 0 && t.root.right.bf == 0
        @test t.root.key == 2 && t.root.left.key == 1 && t.root.right.key == 3
        @test size(t) == 3
    end

    @testset "left-right rotation test" begin
        t = AVLTree{Int64,Int64}()
        insert!(t, 3, 2)
        insert!(t, 1, 2)
        insert!(t, 2, 2)
        @test t.root.bf == 0 && t.root.left.bf == 0 && t.root.right.bf == 0
        @test t.root.key == 2 && t.root.left.key == 1 && t.root.right.key == 3
        @test size(t) == 3
    end

    @testset "right-left rotation test" begin
        t = AVLTree{Int64,Int64}()
        insert!(t, 1, 2)
        insert!(t, 3, 2)
        insert!(t, 2, 2)
        @test t.root.bf == 0 && t.root.left.bf == 0 && t.root.right.bf == 0
        @test t.root.key == 2 && t.root.left.key == 1 && t.root.right.key == 3
        @test size(t) == 3
    end

    @testset "tree{Any,Any} test" begin
        t = AVLTree()
        insert!(t, "item1", "item1")
        @test t.root.key == "item1"
        insert!(t, "item2", "item2")
        insert!(t, "item3", "item3")
        @test t.root.key == "item2"
        @test size(t) == 3
    end

    @testset "fill test" begin
        t = AVLTree{Int64,Int64}()
        for i in rand(Int64, 100)
            insert!(t, i, 0)
        end
        @test size(t) <= 100
    end

    @testset "delete basic" begin
        t = AVLTree{Int64,Int64}()
        insert!(t, 1, 2)
        insert!(t, 2, 2)
        insert!(t, 3, 2)
        @test size(t) == 3
        delete!(t, t.root.left)
        @test isnothing(t.root.left)
        @test t.root.bf == 1
        @test size(t) == 2
        delete!(t, t.root.right)
        @test isnothing(t.root.right)
        @test t.root.bf == 0
        @test size(t) == 1
        delete!(t, t.root)
        @test size(t) == 0
        @test isnothing(t.root)
    end

    @testset "fill and delete all test" begin
        t = AVLTree{Int64,Int64}()
        for i in rand(Int64, 100)
            insert!(t, i, 0)
        end
        @test size(t) <= 100
        while !isnothing(t.root)
            delete!(t, t.root)
        end
        @test isnothing(t.root)
        @test size(t) == 0
    end

    @testset "fill and delete keys test" begin
        t = AVLTree{Int64,Int64}()
        nums = rand(Int64, 100)
        for i in nums
            insert!(t, i, i)
        end
        @test size(t) <= 100
        for i in nums
            delete!(t, i)
        end
        @test size(t) == 0
        @test isnothing(t.root)
    end

    @testset "findkey test" begin
        t = AVLTree{Int64,Int64}()
        for i = 1:1000
            insert!(t, i, i)
        end
        @test size(t) == 1000
        @test 500 == findkey(t, 500)
        @test nothing == findkey(t, 1001)
        @test size(t) == 1000
    end

    @testset "iteration test" begin
        t = AVLTree{Int64,Int64}()
        for i = 1:1000
            insert!(t, i, i)
        end
        s1 = Set{Tuple{Int64,Int64}}([(_x,_x) for _x in 1:1000])
        s2 = Set{Tuple{Int64,Int64}}()
        for i in t
            push!(s2,i)
        end
        @test s1 == s2
    end

    @testset "Base.*" begin
        t = AVLTree{Int64, Int64}()

        for i in 1:100
            insert!(t, i, i)
        end

        @test eltype(t) == Tuple{Int64, Int64}
        @test getindex.(Ref(t), 1:100) == 1:100
        try
            getindex(t, -100)
        catch x
            @test x == KeyError(-100)
        end
        setindex!(t, 10, -10)
        @test t[10] == -10
        @test haskey(t,10)
        @test !haskey(t,-10)
        @test length(t) == 100
        t[-10] = -10
        @test length(t) == 101
        @test !isempty(t)

        @test popfirst!(t) == -10
        @test firstindex(t) == 1
        t[10] = 10
        @test pop!.(Ref(t), 1:100) == 1:100

    end

end