text:
"""
    initGigaSOM(data, args...)

Initializes a SOM by random selection from the training data. A generic
overload that works for matrices and DataFrames that can be coerced to
`Matrix{Float64}`. Other arguments are passed to the data-independent
`initGigaSOM`.

Arguments:
- `data`: matrix of data for running the initialization
"""
function initGigaSOM(data::Union{Matrix,DataFrame}, args...; kwargs...)

    d = Matrix{Float64}(data)

    (n, ncol) = size(d)
    means = [sum(d[:, i]) / n for i = 1:ncol]
    sdevs = [sqrt(sum((d[:, i] .- means[i]) .^ 2.0) / n) for i = 1:ncol]

    return initGigaSOM(ncol, means, sdevs, args...; kwargs...)
end

"""
    function initGigaSOM(data::Dinfo,
                         xdim::Int64, ydim::Int64 = xdim;
                         seed=rand(Int), rng=StableRNG(seed))

`initGigaSOM` overload for working with distributed-style `Dinfo`
data. The rest of the arguments is passed to the data-independent
`initGigaSOM`.

Arguments:
- `data`: a `Dinfo` object with the distributed dataset matrix
"""
function initGigaSOM(data::Dinfo, args...; kwargs...)
    ncol = get_val_from(data.workers[1], :(size($(data.val))[2]))
    (means, sdevs) = dstat(data, Vector(1:ncol))

    initGigaSOM(ncol, means, sdevs, args...; kwargs...)
end

"""
    function initGigaSOM(ncol::Int64,
                         means::Vector{Float64}, sdevs::Vector{Float64},
                         xdim::Int64, ydim::Int64 = xdim;
                         seed = rand(Int), rng = StableRNG(seed))

Generate a stable random initial SOM with the random distribution that matches the parameters.

Arguments:
- `ncol`: number of desired data columns
- `means`, `sdevs`: vectors that describe the data distribution, both of size `ncol`
- `xdim`, `ydim`: Size of the SOM
- `seed`: a seed (defaults to random seed from the current default random generator
- `rng`: a random number generator to be used (defaults to a `StableRNG` initialized with the `seed`)

Returns: a new `Som` structure
"""
function initGigaSOM(
    ncol::Int64,
    means::Vector{Float64},
    sdevs::Vector{Float64},
    xdim::Int64,
    ydim::Int64 = xdim;
    seed = rand(UInt),
    rng = StableRNG(seed),
)

    numCodes = xdim * ydim
    grid = gridRectangular(xdim, ydim)

    # Initialize with an unbiased random gaussian with same mean/sd as the data
    # in each dimension
    codes = randn(rng, (numCodes, ncol))
    for col = 1:ncol
        codes[:, col] .*= sdevs[col]
        codes[:, col] .+= means[col]
    end

    return Som(codes = codes, xdim = xdim, ydim = ydim, grid = grid)
end

"""
    trainGigaSOM(
        som::Som,
        dInfo::Dinfo;
        kernelFun::Function = gaussianKernel,
        metric = Euclidean(),
        somDistFun = distMatrix(Chebyshev()),
        knnTreeFun = BruteTree,
        rStart = 0.0,
        rFinal = 0.1,
        radiusFun = expRadius(-5.0),
        epochs = 20,
        eachEpoch = (e, r, som) -> nothing,
    )

# Arguments:
- `som`: object of type Som with an initialised som
- `dInfo`: `Dinfo` object that describes a loaded dataset
- `kernelFun::function`: optional distance kernel; one of (`bubbleKernel, gaussianKernel`)
            default is `gaussianKernel`
- `metric`: Passed as metric argument to the KNN-tree constructor
- `somDistFun`: Function for computing the distances in the SOM map
- `knnTreeFun`: Constructor of the KNN-tree (e.g. from NearestNeighbors package)
- `rStart`: optional training radius. If zero (default), it is computed from the SOM grid size.
- `rFinal`: target radius at the last epoch, defaults to 0.1
- `radiusFun`: Function that generates radius decay, e.g. `linearRadius` or `expRadius(10.0)`
- `epochs`: number of SOM training iterations (default 10)
- `eachEpoch`: a function to call back after each epoch, accepting arguments
  `(epochNumber, radius, som)`. For simplicity, this gets additionally called
  once before the first epoch, with `epochNumber` set to zero.
"""
function trainGigaSOM(
    som::Som,
    dInfo::Dinfo;
    kernelFun::Function = gaussianKernel,
    metric = Euclidean(),
    somDistFun = distMatrix(Chebyshev()),
    knnTreeFun = BruteTree,
    rStart = 0.0,
    rFinal = 0.1,
    radiusFun = expRadius(-5.0),
    epochs = 20,
    eachEpoch = (e, r, som) -> nothing,
)

    # set the default radius
    if rStart == 0.0
        rStart = (som.xdim + som.ydim) / 2
        @debug "The radius has been determined automatically." rStart rFinal
    end

    # get the SOM neighborhood distances
    dm = somDistFun(som.grid)

    result_som = copy(som)
    result_som.codes = copy(som.codes) # prevent rewriting by reference

    eachEpoch(0, rStart, result_som)

    for epoch = 1:epochs
        @debug "Epoch $epoch..."

        numerator, denominator = distributedEpoch(
            dInfo,
            result_som.codes,
            knnTreeFun(Array{Float64,2}(transpose(result_som.codes)), metric),
        )

        r = radiusFun(rStart, rFinal, epoch, epochs)
        @debug "radius: $r"
        if r <= 0
            @error "Sanity check failed: radius must be positive"
            error("Radius check")
        end

        wEpoch = kernelFun(dm, r)
        result_som.codes = (wEpoch * numerator) ./ (wEpoch * denominator)

        eachEpoch(epoch, r, result_som)
    end

    return result_som
end

"""
    trainGigaSOM(som::Som, train;
                 kwargs...)

Overload of `trainGigaSOM` for simple DataFrames and matrices. This slices the
data, distributes them to the workers, and runs normal `trainGigaSOM`. Data is
`unscatter`d after the computation.
"""
function trainGigaSOM(som::Som, train; kwargs...)

    train = Matrix{Float64}(train)

    #this slices the data into parts and and sends them to workers
    dInfo = scatter_array(:GigaSOMtrainDataVar, train, workers())
    som_res = trainGigaSOM(som, dInfo; kwargs...)
    unscatter(dInfo)
    return som_res
end

"""
    doEpoch(x::Array{Float64, 2}, codes::Array{Float64, 2}, tree)

vectors and the adjustment in radius after each epoch.

# Arguments:
- `x`: training Data
- `codes`: Codebook
- `tree`: knn-compatible tree built upon the codes
"""
function doEpoch(x::Array{Float64,2}, codes::Array{Float64,2}, tree)

    # initialise numerator and denominator with 0's
    sumNumerator = zeros(Float64, size(codes))
    sumDenominator = zeros(Float64, size(codes)[1])

    # for each sample in dataset / trainingsset
    for s = 1:size(x, 1)
        (bmuIdx, bmuDist) = knn(tree, x[s, :], 1)

        target = bmuIdx[1]

        sumNumerator[target, :] .+= x[s, :]
        sumDenominator[target] += 1
    end

    return sumNumerator, sumDenominator
end

"""
    distributedEpoch(dInfo::Dinfo, codes::Matrix{Float64}, tree)

Execute the `doEpoch` in parallel on workers described by `dInfo` and collect
the results. Returns pair of numerator and denominator matrices.
"""
function distributedEpoch(dInfo::Dinfo, codes::Matrix{Float64}, tree)
    return dmapreduce(
        dInfo,
        (data) -> doEpoch(data, codes, tree),
        ((n1, d1), (n2, d2)) -> (n1 + n2, d1 + d2),
    )
end

"""
    mapToGigaSOM(som::Som, dInfo::Dinfo;
        knnTreeFun = BruteTree, metric = Euclidean(),
        output::Symbol=tmp_symbol(dInfo)::Dinfo

Compute the index of the BMU for each row of the input data.

# Arguments
- `som`: a trained SOM
- `dInfo`: `Dinfo` that describes the loaded and distributed data
- `knnTreeFun`: Constructor of the KNN-tree (e.g. from NearestNeighbors package)
- `metric`: Passed as metric argument to the KNN-tree constructor
- `output`: Symbol to save the result, defaults to `tmp_symbol(dInfo)`

Data must have the same number of dimensions as the training dataset
and will be normalised with the same parameters.
"""
function mapToGigaSOM(
    som::Som,
    dInfo::Dinfo;
    knnTreeFun = BruteTree,
    metric = Euclidean(),
    output::Symbol = tmp_symbol(dInfo),
)::Dinfo

    tree = knnTreeFun(Array{Float64,2}(transpose(som.codes)), metric)

    return dtransform(dInfo, (d) -> (vcat(knn(tree, transpose(d), 1)[1]...)), output)
end

"""
    mapToGigaSOM(som::Som, data;
                 knnTreeFun = BruteTree,
                 metric = Euclidean())
Overload of `mapToGigaSOM` for simple DataFrames and matrices. This slices the
data using `DistributedArrays`, sends them the workers, and runs normal
`mapToGigaSOM`. Data is `unscatter`d after the computation.
"""
function mapToGigaSOM(som::Som, data; knnTreeFun = BruteTree, metric = Euclidean())

    data = Matrix{Float64}(data)

    if size(data, 2) != size(som.codes, 2)
        @error "Data dimension ($(size(data,2))) does not match codebook dimension ($(size(som.codes,2)))."
        error("Data dimensions do not match")
    end

    dInfo = scatter_array(:GigaSOMmappingDataVar, data, workers())
    rInfo = mapToGigaSOM(som, dInfo, knnTreeFun = knnTreeFun, metric = metric)
    res = gather_array(rInfo)
    unscatter(dInfo)
    unscatter(rInfo)
    return DataFrame(index = res)
end

"""
    scaleEpochTime(iteration::Int64, epochs::Int64)

Convert iteration ID and epoch number to relative time in training.
"""
function scaleEpochTime(iteration::Int64, epochs::Int64)
    # prevent division by zero on 1-epoch training
    if epochs > 1
        epochs -= 1
    end

    return Float64(iteration - 1) / Float64(epochs)
end


text:
#Debugging helper utils
_debug_output = false
_debug_indent = 0
debug(d::Bool) = global _debug_output = d
macro debug(expr, other...)
    esc(:(if _debug_output
        print(repeat("\t", _debug_indent))
        println($expr,$(other...))
    end))
end
macro debug_addindent()
    esc(:(global _debug_indent += 1))
end
macro debug_subindent()
    esc(:(global _debug_indent -= 1))
end

ext: jl


text:
struct Kplsr
    X::Array{Float64}
    Kt::Array{Float64}
    T::Array{Float64}
    C::Array{Float64}
    U::Array{Float64}
    R::Array{Float64}
    D::Array{Float64}
    DKt::Array{Float64}
    vtot::Array{Float64}
    ymeans::Vector{Float64}
    weights::Vector{Float64}
    kern
    dots
    iter::Vector{Int}
end

"""
    kplsr(X, Y, weights = ones(size(X, 1)); nlv , kern = "krbf", kwargs...)
Kernel partial least squares regression (KPLSR) implemented with a NIPALS algorithm (Rosipal & Trejo, 2001).

* `X` : X-data.
* `Y` : Y-data.
* `weights` : Weights of the observations.
* `nlv` : Nb. latent variables (LVs) to consider.
* 'kern' : Type of kernel used to compute the Gram matrices.
    Possible values are "krbf" or "kpol" (see respective functions `krbf` and `kpol`).
* `kwargs` : Named arguments to pass in the kernel function.

This algorithm becomes slow for n > 1000.

The kernel Gram matrices are internally centered.

## References

Rosipal, R., Trejo, L.J., 2001. Kernel Partial Least Squares Regression in Reproducing Kernel Hilbert Space.
Journal of Machine Learning Research 2, 97-123.

"""
function kplsr(X, Y, weights = ones(size(X, 1));
        nlv, kern = "krbf", tol = 1.5e-8, maxit = 100, kwargs...)
    kplsr!(copy(X), copy(Y), weights;
        nlv = nlv, kern = kern, tol = tol, maxit = maxit, kwargs...)
end

function kplsr!(X, Y, weights = ones(size(X, 1));
        nlv, kern = "krbf", tol = 1.5e-8, maxit = 100, kwargs...)
    X = ensure_mat(X)
    Y = ensure_mat(Y)
    n = size(X, 1)
    q = size(Y, 2)
    weights = mweights(weights)
    ymeans = colmeans(Y, weights)
    center!(Y, ymeans)
    fkern = eval(Meta.parse(kern))
    K = fkern(X, X; kwargs...)     # In the future: fkern!(K, X, X; kwargs...)
    D = Diagonal(weights)
    Kt = K'
    DKt = D * Kt
    vtot = sum(DKt, dims = 1)
    Kc = K .- vtot' .- vtot .+ sum(D * DKt')
    # Pre-allocation
    K = copy(Kc)
    T = similar(X, n, nlv)
    U = copy(T)
    C = similar(X, q, nlv)
    I = Diagonal(ones(n))
    iter = Int.(zeros(nlv))
    # temporary results
    t  = similar(X, n)
    dt = similar(X, n)
    c  = similar(X, q)
    u  = similar(X, n)
    zu = similar(X, n)
    # End
    for a in 1:nlv
        if q == 1
            mul!(t, K, D * vec(Y))   # t = K * D * Y
            t ./= sqrt(dot(t, weights .* t))
            dt .= weights .* t
            mul!(c, Y', dt)
            u .= Y * c
            u ./= sqrt(dot(u, u))
        else
            u .= Y[:, 1]
            ztol = 1.
            ziter = 1
            while ztol > tol && ziter <= maxit
                mul!(t, K, weights .* u)
                t ./= sqrt(dot(t, weights .* t))
                dt .= weights .* t
                mul!(c, Y', dt)
                zu .= Y * c
                zu ./= sqrt(dot(zu, zu))
                ztol = sqrt(sum((u - zu).^2))
                u .= zu
                ziter = ziter + 1
            end
            iter[a] = ziter - 1
        end
        z = I - t * dt'  # slow
        K .= z * K * z'  # slow
        Y .-= t * c'
        T[:, a] .= t
        C[:, a] .= c
        U[:, a] .= u
    end
    DU = D * U
    zR = DU * inv(T' * D * Kc * DU)
    Kplsr(X, Kt, T, C, U, zR, D, DKt, vtot, ymeans, weights, kern, kwargs, iter)
end

"""
    transform(object::Kplsr, X; nlv = nothing)
Compute LVs (score matrix "T") from a fitted model and X-data.
* `object` : The maximal fitted model.
* `X` : X-data for which LVs are computed.
* `nlv` : Nb. LVs to consider. If nothing, it is the maximum nb. LVs.
"""
function transform(object::Kplsr, X; nlv = nothing)
    a = size(object.T, 2)
    isnothing(nlv) ? nlv = a : nlv = min(nlv, a)
    fkern = eval(Meta.parse(object.kern))
    K = fkern(X, object.X; object.dots...)
    DKt = object.D * K'
    vtot = sum(DKt, dims = 1)
    Kc = K .- vtot' .- object.vtot .+ sum(object.D * object.DKt')
    T = Kc * @view(object.R[:, 1:nlv])
    T
end

"""
    coef(object::Kplsr; nlv = nothing)
Compute the b-coefficients of a fitted model.
* `object` : The fitted model.
* `nlv` : Nb. LVs, or collection of nb. LVs, to consider.
    If nothing, it is the maximum nb. LVs.
"""
function coef(object::Kplsr; nlv = nothing)
    a = size(object.T, 2)
    isnothing(nlv) ? nlv = a : nlv = min(nlv, a)
    beta = object.C[:, 1:nlv]'
    q = length(object.ymeans)
    int = reshape(object.ymeans, 1, q)
    (beta = beta, int = int)
end

"""
    predict(object::Kplsr, X; nlv = nothing)
Compute Y-predictions from a fitted model.
* `object` : The maximal fitted model.
* `X` : X-data for which predictions are computed.
* `nlv` : Nb. LVs, or collection of nb. LVs, to consider.
If nothing, it is the maximum nb. LVs.
"""
function predict(object::Kplsr, X; nlv = nothing)
    a = size(object.T, 2)
    isnothing(nlv) ? nlv = a : nlv = (max(minimum(nlv), 0):min(maximum(nlv), a))
    le_nlv = length(nlv)
    T = transform(object, X)
    pred = list(le_nlv, Matrix{Float64})
    @inbounds for i = 1:le_nlv
        z = coef(object; nlv = nlv[i])
        pred[i] = z.int .+ @view(T[:, 1:nlv[i]]) * z.beta
    end
    le_nlv == 1 ? pred = pred[1] : nothing
    (pred = pred,)
end


text:
# This file was generated by the Julia Swagger Code Generator
# Do not modify this file directly. Modify the swagger specification instead.

mutable struct ExpressRouteCircuitRoutesTableSummary <: SwaggerModel
    neighbor::Any # spec type: Union{ Nothing, String } # spec name: neighbor
    v::Any # spec type: Union{ Nothing, Int32 } # spec name: v
    as::Any # spec type: Union{ Nothing, Int32 } # spec name: as
    upDown::Any # spec type: Union{ Nothing, String } # spec name: upDown
    statePfxRcd::Any # spec type: Union{ Nothing, String } # spec name: statePfxRcd

    function ExpressRouteCircuitRoutesTableSummary(;neighbor=nothing, v=nothing, as=nothing, upDown=nothing, statePfxRcd=nothing)
        o = new()
        validate_property(ExpressRouteCircuitRoutesTableSummary, Symbol("neighbor"), neighbor)
        setfield!(o, Symbol("neighbor"), neighbor)
        validate_property(ExpressRouteCircuitRoutesTableSummary, Symbol("v"), v)
        setfield!(o, Symbol("v"), v)
        validate_property(ExpressRouteCircuitRoutesTableSummary, Symbol("as"), as)
        setfield!(o, Symbol("as"), as)
        validate_property(ExpressRouteCircuitRoutesTableSummary, Symbol("upDown"), upDown)
        setfield!(o, Symbol("upDown"), upDown)
        validate_property(ExpressRouteCircuitRoutesTableSummary, Symbol("statePfxRcd"), statePfxRcd)
        setfield!(o, Symbol("statePfxRcd"), statePfxRcd)
        o
    end
end # type ExpressRouteCircuitRoutesTableSummary

const _property_map_ExpressRouteCircuitRoutesTableSummary = Dict{Symbol,Symbol}(Symbol("neighbor")=>Symbol("neighbor"), Symbol("v")=>Symbol("v"), Symbol("as")=>Symbol("as"), Symbol("upDown")=>Symbol("upDown"), Symbol("statePfxRcd")=>Symbol("statePfxRcd"))
const _property_types_ExpressRouteCircuitRoutesTableSummary = Dict{Symbol,String}(Symbol("neighbor")=>"String", Symbol("v")=>"Int32", Symbol("as")=>"Int32", Symbol("upDown")=>"String", Symbol("statePfxRcd")=>"String")
Base.propertynames(::Type{ ExpressRouteCircuitRoutesTableSummary }) = collect(keys(_property_map_ExpressRouteCircuitRoutesTableSummary))
Swagger.property_type(::Type{ ExpressRouteCircuitRoutesTableSummary }, name::Symbol) = Union{Nothing,eval(Meta.parse(_property_types_ExpressRouteCircuitRoutesTableSummary[name]))}
Swagger.field_name(::Type{ ExpressRouteCircuitRoutesTableSummary }, property_name::Symbol) =  _property_map_ExpressRouteCircuitRoutesTableSummary[property_name]

function check_required(o::ExpressRouteCircuitRoutesTableSummary)
    true
end

function validate_property(::Type{ ExpressRouteCircuitRoutesTableSummary }, name::Symbol, val)
end


text:
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
#
# Description
# ==============================================================================
#
#   Auxiliary functions to print the parts of the table.
#
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #

# Flush the content of `buf` to `io`.
function _flush_buffer!(
    io::IO,
    buf::IO,
    overwrite::Bool,
    newline_at_end::Bool,
    num_displayed_rows::Int
)
    # If `overwrite` is `true`, then delete the exact number of lines of the
    # table. This can be used to replace the table in the display continuously.
    str_overwrite = overwrite ? "\e[1F\e[2K"^(num_displayed_rows - 1) : ""

    output_str = String(take!(buf))

    # Check if the user does not want a newline at end.
    !newline_at_end && (output_str = String(chomp(output_str)))

    print(io, str_overwrite * output_str)

    return nothing
end

function _print_omitted_cell_summary(
    buf::IO,
    has_color::Bool,
    num_omitted_cols::Int,
    num_omitted_rows::Int,
    omitted_cell_summary_crayon::Crayon,
    show_omitted_cell_summary::Bool,
    table_width::Int
)
    if show_omitted_cell_summary && ((num_omitted_cols + num_omitted_rows) > 0)
        cs_str_col = ""
        cs_str_and = ""
        cs_str_row = ""

        if num_omitted_cols > 0
            cs_str_col = string(num_omitted_cols)
            cs_str_col *= num_omitted_cols > 1 ? " columns" : " column"
        end

        if num_omitted_rows > 0
            cs_str_row = string(num_omitted_rows)
            cs_str_row *= num_omitted_rows > 1 ? " rows" : " row"

            num_omitted_cols > 0 && (cs_str_and = " and ")
        end

        cs_str = cs_str_col * cs_str_and * cs_str_row * " omitted"

        if textwidth(cs_str) < table_width
            cs_str = _str_aligned(cs_str, :r, table_width)
        end

        has_color && print(buf, omitted_cell_summary_crayon)
        print(buf, cs_str)
        has_color && print(buf, _reset_crayon)
        println(buf)
    end

    return nothing
end

# Print the table header without the horizontal lines.
function _print_table_header!(
    buf::IO,
    display::Display,
    (@nospecialize header::Any),
    header_str::Matrix{String},
    id_cols::Vector{Int},
    id_rows::Vector{Int},
    num_printed_cols::Int,
    Δc::Int,
    cols_width::Vector{Int},
    vlines::Vector{Int},
    # Configurations.
    alignment::Vector{Symbol},
    header_alignment::Vector{Symbol},
    (@nospecialize header_cell_alignment::Ref{Any}),
    show_row_names::Bool,
    show_row_number::Bool,
    tf::TextFormat,
    # Crayons.
    border_crayon::Crayon,
    header_crayon::Vector{Crayon},
    subheader_crayon::Vector{Crayon},
    rownum_header_crayon::Crayon,
    row_name_header_crayon::Crayon
)
    header_num_rows, ~ = size(header_str)

    @inbounds @views for i = 1:header_num_rows
        0 ∈ vlines && _p!(display, border_crayon, tf.column, false)

        for j = 1:num_printed_cols
            # Get the information about the alignment and the crayon.
            if j ≤ Δc
                if show_row_number && (j == 1)
                    crayon_ij    = rownum_header_crayon
                    alignment_ij = alignment[1]
                elseif show_row_names
                    crayon_ij    = row_name_header_crayon
                    alignment_ij = alignment[Δc]
                end
            else
                jc = id_cols[j-Δc]
                crayon_ij    = (i == 1) ? header_crayon[jc] : subheader_crayon[jc]
                alignment_ij = header_alignment[jc]

                # Check for cell alignment override.
                for f in header_cell_alignment.x
                    aux = f(header, i, jc)

                    if aux ∈ (:l, :c, :r, :L, :C, :R, :s, :S)
                        alignment_ij = aux
                        break
                    end
                end

                # If alignment is `:s`, then we must use the column
                # alignment.
                alignment_ij ∈ (:s, :S) && (alignment_ij = alignment[jc + Δc])
            end

            # Prepare the text to be printed.
            header_ij_str = _str_aligned(header_str[i, j], alignment_ij, cols_width[j])
            header_ij_str = " " * header_ij_str * " "

            flp = j == num_printed_cols

            # Print the text.
            _p!(display, crayon_ij, header_ij_str, false)

            # Check if we need to draw a vertical line here.
            _pc!(j ∈ vlines, display, border_crayon, tf.column, "", flp, 1, 0)

            _eol(display) && break
        end

        i != header_num_rows && _nl!(display, buf)
    end

    _nl!(display, buf)

    return nothing
end

# Print the entire table data.
function _print_table_data(
    buf::IO,
    display::Display,
    (@nospecialize data::Any),
    data_str::Matrix{Vector{String}},
    id_cols::Vector{Int},
    id_rows::Vector{Int},
    Δc::Int,
    cols_width::Vector{Int},
    vlines::Vector{Int},
    row_printing_recipe::Vector{NTuple{4, Int}},
    col_printing_recipe::Vector{Int},
    # Configurations.
    alignment::Vector{Symbol},
    body_hlines_format::NTuple{4, Char},
    cell_alignment_override::Dict{Tuple{Int, Int}, Symbol},
    continuation_row_alignment::Symbol,
    ellipsis_line_skip::Integer,
    (@nospecialize highlighters::Ref{Any}),
    noheader::Bool,
    show_row_names::Bool,
    show_row_number::Bool,
    tf::TextFormat,
    # Crayons.
    border_crayon::Crayon,
    row_name_crayon::Crayon,
    text_crayon::Crayon
)
    line_count = 0

    for r in row_printing_recipe
        if r[1] < 0
            if r[1] == _ROW_LINE[1]
                _draw_line!(
                    display,
                    buf,
                    body_hlines_format...,
                    border_crayon,
                    cols_width,
                    vlines
                )
            elseif r[1] == _CONTINUATION_LINE[1]
                _draw_continuation_row(
                    display,
                    buf,
                    tf,
                    text_crayon,
                    border_crayon,
                    cols_width,
                    vlines,
                    continuation_row_alignment
                )
            else
                error("Internal error: wrong symbol in row printing recipe.")
            end

        else
            i, ir, num_lines, l₀ = r

            for l = l₀:(l₀ + num_lines - 1)

                # Check if we should print the ellipsis here.
                display.cont_char = if line_count % (ellipsis_line_skip + 1) == 0
                    '⋯'
                else
                    ' '
                end

                line_count += 1

                num_col_recipes = length(col_printing_recipe)

                for c_id = 1:num_col_recipes
                    c = col_printing_recipe[c_id]

                    flp = c_id == num_col_recipes

                    if c < 0
                        if c == _LEFT_LINE
                            _p!(display, border_crayon, tf.column, flp, 1)
                        elseif c == _COLUMN_LINE
                            _p!(display, border_crayon, tf.column, flp, 1)
                        elseif c == _RIGHT_LINE
                            _p!(display, border_crayon, tf.column, flp, 1)
                        else
                            error("Internal error: wrong symbol in column printing recipe.")
                        end
                    else
                        j = c

                        # Get the information about the alignment and the
                        # crayon.
                        #
                        # NOTE: The variable `data_cell` is used to avoid
                        # applying formatters and highlighters to the row number
                        # and row name columns.
                        if j ≤ Δc
                            if show_row_number && (j == 1)
                                crayon_ij    = text_crayon
                                alignment_ij = alignment[1]
                            elseif show_row_names
                                crayon_ij    = row_name_crayon
                                alignment_ij = alignment[Δc]
                            end
                            jc = 0
                            data_cell = false
                        else
                            jc = id_cols[j - Δc]

                            crayon_ij    = text_crayon
                            alignment_ij = alignment[jc + Δc]
                            data_cell    = true
                        end

                        # String to be processed.
                        if length(data_str[i, j]) >= l
                            data_ij_str = data_str[i, j][l]
                            line_has_data = true
                        else
                            data_ij_str = ""
                            line_has_data = false
                        end

                        # Check if the alignment of this cell is overridden by
                        # the user.
                        if haskey(cell_alignment_override, (ir, jc))
                            alignment_ij = cell_alignment_override[(ir, jc)]
                        end

                        # Check if we have a custom cell.
                        custom_cell =
                            data_cell &&
                            isassigned(data, ir, jc) &&
                            line_has_data &&
                            (data[ir, jc] isa CustomTextCell)

                        # Process the string with the correct alignment and also
                        # apply the highlighters.
                        data_ij_str, crayon_ij = _process_cell_text(
                            data,
                            ir,
                            jc,
                            l,
                            data_cell,
                            custom_cell,
                            data_ij_str,
                            cols_width[j],
                            crayon_ij,
                            alignment_ij,
                            highlighters
                        )

                        # Compute the printable size of the string.
                        data_ij_len = _printable_textwidth(data_ij_str)

                        # If we have a custom cell, then we need a custom
                        # printing function.
                        if custom_cell
                            _p!(display, _default_crayon, " ", false, 1)

                            # Compute the new string given the display size.
                            str, suffix, ~ = _fit_str_to_display(
                                display,
                                data_ij_str,
                                false,
                                data_ij_len
                            )

                            new_lstr = textwidth(str)

                            # Check if we need to crop the string to fit the
                            # display.
                            if data_ij_len > new_lstr
                                crop_line!(
                                    data[ir, jc],
                                    l,
                                    data_ij_len - new_lstr
                                )
                            end

                            # Get the rendered text.
                            rendered_str = get_rendered_line(
                                data[ir, jc],
                                l
                            )::String

                            # Write it to the display.
                            _write_to_display!(
                                display,
                                crayon_ij,
                                rendered_str,
                                suffix,
                                new_lstr + textwidth(suffix)
                            )

                            _p!(display, _default_crayon, " ", false, 1)
                        else
                            _p!(
                                display,
                                crayon_ij,
                                " " * data_ij_str * " ",
                                false,
                                data_ij_len + 2
                            )
                        end
                    end
                end

                _nl!(display, buf)
            end
        end
    end

    return nothing
end


text:
@doc """
    KMeansOptions <: Options

Collect the data necessary during computation of the k means clustering, i.e.

* `points::Vector{P}` – the given data
* `centers::Vector{P}` – the cluster centrs
* `assignment::Vector{<:Int}` – a vector the same length as `points` assigning each of them to a cluster
* `stop::StoppingCriterion` a stoppingCriterion

Here `P` is a data type for points on the manifold the `points` (and `centers`) live on.
This manifold is stored in the [`KMeansProblem`](@ref).

# Constructor

    KMeansOptions(
        points::Vector{P},
        centers::Vector{P},
        stop::StoppingCriterion=StoppingCriterion(100)
    )

Initialize the options. The assignment is set to zero and initialized at the beginning of
the algorithm.
"""
struct KMeansOptions{P} <: Options
    points::Vector{P}
    centers::Vector{P}
    assignment::Vector{<:Int}
    stop::StoppingCriterion
    function KMeansOptions{P}(points::Vector{P}, centers::Vector{P}, stop::StoppingCriterion) where {P}
        return new(points, centers, zeros(Int,length(points)), stop)
    end
end
function KMeansOptions(points::Vector{P}, centers::Vector{P}, stop::StoppingCriterion=StopAfterIteration(100)) where {P}
    return KMeansOptions{P}(points, centers, stop)
end

@doc """
    KMeansProblem <: Problem

Store the fixed data necessary for [`kmeans`](@ref), i.e. only a `Manifold M`.
"""
struct KMeansProblem{TM <: Manifold} <: Problem
    M::TM
end

function initialize_solver!(p::KMeansProblem, o::KMeansOptions)
    k_means_update_assignment!(p,o)
end

function step_solver!(p::KMeansProblem, o::KMeansOptions, ::Int)
    # (1) Update assignments
    k_means_update_assignment!(p,o)
    # (2) Update centers
    for i=1:length(o.centers)
        any(o.assignment==i) && mean!(p.M, o.centers[i], o.points[o.assignment==i])
    end
end

function k_means_update_assignment!(p::KMeansProblem, o::KMeansOptions)
    for i=1:length(o.points)
        o.assignment[i] = argmin([ distance(p.M,o.points[i],c) for c in o.centers ] )
    end
end

"""
    kmeans( M::Manifold, pts::Vector{P};
        num_centers=5,
        centers = pts[1:num_centers],
        stop=StopAfterIteration(100),
        kwargs...
    )

Compute a simple k-means on a Riemannian manifold `M` for the points `pts`.
The `num_centers` defaults to `5` and the initial centers `centers` are set to the first
`num_centers` data items. The stopping criterion is set by default to 100 iterations.

The `kwargs...` can be used to initialize [`RecordOptions`](https://manoptjl.org/stable/plans/index.html#RecordOptions-1) or [`DebugOptions`](https://manoptjl.org/stable/plans/index.html#DebugOptions-1)
decorators from [Manopt.jl](https://manoptjl.org)

Returns the final [`KMeansOptions`](@ref) including the final assignment vector and the centers.
"""
function kmeans(M::Manifold, pts::Vector{P};
    num_centers = 5,
    centers = pts[1:num_centers],
    stop=StopAfterIteration(100),
    kwargs...
    ) where {P}
    p = KMeansProblem(M)
    o =  KMeansOptions(pts,centers,stop)
    o = decorate_options(o; kwargs...)
    oR = solve(p,o)
    return get_options(oR)
end

max_stars_repo_name: JuliaManifolds/ManifoldML

max_issues_repo_name: JuliaManifolds/ManifoldML

max_forks_repo_name: JuliaManifolds/ManifoldML


text:
using RDatasets

include("cv.jl")

iris = dataset("datasets", "iris")

features = Array(iris[:, 1:4])'
ma = maximum(features, 2)
mi = minimum(features, 2)
features = -1 + 2 * (features .- mi) ./ (ma - mi)

# map labels to ints
classes  = unique(iris[:Species])
label2num = Dict()
for (i, l) in enumerate(classes)
    label2num[l] = i
end

labels = Vector{Int}(getindex.([label2num], iris[:Species]))

cv(features, labels, C=2^5, bias=1)


text:
using Xsum, Test, Random

Random.seed!(314159)
setprecision(65536)

@testset "xsum" begin
    for n in (100, 10^4)
        a = randn(n)
        exact = Float64(sum(big.(a)))
        @test exact == xsum(a)

        A = [a a]
        @test exact == xsum(@view A[:,1])
        @test exact == xsum(@view Array(A')[1,:])

        @test 2exact == xsum(2x for x in a) == xsum(x -> 2x, a)

        @test Complex(2exact, 4exact) == xsum(Complex(2x,4x) for x in a)

        @test Complex(2exact, 4exact) == xsum(Iterators.flatten((a, Complex(x,4x) for x in a)))
    end
end

@testset "XAccumulator" begin
    for n in (100, 10^4)
        a = randn(n)
        exact = Float64(sum(big.(a)))
        @test exact == xsum(a)

        s1 = accumulate!(XAccumulator(), a[1:n÷2])
        s2 = accumulate!(XAccumulator(), a[(n÷2)+1:end])
        s1′ = deepcopy(s1) # should work like XAccumulator(s1)
        @test exact == float(accumulate!(s1′, s2))
        @test exact == float(s1 + s2) == float(sum([s1,s2]))
        @test exact == float(accumulate!(XAccumulator(), a[2:end]) + a[1]) ==
                       float(a[1] + accumulate!(XAccumulator(), a[2:end]))

        a[(n÷2)+1:end] *= -1 # exact
        @test xsum(a) == float(s1 - s2) == float(-(s2 - s1)) ==
              float(accumulate!(XAccumulator(), a[2:end]) - (-a[1])) ==
              float(a[1] - accumulate!(XAccumulator(), -a[2:end]))
    end
end


text:
@testset "service module" begin
    @service S3
    @test :S3 in names(Main)
end

@testset "global config, kwargs" begin
    try
        region = "us-east-2"
        AWS.global_aws_config(; region=region)

        @test AWS.global_aws_config().region == region
    finally
        AWS.aws_config[] = AWSConfig()
    end
end

@testset "set global aws config" begin
    test_region = "test region"
    expected = AWSConfig(region=test_region)

    try
        AWS.global_aws_config(expected)
        result = AWS.global_aws_config()

        @test result.region == test_region
    finally
        AWS.global_aws_config(AWSConfig())
    end
end

@testset "set user agent" begin
    new_user_agent = "new user agent"

    @test AWS.user_agent[] == "AWS.jl/1.0.0"
    set_user_agent(new_user_agent)
    @test AWS.user_agent[] == new_user_agent
end

@testset "sign" begin
    aws = AWS.AWSConfig()

    access_key = "access-key"
    secret_key = "ssh... it is a secret"

    aws.credentials.access_key_id = access_key
    aws.credentials.secret_key = secret_key

    time = DateTime(2020)
    date = Dates.format(time, dateformat"yyyymmdd")

    request = Request(
        service="s3",
        api_version="api_verison",
        request_method="GET",
        headers=LittleDict(
            "Host" => "s3.us-east-1.amazonaws.com",
            "User-Agent" => "AWS.jl/1.0.0"
        ),
        resource="/test-resource",
        url="https://s3.us-east-1.amazonaws.com/test-resource"
    )

    @testset "sign v2" begin
        result = AWS.sign_aws2!(aws, request, time)
        content = result.content
        content_type = result.headers["Content-Type"]

        expected_access_key = "AWSAccessKeyId=$access_key"
        expected_expires = "Expires=2020-01-01T00%3A02%3A00Z"
        expected_signature_method = "SignatureMethod=HmacSHA256"
        expected_signature_version = "SignatureVersion=2"
        expected_signature = "Signature=O0MLzMKpEcfVZeHy0tyxVAuZF%2BvrvbgIGgqbWtJLTQ0%3D"

        expected_content = join([
            expected_access_key,
            expected_expires,
            expected_signature_method,
            expected_signature_version,
            expected_signature
        ], '&')

        @test content == expected_content
    end

    @testset "sign v4" begin
        expected_x_amz_content_sha256 = bytes2hex(digest(MD_SHA256, request.content))
        expected_content_md5 = base64encode(digest(MD_MD5, request.content))
        expected_x_amz_date = Dates.format(time, dateformat"yyyymmdd\THHMMSS\Z")

        result = AWS.sign_aws4!(aws, request, time)
        headers = result.headers

        @test headers["x-amz-content-sha256"] == expected_x_amz_content_sha256
        @test headers["Content-MD5"] == expected_content_md5
        @test headers["x-amz-date"] == expected_x_amz_date

        authorization_header = split(headers["Authorization"], ' ')
        @test length(authorization_header) == 4
        @test authorization_header[1] == "AWS4-HMAC-SHA256"
        @test authorization_header[2] == "Credential=$access_key/$date/us-east-1/$(request.service)/aws4_request,"
        @test authorization_header[3] == "SignedHeaders=content-md5;content-type;host;user-agent;x-amz-content-sha256;x-amz-date,"
        @test authorization_header[4] == "Signature=0f292eaf0b66cf353bafcb1b9b6d90ee27064236a60f17f6fc5bd7d40173a0be"
    end
end

@testset "submit_request" begin
    aws = AWS.AWSConfig()

    function _expected_body(body::AbstractString, dict_type::Type)
        parsed = parse_xml(body)
        return xml_dict(XMLDict.root(parsed.x), dict_type)
    end

    @testset "HEAD request method" begin
        expected_result_type = LittleDict

        request = Request(
            service="s3",
            api_version="api_verison",
            request_method="HEAD",
            url="https://s3.us-east-1.amazonaws.com/sample-bucket"
        )

        apply(Patches._aws_http_request_patch) do
            Patches._response!()
            result = AWS.submit_request(aws, request)

            @test result == expected_result_type(Patches.headers)
            @test result isa expected_result_type
        end
    end

    @testset "return stream" begin
        request = Request(
            service="s3",
            api_version="api_verison",
            request_method="GET",
            return_stream=true,
            response_stream=Base.BufferStream(),
            url="https://s3.us-east-1.amazonaws.com/sample-bucket"
        )

        apply(Patches._aws_http_request_patch) do
            Patches._response!()
            result = AWS.submit_request(aws, request)

            @test result == request.response_stream
        end
    end

    @testset "return raw" begin
        request = Request(
            service="s3",
            api_version="api_verison",
            request_method="GET",
            url="https://s3.us-east-1.amazonaws.com/sample-bucket",
            return_raw=true
        )

        @testset "body" begin
            apply(Patches._aws_http_request_patch) do
                Patches._response!()
                result = AWS.submit_request(aws, request)

                @test String(result) == Patches.body
            end
        end

        @testset "body and headers" begin
            apply(Patches._aws_http_request_patch) do
                Patches._response!()
                body, headers = AWS.submit_request(aws, request; return_headers=true)

                @test String(body) == Patches.body
                @test headers == Patches.headers
            end
        end
    end

    @testset "MIME" begin
        request = Request(
            service="s3",
            api_version="api_verison",
            request_method="GET",
            url="https://s3.us-east-1.amazonaws.com/sample-bucket"
        )

        @testset "empty" begin
            apply(Patches._aws_http_request_patch) do
                @testset "default" begin
                    expected_body = ""
                    expected_headers = Pair["Content-Type"=>"",]

                    Patches._response!(headers=expected_headers, body=expected_body)

                    @testset "body" begin
                       result = AWS.submit_request(aws, request)

                       @test String(result) == expected_body
                    end

                    @testset "body and headers" begin
                        body, headers = AWS.submit_request(aws, request; return_headers=true)

                        @test String(body) == expected_body
                        @test headers == expected_headers
                    end
                end

                @testset "text/xml" begin
                    expected_headers = Pair["Content-Type"=>"text/xml",]
                    expected_body_type = LittleDict{Union{Symbol, String}, Any}
                    expected_body = _expected_body(Patches.body, expected_body_type)

                    expected_header_type = LittleDict{SubString{String}, SubString{String}}

                    Patches._response!(headers=expected_headers)

                    @testset "body" begin
                        result = AWS.submit_request(aws, request)

                        @test result isa expected_body_type
                        @test result == expected_body
                    end

                    @testset "body and headers" begin
                        body, headers = AWS.submit_request(aws, request; return_headers=true)

                        @test body == expected_body
                        @test body isa expected_body_type

                        @test headers == LittleDict(expected_headers)
                        @test headers isa expected_header_type
                    end
                end
            end
        end

        @testset "xml" begin
            request = Request(
                service="s3",
                api_version="api_verison",
                request_method="GET",
                url="https://s3.us-east-1.amazonaws.com/sample-bucket",
            )

            expected_body_type = LittleDict{Union{Symbol, String}, Any}
            expected_body = _expected_body(Patches.body, expected_body_type)
            expected_headers = Pair["Content-Type"=>"application/xml",]

            apply(Patches._aws_http_request_patch) do
                Patches._response!(headers=expected_headers,)

                @testset "body" begin
                    result = AWS.submit_request(aws, request)

                    @test result == expected_body
                    @test result isa expected_body_type
                end

                @testset "body and headers" begin
                    body, headers = AWS.submit_request(aws, request; return_headers=true)

                    @test body == expected_body
                    @test body isa expected_body_type

                    @test headers == LittleDict(expected_headers)
                    @test headers isa LittleDict{SubString{String}, SubString{String}}
               end
            end
        end

        @testset "JSON" begin
            json_headers = ["Content-Type"=>"application/json"]
            body = Dict{String,Any}(
                "Marker" => nothing,
                "VaultList" => Any[Dict{String,Any}(
                    "VaultName" => "test",
                    "SizeInBytes" => 0,
                    "NumberOfArchives" => 0,
                    "CreationDate" => "2020-06-22T03:14:41.754Z",
                    "VaultARN" => "arn:aws:glacier:us-east-1:000:vaults/test",
                    "LastInventoryDate" => nothing
                )]
            )
            json_body = JSON.json(body)

            expected_body_type = LittleDict{String, Any}
            expected_body = JSON.parse(json_body, dicttype=LittleDict)

            apply(Patches._aws_http_request_patch) do
                Patches._response!(body=json_body, headers=json_headers,)

                @testset "body" begin
                    result = AWS.submit_request(aws, request)

                    @test result isa expected_body_type
                    @test result == expected_body
                end

                @testset "body and headers" begin
                    body, headers = AWS.submit_request(aws, request; return_headers=true)

                    @test body == expected_body
                    @test body isa expected_body_type

                    @test headers == LittleDict(json_headers)
                    @test headers isa LittleDict{SubString{String}, SubString{String}}
                end
            end
        end

        @testset "Text" begin
            request = Request(
                service="s3",
                api_version="api_verison",
                request_method="GET",
                url="https://s3.us-east-1.amazonaws.com/sample-bucket",
            )

            apply(Patches._aws_http_request_patch) do
                expected_headers = ["Content-Type" => "text/html"]
                expected_body = Patches.body
                expected_header_type = LittleDict{SubString{String}, SubString{String}}

                Patches._response!(headers=expected_headers)

                @testset "body" begin
                    result = AWS.submit_request(aws, request)

                    @test result isa String
                    @test result == expected_body
                end

                @testset "body and headers" begin
                    body, headers = AWS.submit_request(aws, request; return_headers=true)

                    @test body == expected_body
                    @test body isa String

                    @test headers == LittleDict(expected_headers)
                    @test headers isa expected_header_type
                end
            end
        end
    end
end

@testset "_generate_rest_resource" begin
    request_uri = "/{Bucket}/{Key+}"
    args = Dict{String, Any}(
        "Bucket"=>"aws.jl-test",
        "Key"=>"Test-Key"
    )

    expected = "/$(args["Bucket"])/$(args["Key"])"
    result = AWS._generate_rest_resource(request_uri, args)
    @test result == expected
end

@testset "generate_service_url" begin
    region = "us-east-2"
    resource = "/aws.jl-test---timestamp"
    config = AWSConfig()
    config.region = region

    request = Request(
        service="service",
        api_version="api_version",
        request_method="GET",
        resource=resource,
    )

    @testset "regionless endpoints" for regionless_endpoint in ("iam", "route53")
        endpoint = "sdb"
        request.service = regionless_endpoint
        expected_result = "https://$regionless_endpoint.amazonaws.com$resource"
        result = AWS.generate_service_url(config, request.service, request.resource)

        @test result == expected_result
    end

    @testset "region service" begin
        endpoint = "sdb"
        request.service = endpoint
        expected_result = "https://$endpoint.$region.amazonaws.com$resource"
        result = AWS.generate_service_url(config, request.service, request.resource)

        @test result == expected_result
    end

    @testset "sdb -- us-east-1 region exception" begin
        endpoint = "sdb"
        request.service = endpoint
        expected_result = "https://$endpoint.amazonaws.com$resource"
        config.region = "us-east-1"
        result = AWS.generate_service_url(config, request.service, request.resource)

        @test result == expected_result
    end
end

@testset "_return_headers" begin
    @testset "key exists" begin
        expected = true
        dict = Dict{String, Any}("return_headers"=>true)
        result = AWS._return_headers(dict)

        @test result == expected
        @test isempty(dict)
    end

    @testset "key dne" begin
        expected = false
        result = AWS._return_headers(Dict{String, Any}())

        @test result == expected
    end
end

@testset "_flatten_query" begin
    high_level_value = "high_level_value"
    entry_1 = LittleDict("low_level_key_1"=>"low_level_value_1", "low_level_key_2"=>"low_level_value_2")
    entry_2 = LittleDict("low_level_key_3"=>"low_level_value_3", "low_level_key_4"=>"low_level_value_4")

    args = LittleDict("high_level_key"=>high_level_value, "high_level_array"=>[entry_1, entry_2])

    @testset "non-special case suffix" begin
        service = "sts"
        result = AWS._flatten_query(service, args)

        expected = Pair{String,String}[
            "high_level_key" => "high_level_value",
            "high_level_array.member.1.low_level_key_1" => "low_level_value_1",
            "high_level_array.member.1.low_level_key_2" => "low_level_value_2",
            "high_level_array.member.2.low_level_key_3" => "low_level_value_3",
            "high_level_array.member.2.low_level_key_4" => "low_level_value_4"
        ]

        @test result == expected
    end

    @testset "sqs - special casing suffix" begin
        service = "sqs"
        result = AWS._flatten_query(service, args)

        expected = Pair{String,String}[
            "high_level_key" => "high_level_value",
            "high_level_array.1.low_level_key_1" => "low_level_value_1",
            "high_level_array.1.low_level_key_2" => "low_level_value_2",
            "high_level_array.2.low_level_key_3" => "low_level_value_3",
            "high_level_array.2.low_level_key_4" => "low_level_value_4"
        ]

        @test result == expected
    end
end

@testset "_clean_s3_uri" begin
    uri = "/test-bucket/*)=('! +.txt?list-objects=v2"
    expected_uri = "/test-bucket/%2A%29%3D%28%27%21%20%2B.txt?list-objects=v2"
    @test AWS._clean_s3_uri(uri) == expected_uri

    # make sure that other parts of the uri aren't changed by `_clean_s3_uri`
    for uri in (
            "https://julialang.org",
            "http://julialang.org",
            "http://julialang.org:8080",
            "/onlypath",
            "/path?query=  +99",
            "/anchor?query=yes#anchor1"
    )
        @test AWS._clean_s3_uri(uri) == uri
    end
end

@testset "json" begin
    @testset "high-level secrets manager" begin
        @service Secrets_Manager

        secret_name = "aws-jl-test---" * _now_formatted()
        secret_string = "sshhh it is a secret!"

        function _get_secret_string(secret_name)
            response = Secrets_Manager.get_secret_value(secret_name)

            return response["SecretString"]
        end

        Secrets_Manager.create_secret(secret_name, LittleDict("SecretString" => secret_string, "ClientRequestToken" => string(uuid4())))

        try
            @test _get_secret_string(secret_name) == secret_string
        finally
            Secrets_Manager.delete_secret(secret_name, LittleDict("ForceDeleteWithoutRecovery" => "true"))
        end

        @test_throws AWSException _get_secret_string(secret_name)
    end

    @testset "low-level secrets manager" begin
        secret_name = "aws-jl-test---" * _now_formatted()
        secret_string = "sshhh it is a secret!"

        function _get_secret_string(secret_name)
            response = AWSServices.secrets_manager("GetSecretValue", LittleDict("SecretId"=>secret_name))

            return response["SecretString"]
        end

        resp = AWSServices.secrets_manager("CreateSecret", LittleDict(
            "Name"=>secret_name,
            "SecretString"=>secret_string,
            "ClientRequestToken"=>string(uuid4()),
        ))

        try
            @test _get_secret_string(secret_name) == secret_string
        finally
            AWSServices.secrets_manager("DeleteSecret", LittleDict(
                "SecretId"=>secret_name,
                "ForceDeleteWithoutRecovery"=>"true",
            ))
        end

        @test_throws AWSException _get_secret_string(secret_name)
    end
end

@testset "query" begin
    @testset "high-level iam" begin
        @service IAM

        policy_arn = ""
        expected_policy_name = "aws-jl-test---" * _now_formatted()
        expected_policy_document = LittleDict(
            "Version" => "2012-10-17",
            "Statement" => [
                LittleDict(
                    "Effect" => "Allow",
                    "Action" => ["s3:Get*", "s3:List*"],
                    "Resource" => ["arn:aws:s3:::my-bucket/shared/*"]
                )
            ],
        )
        expected_policy_document = JSON.json(expected_policy_document)

        response = IAM.create_policy(expected_policy_document, expected_policy_name)
        policy_arn = response["CreatePolicyResult"]["Policy"]["Arn"]

        try
            response_policy_version = IAM.get_policy_version(policy_arn, "v1")
            response_document = response_policy_version["GetPolicyVersionResult"]["PolicyVersion"]["Document"]
            @test HTTP.unescapeuri(response_document) == expected_policy_document
        finally
            IAM.delete_policy(policy_arn)
        end

        @test_throws AWSException IAM.get_policy(policy_arn)
    end

    @testset "low-level iam" begin
        policy_arn = ""
        expected_policy_name = "aws-jl-test---" * _now_formatted()
        expected_policy_document = LittleDict(
            "Version"=> "2012-10-17",
            "Statement"=> [
                LittleDict(
                    "Effect"=>"Allow",
                    "Action"=>["s3:Get*", "s3:List*"],
                    "Resource"=> ["arn:aws:s3:::my-bucket/shared/*"]
                )
            ],
        )
        expected_policy_document = JSON.json(expected_policy_document)

        response = AWSServices.iam("CreatePolicy", LittleDict("PolicyName"=>expected_policy_name, "PolicyDocument"=>expected_policy_document))
        policy_arn = response["CreatePolicyResult"]["Policy"]["Arn"]

        try
            response_policy_version = AWSServices.iam("GetPolicyVersion", LittleDict("PolicyArn"=>policy_arn, "VersionId"=>"v1"))
            response_document = response_policy_version["GetPolicyVersionResult"]["PolicyVersion"]["Document"]
            @test HTTP.unescapeuri(response_document) == expected_policy_document
        finally
            AWSServices.iam("DeletePolicy", LittleDict("PolicyArn"=>policy_arn))
        end

        @test_throws AWSException AWSServices.iam("GetPolicy", LittleDict("PolicyArn" => policy_arn))
    end

    @testset "high-level sqs" begin
        @service SQS

        queue_name = "aws-jl-test---" * _now_formatted()
        expected_message = "Hello for AWS.jl"

        function _get_queue_url(queue_name)
            result = SQS.get_queue_url(queue_name)

            return result["GetQueueUrlResult"]["QueueUrl"]
        end

        # Create Queue
        SQS.create_queue(queue_name)
        queue_url = _get_queue_url(queue_name)

        try
            # Get Queues
            @test !isempty(queue_url)

            # Change Message Visibility Batch Request
            expected_message_id = "aws-jl-test"

            SQS.send_message(expected_message, queue_url)

            response = SQS.receive_message(queue_url)
            receipt_handle = response["ReceiveMessageResult"]["Message"]["ReceiptHandle"]

            response = SQS.delete_message_batch(
                [
                    LittleDict(
                        "Id"=>expected_message_id,
                        "ReceiptHandle"=>receipt_handle,
                    ),
                ],
                queue_url,
            )

            message_id = response["DeleteMessageBatchResult"]["DeleteMessageBatchResultEntry"]["Id"]
            @test message_id == expected_message_id

            SQS.send_message(expected_message, queue_url)

            result = SQS.receive_message(queue_url)
            message = result["ReceiveMessageResult"]["Message"]["Body"]
            @test message == expected_message
        finally
            SQS.delete_queue(queue_url)
        end

        @test_throws AWSException _get_queue_url(queue_name)
    end

    @testset "low-level sqs" begin
        queue_name = "aws-jl-test---" * _now_formatted()
        expected_message = "Hello for AWS.jl"

        function _get_queue_url(queue_name)
            result = AWSServices.sqs("GetQueueUrl", LittleDict("QueueName" => queue_name))

            return result["GetQueueUrlResult"]["QueueUrl"]
        end

        # Create Queue
        AWSServices.sqs("CreateQueue", LittleDict("QueueName" => queue_name))

        queue_url = _get_queue_url(queue_name)
        @test !isempty(queue_url)

        try
            # Change Message Visibility Batch Request
            expected_message_id = "aws-jl-test"

            AWSServices.sqs("SendMessage", LittleDict(
                    "QueueUrl" => queue_url,
                    "MessageBody" => expected_message
                )
            )

            response = AWSServices.sqs("ReceiveMessage", LittleDict("QueueUrl" => queue_url,))
            receipt_handle = response["ReceiveMessageResult"]["Message"]["ReceiptHandle"]

            response = AWSServices.sqs("DeleteMessageBatch", LittleDict(
                    "QueueUrl" => queue_url,
                    "DeleteMessageBatchRequestEntry" => [
                        LittleDict(
                            "Id" => expected_message_id,
                            "ReceiptHandle" => receipt_handle,
                        )
                    ]
                )
            )

            message_id = response["DeleteMessageBatchResult"]["DeleteMessageBatchResultEntry"]["Id"]
            @test message_id == expected_message_id

            # Send message
            AWSServices.sqs("SendMessage", LittleDict(
                    "QueueUrl" => queue_url,
                    "MessageBody" => expected_message
                )
            )

            # Receive Message
            result = AWSServices.sqs("ReceiveMessage", LittleDict("QueueUrl" => queue_url))
            message = result["ReceiveMessageResult"]["Message"]["Body"]
            @test message == expected_message
        finally
            AWSServices.sqs("DeleteQueue", LittleDict("QueueUrl" => queue_url))
        end

        @test_throws AWSException _get_queue_url(queue_name)
    end
end

@testset "rest-xml" begin
    @testset "high-level s3" begin
        @service S3

        bucket_name = "aws-jl-test---" * _now_formatted()
        file_name = string(uuid4())

        function _bucket_exists(bucket_name)
            try
                S3.head_bucket(bucket_name)
                return true
            catch e
                if e isa AWSException && e.cause.status == 404
                    return false
                else
                    rethrow(e)
                end
            end
        end

        # HEAD operation
        @test _bucket_exists(bucket_name) == false

        # PUT operation
        S3.create_bucket(bucket_name)
        @test _bucket_exists(bucket_name)

        try
            # PUT with parameters operation
            body = "sample-file-body"
            S3.put_object(bucket_name, file_name, Dict("body" => body))
            @test !isempty(S3.get_object(bucket_name, file_name))

            # GET operation
            result = S3.list_objects(bucket_name)
            @test result["Contents"]["Key"] == file_name

            # GET with parameters operation
            max_keys = 1
            result = S3.list_objects(bucket_name, Dict("max_keys" => max_keys))
            @test length([result["Contents"]]) == max_keys
        finally
            # DELETE with parameters operation
            S3.delete_object(bucket_name, file_name)
            @test_throws AWSException S3.get_object(bucket_name, file_name)

            # DELETE operation
            S3.delete_bucket(bucket_name)

            sleep(2)
        end

        @test _bucket_exists(bucket_name) == false
    end

    @testset "low-level s3" begin
        bucket_name = "aws-jl-test---" * _now_formatted()
        file_name = "*)=('! +.txt"  # Special characters which S3 allows

        function _bucket_exists(bucket_name)
            try
                AWSServices.s3("HEAD", "/$bucket_name")
                return true
            catch e
                if e isa AWSException && e.cause.status == 404
                    return false
                else
                    rethrow(e)
                end
            end
        end

        # HEAD operation
        @test _bucket_exists(bucket_name) == false

        # PUT operation
        AWSServices.s3("PUT", "/$bucket_name")
        @test _bucket_exists(bucket_name)

        try
            # PUT with parameters operation
            body = Array{UInt8}("sample-file-body")
            AWSServices.s3("PUT", "/$bucket_name/$file_name", Dict("body" => body))
            @test body == AWSServices.s3("GET", "/$bucket_name/$file_name")

            # GET operation
            result = AWSServices.s3("GET", "/$bucket_name")
            @test result["Contents"]["Key"] == file_name

            # GET with parameters operation
            max_keys = 1
            result = AWSServices.s3("GET", "/$bucket_name", Dict("max_keys" => max_keys))
            @test length([result["Contents"]]) == max_keys

            # POST with parameters operation
            body = """
                <Delete xmlns="http://s3.amazonaws.com/doc/2006-03-01/">
                    <Object>
                        <Key>$file_name</Key>
                    </Object>
                </Delete>
                """

            AWSServices.s3("POST", "/$bucket_name?delete", Dict("body" => body))
            @test_throws AWSException AWSServices.s3("GET", "/$bucket_name/$file_name")
        finally
            # DELETE operation
            AWSServices.s3("DELETE", "/$bucket_name")

            sleep(2)
        end

        @test _bucket_exists(bucket_name) == false
    end
end

@testset "rest-json" begin
    @testset "high-level glacier" begin
        @service Glacier

        timestamp = _now_formatted()
        vault_names = ["aws-jl-test-01---$timestamp", "aws-jl-test-02---$timestamp", ]

        # PUT
        for vault in vault_names
            Glacier.create_vault("-", vault)
        end

        try
            # POST
            tags = Dict("Tags"=> LittleDict("Tag-01" => "Tag-01", "Tag-02" => "Tag-02"))

            for vault in vault_names
                Glacier.add_tags_to_vault("-", vault, tags)
            end

            for vault in vault_names
                result_tags = Glacier.list_tags_for_vault("-", vault)
                @test result_tags == tags
            end

            # GET
            # If this is an Integer AWS Coral cannot convert it to a String
            # "class com.amazon.coral.value.json.numbers.TruncatingBigNumber can not be converted to an String"
            limit = "1"
            args = LittleDict("limit" => limit)
            result = Glacier.list_vaults("-", args)
            @test length(result["VaultList"]) == parse(Int, limit)
        finally
            # DELETE
            for vault in vault_names
                Glacier.delete_vault("-", vault)
            end
        end

        result = Glacier.list_vaults("-")
        res_vault_names = [v["VaultName"] for v in result["VaultList"]]

        for vault in vault_names
            @test !(vault in res_vault_names)
        end
    end

    @testset "low-level glacier" begin
        timestamp = _now_formatted()
        vault_names = ["aws-jl-test-01---$timestamp", "aws-jl-test-02---$timestamp", ]

        # PUT
        for vault in vault_names
            AWSServices.glacier("PUT", "/-/vaults/$vault")
        end

        try
            # POST
            tags = Dict("Tags"=> LittleDict("Tag-01" => "Tag-01", "Tag-02" => "Tag-02"))

            for vault in vault_names
                AWSServices.glacier("POST", "/-/vaults/$vault/tags?operation=add", tags)
            end

            for vault in vault_names
                result_tags = AWSServices.glacier("GET", "/-/vaults/$vault/tags")

                @test result_tags == tags
            end

            # GET
            # If this is an Integer AWS Coral cannot convert it to a String
            # "class com.amazon.coral.value.json.numbers.TruncatingBigNumber can not be converted to an String"
            limit = "1"
            params = LittleDict("limit" => limit)
            result = AWSServices.glacier("GET", "/-/vaults/", params)

            @test length(result["VaultList"]) == parse(Int, limit)
        finally
            # DELETE
            for vault in vault_names
                AWSServices.glacier("DELETE", "/-/vaults/$vault")
            end
        end

        result = AWSServices.glacier("GET", "/-/vaults")
        res_vault_names = [v["VaultName"] for v in result["VaultList"]]

        for vault in vault_names
            @test !(vault in res_vault_names)
        end
    end
end


text:
__precompile__()

module GeoJSON

    using JSON, Compat

    export
        Point,
        MultiPoint,
        LineString,
        MultiLineString,
        Polygon,
        MultiPolygon,
        GeometryCollection,
        Feature,
        FeatureCollection,
        geojson

    include("types.jl")
    include("parser.jl")
end


text:
using DistributedArrays

include("ADMMWorker.jl")

"""
`distributeData(x,y)`

Distributes x and y to the available worker processes and returns
them as distributed Arrays.
"""
function distributeData(x::Array{Float64,2}, y::Array{Float64,1})
    print("distributing x and y...\t\t")
    tic()
    N = nprocs()-1
    if N<2
        error("number of workers needs to be at least 2.")
    end
    x = distribute(x, dist=[N,1])
    y = distribute(y)
    @printf "finished after %.3f seconds\n" toq()
    return (x,y)
end

# TODO: if we dont normalize then z will grow very large. Where should the normalization happen??
"""
`admm(x,y;<keyword arguments>)`

Solves the SVM problem in parallel using the ADMM framework by Stephen Boyd.
See https://web.stanford.edu/~boyd/papers/pdf/admm_distr_stats.pdf.
The algorithm is developed by Caoxie Zhang, Honglak Lee and Kang G. Shin.
See http://www.jmlr.org/proceedings/papers/v22/zhang12a/zhang12a.pdf.
For solving the subproblem the dual coordinate descent method is used.

### Keyword arguments
* `C=1.0`:
the parameter C of the SVM problem
* `rho=1.0`
* `shrinking=false`: the method uses the shrinking heuristic by Thorsten Joachims if true. See https://www.cs.cornell.edu/people/tj/publications/joachims_99a.pdf
* `outer_iterations=10`: the number of admm iterations
* `inner_iterations=10`: the number of iterations of the dual coordinate descent performed during each admm iteration
* `parallel=true`: The subproblem is solved in parallel if true

### Returns
* weight vector `w`
"""
function admm(
x::DistributedArrays.DArray{Float64,2,Array{Float64,2}},
y::DistributedArrays.DArray{Float64,1,Array{Float64,1}};
C=1.0,
rho=1.0,
outer_iterations=10,
inner_iterations=10,
parallel=true
)
    tic()
    N = nprocs()-1
    if N<2
        error("number of workers needs to be at least 2.")
    end

    m,d = size(x)

    # initialize vectors:
    w = zeros(d,N) # every column w[:,i] is the w vector of one of the workers
    z = zeros(d)
    u = zeros(d,N)

    for t in 1:outer_iterations

        ## w-update:
        if parallel # parallel update
            @sync for i in 1:N
                @async begin
                    v = z - u[:,i]
                    worker = workers()[i]
                    w[:,i] = remotecall_fetch(worker,dualcdForADMM2,x,y,v,rho,C,true,inner_iterations,0.001)
                end
            end
        else # sequential update (but still distributed)
            for i in 1:N
                v = z - u[:,i]
                worker = workers()[i]
                w[:,i] = remotecall_fetch(worker,dualcdForADMM2,x,y,v,rho,C,true,inner_iterations,0.001)
                #w[:,i] /= vecnorm(w[:,i]) # normalizing w here leads to very slow convergence
            end
        end

        ## z-update:
        z = sum(broadcast(+,w,z), 2)
        #z = sum(w+z,2) # summiere w+z zeilenweise auf (eine Summe je Zeile)
        z /= (N+1/rho)
        z = vec(z)
        #z /= vecnorm(z)

        ## u-update:
        # subtract z from each column of u+w and store the result in u:
        u = broadcast(-,u+w,z)
    end

    @printf "finished after %.3f seconds (%d iterations)\n" toq() outer_iterations
    return z
end


text:
export parsebool
export between2and8
parsebool(s::String) = lowercase(s) == "yes" ? true : false
between2and8(x) = 2 < x < 8


text:
using Base: @deprecate

@deprecate Distinct() Unique()

# It wasn't a public API but to play on the safe side:
@deprecate induction(itr) extract_transducer(itr) false


text:
@testset "658.find-k-closest-elements.jl" begin
    @test find_closest_elements([1, 2, 3, 4, 5], 4, 3) == [1, 2, 3, 4]
    @test find_closest_elements([1, 2, 3, 4, 5], 4, -1) == [1, 2, 3, 4]
    @test find_closest_elements([10, 15, 24, 32, 60, 74, 84, 91, 105, 113, 114, 117, 150, 155, 173, 192, 231, 244, 271, 278, 300, 302, 324, 375, 384, 393, 420, 439, 465, 474, 490, 522, 585, 592, 592, 615, 619, 716, 768, 778, 823, 842, 843, 852, 852, 853, 909, 929, 930, 970], 20, 345) == [150,155,173,192,231,244,271,278,300,302,324,375,384,393,420,439,465,474,490,522]
end


text:
mutable struct PlateExtendState{U,V,W}
    score::Float64
    weight::Float64
    isempty::Bool
    args::U
    nodes::V
    changes::W
end

function extend_existing_trace!(gen::Plate{T,U}, key::Int, state::PlateExtendState, subtraces, retvals) where {T,U}
    node = haskey(state.nodes, key) ? state.nodes[key] : EmptyAssignment()
    if haskey(state.changes, key)
        kernel_change = state.changes[key]
    else
        kernel_change = nothing
    end
    subtrace::U = state.subtraces[key]
    prev_call = get_call_record(subtrace)
    kernel_args = get_args_for_key(state.args, key)
    (subtrace, kernel_weight) = extend(gen.kernel, kernel_args, kernel_change, subtrace, node)
    state.weight += kernel_weight
    call::CallRecord{T} = get_call_record(subtrace)
    state.score += (call.score - prev_call.score)
    subtraces = assoc(trace, key, subtrace)
    retvals = assoc(retvals, key, call.retval::T)
    state.is_empty = state.is_empty && !has_choices(subtraces)
    (subtraces, retvals)
end

function generate_new_trace!(gen::Plate{T,U}, key::Int, state::PlateExtendState, subtraces, retvals, kernel) where {T,U}
    node = haskey(state.nodes, key) ? state.nodes[key] : EmptyAssignment()
    kernel_args = get_args_for_key(state.args, key)
    (subtrace::U, kernel_weight) = generate(gen.kernel, kernel_args, node)
    state.weight += kernel_weight
    subtraces = push(subtraces, subtrace)
    call::CallRecord{T} = get_call_record(subtrace)
    state.score += call.score
    retvals = push(retvals, call.retval::T)
    (subtraces, retvals)
end

function extend_process_constraints!(nodes, key::Int, node, new_length, to_visit)
    if key <= new_length
        push!(to_visit, key)
        nodes[key] = node
    else
        error("Constraints under key $key not part of trace")
    end
end

function extend_process_constraints!(nodes, key, node, new_length, to_visit)
    error("Constraints under key $key not part of trace")
end

"""
Extend with argument change information
"""
function extend(gen::Plate, args, change::PlateChange, trace::VectorTrace, constraints) where {T}

    (new_length, prev_length) = get_prev_and_new_lengths(args, trace)
    if prev_length < new_length
        error("extend cannot remove random choices")
    end

    # calculate which existing applications to visit
    to_visit = Set{Int}()
    changes = Dict{Int, T}()
    for (i, kernel_change) in zip(change.changed_args, change.sub_changes)
        push!(to_visit, i)
        changes[i] = kernel_change
    end

    _extend(gen, args, trace, constraints, to_visit, changes)
end

"""
Extend without argument change information
"""
function extend(gen::Plate{T,U}, args, change::NoChange, trace::VectorTrace{T,U}, constraints) where {T,U}

    (new_length, prev_length) = get_prev_and_new_lengths(args, trace)

    # visit all existing applications
    to_visit = 1:new_length
    changes = Dict{Int, Any}() # not used

    _extend(gen, args, trace, constraints, to_visit, changes)
end

function _extend(gen::Plate, args, trace::VectorTrace, constraints, to_visit, changes)

    (new_length, prev_length) = get_prev_and_new_lengths(args, trace)
    if prev_length < new_length
        error("extend cannot remove random choices")
    end

    # collect constraints, indexed by key, and error if any are not in the new trace
    nodes = Dict{Int, Any}()
    for (key, node) in get_internal_nodes(constraints)
        extend_process_constraints!(nodes, key, node, new_length, to_visit)
    end

    # collect initial state
    state = PlateExtendState(trace.call.score, 0., trace.is_empty, args, nodes, changes)
    subtraces = trace.subtraces
    retvals = trace.call.retvals

    # visit all existing applications
    for key in to_visit
        (subtraces, retvals) = extend_existing_trace!(gen, key, state, subtraces, retvals)
    end

    # visit each new application and run generate on it
    for key=prev_length+1:new_length
        (subtraces, retvals) = generate_new_trace!(gen, key, state, subtraces, retvals)
    end

    call = CallRecord(state.score, retvals, args)
    trace = VectorTrace(subtraces, call, state.is_empty)
    retchange = nothing
    (trace, state.weight, retchange)
end

max_stars_repo_name: BoltzmannBrain/Gen

max_issues_repo_name: BoltzmannBrain/Gen

max_forks_repo_name: BoltzmannBrain/Gen


text:
#=
Popis
  Funkcia vypocita hodnotu eccentricity centrality pre kazdy vrchol.

Parametre
  g : datova struktura grafu :: GenericGraph
  dist_key : nazov atributu, v ktorom je ulozene ohodnotenie hrany :: String

Navratova hodnota
  eccentricity : slovnik s mapovanim (kluc=vrchol_grafu => hodnota=eccentricita) :: Dict{Int64, Float64}

Poznamky
=#

function centrality_eccentricity(g::GenericGraph; dist_key::AbstractString="weight")

  epi = AttributeEdgePropertyInspector{Float64}(dist_key)
  eccentricity = [v.index => 0.0 for v=vertices(g)]

  for v in vertices(g)

    temp_dists = dijkstra_shortest_paths(g, AttributeEdgePropertyInspector{Float64}(dist_key), [v]).dists
    temp_dists = filter(x -> x != Inf, temp_dists)
    ecc = 1.0/(maximum(temp_dists))

    if ecc != Inf
      eccentricity[v.index] = ecc
    elseif ecc == Inf
      eccentricity[v.index] = 0.0
    end

  end

  return eccentricity

end

max_stars_repo_name: mpuk/GraphAnalysis

max_issues_repo_name: mpuk/GraphAnalysis

max_forks_repo_name: mpuk/GraphAnalysis


text:
module GeneralTaxComponents

#
# This module implements various standard tax calculations, such as indirect tax components and getting tax due from rates and bands.
# It also contains some period constants that really need more thought.
# Currently incomplete but enough to be going on with.
#

export
   DAYS_PER_YEAR,
   WEEKS_PER_MONTH,
   WEEKS_PER_YEAR,

   IncomesDict,
   IndirResult,
   RateBands,
   TaxResult,

   *,

   annualise,
   calc_indirect,
   calctaxdue,
   delete_thresholds_up_to,
   times,
   weeklyise

# note: intialise like f::RateBands = zeros(0)
const RateBands = Vector{<:Real}

const IncomesDict = Dict{Any,Number}

# !! maybe make this 366/365 depending on whether this year is a leap year; see the CPAG guide chapter on WTC amounts, for example
const DAYS_PER_YEAR = 365.25
const WEEKS_PER_YEAR = DAYS_PER_YEAR/7.0
# needed for e.g. UC - they may use
# This is what's used for UC, even though it's
# not consistent with the above. Possibly
# switch to WEEKS_PER_YEAR/12
const WEEKS_PER_MONTH = 4.35 # WEEKS_PER_YEAR/12

function weeklyise( annual_amount )
   round(annual_amount/WEEKS_PER_YEAR, digits=6) # round( x, digits=2) possibly
end

function annualise( weekly_amount :: Number )
   round( weekly_amount*WEEKS_PER_YEAR, digits=2)
end

## TODO rooker wise style stuff

"""
   Useful for e.g. calculating expenses against a list
   of eligible expenses
   FIXME I don't really understand why Dict{T,Number} works here but Dict{Any,Number} doesn't
"""
function times( m1::Dict{T,R}, m2::Dict{T,R})::R where T where R<:Number
   m = zero(R)
   ikey = intersect( keys(m1), keys(m2))
   for k in ikey
      m += m1[k]*m2[k]
   end
   return m
end

import Base.*

function *( m1::Dict{T,R}, m2::Dict{T,R})::R where T where R<:Number
    times(m1, m2)
end

struct TaxResult{T<:Real}
   due :: T
   end_band :: Integer
end

struct IndirResult{T<:Real}
   factor_cost :: T
   vat         :: T
   addvalorem  :: T
   specific    :: T
   total       :: T
end

"""
UK (and maybe other) systems have uprating rules for rates and bands
in legislation. For example, next £10 or £100 annually.
"""
function uprate!(
   x         :: Real,
   uprate_by :: Real,
   next      :: Real = 0.0 )
   # TODO
end

"""
UK Tax bands have special rules - annual band *gaps* uprated to *next* £100
"""
function uprate!(
   bands     :: RateBands,
   uprate_by :: Real,
   next      :: Real = 0.0 )
   # TODO
end

"""
e.g. Pre 1996 (?) National Insurance (check!)
"""
function stepped_tax_calculation(
   ;
   taxable :: Real,
   rates   :: RateBands,
   bands   :: RateBands ) :: TaxResult
      # TODO

end

"""
Tax due on `taxable` income, given rates and thresholds
rates can be one more than thresholds, in which case the last band is assumed infinite.
Rates should be (e.g.) 0.12 for 12%.
"""
function calctaxdue(
      ;
   taxable    :: Number,
   rates      :: RateBands,
   thresholds :: RateBands ) :: TaxResult
   nthresholds = length(thresholds)[1]
   nrates = length(rates)[1]

   @assert (nrates >= 1) && ((nrates - nthresholds) in 0:1 ) # allow thresholds to be 1 less & just fill in the top if we need it
   due = 0.0
   mr  = 0.0
   remaining = taxable
   i = 0
   if nthresholds > 0
      maxv = typemax( typeof( thresholds[1] ))
      gap = thresholds[1]
   else
      maxv = typemax( typeof( taxable ))
      gap = maxv
   end
   while remaining > 0.0
      i += 1
      if i > 1
         if i < nrates
            gap = thresholds[i]-thresholds[i-1]
         else
            gap = maxv
         end
      end
      t = min( remaining, gap )
      # println( "got gap as $gap remaining $remaining")
      due += t*rates[i]
      remaining -= gap
   end
   TaxResult( due, i )
end

"""
Factor cost (tax exclusive cost) given VAT, per unit tax and ad valorem tax).

@param selling_price per unit in some currency
@param vat tax as proportion of input costs (including advalorem and specific duties) 0.175 for 17.5% e.g.
@param advalorem - tax as proportion of final selling price as 0.2 for 20%, for instance
@param specific - amount per (e.g.) bottle, packet, etc. in same units as selling price.

"""
function calc_factor_cost(
   ;
   selling_price :: Real,
   vat           :: Real,
   advalorem     :: Real,
   specific      :: Real ) :: Real

   p = selling_price
   v = vat
   a = advalorem
   s = specific
   return ( p * ( 1.0 - a - ( v * a ))/( 1.0 + v ) ) - s;
end

"""
@param selling_price per unit in some currency
@param vat tax as proportion of input costs (including advalorem and specific duties) 0.175 for 17.5% e.g.
@param advalorem - tax as proportion of final selling price as 0.2 for 20%, for instance
@param specific - amount per (e.g.) bottle, packet, etc. in same units as selling price.
"""
function calc_indir_components_per_unit(
   ;
   selling_price :: Real,
   vat           :: Real,
   advalorem     :: Real,
   specific      :: Real ) :: IndirResult
   factor_cost = calc_factor_cost(
      selling_price = selling_price,
      vat           = vat,
      advalorem     = advalorem,
      specific      = specific );

   add     = advalorem * selling_price
   vat_due = vat * (factor_cost+add+specific)
   total   = vat_due + add + specific
   IndirResult( factor_cost, vat_due, add, specific, total )
end

"""
Given:

* total expenditure;
* an average selling price (£20 per bottle of whisky, say),
* vat (proportion of inputs, inc. other taxes - 0.2 for 20%, say),
* advalorem (proportion of final selling price); and
* specific (e.g. £10 per bottle).

Calculate indirect taxes due, on assumption of unit price elasticity
(e.g. constant spending).

Selling price should have same units as advalorem.
"""
function calc_indirect(
   ;
   expenditure   :: Real,
   selling_price :: Real,
   vat           :: Real,
   advalorem     :: Real,
   specific      :: Real ) :: IndirResult
   per_unit = calc_indir_components_per_unit(
      selling_price = selling_price,
      vat           = vat,
      advalorem     = advalorem,
      specific      = specific )
   q = expenditure / selling_price
   IndirResult(
      q*per_unit.factor_cost,
      q*per_unit.vat,
      q*per_unit.addvalorem,
      q*per_unit.specific,
      q*(per_unit.vat + per_unit.specific + per_unit.addvalorem)
   )
end

function thresholds_to_bands( thresh :: RateBands ) :: RateBands
   n = size( thresh )[1]
   bands = RateBands(undef,n)
   bands[1] = thresh[1]
   for i in 2:n
      bands[i]=thresh[i]-thresh[i-1]
   end
   bands
end

function bands_to_thresholds( bands :: RateBands ) :: RateBands
   n = size( bands )[1]
   thresholds = RateBands(undef,n)
   thresholds[1] = bands[1]
   for i in 2:n
      thresholds[i]=thresholds[i-1]+bands[i]
   end
   thresholds;
end

"""
A little thing that comes up in UK income tax where tax on different sources
is applied progressively, with possibly different rates and bands for each source.

If rates are
    0.1,0.2,0.4
and thresholds are:
    100,200
then
    delete_bands_up_to( rates=rates, bands=bands, 101 )
gives
    rates = 0.2,0.4 bands = 99
"""
function delete_thresholds_up_to( ; rates :: RateBands, thresholds :: RateBands, upto :: Real )::Tuple
   threshdel = 0.0
   deletethresh = -1
   num_thresh = size( thresholds )[1]
   num_rates = size( rates )[1]
   @assert num_rates - num_thresh in [0,1]
   if num_rates > num_thresh
      thresholds = vcat( thresholds, [Inf])
   end
   for i in 1:num_thresh
      if upto < thresholds[i]
         threshdel = (i>1) ? upto - thresholds[i-1] : upto
         # println( "i=$i upto $upto $(thresholds[i])")
         deletethresh = i
         break
      end #
   end # 1:n
   # println(" deletethresh=$deletethresh " )
   if deletethresh == 0 # delete none but set 1st
      thresholds[1] = threshdel
   elseif deletethresh > 0 # delete some
      rates = rates[deletethresh:end]
      thresholds = thresholds[deletethresh:end]
      thresholds .-= threshdel
   elseif deletethresh == -1 # we never find one - top rate only and inf thresh
      rates = rates[end:end]
      thresholds :: RateBands = [ Inf ]
   end
   rates, thresholds
end

end # module

max_stars_repo_name: grahamstark/ScottishTaxBenefitModel

max_issues_repo_name: grahamstark/ScottishTaxBenefitModel

max_forks_repo_name: grahamstark/ScottishTaxBenefitModel


text:
#  Copyright 2016, Iain Dunning, Joey Huchette, Miles Lubin, and contributors
#  This Source Code Form is subject to the terms of the Mozilla Public
#  License, v. 2.0. If a copy of the MPL was not distributed with this
#  file, You can obtain one at http://mozilla.org/MPL/2.0/.

Base.precompile(addtoexpr_reorder, (Array{AffExpr,1},Float64,Array{Float64,1}))
Base.precompile(addtoexpr_reorder, (Array{AffExpr,1},Float64,Array{Int,1}))
Base.precompile(addtoexpr_reorder, (Array{AffExpr,1},Float64,Int))
Base.precompile(addtoexpr_reorder, (Array{AffExpr,2},Float64,Array{Float64,2}))
Base.precompile(addtoexpr_reorder, (Array{AffExpr,2},Float64,Int))
Base.precompile(addtoexpr_reorder, (Array{QuadExpr,1},Array{Variable,1}))
Base.precompile(addtoexpr_reorder, (Array{QuadExpr,1},Float64,Array{Int,1}))
Base.precompile(addtoexpr_reorder, (Array{QuadExpr,1},Float64,Int))
Base.precompile(addtoexpr_reorder, (Float64,Array{Float64,2}))
Base.precompile(addtoexpr_reorder, (Float64,Array{Int,1}))
Base.precompile(addtoexpr_reorder, (Float64,Array{Int,2}))
Base.precompile(addtoexpr_reorder, (Float64,Array{Variable,1}))
Base.precompile(addtoexpr_reorder, (Float64,Array{Variable,2}))
Base.precompile(addtoexpr_reorder, (Float64,Float64))
Base.precompile(addtoexpr_reorder, (Float64,Float64,Array{Int,1}))
Base.precompile(addtoexpr_reorder, (Float64,Float64,Int))
Base.precompile(addtoexpr_reorder, (Float64,Float64,AffExpr))
Base.precompile(addtoexpr_reorder, (Float64,Float64,SOCExpr))
Base.precompile(addtoexpr_reorder, (Float64,Float64,Norm{2}))
Base.precompile(addtoexpr_reorder, (Float64,Float64,QuadExpr))
Base.precompile(addtoexpr_reorder, (Float64,Float64,Variable))
Base.precompile(addtoexpr_reorder, (Float64,Int))
Base.precompile(addtoexpr_reorder, (Float64,Int,Variable))
Base.precompile(addtoexpr_reorder, (Float64,AffExpr))
Base.precompile(addtoexpr_reorder, (Float64,AffExpr,Float64))
Base.precompile(addtoexpr_reorder, (Float64,AffExpr,AffExpr))
Base.precompile(addtoexpr_reorder, (Float64,SOCExpr))
Base.precompile(addtoexpr_reorder, (Float64,Norm{2}))
Base.precompile(addtoexpr_reorder, (Float64,QuadExpr))
Base.precompile(addtoexpr_reorder, (Float64,Variable))
Base.precompile(addtoexpr_reorder, (Float64,Variable,Float64))
Base.precompile(addtoexpr_reorder, (Float64,Variable,Variable))
Base.precompile(addtoexpr_reorder, (AffExpr,Tuple{Array{AffExpr,2},Array{Float64,2},Array{AffExpr,1}}))
Base.precompile(addtoexpr_reorder, (AffExpr,Tuple{Array{AffExpr,2},Array{Int,2},Array{AffExpr,1}}))
Base.precompile(addtoexpr_reorder, (AffExpr,Tuple{Int,Variable}))
Base.precompile(addtoexpr_reorder, (AffExpr,Tuple{Int,Int,Variable}))
Base.precompile(addtoexpr_reorder, (AffExpr,Tuple{Float64,Float64,Float64}))
Base.precompile(addtoexpr_reorder, (AffExpr,Tuple{Float64,Float64,Float64,Int}))
Base.precompile(addtoexpr_reorder, (AffExpr,Tuple{Float64,Float64,Float64,Variable}))
Base.precompile(addtoexpr_reorder, (AffExpr,Tuple{Float64,Float64,Int}))
Base.precompile(addtoexpr_reorder, (AffExpr,Tuple{Float64,Float64,Int,Variable}))
Base.precompile(addtoexpr_reorder, (AffExpr,Tuple{Float64,Float64,Variable}))
Base.precompile(addtoexpr_reorder, (AffExpr,Tuple{Float64,Int,Norm{2}}))
Base.precompile(addtoexpr_reorder, (AffExpr,Tuple{Float64,Int,Variable}))
Base.precompile(addtoexpr_reorder, (AffExpr,Tuple{Float64,Int,Variable,Float64}))
Base.precompile(addtoexpr_reorder, (AffExpr,Tuple{Float64,Variable}))
Base.precompile(addtoexpr_reorder, (AffExpr,Tuple{Float64,Variable,Float64}))
Base.precompile(addtoexpr_reorder, (AffExpr,Tuple{Float64,Variable,Int}))
Base.precompile(addtoexpr_reorder, (AffExpr,Tuple{Float64,Variable,Variable}))
Base.precompile(addtoexpr_reorder, (AffExpr,Tuple{Int,Variable,Variable}))
Base.precompile(addtoexpr_reorder, (AffExpr,Array{Float64,1},Variable))
Base.precompile(addtoexpr_reorder, (AffExpr,Array{Float64,2},Array{AffExpr,1}))
Base.precompile(addtoexpr_reorder, (AffExpr,Array{Int,2},Array{Variable,1}))
Base.precompile(addtoexpr_reorder, (AffExpr,Array{AffExpr,2}))
Base.precompile(addtoexpr_reorder, (AffExpr,Float64))
Base.precompile(addtoexpr_reorder, (AffExpr,Float64,Array{Float64,2}))
Base.precompile(addtoexpr_reorder, (AffExpr,Float64,Float64))
Base.precompile(addtoexpr_reorder, (AffExpr,Float64,Int))
Base.precompile(addtoexpr_reorder, (AffExpr,Float64,AffExpr))
Base.precompile(addtoexpr_reorder, (AffExpr,Float64,SOCExpr))
Base.precompile(addtoexpr_reorder, (AffExpr,Float64,Norm{2}))
Base.precompile(addtoexpr_reorder, (AffExpr,Float64,QuadExpr))
Base.precompile(addtoexpr_reorder, (AffExpr,Float64,Variable))
Base.precompile(addtoexpr_reorder, (AffExpr,Int))
Base.precompile(addtoexpr_reorder, (AffExpr,Int,AffExpr))
Base.precompile(addtoexpr_reorder, (AffExpr,Int,Norm{2}))
Base.precompile(addtoexpr_reorder, (AffExpr,Int,QuadExpr))
Base.precompile(addtoexpr_reorder, (AffExpr,Int,Variable))
Base.precompile(addtoexpr_reorder, (AffExpr,AffExpr))
Base.precompile(addtoexpr_reorder, (AffExpr,AffExpr,AffExpr))
Base.precompile(addtoexpr_reorder, (AffExpr,AffExpr,SOCExpr))
Base.precompile(addtoexpr_reorder, (AffExpr,Norm{2}))
Base.precompile(addtoexpr_reorder, (AffExpr,QuadExpr))
Base.precompile(addtoexpr_reorder, (AffExpr,Variable))
Base.precompile(addtoexpr_reorder, (AffExpr,Variable,Array{Float64,2}))
Base.precompile(addtoexpr_reorder, (AffExpr,Variable,Float64))
Base.precompile(addtoexpr_reorder, (AffExpr,Variable,Int))
Base.precompile(addtoexpr_reorder, (AffExpr,Variable,Variable))
Base.precompile(addtoexpr_reorder, (SOCExpr,Float64,Float64))
Base.precompile(addtoexpr_reorder, (SOCExpr,Float64,Int))
Base.precompile(addtoexpr_reorder, (SOCExpr,Float64,AffExpr))
Base.precompile(addtoexpr_reorder, (SOCExpr,Float64,SOCExpr))
Base.precompile(addtoexpr_reorder, (SOCExpr,Float64,Norm{2}))
Base.precompile(addtoexpr_reorder, (SOCExpr,Float64,QuadExpr))
Base.precompile(addtoexpr_reorder, (SOCExpr,Float64,Variable))
Base.precompile(addtoexpr_reorder, (SOCExpr,Variable))
Base.precompile(addtoexpr_reorder, (QuadExpr,Tuple{Float64,Int,Variable}))
Base.precompile(addtoexpr_reorder, (QuadExpr,Tuple{Float64,Int,Variable,Int,Variable}))
Base.precompile(addtoexpr_reorder, (QuadExpr,Tuple{Float64,Int,Variable,Variable}))
Base.precompile(addtoexpr_reorder, (QuadExpr,Tuple{Float64,Variable,Variable}))
Base.precompile(addtoexpr_reorder, (QuadExpr,Tuple{Int,Variable,Variable}))
Base.precompile(addtoexpr_reorder, (QuadExpr,Float64,Int))
Base.precompile(addtoexpr_reorder, (QuadExpr,Float64,AffExpr))
Base.precompile(addtoexpr_reorder, (QuadExpr,Float64,SOCExpr))
Base.precompile(addtoexpr_reorder, (QuadExpr,Float64,Norm{2}))
Base.precompile(addtoexpr_reorder, (QuadExpr,Float64,QuadExpr))
Base.precompile(addtoexpr_reorder, (QuadExpr,Float64,Variable))
Base.precompile(addtoexpr_reorder, (QuadExpr,Int))
Base.precompile(addtoexpr_reorder, (QuadExpr,Int,QuadExpr))
Base.precompile(addtoexpr_reorder, (QuadExpr,Int,Variable))
Base.precompile(addtoexpr_reorder, (QuadExpr,AffExpr,Float64))
Base.precompile(addtoexpr_reorder, (QuadExpr,AffExpr,AffExpr))
Base.precompile(addtoexpr_reorder, (QuadExpr,QuadExpr))
Base.precompile(addtoexpr_reorder, (QuadExpr,QuadExpr,Int))
Base.precompile(addtoexpr_reorder, (QuadExpr,Variable))
Base.precompile(addtoexpr_reorder, (QuadExpr,Variable,Variable))
Base.precompile(parseCurly, (Expr,Symbol,Vector{Any},Vector{Any},Symbol))
Base.precompile(parseExpr, (Expr,Symbol,Vector{Any},Vector{Any},Symbol))
Base.precompile(parseExpr, (Float64,Symbol,Vector{Any},Vector{Any},Symbol))
Base.precompile(parseExpr, (Int,Symbol,Vector{Any},Vector{Any},Symbol))
Base.precompile(parseExpr, (Symbol,Symbol,Vector{Any},Vector{Any},Symbol))
Base.precompile(parseSum, (Expr,Symbol,Vector{Any},Vector{Any},Symbol))


text:
# test numericRootGenericRandomized
using IncrementalInference
using Base.Test

# TODO -- resid function definitions are changing
# residual functions must have the form:
# function residual!(
      # residual::Vector{Float64},
      # z::Vector{Float64},
      # variables::Tuple )

# y = mx + c
# res = y      -      m*x  -  c
#       meas          variables and fixed values
function lineResidual!(res::Vector{Float64}, y::Vector{Float64}, var::Tuple)
  m, c = var[1][1], var[1][2]
  x = var[2]
  res[1] = y[1] - (m*x[1] + c)
  nothing
end

# TODO -- expand testing to include subcomponent tests from numericRootGenericRandomizedFnc
params = [2.0;3.0]
gg = (res, x) -> lineResidual!(res, [1.0], (params, x))

params = [2.0;3.0]
gg = (res, x) -> lineResidual!(res, [1.0], (params, x))
y = numericRootGenericRandomizedFnc(gg, 1, 1, randn(1))
# y = numericRootGenericRandomized(lineResidual!, 1, [1.0], params, randn(1))
@test abs(y[1] + 1.0) < 1e-10

gg = (res, x) -> lineResidual!(res, [3.0], (params, x))
y = numericRootGenericRandomizedFnc(gg, 1, 1, randn(1))
# y = numericRootGenericRandomized(lineResidual!, 1, [3.0], params, randn(1))
@test abs(y[1] - 0.0) < 1e-10

gg = (res, x) -> lineResidual!(res, [5.0], (params, x))
y = numericRootGenericRandomizedFnc(gg, 1, 1, randn(1))
# y = numericRootGenericRandomized(lineResidual!, 1, [5.0], params, randn(1))
@test abs(y[1] - 1.0) < 1e-10

println("Test shuffling function")

function testshuffle!(res, x)
  # println("testshuffle!(x,res) gets x=$(x), and length(res)=$(length(res))")
  @show res
  @show x
  nval = sum(abs.(x-[11.0;12.0;13.0]))
  # trick the solver so that f/f' = 0/1e10, and therefore < tol
  # resulting in termination of solver
  if nval < 1e-8
    res[1:2] = [0.0;0.0] # fake at root evaluation
  else
    res[1:2] = 1e10*randn(2) # fake large gradient
  end
  nothing
end

# test shuffling function
ALLTESTS = Bool[]
@show x0 = collect(11:13)+0.0
for i in 1:10
  y = numericRootGenericRandomizedFnc(
          testshuffle!,
          2, 3, x0,
          perturb=0.0    )
  @show y
  @show y.%10
  @show yy = y.%10.0
  push!(ALLTESTS, norm(yy-collect(1:3)) < 0.1)
end
@test sum(ALLTESTS) > 9

println("Test if shuffling results in correct mapping for solving")

function testshuffle2!(res, x)
  # println("testshuffle2!(x,res) gets x=$(x), and length(res)=$(length(res))")
  res[1:2] = x - [1.0;2.0] # fake at root evaluation
  nothing
end

# test shuffling function
x0 = collect(11:12)+0.0
for i in 1:10
  println("starting with x0=$(x0)")
  y = numericRootGenericRandomizedFnc(
          testshuffle2!,
          2, 2, x0,
          perturb=0.0,
          testshuffle=true    )
  println("result y=$(y)")
  @test norm(y-collect(1:2)) < 0.1
end

# x is dimension 3, z dimension is 2
function residualrandtest!(res, x)
  val = norm(x[1:2])
  res[1] = 10.0 - val
  nothing
end

for i in 1:10
  x0 = ones(2)
  y = numericRootGenericRandomizedFnc(
          residualrandtest!,
          1, 2, x0   )
  #
  @test abs(norm(y) - 10.0) < 1e-4
end

warn("Test FastRootGenericWrapParam{T} not implemented yet")

# test convexity of rotation residual
#
# N=100
# X = linspace(-pi/2,pi/2,N)
# eul = 0.5*randn(3)
# # RES = zeros(3, N)
# # for i in 1:N
# #   res = zeros(3)
# #   rotationresidual!(res, eul, (zeros(0), [X[i];0.0;0.0]) )
# #   RES[:,i] = res
# # end
#
# using Gadfly
#
# function easyplot(x,y, eul)
#   res = zeros(3)
#   rotationresidual!(res, eul, (zeros(0), [x;0.0;y]) )
#   return norm(res)
# end
#
# plot(z = (x,y) -> easyplot(x,y,eul), x=X, y=X, Geom.contour)


text:
"""
    time
"""
abstract type Time end
abstract type FreeTime <: Time end
abstract type FixedTime <: Time end


text:
# ---
# title: 892. Surface Area of 3D Shapes
# id: problem892
# author: Tian Jun
# date: 2020-10-31
# difficulty: Easy
# categories: Math, Geometry
# link: <https://leetcode.com/problems/surface-area-of-3d-shapes/description/>
# hidden: true
# ---
#
# On a `N * N` grid, we place some `1 * 1 * 1 `cubes.
#
# Each value `v = grid[i][j]` represents a tower of `v` cubes placed on top of
# grid cell `(i, j)`.
#
# Return the total surface area of the resulting shapes.
#
#
#
# **Example 1:**
#
#
#
#     Input: [[2]]
#     Output: 10
#
#
# **Example 2:**
#
#
#
#     Input: [[1,2],[3,4]]
#     Output: 34
#
#
# **Example 3:**
#
#
#
#     Input: [[1,0],[0,2]]
#     Output: 16
#
#
# **Example 4:**
#
#
#
#     Input: [[1,1,1],[1,0,1],[1,1,1]]
#     Output: 32
#
#
# **Example 5:**
#
#
#
#     Input: [[2,2,2],[2,1,2],[2,2,2]]
#     Output: 46
#
#
#
#
# **Note:**
#
#   * `1 <= N <= 50`
#   * `0 <= grid[i][j] <= 50`
#
#
## @lc code=start
using LeetCode

## add your code here:
## @lc code=end